现在个人做网站或者app还有收益,公司简介简短,东莞黄页企业名录,如何做网站自适应45. 跳跃游戏 II 中等 2K 相关企业 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处: 0 j nums[i] i j 如果你在 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 len1strlen(s1),len2strlen(s2),len3strlen(s3),dp[105][105]{0};if(len3!(len1len2)){return false;}dp[0][0]1;for(int i0;ilen1;i){for(int j0;jlen2;j){int pij-1;if(i0){if(dp[i-1][j]1s3[p]s1[i-1])dp[i][j]1;}if(j0){if(dp[i][j-1]1s3[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(beginlen){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,lenstrlen(s);int retMaxLen len * (1 len);for(i0;i20;i){for(j0;j20;j){dp[i][j]0;}}char*** ans malloc(sizeof(char**) * retMaxLen);*returnSize 0;*returnColumnSizes malloc(sizeof(int) * retMaxLen);for(ilen-1;i0;i--){for(ji;jlen;j){if(s[i]s[j]){if(ij)dp[i][j]1;if(j-i1){dp[i][j]1;}if(j-i1){if(dp[i1][j-1]1){dp[i][j]1;}}}}}char* temps[len];int tempsSize0;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 lenstrlen(s),falg0;int dp[301]{0};dp[0]1;for(int i0;ilen;i){for(int j0;jwordDictSize;j){int nstrlen(wordDict[j]);if(n(len-i)){continue;}falg1;for(int k0;kn;k){if(s[ik]!wordDict[j][k]){falg0;}}if(falg1dp[i]1){dp[in]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 max0;int mmatrixSize,nmatrixColSize[0];for(int i0;im;i){for(int j0;jn;j){if(matrix[i][j]1){printf( %d %d ,i,j);for(int b1;ibmjbn;b){printf( b%d\n,b);int falg1;for(int ki;kbi;k){for(int lj;ljb;l){if(matrix[k][l]!1){falg0;break;}}}if(falg1){if(maxb){maxb;}}if(falg0){break;}}}}}return max*max;
} 动态规划 int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){int max0,dp[301][301]{0};int mmatrixSize,nmatrixColSize[0];for(int i0;im;i){for(int j0;jn;j){if(matrix[i][j]1){ dp[i1][j1]fmin(fmin(dp[i][j],dp[i][j1]),fmin(dp[i][j],dp[i1][j]))1;}if(dp[i1][j1]max){maxdp[i1][j1];}}}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],max0;for(int i0;inumsSize;i){dp[i]1;for(int j0;ji;j){if(nums[i]nums[j]){dp[i]fmax(dp[i],dp[j]1);}}if(dp[i]max){maxdp[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 max0;for(int i0;inumsSize;i){for(int j0;ji;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){maxup[i];}if(down[i]max){maxdown[i];}}return max;
}
