975. 奇偶跳 有序集合

975. 奇偶跳 有序集合

做题结果

成功，主要麻烦的地方在于怎么在存在相同值的情况下，同时可以找到在当前数右侧且索引最小

方法：有序集合

1. 不论如何，i

2. 每个值都可以作为初始位置 dp[i][1]+=1,到达以后，奇偶性交错累加。比如到达当前节点是奇数步，那再到达下一个点就是偶数步

3. 索引最小：floor，肯定会求到比当前值小，如果要求到最小索引，应该把小索引排在后面

4. 索引最大：celing:肯定会求到比当前值大，如果要求到最小索引，应该把小索引排在前面

5. 具体地，到达某点后从两个有序集合中移除当前节点，累计到下一个可累计的较大和较小值

class Solution { public int oddEvenJumps(int[] arr) { TreeSet set1 = new TreeSet<>((a,b)->arr[a]!=arr[b]?arr[a]-arr[b]:a-b); TreeSet set2 = new TreeSet<>((a,b)->arr[a]!=arr[b]?arr[a]-arr[b]:b-a); int n = arr.length; for(int i = 0; i < n; i++) { set1.add(i); set2.add(i); } int[][] dp = new int[n][2]; for(int i = 0; i < n; i++){ dp[i][1]+=1; set1.remove(i); set2.remove(i); Integer smaller = set2.floor(i); if(smaller!=null) dp[smaller][1]+=dp[i][0]; Integer bigger = set1.ceiling(i); if(bigger!=null) dp[bigger][0]+=dp[i][1]; } return dp[n-1][0]+dp[n-1][1]; }}

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