LeetCode刷题

713. 乘积小于K的子数组

链接：https://leetcode-cn.com/problems/subarray-product-less-than-k

给定一个正整数数组 nums和整数 k 。
请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
提示: 

1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106

滑动窗口问题
正向滑动窗口可能导致大量重复计算
如 1,2,3,4
[1],[1,2],[1,2,3],[2]

 public int numSubarrayProductLessThanK2(int[] nums, int k) {
        int start = 0;
        int count = 0;
        while (start < nums.length) {
            int end = start;
            int product = nums[start];
            while ( end < nums.length && product  < k){
                count++;
                end++;
                if(end<nums.length){
                    product = product * nums[end];
                }
            }
            start++;
        }
        return count;
    }

如果需要优化，节省计算，则需要发现规律。
规律，找到一个区间 [left,right]，这个区间所有连续子数组都满足条件，且连续子数组的个数为 right- left + 1

  public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) prod /= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }

# 每次到这个位置, 我们会得到一些以right结尾的乘积小于k的连续子数组, 这些子数组不会与之前的任何一个重复:
# [right]
# [right-1, right]
# [right-2, right]
# [right-3, right-2, right]
# ...
# [left, ..., right-3, right-2, right]
# 很明显一共有right - left + 1个
res += right - left + 1

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

核心思路就是找一个点作为起始点，然后进行广搜，将遍历过的陆地都变成海洋。
找起始点的过程为遍历整个二维数组，如果遇到陆地（元素值为 ‘1’）就记岛屿数加1；
BFS 广搜解决
有个技巧是广搜扩展新节点的过程中就将陆地变成海洋，而不是队列吐出的时候，这样可以减少后续的计算量。

  public int numIslands(char[][] grid) {
        int num_islands = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length; col++) {
                // 若当前元素值为1
                if(grid[row][col]== '1'){
                    ++num_islands;
                    grid[row][col] = '0'; // 标记为0 表示已经访问
                    LinkedList<Pair<Integer, Integer>> neighbors = new LinkedList<>();  // 启用队列进行广度搜索
                    neighbors.add(new Pair<>(row,col));

                    while (!neighbors.isEmpty()){
                        Pair<Integer,Integer> pair = neighbors.pop();
                        int currentRow = pair.getKey(),currentCol = pair.getValue();
                        // 访问队首节点的上下左右节点,如果有为1的情况则将其入队
                        if(currentRow-1 >=0 && grid[currentRow-1][currentCol] == '1') {  // 上
                            neighbors.add(new Pair<>(currentRow-1,currentCol));
                            grid[currentRow-1][currentCol] = '0';  // 标记访问
                        }
                        if(currentRow+1 < grid.length && grid[currentRow+1][currentCol] == '1') {  // 下
                            neighbors.add(new Pair<>(currentRow+1,currentCol));
                            grid[currentRow+1][currentCol] = '0';  // 标记访问
                        }
                        if(currentCol-1 >=0 && grid[currentRow][currentCol-1] == '1') {  // 左
                            neighbors.add(new Pair<>(currentRow,currentCol-1));
                            grid[currentRow][currentCol-1] = '0';  // 标记访问
                        }
                        if(currentCol+1 < grid[currentRow].length && grid[currentRow][currentCol+1] == '1') {  // 右
                            neighbors.add(new Pair<>(currentRow,currentCol+1));
                            grid[currentRow][currentCol+1] = '0';  // 标记访问
                        }
                    }

                }
            }
        }
        return num_islands;
    }

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

例子

和岛屿数量一样的题，只是换成了邻接矩阵表示法，深搜 广搜都可，还有种解法是并查集。
不过手写并查集比较费劲，不建议面试的时候尝试。

 /**
     *
     * @param isConnected  图的邻接矩阵表示法
     * @return  广度优先遍历
     */
    public int findCircleNum2(int[][] isConnected) {
        int[] visited = new int[isConnected.length];
        int provinceCnt = 0;
        for (int nodeIndex = 0; nodeIndex < isConnected.length; nodeIndex++) {
                LinkedList<Integer>  queue = new LinkedList<>();
                if(visited[nodeIndex] == 1) continue;
                visited[nodeIndex] = 1;
                queue.add(nodeIndex);
                provinceCnt++;
                while (!queue.isEmpty()){
                     Integer visitNode =  queue.poll();
                    for (int i = 0; i < isConnected[visitNode].length; i++) {
                        if( isConnected[visitNode][i] ==1 && i != visitNode && visited[i]!=1){
                            visited[i] = 1;
                            queue.add(i);
                        }
                    }
                }
        }
        return provinceCnt;
    }

    /**
     * 深度优先遍历
     */
    public int findCircleNum(int[][] isConnected) {
        int[] visited = new int[isConnected.length];
        int provinceCnt = 0;
        for (int nodeIndex = 0; nodeIndex < isConnected.length; nodeIndex++) {
            Stack<Integer>  stack = new Stack<>();
            if(visited[nodeIndex] == 1) continue;
            visited[nodeIndex] = 1;
            stack.add(nodeIndex);
            provinceCnt++;
            while (!stack.isEmpty()){
                Integer visitNode =  stack.pop();
                for (int i = 0; i < isConnected[visitNode].length; i++) {
                    if( isConnected[visitNode][i] ==1 && i != visitNode && visited[i]!=1){
                        visited[i] = 1;
                        stack.add(i);
                    }
                }
            }
        }
        return provinceCnt;
    }