您现在的位置是：首页 >技术交流 >代码随想录训练营第二天|977.有序数组的平方、209.长度最小的子数组、59螺旋矩阵网站首页技术交流

977.有序数组的平方

思路：这道题目的第一反应就是暴力解法。先将元素都平方，之后排序。
回顾：

• 三种基本的排序算法：冒泡、插入、选择
• 两种分治的排序：快排、归并。

看了代码随想录之后：双指针。

暴力解法

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 暴力解法：先平方 然后排序
        // 这里也复习了一下三个基本的排序算法（冒泡、插入、选择）和两个分治思想的排序（快排、归并）
        for(int i=0;i<nums.length;i++){
            nums[i] = nums[i] * nums[i];
        }
        if(nums.length == 1){
            return nums;
        }
        for(int i=nums.length-1;i>=0;i--){
            for(int j=0;j<i;j++){
                if(nums[j]>nums[j+1]){
                    swap(nums, j, j+1);
                }
            }
            
        }
        return nums;
    }
    public void swap(int[] nums, int i, int j){
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }
}

双指针

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 进阶：双指针
        // 新建一个数组；双指针一头一尾，找到平方之后最大的放到新数组（从后往前）
        int[] result = new int[nums.length];
        int l = 0;
        int r = nums.length-1;
        int i = nums.length -1;
            while(r>=l){
                int L = nums[l] * nums[l];
                int R = nums[r] * nums[r];
                if(L > R){
                    result[i] = L;
                    l++;
                    i--;
                }else{
                    result[i] = R;
                    r--;
                    i--;
                }
            }
        
        return result;
    }
}

LeetCode：209.长度最小的子数组
思路：中等题，一般用暴力的解法不会通过。这里采用双指针，或者是滑动窗口。
注意：题目找的是>=而不单单是=
关键点：一个sum用来求和，找到大于等于的范围就记录到result里面。（result的初始化要注意）

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 题目理解错了，这里找的是>= 而不单单是=
        // 滑动窗口：
        int size = nums.length;
        int L = 0;
        int R;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for(R=0;R<size;R++){
            sum +=nums[R];
            while(sum>=target){
                result = Math.min(result, R-L+1);
                sum = sum - nums[L];
                L++;
            }
            
        }
        return result = result==Integer.MAX_VALUE? 0 : result; // 如果最后仍然为最大值就表示没有。返回0
    }
}

LeetCode：59.螺旋数组2（需要二刷）

思路：循环遍历每个位置，把数赋值进去。
关键点：分界条件，容易弄混。

class Solution {
    public int[][] generateMatrix(int n) {
        // 细节很多
        int[][] ans = new int[n][n];
        int count = 1;
        int l = 0; int r = n-1; int t = 0; int b = n-1; 
        while(count<=(n*n)){
            for(int j=l;j<=r;j++){
                ans[t][j] = count++;
            }
            t++;
            for(int i=t;i<=b;i++){
                ans[i][r] = count++;
            }
            r--;
            for(int j=r;j>=l;j--){
                ans[b][j] =count++;
            }
            b--;
            for(int i=b;i>=t;i--){
                ans[i][l] = count++;
            }
            l++;
        }
        return ans;
    }
}

代码随想录的版本需要注意的细节更多。

class Solution {
    public int[][] generateMatrix(int n) {
        // 细节很多
        // 解法二
        int[][] ans = new int[n][n];
        int mid = n/2;
        int offset = 1;
        int loop = n/2;
        int startx = 0;int starty = 0;
        int count = 1;
        int i;int j;
        while(loop>0){
            i = startx;
            j = starty;
            for(j=starty;j<n-offset;j++){
                ans[startx][j] = count++;
            }
            for(i=starty;i<n-offset;i++){
                ans[i][j] = count++;
            }
            for(;j>startx;j--){
                ans[i][j] = count++;
            }
            for(;i>starty;i--){
                ans[i][j] = count++;
            }
            startx++;
            starty++;
            offset+=1;
            loop--;
        }
        if(n%2==1){
            ans[mid][mid] = count;
        } 
        return ans;
    }
}