草稿圖網站
java的Deque

Leetcode 300. 最長遞增子序列

題目：300. 最長遞增子序列
解析：代碼隨想錄解析

解題思路

dp數組的含義是以該元素為結尾的最大長度是多少，并使max來記錄答案

代碼

class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;int []dp = new int[n];int max = 1;Arrays.fill(dp, 1);for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i])dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(dp[i], max);}return max;}
}

總結

暫無

Leetcode 674. 最長連續遞增序列

題目：674. 最長連續遞增序列
解析：代碼隨想錄解析

解題思路

和第300題的區別是，每次只要判斷與前一個的對比

代碼

class Solution {public int findLengthOfLCIS(int[] nums) {int n = nums.length;int []dp = new int[n];int max = 1;Arrays.fill(dp, 1);for (int i = 1; i < n; i++) {if (nums[i-1] < nums[i])dp[i] = Math.max(dp[i], dp[i-1] + 1);max = Math.max(dp[i], max);}return max;}
}

總結

暫無

Leetcode 718. 最長重復子數組

題目：718. 最長重復子數組
解析：代碼隨想錄解析

解題思路

使用二維數組，如果nums1的第i-1個元素和第nums2的第i-2個元素如果相同，則使匹配數dp[i][j]等于dp[i-1][j-1] + 1

代碼

class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int [][]dp = new int[nums1.length+1][nums2.length+1];for (int i = 1; i <= nums1.length; i++) {for (int j = 1; j <= nums2.length; j++) {if (nums1[i-1] == nums2[j-1])dp[i][j] = dp[i-1][j-1] + 1;result = Math.max(result, dp[i][j]);}}return result;}
}//滾動數組
class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int []dp = new int[nums2.length+1];for (int i = 1; i <= nums1.length; i++) {for (int j = nums2.length; j > 0; j--) {if (nums1[i-1] == nums2[j-1])dp[j] = dp[j-1] + 1;elsedp[j] = 0;result = Math.max(result, dp[j]);}}return result;}
}

總結

暫無