Predict the Winner
给一个数组, 两个人只能从两端取数, 求预测那个人能赢. 我就是dfs直接做的, 不过时间太大了. 我看到答案用的是贪婪算法, 选的人肯定选start和end中相对大的, 但是找到这个大的, 需要通过dfs.
|
1 2 3 4 5 6 7 8 |
public class Solution { public boolean PredictTheWinner(int[] nums) { return helper(nums, 0, nums.length-1)>=0; } private int helper(int[] nums, int s, int e){ return s==e ? nums[s] : Math.max(nums[e] - helper(nums, s, e-1), nums[s] - helper(nums, s+1, e)); } } |