括号生成
给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
vector<string> generate(int n){
vector<string> result;
helper(0, 0, "", result, n);
}
void helper(int left, int right, string out, vector<string>& result){
if(left < 0 || right < 0 || left > right) return;
if(left == 0 && right == 0){ //保持左右一致，且左边在前
result.push_back(out);
return;
}
helper(left-1, right, out+"(", result);
helper(left, right-1, out+")", result);
}
全排列1-2
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
//没有重复时，用set即可
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
int n=nums.size();
helper(nums, 0, n-1, res);
return res;
}
void helper(vector<int>& a, int left,int right, vector<vector<int>> &res){
if (left==right) {res.push_back(a);return;}
for (int i=left; i<=right; ++i){
swap(a[i], a[left]);
helper(a,left+1,right,res);
swap(a[i], a[left]);
}
}
子集1-2
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
//不要重复，用set代替vector
vector<vector<int> > subsets(vector<int>& nums) {
int n=nums.size();
vector<vector<int> > result;
vector<int> res;
helper(nums,res,result,0);
return result;
}
void helper(vector<int>& nums, vector<int>& res, vector<vector<int> >& result, int i){
result.push_back(res);
for(;i<nums.size();++i){
res.push_back(nums[i]);
helper(nums, res, result, i+1);
res.pop_back();
}
}
[组合总和1-2]
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
//这一题也可以用指针来计算
vector<vector<int>> combi(vector<int>& nums, int target){
vector<vector<int>> result;
vector<int> res;
sort(nums.begin(), nums.end());
helper( nums, 0, target, res, result);
return result;
}
void helper(vector<int>& nums, int start, int target, vector<int>& res, vector<vector<int>>& result){
if(target < 0) return;
if(target == 0) {
result.push_back(res);
return;
}
for(int i=start; i<nums.size(); ++i){
//if(nums[i] == nums[i-1] && i>start) continue; //不要重复的
res.push_back(nums[i]);
helper(nums, i, target-nums[i], res, result);
res.pop_back();
}
}
分割回文串
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
vector<vector<string>> partition(string s){
vector<vector<string>> result;
vector<string> res;
helper(res, result, s, 0);
return result;
}
void helper(vector<string>& res, vector<vector<string>>& result, string s, int start){
if(start>=s.size()) {
result.push_back(res);
return;
}
for(int i=start;i<s.size();i++){
int l=start;
int r=i;
while(s[l]==s[r] && l<=r){ l--;r++;}
if(l>=r){
res.push_back(s.substr(start, i-start+1));
helper(s, i+1, res, result);
res.pop_back();
}
}
}
复原ip地址
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
vector<string> restoreIpAddresses(string s) {
vector<string> res;
helper(s, 0, "", res);
return res;
}
void helper(string s, int n, string out, vector<string>& res){
if(n==4){
if (s.empty()) res.push_back(out);
return;
}
for(int k=1;k<4;++k){ //每一个最多3位数
if(s.size() < k) break;
int val = atoi(s.substr(0,k).c_str());
if (val > 255 || k!=to_string(val).size()) continue;
helper(s.substr(k), n+1, out+s.substr(0,k)+(n==3?"":"."), res);
}
}
单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) return false;
int m = board.size(), n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (search(board, word, 0, i, j, visited)) return true;
}
}
return false;
}
bool search(vector<vector<char>>& board, string word, int idx, int i, int j, vector<vector<bool>>& visited) {
if (idx == word.size()) return true;
int m = board.size(), n = board[0].size();
if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[idx]) return false;
visited[i][j] = true;
bool res = search(board, word, idx + 1, i - 1, j, visited)
|| search(board, word, idx + 1, i + 1, j, visited)
|| search(board, word, idx + 1, i, j - 1, visited)
|| search(board, word, idx + 1, i, j + 1, visited);
visited[i][j] = false;
return res;
}
电话号码的组合
void helper (string digits, vector<string>& vec, string res, vector<string>& result){
if (digits.length() == 0){
result.push_back(res);
}else{
string digit = digits.substr(0,1);
int num = atoi(digit.c_str());
//int num = digits[0] - '0';
string letters = vec[num-2];
for(int i = 0; i < letters.length(); i++){
string letter = letters.substr(i,i+1);
helper(digits.substr(1), vec, res+letter, result);
}
}
}
vector<string> letterCombinations(string digits, vector<string>& vec) {
vector<string> result;
if (digits.length() != 0)
helper(digits, vec, "", result);
return result;
}
int main(){
string s[]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> vec(s,s+sizeof(s)/sizeof(string));
string digits="23";
vector<string> result = letterCombinations(digits, vec);
}
