西青做网站公司,wordpress通过微信投稿,淘客网站系统免费源码,北京小程序外包讀題
300.最长递增子序列
看完代码随想录之后的想法
思想上很簡單#xff0c;dp[i]表示i之前的包括i的numbers[i]節尾的最長上升子序列的長度
並且透過兩層迴圈#xff0c;一層遍歷全部#xff0c;一層遍歷到i#xff0c;透過比較當前dp[i]還是dp[j] 1哪個比較大…讀題
300.最长递增子序列
看完代码随想录之后的想法
思想上很簡單dp[i]表示i之前的包括i的numbers[i]節尾的最長上升子序列的長度
並且透過兩層迴圈一層遍歷全部一層遍歷到i透過比較當前dp[i]還是dp[j] 1哪個比較大來更新動態規劃的dp數組數據。
674. 最长连续递增序列
自己看到题目的第一想法
稍微將300轉一下就好dp[i] 改為到i之前的最長連續子序列長度為dp[i]公式轉為假設nums[i] nums[i - 1] 就將dp[i] 的值改為前一個值的個數 1就好了
718. 最长重复子数组
自己看到题目的第一想法
的確比較有難度要思考如何去找出重複子序列但是將nums1以及nums2的對應表畫出來後會發現可以透過左上角的值來看重複度假設左上角為1那就代表前一個num2的值與前一個num1的值相等所以當前的值如果也相等那就要基於dp[i - 1][j - 1]的值 1雖然這個想法完整了但是自己對於下標的定義沒有想的很清楚主要是透過畫圖模擬找出規律並推出遞推公式。
看完代码随想录之后的想法
看完之後發現卡哥的做法比較直覺一點但要想到比較難我的想法主要是透過畫圖推出而卡哥是直接在整體数組框架上往外擴一層就免除了我在nums1[i] ! nums2[j] 需要做的額外操作兩者都可以通過只是方法不同而已下標的定義也讓我之前比較模糊的定義有了清晰的了解。 300.最长递增子序列 - 實作
思路 定義DP數組以及下標的含意 dp[i] 代表 i 之前包含i 的number[i] 結尾的最大遞增子序列的長度是多少 遞推公式 透過兩層迴圈一個遍歷numbers.size的數組的長度一個遍歷到i的長度 if (number[i] number[j]) dp[i] max(dp[i], dp[j] 1) 根據遞推公式、題意以及定義確定DP數組如何初始化 每個數做為結尾都至少含有一個所以將數組初始化為1 確定遍歷順序 0 到 i 因為需要前面的數據來進行遍歷所以是由前往後。 0 到 i - 1 只要都有遍歷到就可以了往前或往後都沒有關係但為了方便理解默認由前往後
Code
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint dp (nums.size(), 1);int result 1;for(int i 1; i nums.size(); i ) {for(int j 0; j i; j) {if(nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}if(dp[i] result) result dp[i];}return result;}
};674. 最长连续递增序列 - 實作
思路 定義DP數組以及下標的含意 dp[i] 代表 i 之前包含i 的number[i] 結尾的最長連續遞增子序列的長度是多少 遞推公式 if (number[i] number[i - 1]) dp[i] dp[i - 1] 1; 假設number[i] number[i - 1] 代表number[i - 1]之前都是連續遞增的所以加上當前的數 如果沒有大於就維持初始化 根據遞推公式、題意以及定義確定DP數組如何初始化 每個數做為結尾都至少含有一個所以將數組初始化為1 確定遍歷順序 0 到 i 因為需要前面的數據來進行遍歷所以是由前往後。
Code
class Solution {
public:int findLengthOfLCIS(vectorint nums) {vectorint dp (nums.size(), 1);int result 1;for(int i 1; i nums.size(); i ) {if(nums[i] nums[i - 1]) dp[i] dp[i - 1] 1;if(dp[i] result) result dp[i];}return result;}
};718. 最长重复子数组 - 實作
思路 定義DP數組以及下標的含意 dp[i][j] 代表 0~ i 的nums1以及 0 ~ j 的nums2最長連續遞增子序列長度為dp[i][j] 遞推公式 if(nums1[i] nums2[j]) { if(i 0 j 0) dp[i][j] dp[i - 1][j - 1] 1; else dp[i][j] 1; } 假設nums1[i] nums[j] 其中一個不大於 0 則只加一如果都大於1 則看左上角的數 根據遞推公式、題意以及定義確定DP數組如何初始化 最少為0所以初始化為0 確定遍歷順序 因為需要左上角的數據來進行遍歷所以是由前往後。
Code
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp (nums1.size(), vectorint(nums2.size(), 0));int result 0;for(int i 0; i nums1.size(); i) {for(int j 0; j nums2.size(); j) {if(nums1[i] nums2[j]) {if(i 0 j 0) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] 1;}if(dp[i][j] result) result dp[i][j];}}return result;}
};總結
自己实现过程中遇到哪些困难
今天第一次做遞增子序列的題目一開始先看了題解後面就是一開始的題目轉換思路以及最長重複子数組則是用畫圖的方式推出解法。
今日收获记录一下自己的学习时长
今天大概學了2hr主要是理解子序列的做法該怎麼做。
相關資料
● 今日学习的文章链接和视频链接
300.最长递增子序列
视频讲解动态规划之子序列问题元素不连续| LeetCode300.最长递增子序列_哔哩哔哩_bilibili
https://programmercarl.com/0300.最长上升子序列.html
674. 最长连续递增序列
视频讲解动态规划之子序列问题重点在于连续| LeetCode674.最长连续递增序列_哔哩哔哩_bilibili
https://programmercarl.com/0674.最长连续递增序列.html
718. 最长重复子数组
视频讲解动态规划之子序列问题想清楚DP数组的定义 | LeetCode718.最长重复子数组_哔哩哔哩_bilibili
https://programmercarl.com/0718.最长重复子数组.html
