中国建设工程招投标网站,沈阳关键字优化公司,关键词优化公司哪家强,wordpress 自动收录目录 17. 电话号码的字母组合
37. 解数独
51. N 皇后
52. N皇后 II
89. 格雷编码
90. 子集 II 17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电…目录 17. 电话号码的字母组合
37. 解数独
51. N 皇后
52. N皇后 II
89. 格雷编码
90. 子集 II 17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]
示例 2
输入digits
输出[]
示例 3
输入digits 2
输出[a,b,c]
提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
#include bits/stdc.h
using namespace std;class Solution
{
public:vectorstring result;vectorstring letterCombinations(string digits){string temp;if (digits.length() 0)return result;getAns(digits, 0, temp, result);return result;}void getAns(string digits, int start, string temp, vectorstring result){if (temp.size() digits.length())result.push_back(temp);else{vectorchar let getLet(digits[start]);for (int i 0; i let.size(); i){temp.append(1, let[i]);getAns(digits, start 1, temp, result);temp.pop_back();}}}vectorchar getLet(char i){vectorchar let;if (i 2){let.push_back(a);let.push_back(b);let.push_back(c);}else if (i 3){let.push_back(d);let.push_back(e);let.push_back(f);}else if (i 4){let.push_back(g);let.push_back(h);let.push_back(i);}else if (i 5){let.push_back(j);let.push_back(k);let.push_back(l);}else if (i 6){let.push_back(m);let.push_back(n);let.push_back(o);}else if (i 7){let.push_back(p);let.push_back(q);let.push_back(r);let.push_back(s);}else if (i 8){let.push_back(t);let.push_back(u);let.push_back(v);}else if (i 9){let.push_back(w);let.push_back(x);let.push_back(y);let.push_back(z);}return let;}
};int main()
{Solution s1;string digits 23;for (auto comb : s1.letterCombinations(digits))cout comb ;cout endl;Solution s2;digits ;for (auto comb : s2.letterCombinations(digits))cout comb ;cout endl;Solution s3;digits 2;for (auto comb : s3.letterCombinations(digits))cout comb ;return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:unordered_mapchar, string map {{2, abc}, {3, def}, {4, ghi}, {5, jkl}, {6, mno}, {7, pqrs}, {8, tuv}, {9, wxyz}};vectorstring res;void backtrack(string s, int index, string cur){if (index s.size()){res.push_back(cur);return;}for (int i 0; i map[s[index]].size(); i)backtrack(s, index 1, cur map[s[index]][i]);}vectorstring letterCombinations(string digits){if (digits.size() 0)return res;string cur;backtrack(digits, 0, cur);return res;}
};int main()
{Solution s1;string digits 23;for (auto comb : s1.letterCombinations(digits))cout comb ;cout endl;Solution s2;digits ;for (auto comb : s2.letterCombinations(digits))cout comb ;cout endl;Solution s3;digits 2;for (auto comb : s3.letterCombinations(digits))cout comb ;return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:vectorstring letterCombinations(string digits){if (digits.size() 0)return {};mapchar, string a;a.insert(mapchar, string::value_type(2, abc));a.insert(mapchar, string::value_type(3, def));a.insert(mapchar, string::value_type(4, ghi));a.insert(mapchar, string::value_type(5, jkl));a.insert(mapchar, string::value_type(6, mno));a.insert(mapchar, string::value_type(7, pqrs));a.insert(mapchar, string::value_type(8, tuv));a.insert(mapchar, string::value_type(9, wxyz));int count 1;for (int i 0; i digits.size(); i){count * a[digits[i]].size();}vectorstring res(count);count 1;for (int i 0; i digits.size(); i){int index 0;vectorstring temp(res.begin(), res.begin() count);for (int k 0; k count; k){for (auto c : a[digits[i]]){res[index] temp[k] c;index;}}count * a[digits[i]].size();}return res;}
};int main()
{Solution s1;string digits 23;for (auto comb : s1.letterCombinations(digits))cout comb ;cout endl;Solution s2;digits ;for (auto comb : s2.letterCombinations(digits))cout comb ;cout endl;Solution s3;digits 2;for (auto comb : s3.letterCombinations(digits))cout comb ;return 0;
} 37. 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。
示例
输入 board [[5,3,.,.,7,.,.,.,.],[6,.,.,1,9,5,.,.,.],[.,9,8,.,.,.,.,6,.],[8,.,.,.,6,.,.,.,3],[4,.,.,8,.,3,.,.,1],[7,.,.,.,2,.,.,.,6],[.,6,.,.,.,.,2,8,.],[.,.,.,4,1,9,.,.,5],[.,.,.,.,8,.,.,7,9]]
输出 [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]
解释输入的数独如上图所示唯一有效的解决方案如下所示 提示 board.length 9board[i].length 9board[i][j] 是一位数字或者 .题目数据 保证 输入数独仅有一个解#include bits/stdc.h
using namespace std;class Solution
{
public:void solveSudoku(vectorvectorchar board){Dfs(board, 0);}private:bool flag false;void Dfs(vectorvectorchar board, int n){if (n 0 n 81)if (!JudgeIsNoWant(board, n - 1))return;if (n 81){flag true;return;}int x n / 9;int y n % 9;if (board[x][y] ! .)Dfs(board, n 1);else{for (int i 1; i 10; i){board[x][y] i 48;Dfs(board, n 1);if (flag true)return;board[x][y] .;}}}bool JudgeIsNoWant(vectorvectorchar board, int n){int x n / 9;int y n % 9;for (size_t i 0; i 9; i){if (board[x][i] board[x][y] i ! y)return false;if (board[i][y] board[x][y] i ! x)return false;}for (int i x / 3 * 3; i x / 3 * 3 3; i)for (int j y / 3 * 3; j y / 3 * 3 3; j)if (board[i][j] board[x][y] (i ! x || j ! y))return false;return true;}
};int main()
{Solution s;vectorvectorcharboard {{5,3,.,.,7,.,.,.,.},{6,.,.,1,9,5,.,.,.},{.,9,8,.,.,.,.,6,.},{8,.,.,.,6,.,.,.,3},{4,.,.,8,.,3,.,.,1},{7,.,.,.,2,.,.,.,6},{.,6,.,.,.,.,2,8,.},{.,.,.,4,1,9,.,.,5},{.,.,.,.,8,.,.,7,9}};s.solveSudoku(board);for (auto sudoku : board){for (auto row : sudoku)cout row ;cout endl;}return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:void solveSudoku(vectorvectorchar board){int size board.size();vectorvectorbool rows(size, vectorbool(10));vectorvectorbool cols(size, vectorbool(10));vectorvectorbool boxes(size, vectorbool(10));for (int i 0; i size; i){for (int j 0; j size; j){if (board[i][j] ! .){int num board[i][j] - 0;int idx i / 3 * 3 j / 3;rows[i][num] true;cols[j][num] true;boxes[idx][num] true;}}}dfs(board, 0, rows, cols, boxes);}
private:bool valid(int num, int row, int col, int idx, vectorvectorbool rows,vectorvectorbool cols, vectorvectorbool boxes){return !rows[row][num] !cols[col][num] !boxes[idx][num];}bool dfs(vectorvectorchar board, int size, vectorvectorbool rows,vectorvectorbool cols, vectorvectorbool boxes){if (size 9 * 9){return true;}else{bool ok false;int row size / 9;int col size % 9;int idx row / 3 * 3 col / 3;if (board[row][col] .){for (int i 1; i 9; i){if (valid(i, row, col, idx, rows, cols, boxes)){board[row][col] i 0;rows[row][i] true;cols[col][i] true;boxes[idx][i] true;ok dfs(board, size 1, rows, cols, boxes);if (!ok){rows[row][i] false;cols[col][i] false;boxes[idx][i] false;board[row][col] .;}}}}else{ok dfs(board, size 1, rows, cols, boxes);}return ok;}}
};int main()
{Solution s;vectorvectorcharboard {{5,3,.,.,7,.,.,.,.},{6,.,.,1,9,5,.,.,.},{.,9,8,.,.,.,.,6,.},{8,.,.,.,6,.,.,.,3},{4,.,.,8,.,3,.,.,1},{7,.,.,.,2,.,.,.,6},{.,6,.,.,.,.,2,8,.},{.,.,.,4,1,9,.,.,5},{.,.,.,.,8,.,.,7,9}};s.solveSudoku(board);for (auto sudoku : board){for (auto row : sudoku)cout row ;cout endl;}return 0;
}
以下代码错不显示结果输出起始board
#include bits/stdc.h
using namespace std;class Solution
{
public:int row[9][9], col[9][9], block[9][9];void solveSudoku(vectorvectorchar board){for (int i 0; i 9; i){for (int j 0; j 9; j){if (board[i][j] .)continue;int num board[i][j] - 1;row[i][num] col[j][num] block[i / 3 * 3 j / 3][num] 1;}}dfs(board, 0, 0);}bool dfs(vectorvectorchar board, int r, int c){if (r 8)return true;if (board[r][c] .){for (int i 0; i 9; i){if (row[r][i] || col[c][i] || block[r / 3 * 3 c / 3][i])continue;board[r][c] i 1 0;row[r][i] col[c][i] block[r / 3 * 3 c / 3][i] 1;if (dfs(board, r (c 1) / 9, (c 1) % 9))return true;board[r][c] .;row[r][i] col[c][i] block[r / 3 * 3 c / 3][i] 0;}}elsereturn dfs(board, r (c 1) / 9, (c 1) % 9);return false;}
};int main()
{Solution s;vectorvectorcharboard {{5,3,.,.,7,.,.,.,.},{6,.,.,1,9,5,.,.,.},{.,9,8,.,.,.,.,6,.},{8,.,.,.,6,.,.,.,3},{4,.,.,8,.,3,.,.,1},{7,.,.,.,2,.,.,.,6},{.,6,.,.,.,.,2,8,.},{.,.,.,4,1,9,.,.,5},{.,.,.,.,8,.,.,7,9}};s.solveSudoku(board);for (auto sudoku : board){for (auto row : sudoku)cout row ;cout endl;}return 0;
} 51. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。
示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。
示例 2
输入n 1
输出[[Q]]
提示
1 n 9皇后彼此不能相互攻击也就是说任何两个皇后都不能处于同一条横行、纵行或斜线上。
#include bits/stdc.h
using namespace std;class Solution
{
public:vectorvectorstring solveNQueens(int n){vectorvectorstring res;vectorint stack(n);vectorstring solution(n, string(n, .));dfs(n, 0, stack, solution, res);return res;}private:void dfs(int n, int row, vectorint stack, vectorstring solution, vectorvectorstring res){if (row n){res.push_back(solution);}else{for (int i 0; i n; i){if (row 0 || !conflict(stack, row, i)){solution[row][i] Q;stack[row] i;dfs(n, row 1, stack, solution, res);solution[row][i] .;}}}}bool conflict(vectorint stack, int row, int col){for (int i 0; i row; i){if (col stack[i] || abs(row - i) abs(col - stack[i])){return true;}}return false;}
};int main()
{Solution s;int i 0;for (auto res : s.solveNQueens(4)){cout i endl;for (auto item : res)cout item ;cout endl;}cout endl;return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:vectorvectorstring res;vectorvectorstring solveNQueens(int n){vectorstring board(n, string(n, .));backtrack(board, 0);return res;}void backtrack(vectorstring board, int row){if (row board.size()){res.push_back(board);return;}int n board[row].size();for (int col 0; col n; col){if (!isValid(board, row, col)){continue;}board[row][col] Q;backtrack(board, row 1);board[row][col] .;}}bool isValid(vectorstring board, int row, int col){int n board.size();for (int i 0; i row; i){if (board[i][col] Q){return false;}}for (int i row - 1, j col 1; i 0 j n; i--, j){if (board[i][j] Q){return false;}}for (int i row - 1, j col - 1; i 0 j 0; i--, j--){if (board[i][j] Q){return false;}}return true;}
};int main()
{Solution s;int i 0;for (auto res : s.solveNQueens(4)){cout i endl;for (auto item : res)cout item ;cout endl;}cout endl;return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:bool isValue(vectorint pos, int row, int col){for (int i 0; i row; i){if (col pos[i] || abs(row - i) abs(col - pos[i]))return false;}return true;}void solveNQueensDFS(vectorint pos, int row, vectorvectorstring ans){int n pos.size();if (row n){vectorstring tmp(n, string(n, .));for (int i 0; i n; i)tmp[i][pos[i]] Q;ans.push_back(tmp);}else{for (int col 0; col n; col){if (isValue(pos, row, col)){pos[row] col;solveNQueensDFS(pos, row 1, ans);pos[row] -1;}}}}vectorvectorstring solveNQueens(int n){vectorint pos(n, -1);vectorvectorstring ans;solveNQueensDFS(pos, 0, ans);return ans;}
};int main()
{Solution s;int i 0;for (auto res : s.solveNQueens(4)){cout i endl;for (auto item : res)cout item ;cout endl;}cout endl;return 0;
} 52. N皇后 II
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回 n 皇后问题 不同的解决方案的数量。
示例 1 输入n 4
输出2
解释如上图所示4 皇后问题存在两个不同的解法。示例 2
输入n 1
输出1提示
1 n 9皇后彼此不能相互攻击也就是说任何两个皇后都不能处于同一条横行、纵行或斜线上。#include bits/stdc.h
using namespace std;class Solution
{
public:int totalNQueens(int n){vectorint stack(n);return dfs(n, 0, stack);}private:int dfs(int n, int row, vectorint stack){int count 0;if (row n){return count 1;}else{for (int i 0; i n; i){if (row 0 || !conflict(stack, row, i)){stack[row] i;count dfs(n, row 1, stack);}}return count;}}bool conflict(vectorint stack, int row, int col){for (int i 0; i row; i){if (col stack[i] || abs(row - i) abs(col - stack[i])){return true;}}return false;}
};int main()
{Solution s;cout s.totalNQueens(1) endl;cout s.totalNQueens(4) endl;cout s.totalNQueens(8) endl;return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:bool isvalid(vectorstring temp, int i, int j){ //判断棋盘是否有效//for (int k 0; ktemp[i].size(); k){//判断行。不用判断行了每行放一个之后就会递归到下一行了// if (temp[i][k] Q) return false;//}for (int k 0; k i; k){ //判断列if (temp[k][j] Q)return false;}for (int p i - 1, q j - 1; p 0 q 0; --p, --q){ //判断左上对角线if (temp[p][q] Q)return false;}for (int p i - 1, q j 1; p 0 q temp.size(); --p, q){ //判断右上对角线if (temp[p][q] Q)return false;}return true;}int dfs(int count, vectorstring temp, int i, int n){if (i n)return count;for (int j 0; j n; j){if (isvalid(temp, i, j)){temp[i][j] Q; //递归前修改dfs(count, temp, i 1, n);}temp[i][j] .; //递归后恢复}return count;}int totalNQueens(int n){int count 0;string aa;for (int i 0; i n; i)aa .;vectorstring temp(n, aa);return dfs(count, temp, 0, n);}
};int main()
{Solution s;cout s.totalNQueens(1) endl;cout s.totalNQueens(4) endl;cout s.totalNQueens(8) endl;return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:void recurse(vectorstring solution, int pos, vectorvectorbool validPos, int result){int n solution[0].size();if (pos n){result;return;}for (int i 0; i n; i){if (!validPos[pos][i])continue;vectorvectorbool newPos validPos;for (int j pos; j n; j){newPos[j][i] false;if (i - j pos 0)newPos[j][i - j pos] false;if (i j - pos n)newPos[j][i j - pos] false;}solution[pos][i] Q;recurse(solution, pos 1, newPos, result);solution[pos][i] .;}return;}int totalNQueens(int n){int result 0;vectorstring solution(n, string(n, .));vectorvectorbool validPos vectorvectorbool(n, vectorbool(n, true));recurse(solution, 0, validPos, result);return result;}
};int main()
{Solution s;cout s.totalNQueens(1) endl;cout s.totalNQueens(4) endl;cout s.totalNQueens(8) endl;return 0;
} 89. 格雷编码
格雷编码是一个二进制数字系统在该系统中两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n打印其格雷编码序列。即使有多个不同答案你也只需要返回其中一种。
格雷编码序列必须以 0 开头。
示例 1:
输入: 2
输出: [0,1,3,2]
解释:00 - 001 - 111 - 310 - 2对于给定的 n其格雷编码序列并不唯一。例如[0,2,3,1] 也是一个有效的格雷编码序列。00 - 010 - 211 - 301 - 1
示例 2:
输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。给定编码总位数为 n 的格雷编码序列其长度为 2^n。当 n 0 时长度为 2^0 1。因此当 n 0 时其格雷编码序列为 [0]。
#include bits/stdc.h
using namespace std;class Solution
{
public:vectorint grayCode(int n){int size 1 n;vectorint res;for (int i 0; i size; i){int graycode i ^ (i 1);res.push_back(graycode);}return res;}
};int main()
{Solution s;vectorint res s.grayCode(2);copy(res.begin(), res.end(), ostream_iteratorint(cout, ));cout endl;res s.grayCode(0);copy(res.begin(), res.end(), ostream_iteratorint(cout, ));return 0;
}
#include bits/stdc.h
using namespace std;class Solution
{
public:vectorint grayCode(int n){vectorint res;for (int i 0; i (int)pow(2, n); i)res.push_back(i ^ (i 1));return res;}
};int main()
{Solution s;vectorint res s.grayCode(2);copy(res.begin(), res.end(), ostream_iteratorint(cout, ));cout endl;res s.grayCode(0);copy(res.begin(), res.end(), ostream_iteratorint(cout, ));return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:vectorint grayCode(int n){vectorint res;res.push_back(0);if (n 0)return res;int head 1;for (int i 0; i n; i){for (int j res.size() - 1; j 0; j--){res.push_back(head res[j]);}head 1;}return res;}
};int main()
{Solution s;vectorint res s.grayCode(2);copy(res.begin(), res.end(), ostream_iteratorint(cout, ));cout endl;res s.grayCode(0);copy(res.begin(), res.end(), ostream_iteratorint(cout, ));return 0;
} 90. 子集 II
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
示例 1
输入nums [1,2,2]
输出[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2
输入nums [0]
输出[[],[0]]
提示
1 nums.length 10-10 nums[i] 10#include bits/stdc.h
using namespace std;class Solution
{
public:vectorvectorint subsetsWithDup(vectorint nums){vectorvectorint result;vectorint item;setvectorint rset;result.push_back(item);sort(nums.begin(), nums.end());CreatSet(0, result, item, nums, rset);return result;}void CreatSet(int i, vectorvectorint result,vectorint item, vectorint nums,setvectorint rset){if (i nums.size())return;item.push_back(nums[i]);if (rset.find(item) rset.end()){rset.insert(item);result.push_back(item);}CreatSet(i 1, result, item, nums, rset);item.pop_back();CreatSet(i 1, result, item, nums, rset);}
};int main()
{Solution s;vectorint nums {1,2,2};vectorvectorint res s.subsetsWithDup(nums);for (auto r:res){copy(r.begin(), r.end(), ostream_iteratorint(cout, ));cout endl;}return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:vectorvectorint subsetsWithDup(vectorint nums){sort(nums.begin(), nums.end());vectorvectorint res;vectorint cur;for (int i 0; i nums.size(); i){dfs(res, cur, nums, 0, i);}return res;}void dfs(vectorvectorint res, vectorint cur, vectorint nums, int begin, int n){if (cur.size() n){res.push_back(cur);return;}for (int i begin; i nums.size(); i){if (i begin nums[i] nums[i - 1])continue;cur.push_back(nums[i]);dfs(res, cur, nums, i 1, n);cur.pop_back();}return;}
};int main()
{Solution s;vectorint nums {1,2,2};vectorvectorint res s.subsetsWithDup(nums);for (auto r:res){copy(r.begin(), r.end(), ostream_iteratorint(cout, ));cout endl;}return 0;
} #include bits/stdc.h
using namespace std;class Solution
{
public:vectorvectorint ans;vectorint cur;vectorint v;void dfs(int depth){ans.push_back(cur);if (depth v.size())return;for (int i depth; i v.size(); i){if (i depth v[i] v[i - 1])continue;cur.push_back(v[i]);dfs(i 1);cur.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums){sort(nums.begin(), nums.end());v nums;dfs(0);return ans;}
};string VectorToString(vectorint vec, string split,)
{if (vec.size()0) return [];string res [;for (auto n:vec)res to_string(n) split;return res.substr(0, res.length() - split.size()) ];
}int main()
{Solution s;vectorint nums {1,2,2};vectorvectorint res s.subsetsWithDup(nums);for (auto r:res){cout VectorToString(r) ;}return 0;
}
