青岛装饰公司十强排名,网络优化的目的,四川建设厅网站打不开,做网站从哪方面入门文章目录1 题目理解2 开始思考1 题目理解
给你一个整数数组 arr 和一个整数 difference#xff0c;请你找出并返回 arr 中最长等差子序列的长度#xff0c;该子序列中相邻元素之间的差等于 difference 。 输入#xff1a;整数数组arr#xff0c; 整数difference 输出…
文章目录1 题目理解2 开始思考1 题目理解
给你一个整数数组 arr 和一个整数 difference请你找出并返回 arr 中最长等差子序列的长度该子序列中相邻元素之间的差等于 difference 。 输入整数数组arr 整数difference 输出最长等差子序列的长度 规则这个等差子序列相邻元素的差等于difference 示例 1 输入arr [1,2,3,4], difference 1 输出4 解释最长的等差子序列是 [1,2,3,4]。
示例 2 输入arr [1,3,5,7], difference 1 输出1 解释最长的等差子序列是任意单个元素。
示例 3 输入arr [1,5,7,8,5,3,4,2,1], difference -2 输出4 解释最长的等差子序列是 [7,5,3,1]。
2 开始思考
以arr [1,5,7,8,5,3,4,2,1], difference -2 为例。 处理1子序列是[1] 处理5因为5-1!-1所以产生子序列[5]此时子序列有[1],[5] 处理7因为7-5!-27-1!-2所以产生子序列[7]此时子序列有[1],[5][7] 处理8…此时子序列有[1],[5],[7],[8] 处理5因为5-8!-2,5-7-2,子序列变为[1],[5],[7,5],[8] … 所以发现在处理每一个数的时候和他前面已经形成的每个子序列的某位数字比较符合条件就可以追加不符合条件就单独成一个子序列。当然在追加的时候肯定要选择追加在最长的那个子序列后面。 当一个数追加到子序列之后后面的处理就只与这个数有关系而与子序列的具体序列无关所以可以使用dp。 用dp[i]表示以arr[i]结尾的等差子序列的最长长度。最后结果在dp[0],dp[1]…dp[n-1]之间选择最大的。
class Solution {public int longestSubsequence(int[] arr, int difference) {int n arr.length;int[] dp new int[n];dp[0] 1;int max 1;for(int i1;in;i){dp[i] 1;for(int j0;ji;j){if(arr[j] difference arr[i]){dp[i] Math.max(dp[i],1dp[j]);}}max Math.max(max,dp[i]);}return max;}
}提交之后发现超时。再一思考。当处理arr[i]的时候它等差子序列的前一个数值是确定的一定是arr[i]-difference。也就是说不需要关心从0到i-1每个子序列的最长长度只要关心以arr[i]-difference为结尾的等差子序列的长度即可。
class Solution {public int longestSubsequence(int[] arr, int difference) {int n arr.length;MapInteger,Integer map new HashMapInteger,Integer();int[] dp new int[n];dp[0] 1;map.put(arr[0],1);int max 1;for(int i1;in;i){dp[i] 1;int t arr[i] - difference;if(map.containsKey(t)){dp[i] Math.max(dp[i],map.get(t)1);}map.put(arr[i],dp[i]);max Math.max(max,dp[i]);}return max;}
}在做315 Count of Smaller Numbers After Self的时候因为没有考虑重复元素使用map出错了。所以现在有点犹豫可以这样吗当数值重复的时候会出错吗
还是上面的例子[1],[5],[7,5],[8]当处理数字3的时候3--25当然追加在[7,5]后面变成[7,5,3]。我们从左到右处理当map中有5的长度的时候5一定出现在3前面但是至于是什么位置的5并不关心也没有关系。因为子序列就不一定是连续的。 再从另外一个角度考虑。如果 arr[i-3] arr[i-1] arr[i] 是一个等差序列 那么当 arr[j]arr[i],并且 ji的时候那么 arr[i-3] arr[i-1] arr[j] 也一定是一个等差序列。而且 在i到j之间可能产生一个更长的等差序列数组。 所以map优化以arr[i]为key没有问题。
