代码随想录第二十四天

93.复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

思路：

这段代码通过递归和回溯的方法，将给定的字符串 s 转换成所有可能的合法 IP 地址组合。具体来说，IP 地址由 4 个整数段（0 到 255）组成，每段之间用 . 分隔。该代码的核心思路是依次插入 3 个 .，将字符串分割成 4 段，逐段验证每段的有效性。如果所有段都符合条件，则将当前组合存储为一个合法的 IP 地址。使用递归函数 backTracking，逐步将字符串分割成 4 段。每次递归在字符串的当前位置尝试插入一个 .，并进入下一层递归，直到插入 3 个 . 为止.在每一层递归中，函数会遍历可能的子串，检查其是否符合 IP 地址段的规则：即每段不能大于 255，不能以零开头（除非是单独的 “0”），且只能包含数字。当插入了 3 个 . 时，字符串被分割成了 4 段，此时检查最后一段是否有效。如果有效，则将当前 IP 地址组合存储到结果数组 result 中。通过回溯，函数逐步探索其他可能的分割位置，直到遍历完所有可能的分割方式。最终，restoreIpAddresses 函数返回包含所有合法 IP 地址的数组 result。

解答：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
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 0;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] > '9' || s[i] < '0') {
            return 0;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) {
            return 0;
        }
    }
    return 1;
}
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 count = 0;
            int count1 = 0;
            for (int 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;
    }
    for (int 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;
}

78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

思路：

这个跟昨天的题目很像，但是这里不用加上if条件，只需要一个一个进行寻找，为了防止子集找重，所以每次递归一次，start要加上1，最后返回结果，还是挺轻松的。

解答：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void travelback(int* nums,int numsSize,int* returnSize,int** returnColumnSizes,int combinsize,int start,int*** result,int* num)
{
    (*returnSize)++;
    *result = realloc(*result,sizeof(int*)*(*returnSize));
    (*result)[(*returnSize)-1] = malloc(sizeof(int)*(combinsize+1));
    for(int i = 0;i < combinsize;i++)
    {
        (*result)[(*returnSize)-1][i] = num[i];
    }
    (*returnColumnSizes) = realloc(*returnColumnSizes,sizeof(int)*(*returnSize));
    (*returnColumnSizes)[(*returnSize)-1] = combinsize;
    
    for(int i = start;i < numsSize;i++)
    {
        num[combinsize] = nums[i];
        travelback(nums,numsSize,returnSize,returnColumnSizes,combinsize+1,i+1,result,num);
    }
}
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int** result = NULL;
    *returnColumnSizes = NULL;
    int combinsize = 0;
    int start = 0;
    int* num = malloc(sizeof(int)*numsSize);
    travelback(nums,numsSize,returnSize,returnColumnSizes,combinsize,start,&result,num);
    return result;
}

90.子集||

给你一个整数数组 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

思路：

这道题跟上面那道题的思路差不多，但是我们要注意当有相同元素时，我们只取其中一个进行递归，以免照成重复，所以在这道题中我们需要用到qsort函数来进行排序，然后去掉重复元素后进行递归的结果，就是我们的答案。

解答：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int compare(const void* a,const void* b)
{
    return (*(int*)a-*(int*)b);
}
void travelback(int* nums,int numsSize,int* returnSize,int** returnColumnSizes,int*** result,int combines,int* num,int start)
{
    (*returnSize)++;
    *result = realloc(*result,sizeof(int*)*(*returnSize));
    (*result)[(*returnSize)-1] = malloc(sizeof(int)*combines);
    for(int i = 0;i < combines;i++)
    {
        (*result)[(*returnSize)-1][i] = num[i];
    }
    *returnColumnSizes = realloc(*returnColumnSizes,sizeof(int)*(*returnSize));
    (*returnColumnSizes)[(*returnSize)-1] = combines;
    qsort(nums,numsSize,sizeof(int),compare);
    for(int i = start;i < numsSize;i++)
    {
        if(i > start && nums[i] == nums[i-1])
        {
            continue;
        }
        num[combines] = nums[i];
        travelback(nums,numsSize,returnSize,returnColumnSizes,result,combines+1,num,i+1);
    }
}
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int** result = NULL;
    *returnColumnSizes = NULL;
    int start = 0;
    int combines = 0;
    int* num = malloc(sizeof(int)*numsSize);
    travelback(nums,numsSize,returnSize,returnColumnSizes,&result,combines,num,start);
    return result;
}

反思

第一道题的确很难，我对第一题不是特别清楚，后面的题都还好，只不过有一些思路的确不好想到，但是最终还是能做出来，第一题还需要多多复习和理解。