876. Middle of the Linked List
简单题，我的做法是先数下个数，然后知道中间节点是第几个了。
class Solution { public ListNode middleNode(ListNode head) { ListNode p = head; int cnt = 0; while (p != null) { cnt++; p = p.next; } cnt /=2; p = head; while (cnt>0) { p = p.next; cnt--; } return p; } }
877. Stone Game
这道题我用了记忆化搜索，用递归暴搜可能是能获取到正确结果的，但是直接的递归在重复计算好东西，所以我用dp数组把计算出来的结果保存起来，用的时候直接调取结果，可以减少递归树中重复的部分。
dp[i][j][0] 表示[i,j]区间Alice能取到的最优结果，dp[i][j][1]表示[i,j]区间Lee能取到最优的结果。
class Solution { int[][][] dp; public boolean stoneGame(int[] piles) { dp = new int[piles.length][piles.length][2]; int len = piles.length; int sum = 0; for (int i = 0; i < len; i++) { dp[i][i][0] = piles[i]; dp[i][i][1] = piles[i]; sum += piles[i]; } return help(0, len-1, 0, piles)> sum/2; } private int help(int i, int j, int pos, int[] piles) { if (dp[i][j][pos] != 0) { return dp[i][j][pos]; } int newpos = pos^1; dp[i][j][newpos] = Math.max(help(i+1, j, newpos, piles), help(i, j-1, newpos, piles)); dp[i][j][pos] = Math.max(help(i+1, j, newpos, piles)+piles[i+1], help(i, j-1, newpos, piles)+piles[j-1]); return dp[i][j][pos]; } }
878. Nth Magical Number
用容斥原理可以计算出一个数字Num之下有多少个A或B的倍数cnt，我们从最大值二分这个数字Num，拿cnt和N做比较来决定二分的走向，最终l和r肯定会收敛到一起，这就是我们要的结果了。
这道题的数值范围不是特别大 ，用long就可以完全满足需求了。
class Solution { private long gcd(long x, long y) { if (x%y == 0) return y; return gcd(y, x%y); } public int nthMagicalNumber(int N, int A, int B) { long C = 1l*A*B/gcd(A, B); long r = 1000000000l*40000*40000; long l = 0; while(l < r) { long mid = (l+r)/2; long cnt = mid/A + mid/B - mid/C; if (cnt < N) l = mid+1; else r = mid; } return (int) (l%1000000007); } }
