发表于 | 分类于

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

1
2
3
4
[
  [7],
  [2, 2, 3]
]

解法1：

经典的backtracking的做法。 一个可能的小改进是可以先对原数组进行排序，然后再判断target是否还大于当前可选的节点，这样可以提高一点效率。
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
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        if (candidates.size() == 0 || target <= 0) {
            return res;
        }
        vector<int> cur;
        
        helper(candidates, target, 0, cur, res);
        return res;
    }
    
    void helper(vector<int>& candidates, int target, int pos, vector<int>& cur, vector<vector<int>>& res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.push_back(cur);
            return;
        }
        
        for (int i = pos; i < candidates.size(); ++i) {
            cur.push_back(candidates[i]);
            helper(candidates, target - candidates[i], i,cur, res);
            cur.pop_back();
        }
        return;
    }
};

Java

1

发表于 | 分类于

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

1
2
3
4
5
6
7
8
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解法1： Backtracking

常规的backtracking的题目，这里的特殊点是每一次要更新还剩下需要挑选的数字的个数。 然后用另外一个变量pos记录当前已经探索到的数字的位置。

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
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        
        vector<vector<int>> res;
        if (k <= 0 || n == 0) {
            return res;
        }
        
        vector<int> cur;
        
        helper(n, k, 1, cur, res);
        return res;
        
    }
    
    void helper(int n, int k, int pos, vector<int>& cur, vector<vector<int>>& res) {
        
        if (k == 0) {
            res.push_back(cur);
            return;
        }    
        
        for (int i = pos; i <= n; ++i) {
            cur.push_back(i);
            helper(n, k - 1, i + 1, cur, res);
            cur.pop_back();
        }
        
        return;
        
    }
    
};

Java

1

发表于 | 分类于

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解法1：

还是用通用的backtracking的模板，这里考察的是一个去重的feature。 对于题目意思中需要排除掉重复情况的时候， 我们首先要记得要把原数组进行排序。
然后去重时对于每一个选取的元素，考虑是否和之前的一致（或者是这次循环中第一个选取的值）
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
28
29
30
31
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        
        vector<int> temp;
        
        // sort the nums
        std::sort(nums.begin(), nums.end());
        helper(nums, 0, temp, res);
        return res;
    }
    
    void helper(vector<int>& nums, int pos, vector<int>& cur, vector<vector<int>>& res) {
        
        res.push_back(cur);
        
        if (pos == nums.size()) {
            return;
        }
        
        for (int i = pos; i < nums.size(); ++i) {
            if (i == pos || nums[i] != nums[i - 1]) {
                cur.push_back(nums[i]);
                helper(nums, i + 1, cur, res);
                cur.pop_back();
            }
        }
        return;
    }
};

Java

1

发表于 | 分类于

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解法1： Backtracking O(2^N)

Backtracking的模板解法。 用一个pos记录当前扫描到的位置。对于每一种情况，都是一个subset，所以递归的时候一开始就要把当前的结果给保存到结果集中。
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:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.empty()) {
            return res;
        }
        
        vector<int> cur;
        helper(nums, 0, cur, res);
        return res;
    }
    
    void helper(vector<int>& nums, int pos, vector<int>& cur, vector<vector<int>>& res) {
        
        res.push_back(cur);
        
        for (int i = pos; i < nums.size(); ++i) {
            cur.push_back(nums[i]);
            helper(nums, i + 1, cur, res);
            cur.pop_back();
        }
        
    }
};

Java

1

发表于 | 分类于

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

1
2
3
4
5
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

解法1： DFS O(N^2) N是元素的个数

这题的思路是，对于一个给定的string， 他的起点可以在图中的任意位置，那么我们就必须要对每一个起点进行遍历。 对于任意一个遍历， 需要维护一个visited图，来记录已经访问过的节点。
对于每一个节点，有4个方向可以选择，对每一个方向进行探索，只要其中有一个方向能找到string， 那么就算找到了。
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (word.empty()) {
            return true;
        }
        if (board.empty() || board[0].empty()) {
            return false;
        }
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                bool temp = helper(word, board, visited, i, j);
                if (temp) {
                    return true;
                }
            }
        }
        return false;
    }
    bool helper(string word, vector<vector<char>>& board, vector<vector<bool>>& visited, int row, int col) {
        if (word.empty()) {
            return true;
        }
        if (board[row][col] != word[0]) {
            return false;
        }
        if (word.size() == 1) {
            return true;
        }
        visited[row][col] = true;
        string next = word.substr(1, word.size() - 1);
        // check up
        // bool up = false, right = false, bot = false, left = false;
        if (row > 0 && !visited[row - 1][col] ) {
            bool up = helper(next, board, visited, row - 1, col);
            if (up) {
                return true;
            }
        }
        // right
        if (col < board[0].size() - 1 && !visited[row][col + 1]) {
            bool right = helper(next, board, visited, row, col + 1);
            if (right) {
                return true;
            }
        }
        // down
        if (row < board.size() - 1 && !visited[row + 1][col]) {
            bool bot = helper(next, board, visited, row + 1, col);
            if (bot) {
                return true;
            }
        }
        // left
        if (col > 0 && !visited[row][col - 1]) {
            bool left = helper(next, board, visited, row, col - 1);
            if (left) {
                return true;
            }
        }
        visited[row][col] = false;
        return false;
    }
};

Java

1
2
<!--1-->

发表于 | 分类于

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

1
2
3
4
00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

解法1： Recursive O(2^N)

这题一开始没有思路， 对于没思路的可以考虑多写几个最简单的情况的结果来找规律。本题就是一个列子。如果我们把n = 1， n = 2, n = 3的结果写出来就一目了然了。

1
2
3
n = 1
0
1

1
2
3
4
5
n = 2
00
01
11
10
1
2
3
4
5
6
7
8
9
n = 3
000
001
011
010
110
111
101
100

可以发现，对于n的结果，有2^n个数，前2^n-1个数来自于n-1的结果，后一半的数是把n-1的结果倒序后最高位（n)位上加1即可。
有了这个结论，写程序就比较简单了。复杂度应该是O（2^N)

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
28
29
class Solution {
public:
    vector<int> grayCode(int n) {
        
        if (n == 0) {
            return vector<int> {0};
        }
        if (n == 1) {
           return vector<int> {0,1};
        }
        
        vector<int> previous = grayCode(n - 1);
        vector<int> res;
        
        // add previous level
        for (int i = 0; i < previous.size(); ++i) {
            res.push_back(previous[i]);
        }
        
        for (int i = previous.size() - 1; i >= 0; --i) {
            // add one to the high bits
            int temp =  previous[i] | (1 << n - 1);
            res.push_back(temp);
        }
        
        return res;
    }
};

Java

1

发表于 | 分类于

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

解法1： Backtracking, Time O(2^N), Space O(2^N)

也是比较经典的backtracking的题目，也是不停的去取一部分string，要判断不用继续搜索的条件有这些：

  1. 每个字串是否符合ip的条件，一定要是0到255， 并且开头的不能是0， 除了0本身。
  2. 字串的长度不能超过3
  3. ip一共有4部分组成，所以也要判断是否超i过了这个条件。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        if (s.empty()) {
            return res;
        }
        vector<string> cur;
        helper(s, 0, cur, res);
        return res;
    }
    bool isValid(string s) {
        if (s[0] == '0' && s.size() > 1) {
            return false;
        }
        int temp = stoll(s);
        if (temp >= 0 && temp <= 255) {
            return true;
        } else {
            return false;
        }
    }
    string createIP(vector<string>& cur) {
        string res = "";
        for (int i = 0; i < cur.size() - 1; ++i) {
            res += cur[i] + ".";
        }
        res += cur[cur.size() - 1];
        return res;
    }
    void helper(string s, int pos, vector<string>& cur, vector<string>& res) {
        if (pos == s.size()) {
            if (cur.size() == 4) {
                res.push_back(createIP(cur));
            }
            return;
        }
        if (cur.size() > 4) {
            return;
        }
        for (int i = pos; i < s.size(); ++i) {
            if (cur.size() < 4 && i - pos < 3) {
                string item = s.substr(pos, i - pos + 1);
                // check if the item is between 0 and 255
                if (!isValid(item)) {
                    continue;
                }
                cur.push_back(item);
                helper(s, i + 1, cur, res);
                cur.pop_back();
            }
        }
    }
};

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        List<String> current = new ArrayList<String>();
        helper(s, 0, current, res);
        return res;
    }
    boolean isValid(String s) {
        if (s.charAt(0) == '0' && s.length() > 1) {
            return false;
        }
        int temp = Integer.parseInt(s);
        if (temp >= 0 && temp <= 255) {
            return true;
        }
        return false;
    }
    String createIP(List<String> current) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < current.size() - 1; i++) {
            sb.append(current.get(i));
            sb.append(".");
        }
        sb.append(current.get(current.size() - 1));
        return sb.toString();
    }
    private void helper(String s, int pos, List<String> current, List<String> res) {
        if (pos == s.length()) {
            if (current.size() == 4) {
                res.add(createIP(current));
            }
            return;
        }
        if (current.size() > 4) return;
        for (int i = pos; i < s.length() && i < pos + 3; i++) {
            if (current.size() < 4) {
                String item = s.substring(pos, i + 1);
                if (!isValid(item)) {
                    continue;
                }
                current.add(item);
                helper(s, i + 1, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
}

发表于 | 分类于

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”,
Return

1
2
3
4
[
  ["aa","b"],
  ["a","a","b"]
]

解法1： O(n*2^n)

常规的backtracking解法，这里我们用一个变量cut来记录当前cut的位置， 然后从cut + 1 开始一个一个个试是否是palindrome。
复杂度的计算是由于一共有O(2^N)种可能的partition。
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
private:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if (s.empty()) {
            return res;
        }
        vector<string> cur;
        helper(s, 0, cur, res);
        return res;
    }
    void helper(string s, int cut, vector<string>& cur, vector<vector<string>>& res) {
        if (cut == s.size()) {
            res.push_back(vector<string>(cur));
            return;
        }
        for (int i = cut + 1; i <= s.size(); ++i) {
            string prefix = s.substr(cut, i - cut);
            if (!isPalindrome(prefix)) {
                continue;
            }
            cur.push_back(prefix);
            helper(s, i, cur, res);
            cur.pop_back();
        }
    }
};

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        helper(s, 0, new ArrayList<String>(), res);
        return res;
    }
    private void helper(String s, int pos, List<String> current, List<List<String>> res) {
        if (pos == s.length()) {
            res.add(new ArrayList<>(current));
            return;
        }
        for (int i = pos + 1; i <= s.length(); i++) {
            String cut = s.substring(pos, i);
            if (isPalindrome(cut)) {
                current.add(cut);
                helper(s, i, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
    private boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

发表于 | 分类于

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

解法1：

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            res <<= 1;
            int bit = n & 1;
            res = res | bit;
            n >>= 1;
        }
        return res;
    }
};

Java

1

Follow up

本题的follow up的解法参考这个帖
子

发表于 | 分类于

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:

1
2
3
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

1
2
Input: 1
Output: 0

解法1：

观察可以发现，可以用XOR来flip每一位的bit， 而mark数是从第一个set bit开始所有位都为1的数字。
怎么判断最高的set bit是哪一个呢？可以用log2函数，最高位的1的位置一定是log2(num), 那么为了得到所有都是1的一个数，可以先左移log2(num) + 1， 然后把所得的数字-1即可。
C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int findComplement(int num) {
        int mask = (1 << 1 + static_cast<int>(log2(num))) - 1;
        return mask ^ num;
    }
};

Java

1
2
3
4
5
6
7
8
class Solution {
    public int findComplement(int num) {
        int mask = (1 << ((int)(Math.log10(num) / Math.log10(2)) + 1)) - 1;
        return num ^ mask;
    }
}

解法2：一位一位的转换

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findComplement(int num) {
    // last digit is set bit
    int pos = 0;
    int res = 0;
    for (int i = 0; i < 31 && num != 0; i++) {
        int digit = num & 1;
        num >>= 1;
        pos++;
        int setBit = 1 - digit;
        setBit <<= i;
        res |= setBit;
    }
    return res;
}