LeetCode 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) {List<String> 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}}; // 方向数组，分别为 向右、向下、向左、向上
}