其他:

今日總結
往期打卡

---

300. 最長遞增子序列

跳轉: 300. 最長遞增子序列

學習: 代碼隨想錄公開講解

問題:

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

子序列 是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

思路:

dp[i]代表長度為n的串中末尾值,如果下一個數大于當前最大長度情況下的末尾值,就說明可以再加一個數.不然就看看是否更新其他位置,更新的原則是盡量讓每個位置的值都更小.

要保證這個"插入位置"是比最后一個末尾比當前小的位置的下一個.
查詢位置的過程可以使用二分查找降低復雜度到logn

復雜度:

• 時間復雜度: $O(nlogn)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];int count = 0;for(int i:nums){int left = -1,right = count;while(left+1<right){int mid = (left+right)/2; if(dp[mid]>=i){right = mid;}else left = mid;}dp[right] = i;if(right==count) count++;}return count;}
}

---

674. 最長連續遞增序列

跳轉: 674. 最長連續遞增序列

學習: 代碼隨想錄公開講解

問題:

給定一個未經排序的整數數組，找到最長且 連續遞增的子序列，并返回該序列的長度。

連續遞增的子序列 可以由兩個下標 l 和 r（l < r）確定，如果對于每個 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續遞增子序列。

思路:

如果遞增就+1,不然就歸零,統計歷史最大值.
因為還要加上當前值,所以每次歸零初始化為1.
可以看成條件遞推,如果遞增dp[i] = dp[i-1]+1;

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution {public int findLengthOfLCIS(int[] nums) {int ans = 1;int num = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1])num++;else {if (num > ans)ans = num;num = 1;}}return Math.max(ans, num);}
}

---

718. 最長重復子數組

跳轉: 718. 最長重復子數組

學習: 代碼隨想錄公開講解

問題:

給兩個整數數組 nums1 和 nums2 ，返回 兩個數組中 公共的 、長度最長的子數組的長度 。

思路:

順序遍歷一個數組,逆序找結尾看看能否匹配上次匹配到的部分
(為了防止基于當前更新過的匹配,所以需要逆序,因為是子數組,要保證連續,所以到位置不匹配及時覆蓋為0)
動態規劃就是

if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
}

復雜度:

• 時間復雜度: $O(nm)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public int findLength(int[] nums1, int[] nums2) {int ans = 0;int m = nums1.length;int n = nums2.length;int[] fn = new int[n+1];for (int i = 0; i < m; i++)for (int j = n - 1; j >= 0; j--) {fn[j + 1] = nums1[i] == nums2[j] ? fn[j] + 1 : 0;ans = Math.max(ans, fn[j + 1]);}return ans;}
}

---

2918. 數組的最小相等和(每日一題)

跳轉: 2918. 數組的最小相等和

問題:

給你兩個由正整數和 0 組成的數組 nums1 和 nums2 。

你必須將兩個數組中的 所有 0 替換為 嚴格 正整數，并且滿足兩個數組中所有元素的和 相等 。

返回 最小 相等和 ，如果無法使兩數組相等，則返回 -1 。

思路:

0可以變成任意值,只要都有0就一定能一樣,只有在算上0變1小的一方沒有0的情況下才無解.
解就是0算作1加起來的最大那個和.

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution {public long minSum(int[] nums1, int[] nums2) {long n=0,m=0;boolean a,b;a=b=true;for (int i : nums1) {if (i > 0)n += i;else{n++;a=false;}}for (int i : nums2) {if (i > 0)m += i;else{m++;b=false;}}if(m>n&&a||m<n&&b){return -1;}else return Math.max(m,n);}
}

---

總結

練習了遞增子序列,連續遞增子序列,公共子序列問題.

往期打卡

代碼隨想錄算法訓練營第三十五&三十六天

代碼隨想錄算法訓練營第三十四天

代碼隨想錄算法訓練營第三十三天(補)

代碼隨想錄算法訓練營第三十二天

代碼隨想錄算法訓練營第三十一天

代碼隨想錄算法訓練營第三十天(補)

代碼隨想錄算法訓練營第二十九天

代碼隨想錄算法訓練營第二十八天

代碼隨想錄算法訓練營第二十七天(補)

代碼隨想錄算法訓練營第二十六天

代碼隨想錄算法訓練營第二十五天

代碼隨想錄算法訓練營第二十四天

代碼隨想錄算法訓練營第二十三天

代碼隨想錄算法訓練營周末四

代碼隨想錄算法訓練營第二十二天(補)

代碼隨想錄算法訓練營第二十一天

代碼隨想錄算法訓練營第二十天

代碼隨想錄算法訓練營第十九天

代碼隨想錄算法訓練營第十八天

代碼隨想錄算法訓練營第十七天

代碼隨想錄算法訓練營周末三

代碼隨想錄算法訓練營第十六天

代碼隨想錄算法訓練營第十五天

代碼隨想錄算法訓練營第十四天

代碼隨想錄算法訓練營第十三天

代碼隨想錄算法訓練營第十二天

代碼隨想錄算法訓練營第十一天

代碼隨想錄算法訓練營周末二

代碼隨想錄算法訓練營第十天

代碼隨想錄算法訓練營第九天

代碼隨想錄算法訓練營第八天

代碼隨想錄算法訓練營第七天

代碼隨想錄算法訓練營第六天

代碼隨想錄算法訓練營第五天

代碼隨想錄算法訓練營周末一

代碼隨想錄算法訓練營第四天

代碼隨想錄算法訓練營第三天

代碼隨想錄算法訓練營第二天

代碼隨想錄算法訓練營第一天