LeetCode经典题

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：“23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. 说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

class Solution { public: vector<string> ans; char ops[10][10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> letterCombinations(string digits) { dfs(digits, 0, ""); return ans; } void dfs(string &digits, int u, string path) { if(u == digits.size()) { if(path.size()) ans.push_back(path); return; } int v = digits[u] - '0'; for(int i = 0; ops[v][i]; i ++) { dfs(digits, u + 1, path + ops[v][i]); } } };

46.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] class Solution { public: vector<vector<int>> ans; vector<int> path; vector<bool> st; vector<vector<int>> permute(vector<int>& nums) { st = vector<bool>(nums.size(), false); dfs(nums, 0); return ans; } void dfs(vector<int> &nums, int u) { if(u == nums.size()) { ans.push_back(path); return; } for(int i = 0; i < nums.size(); i ++) { if(!st[i]) { st[i] = true; path.push_back(nums[i]); dfs(nums, u + 1); st[i] = false; path.pop_back(); } } } };

47.全排列2

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2] 输出:

[ [1,1,2], [1,2,1], [2,1,1] ] class Solution { public: vector<vector<int>> ans; vector<int> path; vector<bool> st; vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); st = vector<bool>(nums.size(), false); path = vector<int>(nums.size()); dfs(nums, 0, 0); return ans; } void dfs(vector<int> &nums, int u, int start) { if(u == nums.size()) { ans.push_back(path); return; } for(int i = start; i < nums.size(); i ++) { if(st[i]) continue; path[i] = nums[u], st[i] = true; if(u + 1 < nums.size() && nums[u + 1] == nums[u]) dfs(nums, u + 1, i + 1); else dfs(nums, u + 1, 0); st[i] = false; } } };

78.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3] 输出:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int>> subsets(vector<int>& nums) { dfs(nums, 0, path); return ans; } void dfs(vector<int> &nums, int u, vector<int> &path) { ans.push_back(path); for(int i = u; i < nums.size(); i ++) { path.push_back(nums[i]); dfs(nums, i + 1, path); path.pop_back(); } } }; class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int>> subsets(vector<int>& nums) { dfs(nums, 0); return ans; } void dfs(vector<int> &nums, int u) { ans.push_back(path); for(int i = u; i < nums.size(); i ++) { path.push_back(nums[i]); dfs(nums, i + 1); path.pop_back(); } } };

90.子集2

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2] 输出:

[ [2], [1], [1,2,2], [2,2], [1,2], [] ] class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); dfs(nums, 0); return ans; } void dfs(vector<int> &nums, int u) { if(u == nums.size()) { ans.push_back(path); return; } int k = u; while(k < nums.size() && nums[k] == nums[u]) k ++; dfs(nums, k); for(int i = u; i < k; i ++) { path.push_back(nums[i]); dfs(nums, k); } while(path.size() && path.back() == nums[u]) path.pop_back(); } };

39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1:

输入: candidates = [2,3,6,7], target = 7, 所求解集为:

[ [7], [2,2,3] ]

示例 2:

输入: candidates = [2,3,5], target = 8, 所求解集为:

[ [2,2,2,2], [2,3,3], [3,5] ] class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { dfs(candidates, 0, target); return ans; } void dfs(vector<int>&c, int u, int t) { if(u == c.size()) { if(!t) ans.push_back(path); return; } dfs(c, u + 1, t); while(t >= c[u]) { path.push_back(c[u]); t -= c[u]; dfs(c, u + 1, t); } while(path.size() && path.back() == c[u]) path.pop_back(); } };

40.组合总和2

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为:

[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为:

[ [1,2,2], [5] ] class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); dfs(candidates, 0, target); return ans; } void dfs(vector<int> &c, int u, int t) { if(!t) { ans.push_back(path); return; } if(u == c.size()) return; int k = u + 1; while(k < c.size() && c[k] == c[u]) k ++; dfs(c, k, t); int value = c[u]; for(int i = value, j = u; j < k && i <= t; i += value, j ++) { path.push_back(value); dfs(c, k, t - i); } while(path.size() && path.back() == value) path.pop_back(); } };

216.组合数3

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。 解集不能包含重复的组合。 示例 1:

输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2:

输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

class Solution { public: vector<vector<int>>ans; vector<int> path; vector<vector<int>> combinationSum3(int k, int n) { dfs(k, n, 1); return ans; } void dfs(int k, int n, int start) { if(!k) { if(!n) ans.push_back(path); return; } for(int i = start; i <= 10 - k; i ++) { if(n >= i) { path.push_back(i); dfs(k - 1, n - i, i + 1); path.pop_back(); } } } };

22.括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ "((()))", "(()())", "(())()", "()(())", "()()()" ] class Solution { public: int m; vector<string> ans; vector<string> generateParenthesis(int n) { m = n; dfs("", 0, 0); return ans; } void dfs(string path, int l, int r) { if(l == m && r == m) { ans.push_back(path); return; } if(l < m) dfs(path + "(", l + 1, r); if(l > r) dfs(path + ")", l, r + 1); } };

473.火柴拼正方形

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2] 输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。 示例 2:

输入: [3,3,3,3,4] 输出: false

解释: 不能用所有火柴拼成一个正方形。 注意:

给定的火柴长度和在 0 到 10^9之间。 火柴数组的长度不超过15。

class Solution { public: int side; vector<bool>st; bool makesquare(vector<int>& nums) { if(!nums.size()) return false; int sum = 0; for(auto x : nums) sum += x; if(sum % 4) return false; side = sum / 4; sort(nums.begin(), nums.end()); st = vector<bool>(nums.size()); return dfs(nums, 0, side, nums.size() - 1); } bool dfs(vector<int> &nums, int count, int sum, int start) { if(!sum) { if(++count == 4) return true; return dfs(nums, count, side, nums.size() - 1); } for(int i = start; i >= 0; i --) { if(!st[i] && sum >= nums[i]) { if(i + 1 < nums.size() && !st[i + 1] && nums[i + 1] == nums[i]) continue; st[i] = true; if(dfs(nums, count, sum - nums[i], i - 1)) return true; st[i] = false; //if(nums[i] == sum || sum == side) return false; } } return false; } };

52.N皇后2

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。

[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] class Solution { public: int ans, n; vector<bool> col, diag, anti_diag; int totalNQueens(int _n) { n = _n; col = vector<bool>(n); diag = anti_diag = vector<bool>(2 * n); dfs(0); return ans; } void dfs(int u) { if(u == n) { ans ++; return; } for(int i = 0; i < n; i ++) { if(!col[i] && !diag[u + i] && !anti_diag[u - i + n]) { col[i] = diag[u + i] = anti_diag[u - i + n] = true; dfs(u + 1); col[i] = diag[u + i] = anti_diag[u - i + n] = false; } } } };

37.解数独

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 ‘.’ 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。

class Solution { public: bool row[9][9], col[9][9], st[3][3][9]; void solveSudoku(vector<vector<char>>& board) { memset(row, 0, sizeof row); memset(col, 0, sizeof col); memset(st, 0, sizeof st); for(int i = 0; i < 9; i ++) for(int j = 0; j < 9; j ++) if(board[i][j] != '.') { int v = board[i][j] - '1'; row[i][v] = col[j][v] = st[i/3][j/3][v] = true; } dfs(board, 0, 0); } bool dfs(vector<vector<char>>&board, int x, int y) { if(y == 9) y = 0, x ++; if(x == 9) return true; if(board[x][y] != '.') return dfs(board, x, y + 1); for(int i = 0; i < 9; i ++) { if(board[x][y] == '.' && !row[x][i] && !col[y][i] && !st[x/3][y/3][i]) { board[x][y] = '1' + i; row[x][i] = col[y][i] = st[x/3][y/3][i] = true; if(dfs(board, x, y + 1)) return true; board[x][y] = '.'; row[x][i] = col[y][i] = st[x/3][y/3][i] = false; } } return false; } };

282.给表达式添加运算符

给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

输入: num = “123”, target = 6 输出: [“1+2+3”, “123”] 示例 2:

输入: num = “232”, target = 8 输出: [“23+2", "2+32”] 示例 3:

输入: num = “105”, target = 5 输出: [“1*0+5”,“10-5”] 示例 4:

输入: num = “00”, target = 0 输出: [“0+0”, “0-0”, “0*0”] 示例 5:

输入: num = “3456237490”, target = 9191 输出: []

class Solution { public: vector<string>ans; vector<string> addOperators(string num, int target) { dfs(num, "", 0, 0, 0, target); return ans; } void dfs(string &num, string path, int pos, long long sum, long long mul, int target) { if(pos == num.size()) { if(sum == target) ans.push_back(path); return; } for(int i = pos; i < num.size(); i ++) { if(i > pos && num[pos] == '0') break; long long v = 0; for(int j = pos; j <= i; j ++) v = v * 10 + num[j] - '0'; string number = num.substr(pos, i - pos + 1); if(!pos) { dfs(num, number, i + 1, v, v, target); } else { dfs(num, path + '+' + number, i + 1, sum + v, v, target); dfs(num, path + '-' + number, i + 1, sum - v, -v, target); dfs(num, path + '*' + number, i + 1, sum - mul + mul * v, mul * v, target); } } } };

301.删除无效的括号

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: “()())()” 输出: ["()()()", “(())()”] 示例 2:

输入: “(a)())()” 输出: ["(a)()()", “(a())()”] 示例 3:

输入: “)(” 输出: [""]

class Solution { public: set<string> ans; vector<string> removeInvalidParentheses(string s) { int left = 0, right = 0; for(auto c : s) if(c == '(') { left ++; } else if(c == ')') { if(left) left --; else right ++; } dfs(s, 0, left, right); return vector<string>(ans.begin(), ans.end()); } bool check(string s) { int cnt = 0; for(auto c : s) if(c == '(') cnt ++; else if(c == ')') { cnt --; if(cnt < 0) return false; } return cnt == 0; } void dfs(string s, int u, int left, int right) { if(u == s.size()) { if(check(s)) ans.insert(s); return; } dfs(s, u + 1, left, right); if(left > 0 && s[u] == '(') { string rans = s; s.erase(s.begin() + u); dfs(s, u, left - 1, right); s = rans; } if(right > 0 && s[u] == ')') { string rans = s; s.erase(s.begin() + u); dfs(s, u, left, right - 1); s = rans; } } };