力扣84 双周赛 t4 6144 和力扣305周赛t4 6138

力扣84 双周赛 t4 6144 和力扣305周赛t4 6138

做题结果

失败，被自己乱写一个case卡死 [2,7,3]，第二个7的替换策略想不通

方法：贪心

1. 从后向前找

2. 如果比后面的大，就按后面的数字平分，看看能分几份，如果整除，后续数字不变，分成 part-1份（西瓜切两半只要一刀）

3. 如果不能整除，则尽可能地均分，增大开头的数字，由于没整除，多分出一份 next+1 份，尽可能平均让开头数字变大

class Solution { public long minimumReplacement(int[] nums) { int n = nums.length; long ans = 0L; int next = nums[n-1]; for(int i = n-2; i >= 0; i--){ if(nums[i]>next){ int part = nums[i]/next; if(nums[i]%next==0) { ans += part-1; }else{ ans += part; next = nums[i]/(part+1); } }else next = nums[i]; } return ans; }}

做题结果

成功，这题是中等，直接秒了

方法：动态规划

前一个范围 max(index-k) 到 min(index+k 25) 都可以延长一个到当前字母，选取里面最长的一个和自己相连，注意自己长度是1需要额外增加一个。

class Solution { public int longestIdealString(String s, int k) { int[] dp = new int[26]; int n = s.length(); int ans = 0; for(int i = 0; i < n; i++){ int v =0 ; int index = s.charAt(i)-'a'; for(int start = Math.max(index-k,0); start<=Math.min(index+k,25);start++){ v=Math.max(dp[start],v); } dp[index] = v+1; ans = Math.max(v+1,ans); } return ans; } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。