第二天任務

977.有序數(shù)組的平方

題目建議： 本題關鍵在于理解雙指針思想
題目鏈接：https://leetcode.cn/problems/squares-of-a-sorted-array/
思路：找到第一個非負數(shù)，然后雙指針往兩邊從小到大排序查找。
自己的解法雖然用到了雙指針，但是太啰嗦，得用Carl的思路再實現(xiàn)一下，從index=0和index=length-1的位置從大往小排序查找。

/**
     * 雙指針解法
     * 3種情況：
     * 1. 全是負數(shù)，平方后倒序排；例如：[-5,-3,-2,-1], [-1]
     * 2. 全是正數(shù)，平方后正序排
     * 3. 從負數(shù)到正數(shù)
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {

        final int length = nums.length;
        int[] newNums = new int[length];

        // 第一個是否正數(shù)
        boolean firstPositive = nums[0] >= 0;
        // 全是負數(shù)，倒序即可
        if (!firstPositive && nums[length - 1] < 0) {
            for (int i = 0, j = length - 1; i < length && j >= 0; ) {
                newNums[i] = nums[j] * nums[j];
                i++;
                j--;
            }
            return newNums;
        }
        int right = -1;
        for (int i = 0; i < length; i++) {
            final int num = nums[i];
            if (right < 0 && num >= 0) {
                right = i;
            }
            newNums[i] = nums[i] * nums[i];
        }
        // 全是正數(shù)，正序即可
        if (firstPositive) {
            return newNums;
        }
        // 從負數(shù)，到正數(shù)
        int left = right - 1;
        int[] newNums2 = new int[length];
        int newIndex = 0;
        do {
            final int leftVal = newNums[left];
            final int rightVal = newNums[right];
            if (leftVal <= rightVal) {
                newNums2[newIndex] = leftVal;
                left--;
            } else {
                newNums2[newIndex] = rightVal;
                right++;
            }
            newIndex++;
        } while (left >= 0 && right <= (length - 1));
        // 放入剩余的數(shù)
        while (left >= 0) {
            newNums2[newIndex++] = newNums[left--];
        }
        while (right <= (length - 1)) {
            newNums2[newIndex++] = newNums[right++];
        }
        return newNums2;
    }

209.長度最小的子數(shù)組

題目建議： 本題關鍵在于理解滑動窗口，這個滑動窗口看文字講解 還挺難理解的，建議大家先看視頻講解。 拓展題目可以先不做。
題目鏈接：https://leetcode.cn/problems/minimum-size-subarray-sum/
思路：暴力解法超時了，滑動窗口的思路需要多練習。

/**
     * 雙指針，滑動窗口
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int begin = 0;
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        // 全加起來也小于目標值
        boolean lessThanTarget = true;

        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];

            // 用while不用if，因為可能出現(xiàn)[1,1,1,1,1,100]
            while (sum >= target) {
                lessThanTarget = false;
                minLen = Integer.min(end - begin + 1, minLen);

                sum -= nums[begin];
                begin++;
            }
        }

        return lessThanTarget ? 0 : minLen;

    }

59.螺旋矩陣II

題目建議： 本題關鍵還是在轉(zhuǎn)圈的邏輯，在二分搜索中提到的區(qū)間定義，在這里又用上了。
題目鏈接：https://leetcode.cn/problems/spiral-matrix-ii/
思路：這種題第一次見到，以為會有高深的算法，其實主要是考慮清楚邏輯，然后處理邊界值的問題，根據(jù)Carl的思路寫出了解法。

public int[][] generateMatrix(int n) {

        int[][] result = new int[n][n];

        // 轉(zhuǎn)幾圈
        int circleCount = n / 2;

        int startX = 0;
        int startY = 0;
        int count = 1;
        int offset = 1;
        int val = 1;

        while (count <= circleCount) {

            int x = startX, y = startY;
            //第1條邊：從左到右
            for (; x < n - offset; x++) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            //第2條邊：從右上到右下
            for (; y < n - offset; y++) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            //第3條邊：從右下到左下
            for (; x >= offset; x--) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            //第4條邊：從左下到左上
            for (; y >= offset; y--) {
                result[y][x] = val++;
//              System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
            }

            // 圈數(shù)增加
            count++;
            startX++;
            startY++;
            offset++;

        }
        // 如果是奇數(shù)，填補中間的數(shù)
        if (n % 2 != 0) {
            result[startX][startY] = val;
        }
        return result;
    }