45. 跳跃游戏 II
中等
2K
相关企业
给定一个长度为
n的 0 索引整数数组nums。初始位置为nums[0]。每个元素
nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i + j]处:
0 <= j <= nums[i]i + j < n返回到达
nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1步，然后跳 3步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 题目保证可以到达
nums[n-1]
int jump(int* nums, int numsSize){ int *dp=(int *)malloc(sizeof(int)*numsSize); dp[0]=0; for(int i = 1 ; i < numsSize ; i++ ) { dp[i] = numsSize + 1; } for(int i =1; i< numsSize; i++) { for(int j = 0; j < i; j++) { if(j + nums[j] >= i) { dp[i] = fmin(dp[i],dp[j]+1); } } } return dp[numsSize-1]; }
97. 交错字符串
相关企业
给定三个字符串
s1、s2、s3，请你帮忙验证s3是否是由s1和s2交错 组成的。两个字符串
s和t交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交错 是
s1 + t1 + s2 + t2 + s3 + t3 + ...或者t1 + s1 + t2 + s2 + t3 + s3 + ...注意：
a + b意味着字符串a和b连接。示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true
提示：
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1、s2、和s3都由小写英文字母组成
bool isInterleave(char * s1, char * s2, char * s3){ int len1=strlen(s1),len2=strlen(s2),len3=strlen(s3),dp[105][105]={0}; if(len3!=(len1+len2)){ return false; } dp[0][0]=1; for(int i=0;i<=len1;i++){ for(int j=0;j<=len2;j++){ int p=i+j-1; if(i>0){ if(dp[i-1][j]==1&&s3[p]==s1[i-1]) dp[i][j]=1; } if(j>0){ if(dp[i][j-1]==1&&s3[p]==s2[j-1]) dp[i][j]=1; } } } return dp[len1][len2]; }
131. 分割回文串
中等
1.4K
相关企业
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是 回文串 。返回s所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组
int dp[20][20]={0}; void dfs(char* s, int len, int begin, char*** ans, int* returnSize, int* returnColumnSizes, char** temps, int* tempsSize) { if(begin==len){ char** tmp = malloc(sizeof(char*) * (*tempsSize)); for (int j = 0; j < (*tempsSize); j++) { int tempsColSize = strlen(temps[j]); tmp[j] = malloc(sizeof(char) * (tempsColSize + 1)); strcpy(tmp[j], temps[j]); } ans[*returnSize] = tmp; returnColumnSizes[(*returnSize)++] = *tempsSize; return; } for (int j = begin; j < len; ++j) { if (dp[begin][j]==1) { char* temp = malloc(sizeof(char) * (j - begin + 2)); for (int k = begin; k <= j; k++) { temp[k - begin] = s[k]; } temp[j - begin + 1] = '\0'; temps[(*tempsSize)++]=temp; dfs(s, len, j + 1, ans, returnSize, returnColumnSizes, temps, tempsSize); --*(tempsSize); } } } char*** partition(char* s, int* returnSize, int** returnColumnSizes) { int i,j,len=strlen(s); int retMaxLen = len * (1 << len); for(i=0;i<20;i++){ for(j=0;j<20;j++){ dp[i][j]=0; } } char*** ans = malloc(sizeof(char**) * retMaxLen); *returnSize = 0; *returnColumnSizes = malloc(sizeof(int) * retMaxLen); for(i=len-1;i>=0;i--){ for(j=i;j<len;j++){ if(s[i]==s[j]){ if(i==j) dp[i][j]=1; if(j-i==1){ dp[i][j]=1; } if(j-i>1){ if(dp[i+1][j-1]==1){ dp[i][j]=1; } } } } } char* temps[len]; int tempsSize=0; dfs(s, len, 0, ans, returnSize, *returnColumnSizes, temps, &tempsSize); return ans; }
139. 单词拆分
中等
1.9K
相关企业
给你一个字符串
s和一个字符串列表wordDict作为字典。请你判断是否可以利用字典中出现的单词拼接出s。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅有小写英文字母组成wordDict中的所有字符串 互不相同
bool wordBreak(char * s, char ** wordDict, int wordDictSize){ int len=strlen(s),falg=0; int dp[301]={0}; dp[0]=1; for(int i=0;i<len;i++){ for(int j=0;j<wordDictSize;j++){ int n=strlen(wordDict[j]); if(n>(len-i)){ continue; } falg=1; for(int k=0;k<n;k++){ if(s[i+k]!=wordDict[j][k]){ falg=0; } } if(falg==1&&dp[i]==1){ dp[i+n]=1; } } } if(dp[len]==1) return true; return false; }
221. 最大正方形
中等
1.4K
相关企业
在一个由
'0'和'1'组成的二维矩阵内，找到只包含'1'的最大正方形，并返回其面积。示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
正在上传…重新上传取消转存失败重新上传取消
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
输入：matrix = [["0"]]
输出：0
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]为'0'或'1'暴力超时：
int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){ int max=0; int m=matrixSize,n=matrixColSize[0]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]=='1'){ printf(" %d %d ",i,j); for(int b=1;i+b<=m&&j+b<=n;b++){ printf(" b=%d\n",b); int falg=1; for(int k=i;k<b+i;k++){ for(int l=j;l<j+b;l++){ if(matrix[k][l]!='1'){ falg=0; break; } } } if(falg==1){ if(max<b) { max=b; } } if(falg==0){ break; } } } } } return max*max; }
动态规划：
int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){ int max=0,dp[301][301]={0}; int m=matrixSize,n=matrixColSize[0]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]=='1'){ dp[i+1][j+1]=fmin(fmin(dp[i][j],dp[i][j+1]),fmin(dp[i][j],dp[i+1][j]))+1; } if(dp[i+1][j+1]>max){ max=dp[i+1][j+1]; } } } return max*max; }
279. 完全平方数
中等
1.6K
相关企业
给你一个整数
n，返回 和为n的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，
1、4、9和16都是完全平方数，而3和11不是。示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
int numSquares(int n) { int dp[n +1]; //定义dp的大小 dp[0] = 0; //定义dp的初始状态 int min; for(int i = 1 ; i <= n ; i++) { min = INT_MAX; for(int j = 1 ; j*j <= i;j++) { min = fmin(min, dp[i - j * j]); } dp[i] = min + 1; } return dp[n]; }
300. 最长递增子序列
中等
3K
相关企业
给你一个整数数组
nums，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，
[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
int lengthOfLIS(int* nums, int numsSize){ int dp[numsSize],max=0; for(int i=0;i<numsSize;i++){ dp[i]=1; for(int j=0;j<i;j++){ if(nums[i]>nums[j]){ dp[i]=fmax(dp[i],dp[j]+1); } } if(dp[i]>max){ max=dp[i]; } } return max; }
376. 摆动序列
中等
857
相关企业
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。- 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组
nums，返回nums中作为 摆动序列 的 最长子序列的长度 。示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000
int wiggleMaxLength(int* nums, int numsSize) { int up[numsSize]; memset(up,0,sizeof(int)*numsSize); up[0]=1; int down[numsSize]; memset(down,0,sizeof(int)*numsSize); down[0]=1; int max=0; for(int i=0;i<numsSize;i++){ for(int j=0;j<i;j++){ if(nums[i]>nums[j]){ down[i]=fmax(up[j]+1,down[i]); } if(nums[i]<nums[j]){ up[i]=fmax(down[j]+1,up[i]); } } if(up[i]>max){ max=up[i]; } if(down[i]>max){ max=down[i]; } } return max; }
