LeetCode 311-340

312. 戳气球

把nums数组扩充一下，首尾加一个数字1。
dp[i][j]代表开区间(i,j)所能获得硬币的最大数量。
边界：
(i,j)区间长度小于等于2时，能获得的硬币数为0。
转移方程：
遍历开区间内的所有值，记为k,k代表这个开区间(i,j)最后一个戳破的气球。
那么开区间(i,j)的收益就为dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]。
dp[i][j]等于所有的k取收益最大的一个。
区间长度从3开始遍历，直到区间长度达到数组长度。这样才能保证dp数组更新正确。
最后答案就为dp[0][nums.length-1]

class Solution {
    public int maxCoins(int[] nums) {
        int[] newNums = new int[nums.length + 2];
        newNums[0] = newNums[nums.length + 1] = 1;
        System.arraycopy(nums, 0, newNums, 1, nums.length);
        nums = newNums;
        int[][] dp = new int[nums.length][nums.length];
        for (int L = 3; L <= nums.length; L++) {
            for (int i = 0; i <= nums.length - L; i++) {
                int res = 0;
                int j = i + L - 1;
                for (int k = i + 1; k < j; k++) {
                    int left = dp[i][k];
                    int right = dp[k][j];
                    res = Math.max(res, left + nums[i] * nums[k] * nums[j] + right);
                }
                dp[i][j] = res;
            }
        }
        return dp[0][nums.length - 1];
    }
}

313. 超级丑数

多指针，思想和第264. 丑数 II一样。
pos[j]代表应该用丑数数组uglies中的第几个数去乘以质数数组primes中的第j个数。 初始pos[j]都等于0，每一轮遍历时，都先选出下一个最小的丑数，为了避免重复，需要把所有的uglies[pos[j]] * primes[j] 等于这个丑数的pos[j]进行加1。

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int k = primes.length;
        int[] uglies = new int[n], pos = new int[k];
        uglies[0] = 1;
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE, index = 0;
            for (int j = 0; j < k; j++) {
                if (uglies[pos[j]] * primes[j] < min) {
                    min = uglies[pos[j]] * primes[j];
                    index = j;
                }
            }
            for (int j = 0; j < k; j++) {
                if (min == uglies[pos[j]] * primes[j]) {
                    pos[j]++;
                }
            }
            uglies[i] = min;
        }
        return uglies[n - 1];
    }
}

315. 计算右侧小于当前元素的个数

暴力法，超时：

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    count++;
                }
            }
            res.add(count);
        }
        return res;
    }
}

树状数组：

316. 去除重复字母

先使用一个Map记录每一个字符最后出现的位置，使用一个Set记录某个字符是否在栈中。
遍历字符串，如果栈中没有这个字符，将它进栈，但是进栈之前还需要判断一下：
如果栈顶元素比它大，且栈顶元素之后还会出现，那么将栈顶元素出栈，Set中也要移除栈顶元素。
最后把所有元素出栈就是结果的倒序。

class Solution {
    public String removeDuplicateLetters(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Set<Character> isVisit = new HashSet<>();
        Map<Character, Integer> lastPos = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastPos.put(s.charAt(i), i);
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!isVisit.contains(c)) {
                while (!stack.isEmpty() && c < stack.peek() && lastPos.get(stack.peek()) > i) {
                    isVisit.remove(stack.pop());
                }
                isVisit.add(c);
                stack.push(c);
            }
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.append(stack.pop());
        }
        res.reverse();
        return res.toString();
    }
}

318. 最大单词长度乘积

class Solution {
    public int maxProduct(String[] words) {
        Arrays.sort(words, (o1, o2) -> o2.length() - o1.length());
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            Set<Character> set = new HashSet<>();
            for (char c : words[i].toCharArray()) {
                set.add(c);
            }
            for (int j = i + 1; j < words.length; j++) {
                boolean flag = true;
                for (char c : words[j].toCharArray()) {
                    if (set.contains(c)) {
                        flag = false;
                        break;
                    }
                }
                if (flag == true) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}

319. 灯泡开关

数学题，找规律，只有是完全平方的数最后是亮着的，1到n中完全平方的个数就等于 sqrt(n)向下取整。

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n * 1.0);
    }
}

322. 零钱兑换

回溯，超时：

class Solution {
    int res = Integer.MAX_VALUE;
    List<Integer> temp = new ArrayList<>();

    private void dfs(int begin, int[] coins, int amount) {
        if (begin > coins.length || amount < 0) {
            return;
        }
        if (amount == 0) {
            res = Math.min(res, temp.size());
            return;
        }
        for (int i = begin; i < coins.length; i++) {
            temp.add(coins[i]);
            dfs(i, coins, amount - coins[i]);
            temp.remove(temp.size() - 1);
        }
    }

    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int i = 0, j = coins.length - 1;
        while (i < j) {
            int temp = coins[i];
            coins[i] = coins[j];
            coins[j] = temp;
            i++;
            j--;
        }
        dfs(0, coins, amount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

动态规划：
dp[i]代表凑出金额为i所需最少的硬币数。 初始都赋为amount+1 ，如果最终dp[i]的值是amount+1，说明无法凑出。
边界:
dp[0] = 0
转移方程：
从所有硬币中选择一个硬币j，只要这个硬币j的金额小于等于i，dp[i]就等于dp[i-coins[j]] + 1。 遍历所有的硬币，dp[i]等于其中最小的那个。

最终答案就是dp[amount]。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

324. 摆动排序 II

先排序，然后左半部分和右半部分交叉填入结果中，为了保证答案正确，左边每次要先选最大的，右边每次也要先选最大的。

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int i = (int) Math.ceil(nums.length / 2.0) - 1, j = nums.length - 1;
        int[] res = new int[nums.length];
        int pos = 0;
        while (pos != nums.length) {
            res[pos++] = nums[i--];
            if (pos == nums.length) {
                break;
            }
            res[pos++] = nums[j--];
        }
        for (int k = 0; k < nums.length; k++) {
            nums[k] = res[k];
        }
    }
}

326. 3的幂

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

327. 区间和的个数

前缀和暴力法：

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] pre = new long[nums.length];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            pre[i] = (i - 1 >= 0 ? pre[i - 1] : 0) + nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (pre[j] - (i - 1 >= 0 ? pre[i - 1] : 0) >= lower &&
                        pre[j] - (i - 1 >= 0 ? pre[i - 1] : 0) <= upper) {
                    res++;
                }
            }
        }
        return res;
    }
}

树状数组：

328. 奇偶链表

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode evenHead = head.next;
        ListNode curOdd = head, curEven = evenHead;
        while (curEven != null && curEven.next != null) {
            curOdd.next = curEven.next;
            curEven.next = curEven.next.next;
            curOdd = curOdd.next;
            curEven = curEven.next;
        }
        curOdd.next = evenHead;
        return head;
    }
}

329. 矩阵中的最长递增路径

dfs 超时：

class Solution {
    int res = 1;
    List<Integer> temp = new ArrayList<>();
    boolean[][] isVisit;
    int[] X = {1, -1, 0, 0}, Y = {0, 0, 1, -1};

    private void dfs(int i, int j, int[][] matrix) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || isVisit[i][j] == true) {
            return;
        }
        if (temp.size() > 0 && matrix[i][j] <= temp.get(temp.size() - 1)) {
            res = Math.max(res, temp.size());
            return;
        }
        temp.add(matrix[i][j]);
        res = Math.max(res, temp.size());
        isVisit[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int newI = i + X[k], newJ = j + Y[k];
            dfs(newI, newJ, matrix);
        }
        temp.remove(temp.size() - 1);
        isVisit[i][j] = false;
    }

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        isVisit = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dfs(i, j, matrix);
            }
        }
        return res;
    }
}

记忆化dfs：

class Solution {
    int[][] dp;
    int[] X = {0, 0, 1, -1}, Y = {1, -1, 0, 0};

    private int dfs(int i, int j, int[][] matrix) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        dp[i][j]++;
        for (int k = 0; k < 4; k++) {
            int newI = i + X[k], newJ = j + Y[k];
            if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length && matrix[newI][newJ] > matrix[i][j]) {
                dp[i][j] = Math.max(dp[i][j], dfs(newI, newJ, matrix) + 1);
            }
        }
        return dp[i][j];
    }

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int row = matrix.length, col = matrix[0].length;
        dp = new int[row][col];
        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                res = Math.max(res, dfs(i, j, matrix));
            }
        }
        return res;
    }
}

330. 按要求补齐数组

public class Solution {
    public int minPatches(int[] nums, int n) {
        int res = 0, i = 0;
        long miss = 1;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss += miss;
                res++;
            }
        }
        return res;
    }
}

331. 验证二叉树的前序序列化

class Solution {
    public boolean isValidSerialization(String preorder) {
        int slots = 1;
        String[] split = preorder.split(",");
        for (String s : split) {
            slots--;
            if (slots < 0) {
                return false;
            }
            if (!"#".equals(s)) {
                slots += 2;
            }
        }
        return slots == 0;
    }
}

332. 重新安排行程

通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。
通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的无向图称为欧拉图。
具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。

本题是欧拉图或半欧拉图。使用优先队列贪心的每次往字典序更小的结点进行dfs，直到没有新的到达为止，就把这个结点加入到结果中。最后的答案是将res反转得到。

class Solution {
    Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    List<String> res = new LinkedList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String from = ticket.get(0), to = ticket.get(1);
            if (!map.containsKey(from)) {
                map.put(from, new PriorityQueue<String>());
            }
            map.get(from).offer(to);
        }
        dfs("JFK");
        Collections.reverse(res);
        return res;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        res.add(curr);
    }
}

334. 递增的三元子序列

a 始终记录最小元素，b 为某个子序列里第二大的数。
接下来不断更新 a，同时保持 b 尽可能的小。
如果下一个元素比 b 大，说明找到了三元组。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE;
        for (int i : nums) {
            if (i <= a) {
                a = i;
            } else if (i <= b) {
                b = i;
            } else {
                return true;
            }
        }
        return false;
    }
}

336. 回文对

暴力法，超时：

class Solution {
    private boolean isPar(String str) {
        if ("".equals(str)) {
            return true;
        }
        int i = 0, j = str.length() - 1;
        while (i < j) {
            if (str.charAt(i++) != str.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (isPar(words[i] + words[j])) {
                    res.add(Arrays.asList(i, j));
                }
                if (isPar(words[j] + words[i])) {
                    res.add(Arrays.asList(j, i));
                }
            }
        }
        return res;
    }
}

337. 打家劫舍 III

树形dp：
dp[0]代表偷当前结点的最大金额，dp[1]代表不偷当前结点的最大金额。
采取后序遍历，这样当到达根结点时，就已经知道左右子结点的信息了。

如果不偷当前结点,dp[0]等于左子树的最大金额加上右子树的最大金额。
如果偷当前结点,dp[1]等于当前结点金额加上左子树不偷的金额加上右子树不偷的金额。

class Solution {
    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int[] dp = new int[2];
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        dp[1] = left[0] + right[0] + root.val;
        return dp;
    }

    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
}

338. 比特位计数

n & (n-1)能把n中最低位的1变成0，其它位不变。
这样就很快计算出n中1的个数。

class Solution {
    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            res[i] = count(i);
        }
        return res;
    }

    private int count(int n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= n - 1;
        }
        return sum;
    }

}