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

代码随想录第二十五天

news 2024/11/17 1:56:09

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;
}