Leetcode contests 95 题解

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;
    }
}

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];
    }
}

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);
    }
}