代码随想录算法训练营第二十五天|Day25 回溯算法
491.递增子序列
https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
视频讲解:https://www.bilibili.com/video/BV1EG4y1h78v
思路
int* path;
int pathTop;
int** ans;
int ansTop;
int* length;
void copy() {
int* tempPath = (int*)malloc(sizeof(int) * pathTop);
memcpy(tempPath, path, pathTop * sizeof(int));
length[ansTop] = pathTop;
ans[ansTop++] = tempPath;
}
int find(int* uset, int usetSize, int key) {
int i;
for(i = 0; i < usetSize; i++) {
if(uset[i] == key)
return 1;
}
return 0;
}
void backTracking(int* nums, int numsSize, int startIndex) {
if(pathTop > 1) {
copy();
}
int* uset = (int*)malloc(sizeof(int) * numsSize);
int usetTop = 0;
int i;
for(i = startIndex; i < numsSize; i++) {
if((pathTop > 0 && nums[i] < path[pathTop - 1]) || find(uset, usetTop, nums[i]))
continue;
uset[usetTop++] = nums[i];
path[pathTop++] = nums[i];
backTracking(nums, numsSize, i + 1);
pathTop--;
}
}
int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
path = (int*)malloc(sizeof(int) * numsSize);
ans = (int**)malloc(sizeof(int*) * 33000);
length = (int*)malloc(sizeof(int*) * 33000);
pathTop = ansTop = 0;
backTracking(nums, numsSize, 0);
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
int i;
for(i = 0; i < ansTop; i++) {
(*returnColumnSizes)[i] = length[i];
}
return ans;
}
学习反思
用于寻找序列中的递增子序列。算法主要分为两个函数,backTracking和findSubsequences。backTracking函数是递归的回溯函数,用于生成递增子序列。函数中使用了一个辅助数组path来存储当前的递增子序列,pathTop表示当前path数组中元素的个数。在backTracking函数中,首先判断pathTop的值,如果大于1,则将path数组的内容复制到ans数组中,并更新ansTop的值(ansTop表示ans数组中元素的个数)。然后,创建一个辅助数组uset来存储已经使用过的元素,并用usetTop表示uset中元素的个数。接着,从startIndex开始遍历nums数组,对于每个元素,判断是否满足两个条件:当前元素小于path中最后一位元素,或者在uset中已经存在相同的元素。如果满足条件,则继续遍历下一个元素。如果不满足条件,则将当前元素放入uset数组,并将其放入path数组中,然后递归调用backTracking函数,继续生成递增子序列。最后,需要注意在回溯时将pathTop减1,以便继续遍历下一个元素。findSubsequences函数是主函数,用于调用backTracking函数并返回结果。在函数中,首先对辅助数组进行初始化,并调用backTracking函数生成递增子序列。然后,根据生成的递增子序列更新返回的结果数组returnSize和returnColumnSizes。最后,返回结果数组ans。
46.全排列
https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
视频讲解:https://www.bilibili.com/video/BV1R84y1i7Tm
思路
int* path;
int pathTop;
int** ans;
int ansTop;
void initialize(int* used, int usedLength) {
int i;
for(i = 0; i < usedLength; i++) {
used[i] = 0;
}
}
void copy() {
int* tempPath = (int*)malloc(sizeof(int) * pathTop);
int i;
for(i = 0; i < pathTop; i++) {
tempPath[i] = path[i];
}
ans[ansTop++] = tempPath;
}
void backTracking(int* nums, int numsSize, int* used) {
if(pathTop == numsSize) {
copy();
return;
}
int i;
for(i = 0; i < numsSize; i++) {
if(used[i])
continue;
used[i] = 1;
path[pathTop++] = nums[i];
backTracking(nums, numsSize, used);
pathTop--;
used[i] = 0;
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
path = (int*)malloc(sizeof(int) * numsSize);
ans = (int**)malloc(sizeof(int*) * 1000);
int* used = (int*)malloc(sizeof(int) * numsSize);
initialize(used, numsSize);
ansTop = pathTop = 0;
backTracking(nums, numsSize, used);
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
int i;
for(i = 0; i < ansTop; i++) {
(*returnColumnSizes)[i] = numsSize;
}
return ans;
}
学习反思
使用回溯算法来求解给定数组的全排列。通过不断选择未使用的元素,将其加入当前排列中,并递归搜索剩下的元素,直到得到一个完整的排列。然后将排列复制到结果数组中,并回溯到上一步,继续搜索其他可能的排列。在函数permute中,首先初始化辅助变量path、ans和used。其中path用于存储当前排列,ans用于存储所有的排列,used用于标记元素是否已经被使用过。然后调用backTracking函数开始回溯算法。backTracking函数是实现回溯算法的核心部分。在每一次递归中,首先判断是否已经找到一个完整的排列。如果是,则将当前排列复制到结果数组ans中,并返回。否则,遍历数组nums中的所有元素,对于未使用的元素,将其加入当前排列path中,并将对应的used数组标记为已使用。然后递归调用backTracking函数继续搜索剩下的元素。在递归返回后,需要回溯,即将path中的元素移除,将used数组标记为未使用。最后,在permute函数中设置返回结果的格式,返回结果数组ans,并设置每个排列的长度为numsSize。这段代码的时间复杂度为O(n!)。
N皇后
思路
char ***ans;
char **path;
int ansTop, pathTop;
void copyPath(int n) {
char **tempPath = (char**)malloc(sizeof(char*) * pathTop);
int i;
for(i = 0; i < pathTop; ++i) {
tempPath[i] = (char*)malloc(sizeof(char) * n + 1);
int j;
for(j = 0; j < n; ++j)
tempPath[i][j] = path[i][j];
tempPath[i][j] = '\0';
}
ans[ansTop++] = tempPath;
}
int isValid(int x, int y, int n) {
int i, j;
for(i = 0; i < n; ++i) {
if(path[y][i] == 'Q' || path[i][x] == 'Q')
return 0;
}
i = y - 1;
j = x - 1;
while(i >= 0 && j >= 0) {
if(path[i][j] == 'Q')
return 0;
--i, --j;
}
i = y + 1;
j = x + 1;
while(i < n && j < n) {
if(path[i][j] == 'Q')
return 0;
++i, ++j;
}
i = y - 1;
j = x + 1;
while(i >= 0 && j < n) {
if(path[i][j] == 'Q')
return 0;
--i, ++j;
}
i = y + 1;
j = x -1;
while(j >= 0 && i < n) {
if(path[i][j] == 'Q')
return 0;
++i, --j;
}
return 1;
}
void backTracking(int n, int depth) {
if(pathTop == n) {
copyPath(n);
return;
}
int i;
for(i = 0; i < n; ++i) {
if(isValid(i, depth, n)) {
path[depth][i] = 'Q';
++pathTop;
backTracking(n, depth + 1);
path[depth][i] = '.';
--pathTop;
}
}
}
void initPath(int n) {
int i, j;
for(i = 0; i < n; i++) {
path[i] = (char*)malloc(sizeof(char) * n + 1);
for(j = 0; j < n; j++)
path[i][j] = '.';
path[i][j] = '\0';
}
}
char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){
ans = (char***)malloc(sizeof(char**) * 400);
path = (char**)malloc(sizeof(char*) * n);
ansTop = pathTop = 0;
initPath(n);
backTracking(n, 0);
*returnSize = ansTop;
int i;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
for(i = 0; i < ansTop; ++i) {
(*returnColumnSizes)[i] = n;
}
return ans;
}
学习反思
解决N皇后问题的回溯算法实现。首先定义了ans和path两个全局变量,用于存储结果和当前路径。ans是一个三维字符数组,表示所有解的集合。path是一个二维字符数组,表示当前路径的棋盘状态。copyPath函数用于将path中的元素复制到ans中。首先根据pathTop的大小动态分配tempPath的空间,然后逐个复制path中的元素到tempPath中,并在最后加入'\0'作为字符串结尾。完成复制后,将tempPath赋值给ans[ansTop],并将ansTop自增1。isValid函数用于判断当前位置是否有效。首先通过两个for循环检查同一行和同一列是否有皇后,如果有则返回0表示无效。然后通过四个while循环检查两个斜角方向是否有皇后,如果有则返回0表示无效。最后返回1表示有效。backTracking函数是核心递归函数,用于将皇后放置到棋盘上。首先判断pathTop的大小是否等于n,如果是则说明path中已经有n个皇后,将path复制到ans中,然后返回上一层。否则,遍历当前行的每个位置,如果当前位置有效,则将皇后放置到该位置,然后调用backTracking函数递归下一行,递归完成后进行回溯,将当前位置的皇后移除,继续遍历下一个位置。initPath函数用于初始化path数组,将所有元素设为'.'。首先通过两个for循环分别为path中的每个char*开辟空间,并将所有字符设为'.'。在每个字符串的结尾加入'\0'作为字符串结尾。solveNQueens函数是整体的解决函数。首先初始化ans、path、ansTop和pathTop等变量。然后调用initPath函数初始化path数组。接着调用backTracking函数进行回溯算法。最后设置返回数组的大小和每个解的列数,并返回ans数组。这段代码的时间复杂度为O(n!)。
解数独
https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html
视频讲解:https://www.bilibili.com/video/BV1TW4y1471V
思路
bool isValid(char** board, int row, int col, int k) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == k) {
return false;
}
}
for (int j = 0; j < 9; j++) {
if (board[row][j] == k) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == k) {
return false;
}
}
}
return true;
}
bool backtracking(char** board, int boardSize, int* boardColSize) {
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < *boardColSize; j++) {
/* 遇到数字跳过 */
if (board[i][j] != '.') {
continue;
}
for (int k = '1'; k <= '9'; k++) {
if (isValid(board, i, j, k)) {
board[i][j] = k;
if (backtracking(board, boardSize, boardColSize)) {
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize) {
bool res = backtracking(board, boardSize, boardColSize);
}
学习反思
一个解数独问题的算法实现。算法使用回溯法来求解数独。在isValid函数中,首先判断当前位置所在行是否有重复元素,然后判断当前位置所在列是否有重复元素,最后判断当前位置所在的九宫格是否有重复元素。如果有重复元素,则返回false;否则返回true。在backtracking函数中,使用两层循环遍历数独的每个位置。如果当前位置是空格,则依次尝试填入数字1到9并判断是否满足数独规则。如果满足规则,则将当前位置填入数字,并递归调用backtracking函数继续填下一个位置。如果递归返回true,则说明找到一种解法,返回true;如果递归返回false,则回溯,将当前位置清零,并尝试下一个数字。最后,在主函数solveSudoku中调用backtracking函数求解数独。该算法的时间复杂度是O(9^(nn))。
总结
加油!!!