78. 子集
中等
1.9K
相关企业
给你一个整数数组
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] <= 10nums中的所有元素 互不相同
void dfs(int* nums, int numsSize, int* returnSize, int* returnColumnSizes,int **ans,int *temp,int tempSize,int begin){ for(int i=begin;i<numsSize;i++){ temp[tempSize++]=nums[i]; ans[*returnSize]=(int*)malloc(sizeof(int)*tempSize); for(int j=0;j<tempSize;j++){ ans[*returnSize][j]=temp[j]; } returnColumnSizes[*returnSize]=tempSize; (*returnSize)++; dfs(nums,numsSize,returnSize,returnColumnSizes,ans,temp,tempSize,i+1); tempSize--; } return; } int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ int **ans=(int **)malloc(sizeof(int*)*10000); int *temp=(int*)malloc(sizeof(int)*numsSize); *returnColumnSizes=(int*)malloc(sizeof(int)*10000); * returnColumnSizes[0]=0; *returnSize=1; dfs(nums,numsSize,returnSize,*returnColumnSizes,ans,temp,0,0); return ans; }
90. 子集 II
中等
1K
相关企业
给你一个整数数组
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
int cmp(int* a, int* b) { return *a - *b; } int *falg[100]={0}; void dfs(int* nums, int numsSize, int* returnSize, int* returnColumnSizes,int **ans,int *temp,int tempSize,int begin){ for(int i=begin;i<numsSize;i++){ if(i>0&&nums[i-1]==nums[i]&&falg[i-1]==0){ continue; } temp[tempSize++]=nums[i]; ans[*returnSize]=(int*)malloc(sizeof(int)*tempSize); for(int j=0;j<tempSize;j++){ ans[*returnSize][j]=temp[j]; } returnColumnSizes[*returnSize]=tempSize; (*returnSize)++; falg[i]=1; dfs(nums,numsSize,returnSize,returnColumnSizes,ans,temp,tempSize,i+1); tempSize--; falg[i]=0; } return; } int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ int **ans=(int **)malloc(sizeof(int*)*10000); int *temp=(int*)malloc(sizeof(int)*numsSize); qsort(nums, numsSize, sizeof(int), cmp); *returnColumnSizes=(int*)malloc(sizeof(int)*10000); * returnColumnSizes[0]=0; *returnSize=1; dfs(nums,numsSize,returnSize,*returnColumnSizes,ans,temp,0,0); return ans; }
491. 递增子序列
中等
592
相关企业
给你一个整数数组
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
void backTrack(int* nums, int numsSize, int* returnSize, int** returnColumnSizes, int** returnNums,int *stack,int top, int index) { if (index > numsSize) { return; } if (top >= 2) { returnNums[*returnSize] = (int*)malloc(sizeof(int) * top); memcpy(returnNums[*returnSize], stack,sizeof(int) * top); (*returnColumnSizes)[*returnSize] = top; *returnSize = *returnSize + 1; } int i = index + 1; bool hashSet[201] = { 0 }; //去重 for (; i < numsSize; i++) { if (nums[i] >= nums[index] ) { if (hashSet[nums[i] + 100] == 0) { hashSet[nums[i] + 100] = 1; stack[top] = nums[i]; backTrack(nums, numsSize, returnSize, returnColumnSizes, returnNums, stack, top + 1, i); } } } } int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { *returnSize = 0; *returnColumnSizes = (int*) malloc(sizeof(int)* 32768); //2^15 int ** returnNums = (int**) malloc(sizeof(int*)* 32768); (*returnColumnSizes)[0] = 0; returnNums[0] = NULL; if (numsSize == 1) { return returnNums; } //用到栈 int* stack = (int*)malloc(sizeof(int) * numsSize); int i = 0; int hashSet[201] = { 0 }; //去重 for (i = 0; i < numsSize; i++) { if(hashSet[nums[i] + 100] == 0) { hashSet[nums[i] + 100] = 1; stack[0] = nums[i]; backTrack(nums, numsSize, returnSize, returnColumnSizes, returnNums, stack, 1, i); } } return returnNums; }
198. 打家劫舍
中等
2.4K
相关企业
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400通过次数
693.1K
提交次数
1.3M
通过率
54.2%
int rob(int* nums, int n){ int dp[n+2]; memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) dp[i+2]=fmax(dp[i+1],dp[i]+nums[i]); return dp[n+1]; }
