Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
1
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
1
[[1,2,6], [1,3,5], [2,3,4]]
Credits: Special thanks to @mithmatt for adding this problem and creating all test cases.
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.
voidfunc(int n, int k, vector<int> &tmp, int pos, vector<vector<int>> &res){
if (tmp.size() == k && find(res.begin(), res.end(), tmp) == res.end()) res.push_back(tmp);
elseif (tmp.size() == k) return;
for (int i = pos; i < n; i++) {
tmp.push_back(i + 1);
func(n, k, tmp, i + 1, res);
tmp.pop_back();
}
}
};
39. Combination Sum
Description:
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
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
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
voidfunc(string tmp, int idx, string digits, vector<vector<char>>& m, vector<string>& res){
if (idx == digits.size()) res.push_back(tmp);
int digits_i = digits[idx] - '2';
for (int i = 0; i < m[digits_i].size(); i++) {
tmp += m[digits_i][i];
func(tmp, idx + 1, digits, m, res);
tmp.pop_back();
}
}
};
40. Combination Sum II
Description:
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:
Description: 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.
if (board.empty() || board[0].empty()) returnfalse;
int n = board.size(); int m = board[0].size();
vector<bool> used(n * m, false);
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j++) {
if (search(i, j, 0, n, m, word, used, board)) returntrue;
}
}
returnfalse;
}
boolsearch(int pos_y, int pos_x, int k, int n, int m,string word, vector<bool>& used, vector<vector<char>>& board){
if (k == word.size()) returntrue;
if (pos_x >= m || pos_y >= n || pos_x < 0 || pos_y < 0 || used[pos_y * m + pos_x] == true || board[pos_y][ pos_x] != word[k]) returnfalse;
used[pos_y * m + pos_x] = true;
bool res = search(pos_y - 1, pos_x, k + 1, n, m, word, used, board) //up
|| search(pos_y + 1, pos_x, k + 1, n, m, word, used, board) //down
|| search(pos_y, pos_x - 1, k + 1, n, m, word, used, board) //left
|| search(pos_y, pos_x + 1, k + 1, n, m, word, used, board); //right
used[pos_y * m + pos_x] = false;
return res;
}
};
211. Add and Search Word - Data structure design
Description
Design a data structure that supports the following two operations:
1
2
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note: You may assume that all words are consist of lowercase letters a-z.
Hint: You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first. 解题思路： 不愧是boss关，不会做。 建立字典树，然后通过字典树查找
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
class WordDictionary {
public:
/** Initialize your data structure here. */
struct TrieNode {
public:
TrieNode *child[26];
bool isWord;
TrieNode() : isWord(false) {
for (auto &a: child) { a = NULL;}
}
};
WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
voidaddWord(string word){
TrieNode *p = root;
for (auto &a: word) {
int i = a - 'a';
if (!p -> child[i]) p -> child[i] = new TrieNode();
p = p -> child[i];
}
p -> isWord = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
boolsearch(string word){
return searchWord(word, root, 0);
}
boolsearchWord(string& word, TrieNode *p, int i){
if (i == word.size()) return p -> isWord;
if (word[i] == '.') {
for (auto &a: p -> child) {
if (a && searchWord(word, a, i + 1)) returntrue;
}
returnfalse;
}
else {
return p -> child[word[i] - 'a'] && searchWord(word, p -> child[word[i] - 'a'], i + 1);
}
}
private:
TrieNode *root;
};
Hard
52. N-Queens II
Description: Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Description: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example, There exist two distinct solutions to the 4-queens puzzle:
1
2
3
4
5
6
7
8
9
10
11
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
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
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> table;
for (int i = 0; i < n; i++) {
string tmp = "";
for (int j = 0; j < n; j ++) {
tmp += ((i ==j) ? 'Q' : '.');
}
table.push_back(tmp);
}
vector<string> tmp;
vector<bool> used(n * n, false);
func(0, n, used, table, tmp, res);
return res;
}
voidfunc(int i, int n, vector<bool>& used, vector<string>& table, vector<string>& tmp, vector<vector<string>>& res){
int cnt = 0;
if (i == n) res.push_back(tmp);
for (int j = 0; j < n; j ++) {
bool f = true;
for (int ii = 0; ii < i; ii ++) {
if (used[ii *n + j]) {
f = false; break;
}
}
if (f == false) continue;
int min = i < j ? i : j;
for (int a = 1; a <= min; a++) {
if (used[(i - a) * n + j - a]) {
f = false; break;
}
}
if (f == false) continue;
min = i < (n - j - 1) ? i : (n - j - 1);
for (int a = 1; a <= min; a++) {
if (used[(i -a) * n + j + a]) {
f = false; break;
}
}
if (f) {
used[i * n + j] = true;
tmp.push_back(table[j]);
func(i + 1, n , used, table, tmp, res);
tmp.pop_back();
used[i * n + j] = false;
}
}
}
};
Other
Works Application笔试题 Coin Game
Description： There is a rectangular chessboard containing N*M cells, each of which either has one coin or nothing.
You can move all the coins together in one direction (such as up, down, left, and right), but each time you can move these coins by only one cell.
If any coins fall out of the chessboard, they must be thrown away.
If it is required to keep K coins on the board, what is the minimum moves you have to take?
Output -1 if you can not meet this requirement.
输入描述: The first line of the input are two positive integers n, representing the size of the board. For the next n line(s), each line has m numbers of characters, with ‘o’ indicating a coin, ‘.’ indicates an empty grid. The last line is a positive integer k, indicating the number of coins to be retained.
30% small input: 40% medium input: 30% large input:
输出描述:
1
2
Output
an integer that represents the number of moves, no solution output -1.
示例1 输入
1
2
3
4
5
34
.o..
oooo
..o.
3
输出
1
2
50% case通过率，复杂度过大，回溯如何剪枝？？？
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<vector>
#include<algorithm>
usingnamespacestd;
intcountFunc(int start_row, int end_row, int start_col, int end_col, vector<vector<char>> input){
int cnt = 0;
for (int i = start_row; i < end_row; i++) {
for (int j = start_col; j < end_col; j++) {
if (input[i][j] == 'o') cnt ++;
}
}
return cnt;
}
voidfunc(int k, vector<vector<char>>& input, int start_row, int end_row, int start_col, int end_col, int count, vector<int>& res){
int tmp_cnt = countFunc(start_row, end_row, start_col, end_col, input);
