CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第二天| 977,209,59,54

Posted on

LeetCode.977 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * as the array is non-decreasing, thus we are sure that the elment that 
 * has the largest squre must be at two end. 
 */
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0; 
        int right = nums.length - 1;

        int[] ans = new int[nums.length];

        for (int i = ans.length - 1; i >= 0; i--) {
            if (Math.abs(nums[left]) >= Math.abs(nums[right])) {
                ans[i] = nums[left] * nums[left];
                left++;
            } else {
                ans[i] =  nums[right] * nums[right];
                right--;
            }
            
        }
        return ans;
    }
}

双指针方法的简单应用

LeetCode.209 长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int sum = 0;
        for(int slowIndex = 0, fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            sum += nums[fastIndex];
            while (sum >= target) {
                ans = Math.min(ans, fastIndex - slowIndex + 1);
                sum -= nums[slowIndex++];
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

注意slowIndex的更新应该使用while循环，更新直到sum<target

LeetCode.59 螺旋矩阵II

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
class Solution {
    public int[][] generateMatrix(int n) {

        int[][] ans = new int[n][n];
        int l = 0, r = n - 1, t = 0, b = n - 1; 
        int cnt = 1;

        while(cnt <= n*n) {
          
            for (int i = l; i <= r; i++) {
                ans[t][i] = cnt++;
            }
            t++;

            for (int i = t; i <= b; i++) {
                ans[i][r] = cnt++;
            }
            r--;

            for (int i = r; i >= l; i--) {
                ans[b][i] = cnt++;
            }
            b--;

            for (int i = b; i >= t; i--) {
                ans[i][l] = cnt++;
            }
            l++;
        }

        return ans;

    }
}

对比了一下我的方法和Carl的方法，我写的这个等于是纯粹模拟行为，感觉思维量更少一点，更straightforward.

LeetCode.54 螺旋矩阵

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
38
39
40
41
42
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0, r = n - 1, t = 0, b = m - 1; 

        int cnt = 0;
        List<Integer> ans = new ArrayList<>();

        // && cnt < m * n
        // because this matrix is not a square, 
        while ( cnt < m*n) {
            for (int i = l; i <= r && cnt < m * n; i++) {
                ans.add(matrix[t][i]);
                cnt++;
            }
            t++;


            for (int i = t; i <= b && cnt < m * n; i++) {
                ans.add(matrix[i][r]);
                cnt++;
            }
            r--;

            for (int i = r; i >= l && cnt < m * n; i--) {
                ans.add(matrix[b][i]);
                cnt++;
            }
            b--;

            for (int i = b; i >= t && cnt < m * n; i--) {
                ans.add(matrix[i][l]);
                cnt++;
            }
            l++;
        }

        return ans;
    }
}

这一题的思路和螺旋矩阵II类似，但是注意由于矩阵不是正方形的，每一次循环后要check是否已经完成遍历，避免重复打印。