发表于 | 分类于

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

解法1：Sort + Two pointers O(NlogN) Time + O(1) Space

先考虑将两个数组排序，然后只需要维护两个指针，对于一样的数值就放入返回数组中。同时要考虑去重的情况。这点上九章的答案做的比我更简洁。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());
        int ptr1 = 0;
        int ptr2 = 0;
        vector<int> res;
        while (ptr1 < nums1.size() && ptr2 < nums2.size()) {
            while (ptr1 > 0 && ptr1 < nums1.size() && nums1[ptr1] == nums1[ptr1-1]) ++ptr1;
            while (ptr2 > 0 && ptr2 < nums2.size() && nums2[ptr2] == nums2[ptr2 - 1]) ++ptr2;
            if (ptr1 == nums1.size()) break;
            if (ptr2 == nums2.size()) break;
            if (nums1[ptr1] < nums2[ptr2]) {
                ++ptr1;
            } else if (nums1[ptr1] > nums2[ptr2]) {
                ++ptr2;
            } else {
                res.emplace_back(nums1[ptr1]);
                ++ptr1;
                ++ptr2;
            }
        }
        return res;
    }
};

Java

1

解法2： HashTable O(N) Time + O(N) Space

先扫描第一个数组，建立hashtable，然后扫描第二个数组，同时维持一个结果的hashtable用来去重。
C++
用到了unordered_map’s iterate method.

1
2
3
unordered_map<int, bool> map; // define a map
map.begin() 和 map.end() return iterator of the map, can be used like
for (auto a = map.begin(); a!= map.end(); a++) {}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, bool> map;
        unordered_map<int, bool> res;
        for (int num: nums1) {
            map[num] = true;
        }
        for (int num: nums2) {
            if (map[num] && !res[num])
                res[num] = true;
        }
        // iterate over map
        vector<int> res_vector;
        for (auto iterator = res.begin(); iterator != res.end(); iterator++) {
            if (iterator->second) {
                res_vector.emplace_back(iterator->first);
            }
        }  
        return res_vector;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        Set<Integer> res = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                res.add(num);
            }
        }
        int[] result = new int[res.size()];
        int i = 0;
        for (int num : res) {
            result[i++] = num;
        }
        return result;
    }
}

发表于 | 分类于

Find the sum of all left leaves in a given binary tree.

Example:

3

/ \
9 20
/ \
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

解法1：Recursion O(N) Time

二叉树很自然的想到用递归的办法解决。这里的难点是要记录每一个节点是否为Left child/right child，为此我们需要有一个helper函数来记录。根据OA的结果，root是算作非左子树的。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        return helper(root, false);
    }
    int helper(TreeNode* root, bool isleft) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) {
            return isleft? root->val: 0;
        }
        int left = helper(root->left, true);
        int right = helper(root->right, false);
        return left + right;
    }
};

Java

1

发表于 | 分类于

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

解法1：O(N + M) Time with O(M) Space

经典的用hashtable解决的字母问题，把magazine先hash算出每一个字母出现的次数，然后对ransomNote扫描碰到见过的字母则次数-1，直到所对应的字母的次数小于0（false）或者是可以扫描完所有的ransomNote的字母。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> map (26);
        for (int i = 0; i < magazine.size(); ++i) {
            ++map[magazine[i] - 'a'];
        }
        for (int i = 0; i < ransomNote.size(); ++i) {
            if (map[ransomNote[i] - 'a'] <= 0) {
                return false;
            } else {
                --map[ransomNote[i] - 'a'];
            }
        }
        return true;
    }
};

C++ with std::unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> map;
        for (int i = 0; i < magazine.size(); ++i) {
            map[magazine[i]]++;
        }
        for (int i = 0; i < ransomNote.size(); ++i) {
            if (map[ransomNote[i]] == 0) {
                return false;
            } else {
                --map[ransomNote[i]];
            }           
        }
        return true;
    }
};

Java

1

发表于 | 分类于

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

解法1：O(N)

本题巧妙的办法是要想到等价的操作，将n-1个元素都+1等价于将1个元素-1，在选择+1的时候我们都是避开最大的元素，那么-1的时候就要选择最大的元素。那么问题就转化为了将元素全部转化为最小元素，需要多少步，每步减少一个元素的值。
C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int minNum = INT_MAX;
        int count = 0;
        for (num : nums) minNum = min(minNum, num);
        for (num: nums) count += (num - minNum);
        return count;        
    }
};

Java

1

发表于 | 分类于

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:
Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

解法1：O(nlogn + mlogm) 贪心

如果两个array g和s都是从小到大排序的，那么基本思路就是把满足条件当中最小的一个cookie给孩子，然后再从剩下的cookie中挑选满足条件的最小的cookie给下一个孩子。这似乎就是一种贪心的思路。
排序需要花费O(NlogN)的时间，两个数组分别排序。
排序之后，维护两个指针分别在两个数组。遍历孩子的数组，直到cookie的数组已选完。用到线性的时间。所以整体的复杂度还是O(nlogn)的量级。
C++
用到了std::sort(vector.begin(), vector.end())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // sort two vectors
        std::sort(g.begin(), g.end());
        std::sort(s.begin(), s.end());
        int gPtr = 0;
        int sPtr = 0;
        int num = 0;
        for (; gPtr < g.size() && sPtr < s.size(); ++gPtr) {
            while (sPtr < s.size() && s[sPtr] < g[gPtr]) ++sPtr;
            if (sPtr == s.size()) break;
            ++num;
            ++sPtr;
        }
        return num;
    }
};

Java

1

发表于 | 分类于

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

解法1：O(N^2) Time

一开始观察可以注意到边界上的岛屿需要特殊处理，每一个边界周长都有效。对于每一个岛屿，要判断每一条边界是否有效，如果是在grid的边界上则直接有效，否贼考虑是否上下左右为0，如果是则为有效边界。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int perimeter = 0;
        int row = grid.size();
        int col = grid[0].size();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                // check left boundary
                if (grid[i][j] != 0) {
                    if (j == 0) ++perimeter;
                    if (j == col - 1) ++perimeter;
                    if (j != 0 && grid[i][j - 1] == 0) ++perimeter;
                    if (j != col - 1 && grid[i][j + 1] == 0) ++perimeter;
                    if (i == 0) ++perimeter;
                    if (i == row - 1) ++perimeter;
                    if (i != 0 && grid[i - 1][j] == 0) ++perimeter;
                    if (i != row - 1 && grid[i + 1][j] == 0) ++perimeter;
                }                
            }
        }
        return perimeter;
    }
};

Java

1

发表于 | 分类于

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

解法1：双指针 O(N) time with O(1) space

这题的思路很像Quick Sort里partition的思路，需要用到两个指针。一个指针用来traverse，另一个用来记录下一个非0的元素需要插入的位置。
C++中有一个swap function，可以交换两个reference的值。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if (nums.size() == 0) {
            return;
        }
        for (int i = 0, j = 0; i < nums.size(); i++) {
            if (nums[i]) {
                swap(nums[i], nums[j++]);
            }
        }
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j++] = temp;
            }
        }
    }
}

发表于 | 分类于

invert a binary tree.

4

/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1

解法1：Recursion, Divide & Conquer, O(N) time

很典型的一个Divide & Conquer题目，用递归的办法很简单。先对左子树invert，然后对右子树invert,最后交换左右子树即可。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) {
            return root;
        }
        invertTree(root->left);
        invertTree(root->right);
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        return root;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = temp;
        return root;
    }
}

发表于 | 分类于

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = “abcd”
t = “abcde”

Output:
e

Explanation:
‘e’ is the letter that was added.

解法1：O(N) Time Complexity with O(1) Space

用Hash的思路，对短字符串建立Hash索引，然后长字符串里面每一个字符减一，最后如果发现出现负数次数的字符时则一定是多出来的那个字符。
C++ 中注意unordered_map的用法，unordered_map::operator[] 对于不存在的元素会进行插入操作并初始化对应的map数值。
Java取字符串中的字符的method是s.charAt(i)
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        std::unordered_map<char, int> strmap;
        for (char c: s) ++strmap[c];
        for (char c: t) {
            --strmap[c];
            if (strmap[c] < 0) return c;
        }
        return 0;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public char findTheDifference(String s, String t) {
       int[] map = new int[26];
       for (int i = 0; i < s.length(); i++) {
           map[s.charAt(i) - 'a']++;
           map[t.charAt(i) - 'a']--;
       }
       map[t.charAt(t.length() - 1) - 'a']--;
       char res = 'a';
       for (int i = 0; i < 26; i++) {
           if (map[i] < 0) {
               res += i;
               break;
           }
       }
       return res;
    }
}

解法2：O(N) Time Complexity with O(1) Space

找不同的题目可以尝试用抵消的思路。一个抵消的工具就是XOR，如果对每一个字符进行异或操作，由于相同的元素抵消，剩下的一定是不相同的那一个。
C++

1
2
3
4
5
6
7
8
9
class Solution {
public:
    char findTheDifference(string s, string t) {
       char res = 0;
       for (char c: s) res ^= c;
       for (char c: s) res ^= c;
       return res;
    }
};