我有云服务器如何建站,购物app下载,wordpress移动端禁止放大,易企网络网站建设目录 35. 搜索插入位置题目链接标签思路代码 242. 有效的字母异位词题目链接标签思路代码 994. 腐烂的橘子题目链接标签思路代码 35. 搜索插入位置
题目链接
35. 搜索插入位置
标签
数组 二分查找
思路
本题与 704. 二分查找 十分相似#xff0c;只不过本题在找不到 tar… 目录 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;}// 感染上下左右的橘子将感染的橘子状态设置为-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}}; // 方向数组分别为 向右、向下、向左、向上
}
