代码随想录算法训练营第二十四天|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中，使用了一个判断条件来跳过重复元素。如果当前的元素与前一个元素相同，并且不是起始位置，就跳过这个元素。这样可以避免生成重复的子集。

总结

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