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[]时得自己构建 字符与索引之间的映射。例如：

1. 如果统计的是全部的大写字符，则对于大写字符ch，它在统计数组中的索引为ch - 'A'，这个统计数组的长度为26；
2. 如果统计的是全部的小写字符，则对于小写字符ch，它在统计数组中的索引为ch - 'a'，这个统计数组的长度为26；
3. 如果统计的是全部字符，则对于字符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;}// 感染上下左右的橘子，将感染的橘子状态设置为-2private 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; // 则将其感染}}}// 统计本轮感染的橘子数量，统计完毕后将感染橘子的状态置为2private 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}}; // 方向数组，分别为 向右、向下、向左、向上
}