怎样加入网站,python前端开发需要学哪些东西,开发一个网站要多久,网站做3儿童车开场动画子序列问题二 1.最长定差子序列2.最长的斐波那契子序列的长度3.最长等差数列4.等差数列划分 II - 子序列 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#xff0c;我们一起努力吧!#x1f603;收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1.最长定差子序列
题目链接 1218. 最长定差子序列
题目分析 给你一个整数数组 arr 和一个整数 difference请你找出并返回 arr 中最长等差子序列的长度该子序列中相邻元素之间的差等于 difference 。
算法原理 1.状态表示 经验 题目要求
dp[i] 表示以 i 位置的元素为结尾的所有子序列中最长的等差子序列的长度 2.状态转移方程 设 i 位置里面元素为a如果以 i 位置元素为结尾研究最长等差子序列的长度其实 i 位置前面那个元素已经确定了这道题和最长递增子序列是有区别的那道题 i 位置前面的元素是要从前往后遍历一遍的来找倒数第二个元素在哪里。这道题已经告诉我们相邻两个元素的差是diff我只要知道最后一个元素就能推出倒数第二个元素。设倒数第二个元素为b。 a - b diff — b diff - a。
根据 b 存不存在可以分两个情况
b不存在a本身就是
b存在因为是乱序的前面可能有很多元素等于b其实我们只需要考虑最后一个b元素的位置就可以了。因为我们想要的是以b元素为结尾的最长等差子序列的长度最后一个b元素所在位置dp[j1]里面的值至少大于等于前面以b元素为结尾最长等差子序列的长度。然后加上 i 位置的元素。 这里有个优化
虽然我们是可以从后往前遍历找到最后一个b元素所在的位置的但是我们可以这也做可以之间把 b 元素 和它对应的 dp[i] 放在hash表。就不用去遍历了可以O(1)的时间复杂度就找到。
将 元素 dp[j] 的值绑定放进哈希表中
甚至我们还可以将 a 元素 dp[i] 绑定放进哈希表。这样的话就不用要哈希表了。
直接在哈希表中做动态规划 3.初始化 我们只需要将以第0个位置元素为结尾子序列最长的等差子序列的长度初始化一下就行了反正没得选就是自己本身。
dp[arr[0]] 1 4.填表顺序 从左往右 5.返回值 我们要返回的是最长的等差子序列长度但是这个长度可能在dp表里任意一个位置因此返回 dp 表里面的最大值
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {// 创建 dp 表unordered_mapint,int hash; //arr[i] - dp[i]// 初始化hash[arr[0]] 1;//填表int ret 1;for(int i 1; i arr.size(); i){//hash[arr[i]]保证b是最新的值//hash[arr[i] - difference]保证如果不存在value是0hash[arr[i]] hash[arr[i] - difference] 1;ret max(ret,hash[arr[i]]);}return ret;}
};2.最长的斐波那契子序列的长度
题目链接 873. 最长的斐波那契子序列的长度
题目分析 满足斐波那契数列条件元素长度大于等于3还有从第三个元素开始每个元素都等于前两个元素的和如果序列满足这两个条件我们就称之为斐波那契数列。 注意这道题给的是严格递增不仅是递增的而且元素还是不重复的。填表的时候有优化的作用。
算法原理 1.状态表示 经验 题目要求
dp[i] 表示以 i 位置元素为结尾所有子序列中最长斐波那契数列子序列的长度
我们尝试用这个状态表示来看看能不能推导出来状态转移方程。
我们是 i 位置来划分问题的在 0 ~ i -1 任选一个位置 j 通过 j 位置的 dp[j] 来更新出 i 位置的dp[i]这是之前做子序列的方法。但是这道题就不行了。我们的状态表示只是表示出来最长斐波那契数列子序列的长度但是并不知道具体的斐波那契序列。其实如果我们知道最后两个位置的值nums[j]nums[i]我们是能推导出来在前面一个位置的。但是dp[j]根本不知道这个斐波那契数列是什么样。所有我们不能直接用dp[j]的值去更新dp[i]的值。所以上面的状态表示不对 通过刚才的分析我们发现如果在一个斐波那契数列知道最后两个元素其实是可以把前面所有的元素都推出来的。 … a-(b-a)b-aba。既然单独一个位置为结尾推不出来斐波那契子序列长什么样子但是如果能用两个元素为结尾就能推出斐波那契子序列长什么样子。一维解决不了问题在扩一维。
dp[i][j] 表示 以 i 位置以及 j 位置的元素为结尾的所有子序列中最长斐波那契子序列长度。 (i 位置 j 位置) 2.状态转移方程 如果我们以最后两个位置为结尾其实我们是可以直接知道倒数第三个数设倒数第三个数为 a a c - b设 a 的下标为 k 根据a可以分下面三种情况
a不存在a存在且baca存在且ab
a不存在根本构不成斐波那契子序列dp[i][j]本应该是0的但是dp[i][j] 表示以 ij位置为结尾至少有两个元素。所以给2。如果dp里面都是2说明没有都没有构成斐波那契子序列最后直接返回0就可以了。
a存在且baca虽然存在但是在bc中间不符合斐波那契数列所以也是给2。
a存在且ab我们要的是最长斐波那契子序列长度先把 k 位置元素拿出来在把 i 位置元素拿出来先找到以着两个位置元素为结尾的最长斐波那契子序列后面在加上一个j位置元素就可以了。 而以ki位置元素为结尾最长斐波那契子序列正好在dp[k][j]中然后再加上1 优化找a元素所在位置比较花时间因此我们将数组中所有元素与它们的下标绑定存在哈希表中。数组里面的元素是严格递增不会存在重复元素 3.初始化 表里面所有的值都初始化为2就不用考虑前面两种情况了。 但是细心的会发现不能把表里面的值都初始化为2dp[0][0] 相当于里面就一个元素里面的值就是1。其实我们在状态表示就已经规定好了 i j。对于这个二维dp表我们只会用到上半部分 4.填表顺序 从上到下从左到右 5.返回值 dp表里面的最大值 ret , ret 3 ? 0 : ret
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {int n arr.size();//优化unordered_mapint,int hash;for(int i 0; i n; i)hash[arr[i]] i;int ret 2;vectorvectorint dp(n,vectorint(n,2));for(int j 2; j n; j)// 固定最后⼀个位置{for(int i 1; i j; i) // 固定倒数第⼆个位置{int a arr[j] - arr[i];// 条件成⽴的情况下更新 if(a arr[i] hash.count(a))dp[i][j] dp[hash[a]][i] 1;ret max(ret,dp[i][j]);// 统计表中的最⼤值}}return ret 3 ? 0 : ret;}
};3.最长等差数列
题目链接 1027. 最长等差数列
题目分析 在数组中找一个子序列这个子序列要是最长的等差子序列返回长度。
算法原理 1.状态表示 经验 题目要求
dp[i] 表示以 i 位置元素为结尾的所有子序列中最长的等差序列的长度。
接下来以这个状态表示分析一下能推导出来状态转移方程说明这个状态表示是对的推导不出来说明这个状态表示是错的。
我想求 以 i 位置元素为结尾的 dp[i] 的值根据以往的经验 要去 0 ~ i - 1 位置找dp[j]去更新dp[i]但是这道题不行这道题要找的是 最长的等差序列的长度。而dp[i-1]表示以 i -1 位置元素为结尾的所有子序列中最长的等差序列的长度。我只知道长度并不知道等差子序列是什么这个 i 到底能不能跟在 j 后面是不知道的因此上面状态表示不对。
如果我们知道等差序列最后两个元素我们就知道把这个等差序列前面所有元素都推出来设倒数第一个位置是 a 倒数第二个位置是 b 倒数第三个位置为 xx 2*a-b。
因此我们的状态表示
dp[i][j] 表示以 i 位置以及 j 位置的元素为结尾的所有子序列中最长的等差序列的长度i j。 2.状态转移方程 设倒数第二个位置 i 位置元素为 b倒数第一个位置 j 位置元素为 a我们可以推出来倒数第三个位置 k 位置元素为 a 2b -c
根据倒数第三个 k 位置可以分为三种情况
a不存在a存在i k ja存在k i
a不存在以及a存在i k ja在bc中间单独bc就能构成等差子序列因此长度为2 a存在k ia b在i 位置左边但是这里又有很多种情况这个a可能有很多个。那这个时候我们需要把所有情况都考虑吗。其实不需要假设前面最长子序列是以a元素为结尾那最后一个a所在位置的长度至少大于等于前面的a的长度。所有我们只考虑离 i 位置最近的a就可以了。我们的 k 也表示的是左边离 i 位置最近的那个下标。 dp[i][j] 表示以 ij 为结尾的最长子序列的长度这个时候如果发现倒数第三个元素存在并且i左边是不是可以先找到以 ki 为结尾的最长的长度然后加一个 j 位置元素就行了而以 ki 为结尾的最长的长度正好就是 dp[k][i] 还没完有没有发现我们找下标k并不是O(1)的时间复杂度。本来dp[i][j] 时间复杂度就已经是O(N ^ 2)又来了一层循环时间复杂度就变成 O(N ^ 3)。
优化一下我们要找到的是离 i 位置最近a元素的下标
在 dp 之前将所有元素 下标绑定放在hash表中元素下标数组(适合数组中无重复元素)。但是如果这个数据非常恶心它会把下标数组搞得非常大时间复杂度依旧是O(N ^ 3)。 2.一边 dp一边保存离它最近的元素的下标元素下标(适合数组中有重复元素)。 这样就是O(1)时间复杂度。
选第二种方式写代码有技巧和填表顺序有关我们先分析下面的。 3.初始化 表里面所有的值都初始化为2就不用考虑前面两种情况了。 但是细心的会发现不能把表里面的值都初始化为2dp[0][0] 相当于里面就一个元素里面的值就是1。其实我们在状态表示就已经规定好了 i j。对于这个二维dp表我们只会用到上半部分 4.填表顺序 我们是以i j 位置为结尾填表也有两种方法
第一种
先固定倒数第一个数枚举倒数第二个数
先固定最后一个数 j枚举倒数第二个数也就是说 i 位置是从0 开始到 j - 1 。当 i 0 算一下 dp[i][j]当 i 1 算一下 dp[i][j] 。。。 第二种
先固定倒数第二个数枚举倒数第一个数
先固定 i让 j 从 i 1 位置开始往后枚举。 那我们选哪种策略呢回到优化一边 dp一边保存离它最近的元素的下标元素下标(适合数组中有重复元素)。 如果选择第一种策略会有一种问题i 位置是一直移动的那最近的元素也是在一直改变。很难保证是最近的。 所以我们选择第二种初始化方式。当我们固定 i 位置之后j是往后移动的。当把 i 位置填完之后ij都会往后移动我们就可以把i位置的元素存到hash表里。
所以我们选择第二种填表顺序当 i 位置填完之后将 i 位置的值放入到hash表中即可。 5.返回值 dp[i][j] 表示以 ij 为结尾的最长子序列的长度题目要求的是整个子序列中最长的那个。所以返回 dp 表中的最大值。
class Solution {
public:int longestArithSeqLength(vectorint nums) {//优化unordered_mapint,int hash;hash[nums[0]] 0;int n nums.size();vectorvectorint dp(n,vectorint(n,2));//创建 dp 表 初始化int ret 2;for(int i 1; i n - 1; i)//固定倒数第二个数{for(int j i 1; j n; j)//枚举倒数第一个数{int a 2 * nums[i] - nums[j];if(hash.count(a)){dp[i][j] dp[hash[a]][i] 1;ret max(ret,dp[i][j]);}}hash[nums[i]] i;}return ret;}
};4.等差数列划分 II - 子序列
题目链接 446. 等差数列划分 II - 子序列
题目分析 给你一个整数数组 nums 返回 nums 中所有 等差子序列 的数目。
如果一个序列中 至少有三个元素 并且任意两个相邻元素之差相同则称该序列为等差序列。
算法原理 1.状态表示 经验 题目要求
dp[i] 表示 以 i 位置元素为结尾的所有子序列中等差子序列的个数
接下来就以这个状态表示看看能不能分析出状态转移方程
以 i 位置元素为结尾的子序列根据前面的经验 有可能是自己本身有可能是前面 0 ~ i - 1 区间 dp[i - 1]dp[i - 2] … dp[0] 去更新dp[i]进而得到状态转移方程。dp[i - 1] 对应 i - 1 位置元素dp[i - 2] 对应 i - 2 位置元素… 。这道题我们要的是等差子序列要的是 i 位置跟在这些元素的后面我们的状态表示只是等差子序列的个数i 位置跟在前面元素后面形成等差子序列必须要是能跟才行。这个状态表示我们只知道子序列的个数但是不能确定一个具体的子序列。 因此这个状态表示不对。重新定义一个状态表示。我们如果等差子序列最后两个位置元素就可以把整个等差子序列推出来了。因此状态表示可以这样定义
dp[i][j] 表示以 i 位置的元素以及 j 位置的元素为结尾的所有子序列中等差子序列的个数i j。 2.状态转移方程 设倒数第二个位置 i 位置元素为b倒数第一个位置 j 位置元素为 c倒数第三个位置 k位置 元素为a a 2b - c
根据 a 可以分三种情况
a不存在a存在i k ja存在k i
a不存在a存在i k j 构不成等差子序列给0就行了
a存在k i但是这里又有很多种情况这个a可能有很多个。是全都都考虑还是只考虑最后一个位置的a呢注意我们这里要的是等差子序列的个数并不是最长等差子序列长度等等。bc可以和前面任意一个a构成等差子序列因此我们都要考虑。
dp[i][j] 表示以 ij 为结尾的等差子序列的个数这个时候如果发现倒数第三个元素存在并且i左边是不是可以先找到以 ki 为结尾的等差子序列个数然后加一个 j 位置元素就行了而以 kx i 为结尾的等差子序列个数正好就是 dp[kx][i]然后在加上 j 位置注意这里求的是个数因此 dp[i][j] dp[ki][i] 1 这里有个优化a可能是由重复的dp[i][j]时间复杂度是O(N ^ 2)如果在遍历去找a时间复杂度就是O(N ^ 3)了因此
在dp之前将元素下标数组绑定在一起放在哈希表中。 3.初始化 最差情况下就是 i j 位置元素为结尾不构成等差子序列所以可以把dp表里面所有的值都初始化为0 4.填表顺序 固定倒数第一个数枚举倒数第二个数 5.返回值 要的是等差子序列的个数因此返回 dp 表里面所有元素的和。
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();//优化unordered_maplong long,vectorint hash;for(int i 0; i n; i)hash[nums[i]].push_back(i);vectorvectorint dp(n,vectorint(n));//创建 dp 表 初始化int ret 0;for(int j 2; j n; j)// 固定倒数第⼀个数{for(int i 1; i j; i)// 枚举倒数第⼆个数{long long a (long long)2 * nums[i] - nums[j];//处理数据溢出if(hash.count(a)){for(auto k : hash[a]){if(k i)dp[i][j] dp[k][i] 1;elsebreak;}ret dp[i][j];}}}return ret;}
};
