【代码随想录】【算法训练营】【第28天】 [93]复原IP地址 [78]子集 [90]子集II

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 28，工作的周二~

题目详情

[93] 复原 IP 地址

题目描述

93 复原 IP 地址

解题思路

前提：分割问题
思路：回溯算法，确定每次递归回溯的分割位置。
重点：主要考虑清除分割位置的选取，即树状结构的划分。

代码实现

C语言

回溯

保存.的位置 + 字符串尾\0 + returnSize初始化为0

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

bool isValidIp(char *s, int startIdx, int endIdx)
{
    if ((s == NULL) || (strlen(s) == 0) || (startIdx > endIdx))
    {
        return false;
    }
    // 起始为0情况
    if ((s[startIdx] == '0') && (startIdx != endIdx))
    {
        return false;
    }
    // 无效字符情况
    int num = 0;
    for (int idx = startIdx; idx <= endIdx; idx++)
    {
        if ((s[idx] < '0') || (s[idx] > '9'))
        {
            return false;
        }
        num = num * 10 + (s[idx] - '0');
    }
    // 超过255情况
    if (num > 255)
    {
        return false;
    }
    return true;
}

void backtracking(char *s, int strLen, int startIdx, int protNum, int *portLoc, char ***ans, int *returnSize)
{
    // 退出条件
    if (protNum == 3) {
        // 判断最后一段是否符合IP有效段
        if (((strLen - startIdx) < 4) && (isValidIp(s, startIdx, strLen - 1))) {
            // 保存输出结果
            *ans = (char **)realloc(*ans, sizeof(char *) * (*returnSize + 1));
            (*ans)[*returnSize] = (char *)malloc(sizeof(char) * 17);
            int count = 0;
            int tmp = 0;
            for (int i = 0; i < strLen; i++)
            {
                if ((count < 3) && (portLoc[count] == i))
                {
                    (*ans)[*returnSize][tmp++] = '.';
                    count++;
                }
                (*ans)[*returnSize][tmp++] = s[i];
            }
            (*ans)[*returnSize][tmp] = '\0';
            (*returnSize)++;
        }
        return ;
    }
    //递归
    for (int idx = startIdx; (idx < strLen) && (idx < startIdx + 4); idx++)
    {
        // 判断是否为IP有效段
        if (isValidIp(s, startIdx, idx)) {
            // 有效，保存该.位置
            portLoc[protNum] = idx + 1;
        }
        else {
            continue;
        }
        backtracking(s, strLen, idx + 1, protNum + 1, portLoc, ans, returnSize);
        // 回溯
    }
}

char** restoreIpAddresses(char* s, int* returnSize) {
    *returnSize = 0;
    char **ans = NULL;
    if ((s == NULL) || (strlen(s) == 0))
    {
        return NULL;
    }
    // 输出变量初始化
    int strLen = strlen(s);
    int portLoc[3] = {0};
    backtracking(s, strLen, 0, 0, portLoc, &ans, returnSize);
    return ans;
}

[78] 子集

题目描述

78 子集

解题思路

前提：组合子集问题，无重复元素
思路：回溯，输出树上所有节点的路径
重点：先输出路径，再判断退出条件，以免遗漏子集。

代码实现

C语言

回溯

树的所有结点路径 + 全局变量初始化

/**
 * 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 **ans;
int ansSize = 0;
int *colSizes;
int *tmpNums;
int tmpNumsSize = 0;

void collect()
{
    ans[ansSize] = (int *)malloc(sizeof(int) * tmpNumsSize);
    for (int i = 0; i < tmpNumsSize; i++) {
        ans[ansSize][i] = tmpNums[i];
    }
    colSizes[ansSize] = tmpNumsSize;
    ansSize++;
    return ;
}

void backtracking(int *nums, int numsSize, int startIdx)
{
    // 收集该结点路径
    collect();
    // 终止条件
    if (startIdx >= numsSize) {
        return ;
    }
    // 递归
    for (int j = startIdx; j < numsSize; j++) {
        // 保存该结点
        tmpNums[tmpNumsSize++] = nums[j];
        backtracking(nums, numsSize, j + 1);
        // 回溯
        tmpNumsSize--;
    }
    return ;
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 全局变量初始化
    ans = (int **)malloc(sizeof(int *) * 10000);
    colSizes = (int *)malloc(sizeof(int) * 10000);
    tmpNums = (int *)malloc(sizeof(int) * numsSize);
    ansSize = 0;
    tmpNumsSize = 0;
    backtracking(nums, numsSize, 0);
    *returnSize = ansSize;
    *returnColumnSizes = colSizes;
    return ans;
}

[90] 子集II

题目描述

90 子集II

解题思路

前提：组合子集问题，有重复元素
思路：回溯，排序后同一树层去重，输出树上所有节点的路径。
重点：同一树层去重；先输出路径，再判断退出条件，以免遗漏子集。

代码实现

C语言

回溯

回溯 + 同一树层元素去重 + 输出全结点路径

/**
 * 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 **ans;
int ansSize;
int *length;
int *path;
int pathSize;
bool *used;

int cmp(void *p1, void *p2)
{
    return *(int *)p1 > *(int *)p2;
}

void collect()
{
    ans[ansSize] = (int *)malloc(sizeof(int) * pathSize);
    // 输出该子集
    for (int j = 0; j < pathSize; j++) {
        ans[ansSize][j] = path[j];
    }
    length[ansSize] = pathSize;
    ansSize++;
    return ;
}

void backtracking(int *nums, int numsSize, int startIndex)
{
    // 输出该子集
    collect();
    // 退出条件
    if (startIndex >= numsSize) {
        return;
    }
    // 递归
    for (int i = startIndex; i < numsSize; i++) {
        // 去重
        if ((i > 0) && (nums[i] == nums[i - 1]) && (used[i - 1] == false)) {
            continue;
        }
        // 保存该元素
        path[pathSize++] = nums[i];
        used[i] = true;
        backtracking(nums, numsSize, i + 1);
        // 回溯
        pathSize--;
        used[i] = false;
    }
    return ;
}

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 全局变量初始化
    ans = (int **)malloc(sizeof(int *) * 10000);
    ansSize = 0;
    length = (int *)malloc(sizeof(int) * 10000);
    path = (int *)malloc(sizeof(int) * numsSize);
    pathSize = 0;
    used = (bool *)malloc(sizeof(bool) * numsSize);
    for (int k = 0; k < numsSize; k++) {
        used[k] = false;
    }

    // 排序
    qsort(nums, numsSize, sizeof(int), cmp);

    // 回溯
    backtracking(nums, numsSize, 0);

    // 赋值输出结果
    *returnSize = ansSize;
    *returnColumnSizes = length;

    return ans;
}