分类： leetcode

LCP24.数字游戏

目标

小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。

主办方请小扣回答出一个长度为 N 的数组，第 i 个元素(0 <= i < N)表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。

由于答案可能很大，请将每个最小操作数对 1,000,000,007 取余。

思路

老实说这道题我花了好一会儿才弄清楚题目要求，最后解法还因为超时没有通过。

先解释一下目标吧，实际上需要求解的是每一个位置上的局部最优解。所谓局部指仅考虑当前位置及之前的所有位置的操作次数。所谓最优是指初始序列达到满足条件的状态（公差为1的等差数列）时所做操作总和的最小值。如果有N个计数器，那么就有N个满足条件的序列，有可能前面操作最少的序列并不是后面操作最少的序列，即前面位置的总操作次数可能并不是当前最优解的一部分。可以参考上面图片的示例3。

我的思路就是直接暴力破解，循环遍历输入的数组，在第i次遍历中，分别将（0 ~ i-1）位置上的元素作为基点k，左侧的序列依次减1，右侧的依次加1。在第k个序列中求解（0 ~ i-1）位置上操作次数的累加和。在第j个位置上的操作次数为 nums[k]-(k-j)。

代码

public static int[] numsGame2(int[] nums) {
    int[] res = new int[nums.length];
    // 累加k序列的操作总和
    int[] acc = new int[nums.length];
    for (int i = 1; i < nums.length; i++) {
        for (int k = 0; k <= i; k++) {
            int temp = acc[k];
            // 增加一些判断跳过一些计算
            if(temp >= res[i] && res[i] != 0){
                continue;
            }
            // 这里看似套了3个循环，但其实只有在k序列第一次出现时才会循环i次，那么前面的i-1次只需从acc中累计即可，实际时间复杂度是O(n^2)
            for (int j = temp == 0 ? 0 : i; j <= i; j++) {
                temp += Math.abs(nums[j] - (nums[k] - (k - j)));
            }
            acc[k] = temp;
            if (k == 0) {
                res[i] = temp;
            } else {
                res[i] = Math.min(res[i], temp);
            }
        }
        res[i] = res[i] % 1000000007;
    }
    return res;
}
acc a b c d
acc[0] 0 |b-a-1| |c-a-2| |d-a-3\
acc[1] |a-b+1| 0 |c-b-1| |d-b-2\
acc[2] |a-c+2| |b-c+1| 0 |d-c-1\
acc[3] |a-d+3| |b-d+2| |c-d+1| 0

如上表所示，如果序列是[a,b,c,d]，基点k等于c的时候，前2次从acc累加，最后一次需要重新累加。时间复杂度为O(n^2)。这和我们常见的外层循环N次，内层循环N次不同。循环的计算次数序列为1、3、5、7...，根据等差数列求和公式：Sn = n × a1 + (n × (n-1)/2) × d，当 d=2，a1=1 时，Sn = n^2。

性能

由于题目给出的数组最大长度是10^5，暴力求解是不可行的。也尝试了增加条件判断跳过一些计算但还是无法降低问题的规模。于是就开始怀疑是否前面的计算结果是否与后面的计算有关联，可以简化后面的计算？更优的算法复杂度应为O(nlogn)、O(logn) 和 O(n)。我思考了很久，应该是存在知识盲区了。我去看了答案，涉及到求中位数。其实一开始有想过中位数，方差均值这些，但是没想到和这个最优解有什么关系。今天没时间了，抽空再看看吧。

106.从中序与后序遍历序列构造二叉树

目标

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路

有了前面 从前序与中序遍历序列构造二叉树 的经验这个问题就很好处理了。二叉树的后序遍历指先访问左子树、再访问右子树，最后访问根节点。

只需从后序序列的最后一个元素向前遍历即可，最后一个是根节点，接着是右子树、左子树的根节点 （注意这里是先右后左）。

还是在中序遍历中找到该根节点，然后其左侧的为左子树，右侧为右子树。依次递归遍历右子树与左子树，在递归方法中根节点取后序序列的前一个节点即可。

代码


/**
 * @date 2024-02-21 14:12
 */
public class BuildBinaryTreeFromMidPost {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

//    static int[] inorder = new int[]{9, 3, 15, 20, 7};
    static int[] inorder = new int[]{2,3,1};
//    static int[] inorder = new int[]{-1};

//    static int[] postorder = new int[]{9, 15, 7, 20, 3};
    static int[] postorder = new int[]{3,2,1};
//    static int[] postorder = new int[]{-1};

    static int postCursor = postorder.length - 1;

    public static void main(String[] args) {
        int rootIndex = 0;
        TreeNode root = new TreeNode(postorder[postCursor]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == postorder[postCursor]) {
                rootIndex = i;
                // 一定能够找到
                postCursor--;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        // 注意这个postCursor应该是共享变量，原先是想以参数传递的，但是发现递归的时候还要将它传回来，改成了共享变量
        // 这里是先遍历右子树再左子树
        if (rightStartIndex < inorder.length) {
            root.right = traverseSubTree(inorder, rightStartIndex, inorder.length);
        }
        if (leftEndIndex >= 0) {
            root.left = traverseSubTree(inorder, 0, leftEndIndex);
        }
        System.out.println(root);
    }

    public static TreeNode traverseSubTree(int[] inorder, int start, int end) {
        TreeNode subRoot = new TreeNode(postorder[postCursor]);
        int rootIndex = start;
        for (int i = start; i <= end; i++) {
            if (inorder[i] == postorder[postCursor]) {
                rootIndex = i;
                postCursor--;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        // 临界条件判断，这里应该是<=，并且排除掉inorder.length
        // 这里是先遍历右子树再左子树
        if (rightStartIndex <= end && rightStartIndex != inorder.length) {
            // 这里的结束条件传end
            subRoot.right = traverseSubTree(inorder, rightStartIndex, end);
        }
        if (leftEndIndex >= start) {
            subRoot.left = traverseSubTree(inorder, start, leftEndIndex);
        }
        return subRoot;
    }
}

性能

105.从前序与中序遍历序列构造二叉树

目标

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路

首先要明白先序遍历与中序遍历的概念。所谓二叉树的 先序遍历 指的是 先访问根节点，然后遍历左子树，再遍历右子树。中序遍历 则是 先遍历左子树，再根节点，然后右子树。

很容易想到使用递归，关键点是数组左右边界的维护，临界条件的判断。

注意到 先序遍历数组的第一个节点一定是根节点，其后面的节点则是其左子树或右子树的根节点。

于是先根据根节点在中序遍历中找到该根节点，然后其左侧的为左子树，右侧为右子树。依次递归遍历左子树与右子树（注意判断边界条件），在递归方法中根节点取刚才根节点的后一个节点（需要一个共享变量来记录位置）。

代码


/**
 * @date 2024-02-20 11:43
 */
public class BuildBinaryTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    static int[] preorder = new int[]{3, 9, 20, 15, 7};
//    static int[] preorder = new int[]{1,2,3};
//    static int[] preorder = new int[]{-1};

    static int[] inorder = new int[]{9, 3, 15, 20, 7};
//    static int[] inorder = new int[]{2,3,1};
//    static int[] inorder = new int[]{-1};

    static int preCursor = 0;

    public static void main(String[] args) {
        int rootIndex = 0;
        TreeNode root = new TreeNode(preorder[preCursor]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[preCursor]) {
                rootIndex = i;
                // 一定能够找到
                preCursor++;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        if (leftEndIndex >= 0) {
            root.left = traverseSubTree(inorder, 0, leftEndIndex);
        }
        // 注意这个preCursor应该是共享变量
        if (rightStartIndex < inorder.length) {
            root.right = traverseSubTree(inorder, rightStartIndex, inorder.length);
        }
        System.out.println(root);
    }

    public static TreeNode traverseSubTree(int[] inorder, int start, int end) {
        TreeNode subRoot = new TreeNode(preorder[preCursor]);
        int rootIndex = start;
        for (int i = start; i <= end; i++) {
            if (inorder[i] == preorder[preCursor]) {
                rootIndex = i;
                preCursor++;
                break;
            }
        }
        int leftEndIndex = rootIndex - 1;
        int rightStartIndex = rootIndex + 1;
        if (leftEndIndex >= start) {
            subRoot.left = traverseSubTree(inorder, start, leftEndIndex);
        }
        // 临界条件判断，这里应该是<=，并且排除掉inorder.length
        if (rightStartIndex <= end && rightStartIndex != inorder.length) {
            // 这里的结束条件传end
            subRoot.right = traverseSubTree(inorder, rightStartIndex, end);
        }
        return subRoot;
    }
}

性能

我的目标是能解决问题就好，看了下性能分布还有优化的空间，官网还给出了迭代的解法，没时间看。递归应该是更容易理解的方法了。希望能够坚持下去吧。