当前位置： 首页 > article >正文

代码随想录第二十五天

article 2024/11/15 23:47:34

491.非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

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

提示：

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

思路：

这道题感觉跟前几道题很像，但是要注意，我们要去重还要找出按照递增顺序排列的子集，所以当找到的个数大于2时，就往数组里面放入，并且我们要注意递归元素的条件，一是递增，二是不能与前一个元素相同，不然会重复。但是这样做出来还有一点问题，那就是会超出内存限制，所以我们要释放内存并且减少realloc的使用，最后得出答案。

解答：

第一种方法：

/**
 * 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 tarvelback(int* nums,int numsSize,int* returnSize,int** returnColumnSizes,int*** result,int combinesize,int* num,int start)
{
    if(combinesize >= 2)
    {
        (*returnSize)++;
        *result = realloc(*result,sizeof(int*)*(*returnSize));
        (*result)[(*returnSize)-1] = malloc(sizeof(int)*combinesize);
        for(int i = 0;i < combinesize;i++)
        {
            (*result)[(*returnSize)-1][i] = num[i];
        }
        *returnColumnSizes = realloc(*returnColumnSizes,sizeof(int)*(*returnSize));
        (*returnColumnSizes)[(*returnSize)-1] = combinesize;
    }
    int used[201] = {0};
    for(int i = start;i < numsSize;i++)
    {
        if((combinesize == 0 || num[combinesize-1] <= nums[i]) && !used[nums[i]+100])
        {
            num[combinesize] = nums[i];
            used[nums[i]+100] = 1;
            tarvelback(nums,numsSize,returnSize,returnColumnSizes,result,combinesize+1,num,i+1);
        }
    }
}
int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    int start = 0;
    int combinesize = 0;
    int** result = NULL;
    int* num = malloc(sizeof(int)*numsSize);
    tarvelback(nums,numsSize,returnSize,returnColumnSizes,&result,combinesize,num,start);
    return result;
}

注：但是超出了内存限制。

第二种方法(未超出内存限制的方法):

/**
 * 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*** result, int combinesize, int* num, int start) {
    if (combinesize >= 2) {
        if (*returnSize % 10 == 0) { 
            *result = realloc(*result, sizeof(int*) * (*returnSize + 10));
            *returnColumnSizes = realloc(*returnColumnSizes, sizeof(int) * (*returnSize + 10));
        }
        (*result)[*returnSize] = malloc(sizeof(int) * combinesize);
        for (int i = 0; i < combinesize; i++) {
            (*result)[*returnSize][i] = num[i];
        }
        (*returnColumnSizes)[*returnSize] = combinesize;
        (*returnSize)++;
    }
    
    int used[201] = {0};  
    for (int i = start; i < numsSize; i++) {
        if ((combinesize == 0 || num[combinesize - 1] <= nums[i]) && !used[nums[i] + 100]) {
            num[combinesize] = nums[i];
            used[nums[i] + 100] = 1;
            travelback(nums, numsSize, returnSize, returnColumnSizes, result, combinesize + 1, num, i + 1);
        }
    }
}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    int** result = NULL;
    int* num = malloc(sizeof(int) * numsSize);
    travelback(nums, numsSize, returnSize, returnColumnSizes, &result, 0, num, 0);
    free(num);  
    return result;
}

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

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

思路:

全排列也是回溯算法的一种，这里要往最终返回的数组里面放入数字的前提条件是，递归的次数等于数组里面的元素个数，同时在放入元素的同时，我们要放入一个bool数组来判断这个元素是否已经加入到了数组里面，然后当递归结束开始回溯时，我们要还原元素的bool值，让他寻找新的路径，最终返回答案。

解答：

/**
 * 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*** result,int combinesize,int* num,bool* used)
{
    if(combinesize == numsSize)
    {
        (*returnSize)++;
        *result = realloc(*result,sizeof(int*)*(*returnSize));
        (*result)[(*returnSize)-1] = malloc(sizeof(int)*combinesize);
        for(int i = 0;i < combinesize;i++)
        {
            (*result)[(*returnSize)-1][i] = num[i];
        }
        *returnColumnSizes = realloc(*returnColumnSizes,sizeof(int)*(*returnSize));
        (*returnColumnSizes)[(*returnSize)-1] = combinesize;
        return;
    }
    for(int i = 0;i < numsSize;i++)
    {
       if(used[nums[i]+10])
       {
         continue;
       }
       num[combinesize] = nums[i];
       used[nums[i]+10] = true;
       travelback(nums,numsSize,returnSize,returnColumnSizes,result,combinesize+1,num,used);
       used[nums[i]+10] = false;
    }
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    int* num = malloc(sizeof(int)*(numsSize+1));
    int combinesize = 0;
    int** result = NULL;
    bool used[21] = {0};
    travelback(nums,numsSize,returnSize,returnColumnSizes,&result,combinesize,num,used);
    return result;
}

47.全排列||

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

思路：

对于这道题，我们要先做好前置工作，给这个数组按顺序进行排序，排好序后使用一个布尔数组 used 标记每个元素是否已被使用。在排列过程中，代码跳过已使用的元素，并对重复元素进行特别处理：对于连续的重复元素，只有当前一个相同元素已被使用时，才使用当前元素。最后得到的就是去重后的正确答案。

解答：

/**
 * 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 combinesize,int* num,bool* used)
{
    if(combinesize == numsSize)
    {
        (*returnSize)++;
        *result = realloc(*result,sizeof(int*)*(*returnSize));
        (*result)[(*returnSize)-1] = malloc(sizeof(int)*combinesize);
        for(int i = 0;i < combinesize;i++)
        {
            (*result)[(*returnSize)-1][i] = num[i];
        }
        *returnColumnSizes = realloc(*returnColumnSizes,sizeof(int)*(*returnSize));
        (*returnColumnSizes)[(*returnSize)-1] = combinesize;
        return;
    }
    qsort(nums,numsSize,sizeof(int),compare);
    for(int i = 0;i < numsSize;i++)
    {
        if(used[i])
        {
            continue;
        }
        if(i > 0 && nums[i] == nums[i-1] && !used[i-1])
        {
           continue;
        }
        num[combinesize] = nums[i];
        used[i] = true;
        travelback(nums,numsSize,returnSize,returnColumnSizes,result,combinesize+1,num,used);
        used[i] = false;
    }
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    int* num = malloc(sizeof(int)*numsSize);
    int** result = NULL;
    int combinesize = 0;
    bool used[21] = {0};
    travelback(nums,numsSize,returnSize,returnColumnSizes,&result,combinesize,num,used);
    return result;
}

反思：

今天的题目都是在昨天题目的基础上进行变化的，通过这些天的练习，对于回溯算法有了一定的思路了，但是像后三道比较难的题目，就等到二刷的时候再做。


http://www.kler.cn/a/386294.html

相关文章：

  • LeetCode105.从前序与中序遍历构造二叉树
  • Java集合框架之Collection集合遍历
  • 批量重命名Excel文件并排序
  • 【LeetCode】【算法】581. 最短无序连续子数组
  • Cyberchef配合Wireshark提取并解析HTTP/TLS流量数据包中的文件
  • ios swift开发--ios远程推送通知配置
  • 减速机在工业机械中的核心作用！
  • 如何实现Delay_us和Delay_ms延时（SysTick定时器）
  • Flink安装和Flink CDC实现数据同步
  • 05 SQL炼金术：深入探索与实战优化
  • Docker平台搭建方法
  • CST案例分析：TLM算法仿真5G毫米波手机天线和整机
  • H.264/H.265播放器EasyPlayer.js无插件H5播放器关于WASM的压缩优化
  • 领略CSS Flex布局的精髓：打造响应式与创新设计
  • 基于开源 AI 智能名片 S2B2C 商城小程序的视频号交易小程序优化研究
  • 人脸识别发展现状及发展前景
  • 【微信小程序】基本语法
  • appium启动 install driver安装驱动
  • 前端入门一之JS对象、字符串对象、数组对象、Data()对象等
  • HTML CSS H5C3样式语句汇总20241105
  • SpringBoot健身房管理系统：敏捷开发实践
  • HTML 鼠标滑动 页面的header背景从透明色变为黑色
  • GitLab基于Drone搭建持续集成（CI/CD）
  • Vue前端开发：animate.css第三方动画库
  • TOSHIBA 74VHC00FT COMS汽车、工业企业的选择
  • windows terminal下载安装并替换vscode默认终端