网站建立明细预计表,浙江网站建设外贸,六安网站制作多少钱,阿里云官网登陆入口一、子序列/子数组问题 子序列#xff1a;按原数组的顺序排列#xff0c;不一定是原数组中的相邻元素组成的。即子序列可以是不连续的。 子数组#xff1a;原数组中连续的几个元素组成的数组。 1. 300【最长递增子序列】
题目#xff1a; 给你一个整数数组 nums #xff…一、子序列/子数组问题 子序列按原数组的顺序排列不一定是原数组中的相邻元素组成的。即子序列可以是不连续的。 子数组原数组中连续的几个元素组成的数组。 1. 300【最长递增子序列】
题目 给你一个整数数组 nums 找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。代码
class Solution {public int lengthOfLIS(int[] nums) {//dp表示以数组中第i个元素为结尾的最长严格递增子序列的长度//dp[i] max(dp[j])1,其中nums[j]是nums[i]左边小于nums[i]的元素//dp[0] 1int[] dp new int [nums.length];dp[0] 1;int max 1;for(int i1;inums.length;i){int tmp 0;for(int j0;ji;j){if(nums[j]nums[i]){tmp Math.max(tmp,dp[j]);}}dp[i] tmp 1;max Math.max(dp[i],max);}return max;}
}2. 72【编辑距离】
题目 给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作 插入一个字符删除一个字符替换一个字符 代码
class Solution {public int minDistance(String word1, String word2) {//两个字符串的操作使用双指针i指向word1j指向word2//dp[i][j]表示由左向右操作到word1的第i个位置word2的第j个位置需要的最少操作数。//dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]1)//dp[0][j] j,dp[i][0] iint m word1.length();int n word2.length();if(n0) return m;if(m0) return n;int[][] dp new int [m1][n1];for(int i0;im;i){dp[i][0] i;}for(int i0;in;i){dp[0][i] i;}for(int i1;im;i){for(int j1;jn;j){if(word1.charAt(i-1)word2.charAt(j-1)){dp[i][j] dp[i-1][j-1];}else{dp[i][j] minDp(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])1;}}}return dp[m][n];}public int minDp(int a,int b,int c){int tmp Math.min(a,b);tmp Math.min(tmp,c);return tmp;}
}3. 53【最大子数组的和】
题目 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组是数组中的一个连续部分。代码
class Solution {public int maxSubArray(int[] nums) {//dp[i]表示以nums[i]为结尾的最大子数组的和//dp[i] max(dp[i-1]nums[i],nums[i])//dp[0] nums[0]int[] dp new int [nums.length];dp[0] nums[0];int max nums[0];for(int i1;inums.length;i){dp[i] Math.max(dp[i-1]nums[i],nums[i]);max Math.max(dp[i],max);}return max;}
}4. 674【最长连续自增序列】
题目 给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。代码
//方法一双指针
class Solution {public int findLengthOfLCIS(int[] nums) {//双指针法固定左指针移动右指针//直到右指针所指元素不满足条件,将左指针指向右指针int i0;int max 1;for(int j1;jnums.length;j){if(nums[j-1]nums[j]){max Math.max(max,j-i1);}else{i j;}}return max;}
}
//方法二动态规划
class Solution {public int findLengthOfLCIS(int[] nums) {//dp[i]表示以第i个元素结尾的最长连续递增子序列的长度//dp[i]1 or dp[i-1]1//dp[0]1int[] dp new int[nums.length];dp[0] 1;int max1;for(int i1;inums.length;i){if(nums[i-1]nums[i]){dp[i] dp[i-1]1;}else{dp[i] 1;}max Math.max(max,dp[i]);}return max;}
}5. 718【最长重复子数组】
题目 给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度。代码
class Solution {public int findLength(int[] nums1, int[] nums2) {//dp[i][j]表示以nums1[i],nums2[j]结尾的最长的公共子数组长度//dp[i][j] dp[i-1][j-1]1 (nums1[i]nums2[j])//dp[0][0] 0(nums1[i-1]!nums2[j-1]) or 1(nums1[i-1]nums2[j-1])int n nums1.length;int m nums2.length;int[][] dp new int[n][m];int max0;for(int i0;in;i){if(nums1[i]!nums2[0]){dp[i][0] 0;}else{dp[i][0] 1;}max Math.max(dp[i][0],max);}for(int i0;im;i){if(nums1[0]!nums2[i]){dp[0][i] 0;}else{dp[0][i] 1;}max Math.max(dp[0][i],max);}for(int i1;in;i){for(int j1;jm;j){if(nums1[i] nums2[j]){dp[i][j] dp[i-1][j-1]1;}else{dp[i][j] 0;}max Math.max(dp[i][j],max);}}return max;}
}6. 1143【最长公共子序列】
题目 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。 一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。 例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。代码
class Solution {public int longestCommonSubsequence(String text1, String text2) {//dp[i][j]表示以text1[i],text2[j]为结尾的最长公共子序列长度//dp[i][j] dp[i-1][j-1]1(text1[i]text2[j]) or//dp[i][j] max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])//dp[i][0] 0(text1[0]!text2[0]) or 1(text1[0]text2[0])//dp[0][i] 0(text1[0]!text2[0]) or 1(text1[0]text2[0])int n text1.length();int m text2.length();int[][] dp new int[n][m];boolean flag false;for(int i0;in;i){if((text1.charAt(i) text2.charAt(0))||flagtrue){dp[i][0] 1;flag true;}else {dp[i][0] 0;}}int max0;if(flag){max 1;}flag false;for(int i0;im;i){if((text1.charAt(0)text2.charAt(i))||flagtrue){dp[0][i] 1;flag true;}else{dp[0][i] 0;} }for(int i1;in;i){for(int j1;jm;j){if(text1.charAt(i) text2.charAt(j)){dp[i][j] dp[i-1][j-1]1;}else{dp[i][j] maxNum(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);}max Math.max(max,dp[i][j]);}}return max;}public int maxNum(int a,int b,int c){int tmp Math.max(a,b);return Math.max(tmp,c);}
}7. 647【回文子串】
题目 给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。代码
class Solution {public int countSubstrings(String s) {//dp[i][j]表示在substring(i,j1)是否是回文串//dp[i][j] true(s[i]s[j]) or false(s[i]!s[j])//因为i由i1决定j由j-1决定所以需要从左下角开始遍历//dp[][0]false or true,dp[n-1][]false or trueint n s.length();boolean[][] dp new boolean[n][n];int ans 0;for(int in-1;i0;i--){for(int ji;jn;j){if(s.charAt(i)s.charAt(j)){if(j-i1){dp[i][j] true;ans;}else if(dp[i1][j-1]){dp[i][j] true;ans;}}}}return ans;}
}8. 5【最长回文子串】
题目 给你一个字符串 s找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。代码
class Solution {public String longestPalindrome(String s) {//dp[i][j]表示substring(i,j1)是否是回文串//dp[i][j] true(s[i]s[j]) or false(s[i]!s[j])//dp[i][j] true(s[i]s[j] and j-i1 or dp[i1][j-1])int n s.length();boolean[][] dp new boolean[n][n];int maxLen 0;int index 0;for(int in-1;i0;i--){for(int ji;jn;j){if(s.charAt(i) s.charAt(j)){if(j-i1){dp[i][j] true;}else if(dp[i1][j-1]){dp[i][j] true;}if(dp[i][j] (maxLen j-i1)){maxLen j-i1;index i;}}}}return s.substring(index,indexmaxLen);}
}
