刷题记录｜目标101题--分治法

前段时间心情不好好久，今天开始还是要继续刷题之路啦！早日逃离互联网！

写在前面

开个贴记录一下刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

贪心算法：https://www.nowcoder.com/discuss/1051877
双指针：https://www.nowcoder.com/discuss/1057237
二分查找：https://www.nowcoder.com/discuss/1059986
排序：链接
搜索：链接
动态规划：https://www.nowcoder.com/discuss/1071676

分治法

曾经的我年少无知，也想要求证主定理，但是经过大量的挣扎，还是奉劝大家不要浪费这个时间了，需要很深的数学功底，而且面试也不可能会考，还是背住就vans了

No.1 Different Ways to Add Parentheses

题目链接：https://leetcode.com/problems/different-ways-to-add-parentheses/

解题思路：

将“+”“-”“*”看作是分割符号，分割出左右两边的表达式，递归求左右的数组，记录回来后进行算数操作，最后特殊处理没有算数符号的情况

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> list = new ArrayList<>();
        int n = expression.length();
        for (int i = 0; i < n; i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(expression.substring(0,i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1,n));
                for (int l = 0;l < left.size(); l++) {
                    for (int r = 0; r < right.size(); r++) {
                        if (c == '+') {
                            list.add(left.get(l) + right.get(r));
                        } else if (c == '*') {
                            list.add(left.get(l) * right.get(r));
                        } else {
                            list.add(left.get(l) - right.get(r));
                        }
                    }
                }
            }
        }
        if (list.size() == 0) list.add(Integer.parseInt(expression));
        return list;
    }
}

No.2 Beautiful Array

题目链接：https://leetcode.com/problems/beautiful-array/

解题思路：

这题确实好难理解，我看了好久都没能领会，这里也只是和大家分享我的思路历程。

一个 beautiful array 他的 2 *nums[i] 的 array 和 2 * nums[i] - 1 的 array 都是 beatiful array
2 * nums[k] != nums[i] + nums[j] 中 2 * nums[k] 为一个偶数，所以如果 nums[i] 和 nums[j]中一个为奇数一个为偶数，则这个式子就成立了。
综上，可以从1开始遍历，每次创建 2 * nums[i] 和 2* nums[i] - 1 的两个数组，将他俩相加，即可得到一个长度*2的 beatiful array，其中左边为 beatiful array，右边为 beatiful array，他俩接壤的部分，由于第二点一个为奇数，一个为偶数，所以也成立为 beautiful array

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(1);
        while (res.size() < n) {
            List<Integer> temp = new ArrayList<>();
            for (int i : res) {
                if (i * 2 - 1 <= n) 
                    temp.add(i * 2 - 1);
            }
            for (int i : res) {
                if (i * 2 <= n) 
                    temp.add(i * 2);
            }
            res = temp;
        }
        return res.stream().mapToInt(i -> i).toArray();
    }
}

No.3 Burst Balloons

题目链接：https://leetcode.com/problems/burst-balloons/

解题思路：

本题dp，如果令k为第一个被击中的气球，从而分为solve(nums,i,k -1)和solve(nums,k+1,j)，则面临k已经被击中，左右两边并不知道其相邻函数的到底谁被剩了下来，也就不知道应该✖️几，所以我们反向操作，令k为最后一个被击中的，则k一定是*1*1，左右两边也知道其面对的是1+left+nums[k]和nums[k]+right+1。

注意为了避免重复计算，最好用mem[i][j]数据将已经计算的存储下来，优化时间复杂度

class Solution {
    int[][] mem = new int[300][300];
    public int maxCoins(int[] nums) {
        for (int i = 0; i < 300; i ++) {
            Arrays.fill(mem[i], - 1);
        }
        return solve(nums,0,nums.length - 1);
    }
    private int solve(int[] nums, int i, int j) {
        if (i > j) return 0;
        if (mem[i][j] != -1) return mem[i][j];
        if (i == j) {
            int temp = nums[i];
            if (i - 1 >= 0) temp *= nums[i - 1];
            if (j + 1 < nums.length) temp *= nums[j + 1];
            return temp;
        }
        int ans = 0;
        for (int k = i; k <= j; k ++) {
            int temp = nums[k];
            if (i - 1 >= 0) temp *= nums[i - 1];
            if (j + 1 < nums.length) temp *= nums[j + 1];
            temp += solve(nums, i, k - 1) + solve(nums, k + 1, j);
            ans = Math.max(ans, temp);
        }
        mem[i][j] = ans;
        return ans;
    }
}