作者： admin

目标

给出一个满足下述规则的二叉树：

1. root.val == 0
2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

说明：

• TreeNode.val == -1
• 二叉树的高度不超过 20
• 节点的总数在 [1, 10^4] 之间
• 调用 find() 的总次数在 [1, 10^4] 之间
• 0 <= target <= 10^6

思路

dfs还原节点val，并将其加入到Hash表中，直接contains判断。

这个题被标为medium，估计是想让我们自己实现Hash表来查找元素吧。

代码

/**
 * @date 2024-03-12 2:41
 */
public class FindElements {
    Set<Integer> elements;

    public FindElements(TreeNode root) {
        elements = new HashSet<>();
        recover(root, 0);
    }

    public void recover(TreeNode root, int value) {
        if (root == null) {
            return;
        }
        root.val = value;
        elements.add(value);
        recover(root.left, 2 * value + 1);
        recover(root.right, 2 * value + 2);
    }

    public boolean find(int target) {
        return elements.contains(target);
    }
}

性能

目标

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

• 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
• 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1：

输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

示例 2：

输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

说明：

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret 和 guess 仅由数字组成

思路

这个题目的算法还是挺直接的，就是比较相应位置上的数字是否一致，如果一致bulls加1，否则就要累加错误数字的出现次数，但最多不能超过其在secret中的个数。

代码

/**
 * @date 2024-03-10 0:36
 */
public class GetHint {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        char[] secretCharArray = secret.toCharArray();
        int[] missArray = new int[10];
        int[] cowsArray = new int[10];
        for (int i = 0; i < secretCharArray.length; i++) {
            int guessCharacter = guess.charAt(i) - '0';
            int secretCharacter = secretCharArray[i] - '0';
            if (guessCharacter == secretCharacter) {
                bulls++;
            } else {
                missArray[secretCharacter] += 1;
                cowsArray[guessCharacter] += 1;
            }
        }
        for (int i = 0; i < cowsArray.length; i++) {
            if (missArray[i] > 0 && cowsArray[i] > 0) {
                cows += Math.min(missArray[i], cowsArray[i]);
            }
        }
        StringBuilder sb = new StringBuilder();
        return sb.append(bulls).append('A').append(cows).append('B').toString();
    }
}

这里面有几点需要注意：

1. 数组只需要保留0-9十个数字即可
2. 数字字符减去'0'可以得到对应的整型数字
3. 不要使用加号拼接返回的结果，因为每一次字符串的修改都会创建新的对象，会显著影响性能

性能

目标

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为 美丽数组 。

• nums.length == n.
• nums 由两两互不相同的正整数组成。
• 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。

返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 10^9 + 7。

示例 1：

输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。

示例 2：

输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。 
- nums 的长度为 n = 3 。 
- nums 由两两互不相同的正整数组成。 
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。

示例 3：

输入：n = 1, target = 1
输出：1
解释：nums = [1] 是美丽数组。

说明：

• 1 <= n <= 10*9
• 1 <= target <= 10^9

思路

首先，美丽数组一个长度为n的数组，数组中的元素均不相同且为正整数，且任意两个元素之后不能等于target。

我们需要寻找所有可能的美丽数组中，所有元素和最小的那一个。并返回这个最小和。

如何才能使元素和最小？

很明显应该是从1开始的正整数序列，但是这个序列中的值相加不能等于target。

那么本质上是要求 1______mid~~~~~~target______这一序列的值，其中~~~~~~区间的值应舍去，因为会与前面的相加得到target。

刚开始想的是循环遍历 [1, n) 累加和，并记录target - i，如果遍历的过程中遇到了就直接跳过，但是提交后提示超出内存限制。于是进行修改，不保存不符合条件的元素，直接根据下标来判断，这次提示超时。

然后尝试不使用循环，直接使用等差数列求和公式计算，结果整型溢出。需要注意运算符优先级高的会先计算，如果没有显式地类型转换就会溢出，并且隐式类型转化使用的是溢出后的值。

代码

/**
 * @date 2024-03-08 9:00
 */
public class MinimumPossibleSum {

    public final int MOD = 1000000007;

    public int minimumPossibleSum(int n, int target) {
        int mid;
        mid = target / 2;
        if (n <= mid) {
            return (int) ((n + n * (n - 1L) / 2L) % MOD);
        } else {
            int r = n - mid;
            return (int) (((mid + mid * (mid - 1L) / 2L) + (long) target * r + r * (r - 1L) / 2L) % MOD);
        }
    }
}

性能

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0
• 返回 word 的可整除数组。

示例 1：

输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

说明：

• 1 <= n <= 10^5
• word.length == n
• word 由数字 0 到 9 组成
• 1 <= m <= 10^9

思路

题目要求的是从字符串第一个数字开始，验证数字能否被给定的正整数m整除。很容易想到的方法是创建一个StringBuilder，遍历字符串的Character，依次加入StringBuilder，然后转化为数字，求余判断能否整除。提交运行发现会溢出，虽然word的最大长度为10^5，但是Long的最大值也才 9223372036854775807 共19位，直接求解行不通。

很自然地想到需要分治处理，比方说先在Long的范围内算，每次处理19位，然后记录余数，再接上后面的18位。但是感觉这样具体实现起来很别扭，实际上求余数的时候也没必要每次都从头开始。

因此，我们可以用每一位对m（它不超过10^9，在Integer 2147483647 的范围内）进行MOD运算，同时记录结果。如果为0，则将输出数组中的相应位置赋值为1，否则为0。然后将余数 remainder * 10加上下一位字符所示的数字，再进行MOD运算以此类推即可。

代码

/**
 * @date 2024-03-07 9:27
 */
public class DivisibilityArray {
    public int[] divisibilityArray(String word, int m) {
        long remainder = 0;
        int n = word.length();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            remainder = (remainder * 10 + (word.charAt(i) - '0')) % m;
            if (remainder == 0) {
                res[i] = 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        DivisibilityArray main = new DivisibilityArray();
        String str = "1000000000100000000030199999999610000000009199999999079999999938299999999010000000009999999991100000000010000000001000000000100000000071999999992100000000010000000003099999999759999999951000000000100000000010000000001000000000822999999988269999999921000000000100000000010000000005999999995900999999991100000000069999999947445979999999641999999999059999999957999999993100000000080609999999868999999992599999999867999999993100000000";
        int m = 1000000000;
        main.divisibilityArray(str, m);
    }
}

这里面有个小技巧，就是使用 Character - '0'来得到相应的数字，Character.getNumericValue考虑的情况比较多，这里用不到。同时需要注意，余数应使用long类型防止整数溢出。

性能