首页 > 代码库 > 390. Elimination Game
390. Elimination Game
There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.
We keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Find the last number that remains starting with a list of length n.
Example:
Input:n = 9,1 2 3 4 5 6 7 8 92 4 6 82 66Output:6
这道题dp的方法如下，dp能比较好的显示思路
public int LastRemaining(int n) { if(n<=2) return n; if(n==3) return 2; var left = new int[n+1]; var right = new int[n+1]; left[1] = 1; right[1] = 1; left[2] = 2; right[2] = 1; for(int i= 3;i<=n;i++) { if(i%2 == 0) { left[i] = 2*right[i/2]; right[i] = 2*left[i/2]-1; } else { left[i] = 2*right[i/2]; right[i] = 2*left[i/2]; } } return left[n];}
然后DP需要的space太大了，所以这题适合用backtracking做
public int LastRemaining(int n) { return BackTracking(n,true); } private int BackTracking(int n, bool left) { if(n<=2) return left?n:1; if(n%2 == 0) return 2*BackTracking(n/2, !left)-(left?0:1); else return 2*BackTracking(n/2,!left); }
390. Elimination Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。