Posted Updated LeetCode / Medium / 复习a minute read (About 150 words)

713. Subarray Product Less Than K

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

滑动窗口，维护一个窗口内的乘积。
当乘积小于目标值时，窗口右侧向右移动。每加入一个新数值，可以增加(j-i+1)个组合。
当乘积大于目标时，窗口左侧向右移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int i = 0;
        int j = 0;
        int product = nums[0];
        int count = 0;
        
        while(i < nums.length && j < nums.length){
            if(product < k){
                count += (j - i) + 1;
                j++;
                if(j < nums.length ) product *= nums[j];
            }
            else{
                product /= nums[i];
                i++;
            }   
        }
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 451 words)

209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

滑动窗口，先取最左侧数字。记录窗口的最小值。
如果小于目标值，则右侧窗口向右移动，扩大窗口。更新窗口内的值。
如果大于等于目标值，则左侧窗口向右移动，缩小窗口。更新窗口内的值。
同时如果窗口大小小于最小值则更新窗口最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = nums[0];
        while(right < nums.length){
            if(sum >= target){
                min = Math.min(min, right - left + 1);
                sum -= nums[left];
                left++;
            }
            else{
                right++;
                if(right < nums.length) sum += nums[right];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

计算前缀和。
前缀和[j]与前缀和的[i]的差就是i+1到j的和。
因此需要找到sum[j] - sum[i] >= k。
暴力枚举的话需要O(n^2^)的时间复杂度。

由于前缀和是有序的，因此我们可以采用二分搜索。
寻找sum[j] - k >= sum[i]。
Arrays.binarySearch方法可以返回查找到的目录。
如果没有该值，方法会返回一个负数，其取反（x取反相当于[-(x+1)]）的值就是应该插入的目录。
将ans设置为无限大，如果(index - i)小于最小值则更新到ans。

时间复杂度O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int[] sum = new int[nums.length+1];
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < sum.length; i++){
            int search = sum[i] + target;
            int index = Arrays.binarySearch(sum, search);
            if(index < 0){
                index = ~index;
            }
            if(index < sum.length){
                ans = Math.min(ans, index - i);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
200. Number of Islands
Posted Updated LeetCode / Medium2 minutes read (About 309 words)

200. Number of Islands

Question

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Solution

遍历所有点，如果等于1则对其进行DFS搜索。
在搜索的同时将1设为0。
如果等于0则递归返回。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    char[][] area;
    public int numIslands(char[][] grid) {
        area = grid;
        int count = 0;
        
        for(int i = 0; i < area.length; i++){
            for(int j = 0; j < area[0].length; j++){
                if(area[i][j] == '1'){
                    dfs(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int i, int j){
        if(area[i][j] == '0'){
            return;
        }
        area[i][j] = '0';
        
        if( i+1 < area.length ){
            dfs(i+1, j);
        }
        if( i-1 >= 0 ){
            dfs(i-1, j);
        }
        if( j+1 < area[0].length ){
            dfs(i, j+1);
        }
        if( j-1 >= 0 ){
            dfs(i, j-1);
        }
    }
}

Solution 2

同样是dfs搜索遍历每个位置，然而这个方法使用visited[][]数组来记录点是否被访问过。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    int[][] visited;
    char[][] map;
    int[][] operations;
    public int numIslands(char[][] grid) {
        visited = new int[grid.length][grid[0].length];
        map = grid;
        int count = 0;
        operations = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(visited[i][j] == 1 || map[i][j] == '0') continue;
                dfs(i, j);
                count++;
            }
        }
        return count;
    }
    
    private void dfs(int x, int y){
        if(x < 0 || x >= map.length || y < 0 || y >= map[0].length ) return;
        if(visited[x][y] == 1 || map[x][y] == '0') return;
        visited[x][y] = 1;
        for(int[] operation : operations){
            int m = x + operation[0];
            int n = y + operation[1];
            dfs(m, n);
        }
        
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 243 words)

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

对于数组中每个数字，计算其前缀的和。
前缀[i]减去前缀[j]的差，等于[j]-[i]之间数字的和。（类似一种DP，数组可以用一个变量代替。）

因此，原题目等于寻找找 前缀[i]-前缀[j] = k。
用哈希表储存已经遍历过的前缀和出现的次数。
每次遍历时先查看哈希表内是否有当前[前缀和-k]的键在。
如果有则加入到count中。
（哈希表中需要提前放入一个0键，值等于1，为了计算[前缀和-k]等于0的情况。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int subarraySum(int[] nums, int k) {
        
        int[] sum = new int[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap();
        int count = 0;
        map.put(0, 1);
        
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
            count += map.getOrDefault(sum[i]-k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 258 words)

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

当前数字之外的积等于左边所有数字的积乘以右边所有数字的积。
因此可以维护两个数组，分别计算从左到右的乘积，和从右到左的乘积。

由于返回答案不算占用空间，因此可以将左侧乘积的数组保存在答案数组上。
然后在遍历时，从右至左遍历，使用一个变量储存右边的乘积，直接将两者的乘积更新在答案数组上。
此时空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = 1;
        
        for(int i = 1; i < nums.length; i++){
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        int rightProduct = 1;
        
        for(int j = nums.length-1; j >=0; j--){
            ans[j] = ans[j] * rightProduct;
            rightProduct *= nums[j];
        }
        return ans;   
    }
}
Follow

Recents

Archives

Links

×