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;
}
网友评论