代码随想录算法训练营第二十四天|Day24 回溯算法

93.复原IP地址

题目链接/文章讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html

视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/

思路

char** result;
int resultTop;
int segments[3];
int isValid(char* s, int start, int end) {if(start > end)return 0;if (s[start] == '0' && start != end) { return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { return false;}num = num * 10 + (s[i] - '0');if (num > 255) { return false;}}return true;
}
void backTracking(char* s, int startIndex, int pointNum) {if(pointNum == 3) {if(isValid(s, startIndex, strlen(s) - 1)) {char* tempString = (char*)malloc(sizeof(char) * strlen(s) + 4);int j;int count = 0;int count1 = 0;for(j = 0; j < strlen(s); j++) {tempString[count++] = s[j];if(count1 < 3 && j == segments[count1]) {tempString[count++] = '.';count1++;}}tempString[count] = 0;result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));result[resultTop++] = tempString;}return ;}int i;for(i = startIndex; i < strlen(s); i++) {if(isValid(s, startIndex, i)) {segments[pointNum] = i;backTracking(s, i + 1, pointNum + 1);}else {break;}}
}
char ** restoreIpAddresses(char * s, int* returnSize){result = (char**)malloc(0);resultTop = 0;backTracking(s, 0, 0);*returnSize = resultTop;return result;
}

学习反思

使用回溯算法解决了将字符串s分割为IP地址的问题。代码中的函数isValid用于判断分割出的子串是否是合法的IP地址的一部分。函数backTracking用于递归地生成所有可能的IP地址分割方案。

1. 代码中使用了全局变量result和resultTop作为存储结果的数组和数组大小。在需要扩容数组时，使用了realloc函数进行动态内存分配。虽然这种做法是合法的，但不推荐使用全局变量，因为全局变量的使用会增加代码的不确定性和难以维护性。

2. 在递归函数backTracking中，使用了一个额外的数组segments来记录应该加入.的位置。这样可以避免在生成最终的IP地址字符串时的复杂操作。同时，也使用了两个计数器count和count1来分别记录字符串的下标和.的数量。

3. 在递归函数backTracking中，使用了两层循环。外层循环用于遍历从startIndex到字符串的末尾的所有可能的起始位置，内层循环用于判断从startIndex到当前位置的子串是否是合法的IP地址的一部分。在内层循环中，如果遇到不合法的子串，则退出内层循环，进入下一轮外层循环。

78.子集

题目链接/文章讲解：https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html

视频讲解：https://www.bilibili.com/video/BV1U84y1q7Ci

思路

void backtrack(int* nums, int numsSize, int startIndex, int** result, int* returnSize, int* returnColumnSizes, int* path, int pathSize) {result[*returnSize] = malloc(pathSize * sizeof(int)); for (int i = 0; i < pathSize; i++) {result[*returnSize][i] = path[i];}returnColumnSizes[*returnSize] = pathSize; (*returnSize)++; for (int i = startIndex; i < numsSize; i++){path[pathSize] = nums[i];backtrack(nums, numsSize, i + 1, result, returnSize, returnColumnSizes, path, pathSize + 1);}
}
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int** result = malloc(1024 * sizeof(int*)); *returnColumnSizes = malloc(1024 * sizeof(int)); int* path = malloc(numsSize * sizeof(int)); backtrack(nums, numsSize, 0, result, returnSize, *returnColumnSizes, path, 0);free(path);return result;
}

学习反思

实现了生成一个数组的所有子集的功能。使用回溯算法解决了这个问题。代码中的函数backtrack用于递归地生成所有子集，函数subsets是一个包装函数，用于初始化一些变量，并调用backtrack函数。

1. 在backtrack函数中，首先将当前路径添加到结果中。为当前子集分配内存并将路径的元素复制到当前子集中。然后记录当前子集的大小，并递增结果的计数。这样可以将当前子集添加到结果数组中。

2. 在递归函数backtrack中，使用了两层循环。外层循环用于遍历从startIndex到数组的末尾的所有可能的起始位置，内层循环用于构建子集。在内层循环中，将当前数字添加到路径中，然后递归调用自身，继续构建子集。

3. 在主函数subsets中，首先初始化一些变量，包括结果数组、每个子集的大小数组和当前路径数组。然后调用backtrack函数，开始回溯过程。

90.子集II

题目链接/文章讲解：https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html

视频讲解：https://www.bilibili.com/video/BV1vm4y1F71J

思路

int compare(const void* a, const void* b) {return (*(int*)a - *(int*)b);
}void backtrack(int* nums, int numsSize, int startIndex, int** result, int* returnSize, int* returnColumnSizes, int* path, int pathSize) {result[*returnSize] = malloc(pathSize * sizeof(int)); for (int i = 0; i < pathSize; i++) {result[*returnSize][i] = path[i];}returnColumnSizes[*returnSize] = pathSize; (*returnSize)++;for (int i = startIndex; i < numsSize; i++) {if (i > startIndex && nums[i] == nums[i - 1]) {continue;}path[pathSize] = nums[i];backtrack(nums, numsSize, i + 1, result, returnSize, returnColumnSizes, path, pathSize + 1);}
}
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {*returnSize = 0;qsort(nums, numsSize, sizeof(int), compare);int** result = malloc(1024 * sizeof(int*));*returnColumnSizes = malloc(1024 * sizeof(int));int* path = malloc(numsSize * sizeof(int)); backtrack(nums, numsSize, 0, result, returnSize, *returnColumnSizes, path, 0);free(path);return result;
}

学习反思

实现了生成一个包含重复元素的数组的所有子集的功能。与之前的代码相比，主要的变化在于在回溯的过程中加入了去重操作。

1. 在主函数subsetsWithDup中，首先对输入的数组进行排序，以便在后续的回溯过程中去重。通过调用qsort函数，使用自定义的比较函数对数组进行排序。

2. 在回溯函数backtrack中，使用了一个判断条件来跳过重复元素。如果当前的元素与前一个元素相同，并且不是起始位置，就跳过这个元素。这样可以避免生成重复的子集。

总结

对回溯算法有了更深刻的认识，加油！！！