1 全排列
- 题目链接：46. 全排列 “46. 全排列”)
1.1 题目描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例1:
输入: nums = [1,2,3]
输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例2:
输入: nums = [0,1]
输出: [[0,1],[1,0]]
示例3:
输入: nums = [1]
输出: [[1]]
1.2 思路
/analysis_of_question_and_solving_thought_here/
完整代码如下：
Cpp实现
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
int size;
void dfs(vector<int>& nums, int startIndex, vector<bool>& used){
if(path.size() == size){
res.emplace_back(path);
return;
}
for(int i = 0; i < size; ++i){
if(used[nums[i]+10]){
continue; //检测是否用过该数字以及当前数字加入后是否还是递增的
}
used[nums[i]+10] = true; //已经访问过该数字，哈希置为true
path.emplace_back(nums[i]);
dfs(nums, i+1, used);
used[nums[i]+10] = false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
size = nums.size();
vector<bool> used(size, 0);
dfs(nums, 0, used);
return res;
}
};C实现
int** res;
int* path;
bool used[21] = {0};
int size;
void copy(int pathSize, int *returnSize, int **returnColumnSizes){
res[*returnSize] = (int *)malloc(sizeof(int)*pathSize);
(*returnColumnSizes)[*returnSize] = pathSize;
for(int i = 0; i < pathSize; ++i){
res[*returnSize][i] = path[i];
}
(*returnSize)++;
}
void dfs(int* nums, int startIndex, int pos, int* returnSize, int** returnColumnSizes){
if(pos == size){
copy(pos, returnSize, returnColumnSizes);
return;
}
for(int i = 0; i < size; ++i){
if(used[nums[i]+10]){
continue;
}
used[nums[i]+10] = true;
path[pos] = nums[i];
dfs(nums, i+1, pos+1, returnSize, returnColumnSizes);
used[nums[i]+10] = false;
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
size = numsSize;
res = (int**)malloc(sizeof(int *)*46656);
*returnColumnSizes = (int *)malloc(sizeof(int)*46656);
*returnSize = 0;
if(size == 0) return res;
path = (int *)malloc(sizeof(int)*6);
dfs(nums, 0, 0, returnSize, returnColumnSizes);
return res;
} 2 全排列 II
- 题目链接：47. 全排列 II “47. 全排列 II”)
2.1 题目描述
给定一个可包含重复数字的序列 nums ，按 任意顺序 返回所有不重复的全排列。
示例1:
输入: nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
示例2:
输入: nums = [1,2,3]
输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
2.2 思路
/analysis_of_question_and_solving_thought_here/
完整代码如下：
Cpp实现
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
int size;
void dfs(vector<int>& nums, vector<bool>& used){
if(path.size() == size){
res.emplace_back(path);
return;
}
for(int i = 0; i < size; ++i){
if(i > 0 && nums[i] == nums[i-1] && !used[i-1]){
continue; //检测是否用过该数字以及当前数字加入后是否还是递增的
}
if(used[i]){
continue;
}
used[i] = true; //已经访问过该数字，哈希置为true
path.emplace_back(nums[i]);
dfs(nums, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
size = nums.size();
vector<bool> used(size, false);
sort(nums.begin(), nums.end());
dfs(nums, used);
return res;
}
};C实现
int** res;
int* path;
int size;
bool *used;
void copy(int pathSize, int *returnSize, int **returnColumnSizes){
res[*returnSize] = (int *)malloc(sizeof(int)*pathSize);
(*returnColumnSizes)[*returnSize] = pathSize;
for(int i = 0; i < pathSize; ++i){
res[*returnSize][i] = path[i];
}
(*returnSize)++;
}
void dfs(int* nums, int pos, int* returnSize, int** returnColumnSizes){
if(pos == size){
copy(pos, returnSize, returnColumnSizes);
return;
}
for(int i = 0; i < size; ++i){
if(i > 0 && nums[i] == nums[i-1] && !used[i-1]){
continue;
}
if(used[i]){
continue;
}
used[i] = true;
path[pos] = nums[i];
dfs(nums, pos+1, returnSize, returnColumnSizes);
used[i] = false;
}
}
bool cmp(const void *a, const void * b){
return (*(int *)a > *(int *)b);
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
size = numsSize;
int n = pow(size, size);
res = (int**)malloc(sizeof(int *)*n);
*returnColumnSizes = (int *)malloc(sizeof(int)*n);
*returnSize = 0;
if(size == 0) return res;
qsort(nums, size, sizeof(int), cmp);
used = malloc(sizeof(bool)*size);
memset(used, 0, sizeof(bool)*size);
path = malloc(sizeof(int)*8);
dfs(nums, 0, returnSize, returnColumnSizes);
free(path);
return res;
} 3 重新安排行程
- 题目链接：332. 重新安排行程
3.1 题目描述
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例1:
输入: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
输出: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]
示例2:
输入: tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
输出: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
解释: 另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] ，但是它字典排序更大更靠后。
3.2 思路
上来直接回溯，先按票的第二个排个序，然后就是回溯，然后喜提双5％.~
完整代码如下：
Cpp实现
class Solution {
public:
int size;
bool flag;
vector<string> res;
void dfs(vector<vector<string>> tickets, vector<bool>& visited, int rest){
if(flag || rest == 0){
if(flag) return;
flag = true;
return;
}
for(int i = 0; i < size; ++i){
if(visited[i] || tickets[i][0] != res.back()){
continue;
}
visited[i] = 1;
res.emplace_back(tickets[i][1]);
dfs(tickets, visited, rest - 1);
if(flag) return;
res.pop_back();
visited[i] = 0;
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
size = tickets.size();
flag = false;
vector<bool> visited(size, 0);
res.emplace_back("JFK");
sort(tickets.begin(), tickets.end(),
[](const vector<string>&a, const vector<string>&b){
return a[1] < b[1]; //lambda表达式，进行排序
});
dfs(tickets, visited, size);
return res;
}
};C实现
4 N 皇后
- 题目链接：51. N 皇后
4.1 题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例1:
输入: n = 4
输出: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
示例2:
输入: n = 1
输出: [[“Q”]]
4.2 思路
先创建一个vector visited，元素为pair，pair中的元素分别代表已经访问过的行和列. N皇后要求每一行、每一列、每个45°角上的格子有且仅有一个皇后Q.
用一个变量来存储还有多少个皇后没被放到棋盘上，这里定义为
rest，初始化为n(因为一开始还没放皇后的时候就还剩n个皇后要放). 当某次递归开始前检测到rest == 0时说明皇后已经放完了，将结果插入到答案vector中。用一个变量来表示当前的皇后要放的行数，这里定义为
row，很显然，当row >= n这个条件成立时说明越界，直接返回即可。递归过程进行列数的选择，即循环遍历列，并判断当前行中所遍历的列数是否可以放皇后，可以的话，则将行数、列数作为一个
pair插入到visited中，并进行下一层递归。
要注意，每一行为一个
string，这个string要初始化为n个.,然后当当前位置可行时则将对应位置置为Q表示在这个格子放皇后。回溯后需要将这个格重新赋值为.。
完整代码如下：
Cpp实现
class Solution {
public:
vector<vector<string>> res;
vector<string> tmp;
bool check(int row, int col, vector<pair<int, int>> visited){ //检测位置是否可行
for(auto iter: visited){
if(row == iter.first //同列
|| col == iter.second //同行
||(abs(row - iter.first) == abs(col - iter.second))){ //45°角
return false;
}
}
return true;
}
void dfs(int n, int row, vector<pair<int, int>>& visited, int rest){
if(row >= n|| rest == 0){
if(rest == 0){
res.emplace_back(tmp);
}
return;
}
string str = "";
for(int i = 0; i < n; ++i){
str += ".";
}
for(int c = 0; c < n; ++c){
if(check(row,c, visited)){
visited.emplace_back(make_pair(row, c));
str[c] = 'Q';
tmp.emplace_back(str);
dfs(n, row+1, visited, rest-1);
str[c] = '.';
visited.pop_back();
tmp.pop_back();
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<pair<int, int>> visited;
dfs(n, 0, visited, n);
return res;
}
}; 5 解数独
- 题目链接：37. 解数独
5.1 题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例1:
输入: 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”]]
5.2 思路
/analysis_of_question_and_solving_thought_here/
完整代码如下：
Cpp实现
class Solution {
public:
bool check(vector<vector<char>>& board, int row, int col, char ch){
int new_r = row/3*3, new_c = col/3*3;
for(int i = 0; i < 9; ++i){
new_r += i/3, new_c += i%3;
if(board[row][i] == ch ||
board[i][col] == ch ||
board[new_r][new_c] == ch){
return false;
}
}
return true;
}
bool dfs(vector<vector<char>>& board){
for(int row = 0; row < 9; ++row){
for(int col = 0; col < 9; ++col){
if(board[row][col] != '.'){
continue;
}
for(int i = 1; i <= 9; ++i){
char ch = i + '0';
if(check(board, row, col, ch)){
board[row][col] = ch;
if(dfs(board)) return true;
}
board[row][col] = '.';
}
return false;
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
dfs(board);
}
};C实现
总结
这五道题加上第1部分的第10题值得再刷两三遍！
