目录
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. 有效的字母异位词
题目链接
标签
哈希表 字符串 排序
思路
若 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. 腐烂的橘子
题目链接
标签
广度优先搜索 数组 矩阵
思路
本题是一道 模拟题，可以采用 模拟橘子腐烂过程 的方法来计算感染的时间：感染之前先记录新鲜橘子的数量，只有在新鲜橘子数量大于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}}; // 方向数组，分别为 向右、向下、向左、向上
}
