LeetCode 第132场周赛

除数博弈

题目描述

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

示例 1：

1
2
3

输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

1
2
3

输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

1 <= N <= 1000

思路

可以使用动态规范的方式。

N能否胜利取决于N-factor，假如存在一个factor，如果N-factor时候爱丽丝无法取胜，那么爱丽丝可以选择factor，这样对手无法取胜，自己可以取得胜利。如果不存在这样的factor，则爱丽丝选择任何数都无法取胜。

代码

public class P1025 {
    public boolean divisorGame(int N) {
        boolean[] winArray = new boolean[N + 1];
        winArray[1] = false;
        for (int i = 2; i <= N; i++) {
            if (!winArray[i - 1]) {
                winArray[i] = true;
            } else {
                for (int j = 2; j * j <= i; j++) {
                    if (N % j == 0) {
                        int factor1 = j, factor2 = N / j;
                        if (!winArray[N - factor1] || !winArray[N - factor2]) {
                            winArray[i] = true;
                            break;
                        }
                    }
                }
                winArray[i] = false;
            }
        }
        return winArray[N];
    }

}

扩展

其实上述方法并不是最优的。

其实可以证明出来该问题有通项公式。

证明有点类似于巴什博奕：

巴什博奕

两个聪明人玩游戏，有n个石子，每人可以随便拿1~m个石子，谁拿空谁就获胜。问谁会胜利？

分析
假如石子有1~m个，那么先手必胜。

假如石子有m+1个，先手无论拿多少，后手都可以拿完，先手必败。

假如石子有m+2~2m个，先手可以拿剩下m+1个，先手必胜。

使用数学归纳法：

当石子的数量为 n = k * (m + 1) + r（r > 0 && r < m + 1），先手会拿走r个，假如后手拿走x个，先手会拿走m + 1 - x个，先手必胜。

当石子的数量为n = k * (m + 1)时候，同理可知先手必败。

最终，当N是偶数时候，结果是true，否则为false。

节点与其祖先之间的最大差值

题目描述

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

输入：[8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

提示：

树中的节点数在 2 到 5000 之间。
每个节点的值介于 0 到 100000 之间。

思路

直接递归去做就可以了。

代码

public class P1026 {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public int maxAncestorDiff(TreeNode root) {
        if (root == null)
            return 0;
        return minMax(root)[2];
    }

    private int[] minMax(TreeNode root) {
        int[] arr = new int[3];
        arr[0] = arr[1] = root.val;
        arr[2] = 0;
        if (root.left != null) {
            int[] leftArr = minMax(root.left);
            arr[0] = Math.min(arr[0], leftArr[0]);
            arr[1] = Math.max(arr[1], leftArr[1]);
            int maxDiff = Math.max(Math.abs(root.val - arr[0]), Math.abs(root.val - arr[1]));
            arr[2] = Math.max(maxDiff, leftArr[2]);
        }
        if (root.right != null) {
            int[] rightArr = minMax(root.right);
            arr[0] = Math.min(arr[0], rightArr[0]);
            arr[1] = Math.max(arr[1], rightArr[1]);
            int maxDiff = Math.max(Math.abs(root.val - arr[0]), Math.abs(root.val - arr[1]));
            arr[2] = Math.max(arr[2], Math.max(maxDiff, rightArr[2]));
        }
        return arr;
    }

}

最长等差数列

给定一个整数数组 A，返回 A 中最长等差子序列的长度。

回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。

示例 1：

输入：[3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例 2：

输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：

输入：[20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：

2 <= A.length <= 2000
0 <= A[i] <= 10000

思路

暴力搜索，时间复杂度O(n^2)。使用Map来存储第i个数当前的关于不同的差的序列长度。最坏空间复杂度也是O(n^2)。我直接开了一个很大的数组，来代替二维的Map。

代码

public class P1027 {

    private static final int BASE = 10000;

    public int longestArithSeqLength(int[] A) {
        int length = A.length;
        int longestLength = 1;
        int[][] matrix = new int[length][20002];
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                int diff = A[i] - A[j]; 
                matrix[i][BASE + diff] = Math.max(matrix[i][BASE + diff], matrix[j][BASE + diff] + 1);
                if (matrix[i][BASE + diff] > longestLength)
                    longestLength = matrix[i][BASE + diff];
            }
        }
        return longestLength + 1;
    }
}

从先序遍历还原二叉树

题目描述

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

示例 1：

1 2	输入："1-2--3--4-5--6--7" 输出：[1,2,5,3,4,6,7]

示例 2：

1 2	输入："1-2--3---4-5--6---7" 输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

1 2	输入："1-401--349---90--88" 输出：[1,401,null,349,88,90]

（其实有图的，不过懒得放了）

思路

一般和二叉树有关的问题，都很适合用栈来解决（递归也是在使用栈）。这个题扫描字符，然后用栈来存储当前路径。栈底元素就是根节点。

代码

public class P1028 {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode recoverFromPreorder(String S) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode result = null;
        char[] array = S.toCharArray();
        int i = 0;
        while (i < S.length()) {
            int level = 0;
            while (array[i + level] == '-')
                level++;
            i += level;
            int num;
            StringBuilder sb = new StringBuilder();
            while (i < S.length() && array[i] != '-') {
                sb.append(array[i]);
                i++;
            }
            num = Integer.valueOf(sb.toString());
            TreeNode newNode = new TreeNode(num);

            while (stack.size() > level)
                stack.pop();

            if (!stack.isEmpty()) {
                TreeNode parent = stack.peek();
                if (parent.left == null)
                    parent.left = newNode;
                else
                    parent.right = newNode;
            } else
                result = newNode;
            stack.push(newNode);
        }
        return result;
    }
}

Tags: 算法

← Floyd 判圈算法 Redis 底层数据结构 →

扫描二维码，分享此文章