自己的网站可以做淘客吗,资讯网站域名选购,中信建设有限责任公司官方网站,郑州营销型网站建设工作室目录 704. 二分查找题目链接标签思路代码 290. 单词规律题目链接标签思路代码 200. 岛屿数量题目链接标签思路代码 704. 二分查找
题目链接
704. 二分查找
标签
数组 二分查找
思路
这道题是 二分查找 最经典的一道题#xff0c;掌握了本题的思想就进入了 二分 思想的大… 目录 704. 二分查找题目链接标签思路代码 290. 单词规律题目链接标签思路代码 200. 岛屿数量题目链接标签思路代码 704. 二分查找
题目链接
704. 二分查找
标签
数组 二分查找
思路
这道题是 二分查找 最经典的一道题掌握了本题的思想就进入了 二分 思想的大门。
二分查找 指的是每次查找把区间分为两半然后将目标值 target 与区间中点 mid 对应的值 nums[mid] 作比较由于数组是 升序 的所以如果 target 小于 nums[mid]则下一轮查找的区间为左子区间因为只有在左子区间才能找到比 nums[mid] 小的数如果 target 大于 nums[mid]则下一轮查找的区间为右子区间因为只有在右子区间才能找到比 nums[mid] 大的数如果 target 等于 nums[mid]则直接返回 mid 作为 target 的下标。当查找区间长度不够0时退出查找返回 -1 表示没有找到。
注意二分查找 的前提是 数组有序如果数组是无序的那么将无法每次排除掉半个区间。
代码
class Solution {public int search(int[] nums, int target) {int left 0, right nums.length - 1; // left和right分别为查找区间的左、右索引while (left right) { // 当查找区间长度不够0时退出查找int mid left (right - left 1); // 获取区间中间元素的索引if (target nums[mid]) { // 如果 target 小于 nums[mid]right mid - 1; // 将区间的 右端点 移动到 中点-1 处下一轮查找的区间为左子区间} else if (target nums[mid]) { // 如果 target 大于 nums[mid]left mid 1; // 将区间的 左端点 移动到 中点1 处下一轮查找的区间为右子区间} else { // 如果 target 等于 nums[mid]return mid; // 返回 mid 作为 target 的下标}}return -1; // 没有找到 target返回 -1}
}290. 单词规律
题目链接
290. 单词规律
标签
哈希表 字符串
思路
本题与 205. 同构字符串 很像要么使用 建立双向索引 的方法要么使用 查找第一次出现索引 的方法。上面那道题是用 字符与字符 之间的索引比较而本题则是使用 字符与字符串 之间的索引比较。
建立双向索引 的方法是一种容易想到的方法它的核心思想就是分别使用两个 Map分别记录从 pattern中的字符 到 s中的字符串 的映射和从 s中的字符串 到 pattern中的字符 的映射然后截取每个 字符 与 字符串查看 字符 与 字符串 能否 互相映射如果 字符 或 字符串 没有映射则先建立映射。
相比之下查找第一次出现索引 这种方法更难想到因为它更偏向 底层上面的方法使用 Map 存储了 每个字符对应的第一个字符串 或 每个字符串对应的第一个字符其实不需要这么复杂只需要存储 每个字符第一次出现的位置 和 每个字符串第一次出现的位置 即可因为比较 字符 与 字符串 能否 互相映射 的更底层就是 比较 字符第一次出现的索引 与 字符串第一次出现的索引 是否一致。
思路明确了先将字符串 s 用空格分割为 list然后检查 pattern中字符的个数 与 list中字符串的个数 是否相等如果这两个值不相等那就说明 pattern 和 s 不遵循相同的规律返回 false接着获取 pattern 中每个字符第一次出现的索引 和 list 中每个字符串第一次出现的索引如果它们不同则说明 pattern 和 s 不遵循相同的规律返回 false如果能比较完全部 字符 与 字符串 都不返回 false那么说明 pattern 和 s 遵循相同的规律返回 true。
代码
class Solution {public boolean wordPattern(String pattern, String s) {ListString list List.of(s.split( )); // 用 空格 分割将 pattern 分割到一个 List 集合中int n pattern.length(); // 获取 s 的长度if (n ! list.size()) { // 如果 pattern中字符的个数 与 list中字符串的个数 不相同return false; // 则 pattern 和 s 不遵循相同的规律返回 false}for (int i 0; i n; i) { // 遍历比较每个 字符 与 字符串int pi pattern.indexOf(pattern.charAt(i); // 获取 本字符 第一次出现的索引int si list.indexOf(list.get(i)); // 获取 本字符串 第一次出现的索引if (pi ! si) { // 如果 字符第一次出现的索引 与 字符串第一次出现的索引 不同return false; // 则 pattern 和 s 不遵循相同的规律返回 false}}return true; // pattern 和 s 遵循相同的规律返回 true}
}200. 岛屿数量
题目链接
200. 岛屿数量
标签
深度优先搜索 广度优先搜索 并查集 数组 矩阵
思路
本题的目标是 找到岛屿的个数岛屿的定义是 一片连通的1。
题目可没有说不能修改原地图所以可以遍历整个地图如果找到陆地该元素等于 1就让岛屿数加一并使用 深度优先搜索 淹没这块陆地所在的岛屿将这片连通的 1 全部变成 0之后接着遍历直到遍历完整个地图。
代码
class Solution {public int numIslands(char[][] grid) {int res 0;int m grid.length, n grid[0].length;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) { // 如果i和j指向的是陆地res; // 则岛屿数加一flood(grid, i, j); // 淹没这整座岛屿}}}return res;}// 在grid中淹没 含有i和j指向陆地的 整座岛屿private void flood(char[][] grid, int i, int j) {grid[i][j] 0; // 先淹没i和j指向的陆地for (int k 0; k 4; k) {int ki i dir[k][0], kj j dir[k][1];if (ki 0 ki grid.length kj 0 kj grid[0].length // 如果ki和kj没有越界 grid[ki][kj] 1) { // 并且ki和kj指向的元素为1即ki和kj指向陆地flood(grid, ki, kj);; // 则淹没ki和kj指向的陆地}}}private int[][] dir {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组分别为 向右、向下、向左、向上
}
