LeetCode 35, 242, 994

35. 搜索插入位置

题目链接

35. 搜索插入位置

思路

本题与 704. 二分查找十分相似，只不过本题在找不到 target 时不返回 -1，而是返回 target 应该插入的位置。

可以思考一下当找不到值时，左、右指针 left, right 指向哪里。结论是 左指针left指向第一个大于target的元素，右指针right指向最后一个小于target的元素。

例如对于nums = [1, 2, 3, 4, 5, 7, 8], target = 6：

开始left = 0, right = 6, mid = 3，发现此时target > nums[mid]，将左指针left移动到mid + 1的位置；
此时left = 4, right = 6, mid = 5，发现此时target < nums[mid]，将右指针right移动到mid - 1的位置；
此时left = 4, right = 4, mid = 4，发现此时target > nums[mid]，将左指针left移动到mid + 1的位置；
此时left = 5, right = 4，有left > right，退出循环。

发现left = 5是nums中第一个大于target的元素，而right = 4是nums中最后一个小于target的元素，而left = 5恰好是这个元素应该插入的位置，所以 在找不到值时，返回left作为待插入索引。

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (target < nums[mid]) {
                right = mid - 1; // 在左子区间查询
            } else if (target > nums[mid]) {
                left = mid + 1; // 在右子区间查询
            } else {
                return mid;
            }
        }
        return left; // 在找不到值时，返回 left 作为待插入索引
    }
}

242. 有效的字母异位词

题目链接

242. 有效的字母异位词

思路

若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。理解了这句话就会做本题了，这句话意味着对于 s 和 t，不需要关心它们的字符顺序，只需要关心它们每个字符出现的次数，所以可以通过 先统计两个字符串中每个字符出现的次数，然后比较统计的结果是否完全一致 的方法来解决本题。

统计字符出现的次数有两种方法，一种是使用Map，键为字符，值为字符出现的次数；另一种是使用int[]，索引为字符（字符最多也就128个，并且 字符的底层就是数字），索引指向的元素为字符出现的次数。使用int[]比Map要快很多，所以本题解使用int[]。

一般来说，使用int[]时得自己构建 字符与索引之间的映射。例如：

如果统计的是全部的大写字符，则对于大写字符ch，它在统计数组中的索引为ch - 'A'，这个统计数组的长度为26；
如果统计的是全部的小写字符，则对于小写字符ch，它在统计数组中的索引为ch - 'a'，这个统计数组的长度为26；
如果统计的是全部字符，则对于字符ch，它在统计数组中的索引为ch - '\0'（由于'\0' == 0，所以这里的索引可以简写为ch），这个统计数组的长度为128。

代码

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] sCnt = count(s); // 统计s中的字符出现次数
        int[] tCnt = count(t); // 统计t中的字符出现次数
        for (int i = 0; i < sCnt.length; i++) {
            if (sCnt[i] != tCnt[i]) { // 如果有一个字符的出现次数不一样
                return false; // 则不是字母异位词，返回 false
            }
        }
        return true; // 每个字符的出现情况都一样，返回 true
    }
    // 统计字符串str中的字符出现次数
    private int[] count(String str) {
        int[] cnt = new int[26]; // s 和 t 仅包含小写字母，共26个
        for (char ch : str.toCharArray()) {
            cnt[ch - 'a']++;
        }
        return cnt;
    }
}

994. 腐烂的橘子

题目链接

994. 腐烂的橘子

思路

本题是一道 模拟题，可以采用 模拟橘子腐烂过程 的方法来计算感染的时间：感染之前先记录新鲜橘子的数量，只有在新鲜橘子数量大于0的情况下才进行感染，每轮感染对腐烂橘子上下左右的新鲜橘子进行感染，然后统计本轮感染的橘子的数量，如果本轮感染没有感染任何橘子，则说明新鲜橘子不可能被感染完，返回 -1；否则就将本轮感染的橘子从新鲜橘子中移除，并让时间加1分钟。当新鲜橘子数量为0时，返回时间即可。

模拟有一个难点：如何统计每轮感染的橘子数？可以在感染时将橘子的状态设置为0, 1, 2除外的任意一种状态，然后在统计时遍历整个网格，对于状态为自定义状态的橘子，将其状态改为2，并让统计结果加一。

代码

class Solution {
    public int orangesRotting(int[][] grid) {
        int time = 0; // 记录感染的时间
        int rest = countFresh(grid); // 剩余新鲜橘子的数量
        
        while (rest > 0) {
            // 对腐烂橘子上下左右的新鲜橘子进行感染
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == 2) {
                        infect(grid, i, j);
                    }
                }
            }
            
            int infected = countInfect(grid); // 统计本轮感染的橘子数量
            if (infected == 0) { // 如果本轮感染的橘子数量为0，则说明不可能感染完所有橘子
                return -1;
            }

            rest -= infected; // 将 本轮感染的橘子 从 剩余新鲜的橘子中 移除
            time++; // 时间过了1分钟
        }
        return time;
    }
    // 感染上下左右的橘子，将感染的橘子状态设置为-2
    private void infect(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        for (int k = 0; k < 4; k++) {
            int ki = i + dir[k][0], kj = j + dir[k][1];
            if (ki >= 0 && ki < m && kj >= 0 && kj < n // 如果这个橘子在矩阵中
                    && grid[ki][kj] == 1) { // 并且是新鲜橘子
                grid[ki][kj] = -2; // 则将其感染
            }
        }
    }
    // 统计本轮感染的橘子数量，统计完毕后将感染橘子的状态置为2
    private int countInfect(int[][] grid) {
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == -2) {
                    cnt++;
                    grid[i][j] = 2;
                }
            }
        }
        return cnt;
    }
    // 统计初始的新鲜橘子数量
    private int countFresh(int[][] grid) {
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
    private int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组，分别为 向右、向下、向左、向上
}