标签： 数组

303.区域和检索_数组不可变

目标

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

说明：

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= i <= j < nums.length
  • 最多调用 104 次 sumRange 方法

思路

这个题看到之后没多想，提交之后发现和别人的性能差了10倍。这里的技巧就是提前将和计算的结果保存起来，用的时候直接用 prefix[right+1] - prefix[left] 即可。因为数组不可变所以这样是可行的。

这里没有使用 prefix[right] - prefix[left-1] 因为可以省去left为0的判断，不过多占用了4字节。其实没有必要纠结这些，真要计较的话，当left为0时还少了两次减法呢，并且cpu指令执行也有分支预测，无需关注这些细节。

代码

/**
 * @date 2024-03-18 8:36
 */
public class NumArray {

    private final int[] prefixSum;

    public NumArray(int[] nums) {
        prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }

    public static void main(String[] args) {
        NumArray main = new NumArray(new int[]{-2, 0, 3, -5, 2, -1});
        System.out.println(main.sumRange(0, 2));
        System.out.println(main.sumRange(2, 5));
        System.out.println(main.sumRange(0, 5));
    }
}

性能

2789.合并后数组中的最大元素

目标

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次：

  • 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

示例 1：

输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选中 i = 1 ，得到数组 nums = [5,6] 。
- 选中 i = 0 ，得到数组 nums = [11] 。
最终数组中只有一个元素，即 11 。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

思路

这个题要我们对一个数组进行操作并返回最大的元素值。这里的操作指的是合并相邻的非严格递增元素。

刚开始没有头绪，如果真的按照操作步骤先把符合条件的值求出来，替换掉较大元素的值并删掉较小元素，那么就需要频繁地移动数组数据。

除此之外需要考虑一个重要的问题，如何合并才能使最终的结果最大？如果从前向后合并，比如 [2,6,7] 先合并前两个得到[8,7]肯定没有从后向前合并得到的值 [2, 13] [15] 大。是否存在那种先从前向后合并，然后再从后向前合并才能得到最大值的情况？

刚开始是不那么容易弄清的。也考虑过优先合并 后面的元素值 比 合并后的元素值 大的 元素，提前考虑了一步能否避免上面的情况？好像可以，因为操作没有破坏原数组能否合并的状态。那么这种操作需要循环几次？时间复杂度是O(n)~O(nlogn)吗？

[1,2,1,4,1,2,1,4]一次遍历后可以变为[3,5,3,5]，然后再遍历一次得到 [8, 8]，再来一次 [16]，即O(nlogn)。更好的情况就是递增序列O(n)。

经过上面的分析可以发现，优先使后面的元素最大才能得到最大值。那么为什么不从后向前遍历并累加呢？如果遇到一个元素的值比后面所有元素的累加和还要大，那不管前面怎么操作，由于元素都是正整数，合并后只会更大。

想清楚了这一点就非常简单了。

代码

/**
 * @date 2024-03-14 11:29
 */
public class MaxArrayValue {

    public long maxArrayValue(int[] nums) {
        long res = nums[nums.length - 1];
        for (int i = nums.length - 1; i >= 1; i--) {
            res = res >= nums[i - 1] ? res + nums[i - 1] : nums[i - 1];
        }
        return res;
    }

    public static void main(String[] args) {
        MaxArrayValue main = new MaxArrayValue();
//        int[] nums = new int[]{2, 3, 7, 9, 3};
//        int[] nums = new int[]{5, 3, 3};
//        int[] nums = new int[]{77};
        int[] nums = new int[]{34, 95, 50, 12, 25, 100, 21, 3, 25, 16, 76, 73, 93, 46, 18};
        System.out.println(main.maxArrayValue(nums));
    }
}

性能

2684.矩阵中移动的最大次数

目标

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。

示例 1：

输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2：

输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

说明：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^6

思路

题目要我们求从矩阵第一列出发的最大移动次数。当前单元格可以移动到其后面一列的上中下三格，如果相应位置的值大于当前元素的话。

这道题可以使用动态规划来做，虽然重叠的子问题不多。从右向左，从下到上/从上到下，计算每个单元格可以移动的最大次数。然后求第一列的最大值即可。

值得注意的是这种列在外层从右向左的循环方式。如果像平时那样外层行循环内层列循环，那么写状态转移方程时，子问题可能还未计算。

官网题解给的是广度优先搜索的方法，遍历第一列起点，将能到达的第二列的格子加入集合，然后遍历这些格子，如此反复直到无法继续或者到达矩阵最大边界n-1。

代码

/**
 * @date 2024-03-16 15:08
 */
public class MaxMoves {

    public int maxMoves(int[][] grid) {
        int[][] dp = new int[grid.length][];
        for (int i = 0; i < grid.length; i++) {
            dp[i] = new int[grid[i].length];
        }
        int res = 0;
        int i = grid.length - 1;
        for (int j = grid[i].length - 2; j >= 0; j--) {
            i = grid.length - 1;
            for (; i >= 0; i--) {
                if (i != 0 && grid[i][j] < grid[i - 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1] + 1);
                }
                if (grid[i][j] < grid[i][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
                }
                if (i != grid.length - 1 && grid[i][j] < grid[i + 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j + 1] + 1);
                }
                if (j == 0){
                    res = Math.max(res, dp[i][0]);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        MaxMoves main = new MaxMoves();
        System.out.println(main.maxMoves(new int[][]{{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}}));
    }
}

性能

网友的题解还有网格DFS（2ms）、BFS（6ms）。虽然时间复杂度都是O(mn)，但是性能差别还是挺大的。有时间可以分析一下，性能到底差在哪里。先不追求性能100%了，先以最快的速度将题过一遍。

299.猜数字游戏后续—-关于字符串拼接的性能分析

起因

前面有一道猜数字游戏的题，去看性能分析，多数都是5ms。没错，我第一次提交的时候也是5ms。当时我就去看1ms的答案，想找找差距。经过仔细地对比，发现是返回结果时没有使用StringBuilder。乍一看好像可以说得过去，由于字符串的不可变性，拼接字符串实际上返回的是新对象。但是拼接了3次，就要创建3个对象吗？

在jsl8中有这样的描述：Java编译器可以使用StringBuffer或类似技术减少中间String对象。

Thinking in Java中也有提到：

尽管如此，书中建议我们不要在循环中使用字符串拼接，因为会重复创建StringBuilder对象。

题外话，也不是所有的字符串拼接都会使用StringBuilder，如果拼接的都是字符串常量，编译后会进行常量折叠。

那么问题来了，我们没有在循环中进行字符串拼接，为什么会有性能差异？

JMH测试

那我们就使用JMH分别测一测leetCode上提交5ms与1ms的代码。二者之间除了返回时字符串拼接的方式不同，其余代码均相同。


/**
 * @date 2024-03-13 11:19
 */
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 10, time = 1)
@Threads(1)
@Fork(1)
@State(value = Scope.Benchmark)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class Test {

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(Test.class.getSimpleName())
                .result("result.json")
                .resultFormat(ResultFormatType.JSON).build();
        new Runner(opt).run();
    }

    @Param(value = {"1122", "1807", "1123"})
    private String secret;
    @Param(value = {"2211", "7810", "0111"})
    private String guess;

    /** 5ms*/
    @Benchmark
    public String stringConcatenation() {
        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]);
            }
        }
        return bulls + "A" + cows + "B";
    }

    /** 1ms*/
    @Benchmark
    public String stringBuilder() {
        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();
    }

}

性能

测试结果发现性能差异不大。具体是什么原因就不清楚了，可能是leetcode没有进行编译优化或者是根据代码特征直接给的性能分析？

需要考虑 服务器负载、JVM的即时编译行为、测试用例的具体数据分布 等因素。

我发现同一道题，不同时间测试用例可能是不同的，比如代码提交后提示解答错误 73/74，修改了代码过了一段时间提交发现问题没有解决，还提示解答错误 73/74，但是输入的数据是不同的。

后续

我在评论区还发现了一位网友的一次遍历的写法，可以说是很巧妙了。但是，只要使用字符串拼接，性能就是5ms。

class Solution {
    public String getHint(String secret, String guess) {
        int[] nums = new int[10];
        int countA = 0, countB = 0;
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) countA++;
            else {
                if (nums[guess.charAt(i) - '0']-- > 0) countB++;
                if (nums[secret.charAt(i) - '0']++ < 0) countB++;
            }
        }
        StringBuilder sb = new StringBuilder();
        return sb.append(countA).append('A').append(countB).append('B').toString();
    }
}

最后说一下这个一次遍历的思路，如果猜测的数字与secret当前位置的数字不符：

当猜测数字计数却大于0，说明secret之前遇到过，算是位置不正确，应该将bulls加一。不论前面判断结果怎样，猜测数字计数总要减一。

当secret数字计数小于0，说明guess之前猜到过，但是由于当时没有多余的secret数字，所以没有加。这里遇到了，就将bulls加一。不论前面的判断结果，猜测数字计数总要加一。

2129.将标题首字母大写

目标

给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写 ：

  • 如果单词的长度为 1 或者 2 ，所有字母变成小写。
  • 否则，将单词首字母大写，剩余字母变成小写。

请你返回 大写后 的 title 。

示例 1：

输入：title = "capiTalIze tHe titLe"
输出："Capitalize The Title"
解释：
由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。

示例 2：

输入：title = "First leTTeR of EACH Word"
输出："First Letter of Each Word"
解释：
单词 "of" 长度为 2 ，所以它保持完全小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

示例 3：

输入：title = "i lOve leetcode"
输出："i Love Leetcode"
解释：
单词 "i" 长度为 1 ，所以它保留小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

说明：

  • 1 <= title.length <= 100
  • title 由单个空格隔开的单词组成，且不含有任何前导或后缀空格。
  • 每个单词由大写和小写英文字母组成，且都是 非空 的。

思路

这个要看清题目，单词的长度为 1 或者 2 ，所有字母变成小写。并不是指传入的title长度，而是title中的单词。此外要熟悉字符对应的ASCII码：

Character ASCII
A-Z 65-90
a-z 97-122
空格 32

读取字符数组中的字符，记录第一个字符的index，跳过，将后续的字符均转为小写，直到遇到空格，记录单词字符个数。如果字符个数大于2，将first对应的字符转为大写，否则转为小写。

代码

/**
 * @date 2024-03-11 0:16
 */
public class CapitalizeTitle {

    public String capitalizeTitle(String title) {
        // 使用System.arraycopy复制的数组，可以直接操作
        char[] chars = title.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char first = (char) i++;
            int counter = 1;
            while (i < chars.length && chars[i] != 32) {
                if (chars[i] < 97) {
                    chars[i] = (char) (chars[i] + 32);
                }
                i++;
                counter++;
            }
            if (counter > 2) {
                if (chars[first] >= 97) {
                    chars[first] = (char) (chars[first] - 32);
                }
            } else {
                if (chars[first] < 97) {
                    chars[first] = (char) (chars[first] + 32);
                }
            }
        }
        return new String(chars);
    }
}

性能

299.猜数字游戏

目标

你在和朋友一起玩 猜数字（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. 不要使用加号拼接返回的结果，因为每一次字符串的修改都会创建新的对象，会显著影响性能

性能

2834.找出美丽数组的最小和

目标

给你两个正整数：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);
        }
    }
}

性能

2575.找出字符串的可整除数组

给你一个下标从 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类型防止整数溢出。

性能

121.买卖股票的最佳时机

目标

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

说明：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

思路

虽然这是一道简单题，但是我也想了一个多小时。算法实现起来简单，但是算法的设计，如何得到满足条件的结果也不是那么直观。

说回这道题，要求得最大利润，我们都明白要低买高卖。难道这道题就是让求数组的最大值与最小值？显然不是。我们的目标是求取一个买入点，再其之后的某天卖出获得的利润最大。只能操作一次，可以看成是长线交易（后面还有一道可以多次操作的题）。

暴力解法是遍历股票价格数组，然后向后循环，求得最大利润。时间复杂度是O(n!)，不可行。

思考下面的问题：

取得最大利润是否必须在最低点买入？不是，比如[2,8,1,6]。

取得最大利润是否必须在最高点卖出？不是，比如[3,8,1,7]。

但是，如果遇到了更低的价格，那么它一定是当前最佳的买入点。因为不管后续价格怎么波动，想要获得最大收益，被减数当然越小越好。

因此，问题可以转化为：任取一个买入点，向后遍历并记录最大利润，直到出现一个更低的买入点，在这之前的一段时间内，我们所选的就是最佳买入点，可以记录这段时间内的最大利润。然后以新的最佳买入点继续向后遍历并记录最大利润，直到一个新的最佳买入点出现。在这一过程中如果最大利润比之前的值更大就替换掉。这样我们就得到了问题的答案。

其实，一开始我并没有这么清晰的思路。只是跟着感觉走：

  1. 首先，如果遍历时发现股票价格是递减的，那么我们肯定不能买入。这里，我们需要计算后一天减去前一天的收益，如果连着都是负数，那么直接跳过。
  2. 然后，如果找到了第一个正收益的点，那么我们买入。之后，我们开始累加收益，这样累加得到的是当天到买入点的收益。即 如果a是我们的买入点，那么往后利润的累加和 profitSum 为 (b - a) + (c - b) + (d - c) + (e - d) = e - a。在这一过程中，我们记录最大收益 profitMax。
  3. 接下来，我们需要找到更低的买入点。如果我们的买入点是i，当我们遍历到第j天的时候，profitSum = prices[j] - prices[i]，而当天与前一天的利润为 profit = prices[j] - prices[j-1]，如果profit > profitSum，那么prices[j] - prices[j-1] > prices[j] - prices[i] 即 prices[j-1] < prices[i]。j-1 就是新的最佳买入点。这时我们需要将利润和重置，然后再比较最大利润。

最开始写的时候忽略了查找最新买入点的这个步骤，增加的这个判断 profit > profitSum 是根据错误案例调试出来的，感觉就是如果一天的收益就比之前的历史收益大了，那就没必要再累加前面的利润了，应该重新开始。

代码

/**
 * @date 2024-03-03 1:44
 */
public class MaxProfit {

    public int maxProfit(int[] prices) {
        int profitSum = 0;
        int profitMax = 0;
        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - prices[i - 1];
            if (profitSum <= 0 && profit <= 0) {
                continue;
            }
            profitSum += profit;
            if (profit > profitSum) {
                //  最开始的时候没写这个判断
                profitSum = profit;
            }
            if (profitSum > profitMax) {
                profitMax = profitSum;
            }

        }
        return profitMax;
    }

    public static void main(String[] args) {
        MaxProfit main = new MaxProfit();
        System.out.println(main.maxProfit(new int[]{3, 3, 5, 0, 0, 3, 1, 4}));
    }

}

理清楚之后发现许多操作是没必要的，比如累加每天的利润，实际就是当天价格减去买入点价格。

    public int maxProfit(int[] prices) {
        int buyPoint = 0;
        int profitMax = 0;
        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - prices[buyPoint];
            if (profit <= 0) {
                buyPoint = i;
            } else if (profit > profitMax) {
                profitMax = profit;
            }

        }
        return profitMax;
    }

性能

优化后

169.多数元素

目标

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

说明：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路

今天做个简单题吧。要求时间复杂度是O(n)，那么就不能嵌套循环，空间复杂度度是O(1)，也就不能开辟新数组。很自然的可以想到：累加当前出现次数 count 最多的元素 res，如果遇到其它元素则减1，当 count 为负数时，说明当前出现次数最多的元素 可能 发生改变，将res替换为当前元素，并将count置1。

这里说 可能，是因为只要遇到与所选元素值不相等的， count 就减1。我们并不清楚这些其它元素值是否都相同，只能够推出当初所选的多数被其它少数反超了。但是从总体来考虑，如果我们所选择的真是多数元素，那么它一定会在后面再次反超。

官网介绍了一种投票算法 Boyer-Moore，应该也是这种思路吧。

官网还给出了一种分治算法，主要思想是：如果将数组分成两部分，那么数组的众数至少是一部分的众数。递归求解，然后回溯合并，确定子数组众数。不过时间复杂度O(nlog⁡n)，参考算法导论P53主定理。空间复杂度：O(log⁡n)，递归用到的栈空间。

代码

/**
 * @date 2024-03-02 22:24
 */
public class MajorityElement {
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != res) {
                count--;
                // 出错点：反超时应当将值设为1，参考错误用例[10,9,9,9,10]
                if (count < 0) {
                    res = nums[i];
                    count = 1;
                }
            } else {
                count++;
            }
            // 本以为加上可以提高性能，谁知道还慢了2ms
            // if (count > Math.floor(nums.length / 2.0)) {
            //     break;
            // }
        }
        return res;
    }

    public static void main(String[] args) {
        MajorityElement main = new MajorityElement();
        System.out.println(main.majorityElement(new int[]{10, 9, 9, 9, 10}));
    }
}

性能

本以为判断条件可以提高效率，谁知道还慢了2ms，耗时增加了2倍，因为每次算出答案基本上也都循环完了。