数组

leetcode 59 螺旋数组2

看到题目的第一想法
注意边界值的处理，使用左闭右开的形式，每一次循环的时候都不处理一条边的最后一个值，把它让到下一次处理。并且作为n如果为奇数的话，就要对最中间的值进行处理。
一开始写的代码如下所示，这里我没有考虑到如果是n=5,7…等等大数的时候，循环的话，每一次都要对起始点进行处理，但是我还是使用i,j两个值，这就会报错。因为i，j是每次循环的起始点是不一样的。因为到下一次循环的时候，i，j赋值的值又是0所以肯定有问题。

 int[][] arr= new int[n][n];
        int count=1;
        int offset=1;
        int i=0,j=0;
        int startx=0;
        int starty=0;
        while((n/2)!=0){
            for(j=0;j<n-offset;j++){
                arr[startx][j]=count++;
            }
            for(i=0;i<n-offset;i++){
                arr[i][j]=count++;
            }
            for(;j>starty;j--){
                arr[i][j]=count++;
            }
            for(;i>startx;i--){
                arr[i][j]=count++;
            }
            startx++;
            starty++;
            offset++;
        }

看完题解后的想法
思路没问题，主要就是起始点的变化要处理
这里我设置了两个值startx,starty用来表示每次开始的起点，而且注意offeset也就是循环到内部的话，这个时候是要offet+=2的。因为我们要再减去一个数而且循环要做减法操作，不然一直是死循环。每次循环都要更新起点这样就可以了。i，j的初始起点也是变化的。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] arr= new int[n][n];
        int count=1;
        int offset=1;
        int i=0,j=0;
        int startx=0;
        int starty=0;
        int loop=n/2;
        while(loop!=0){
            for(j=starty;j<startx+n-offset;j++){
                arr[startx][j]=count++;
            }
            for(i=startx;i<starty+n-offset;i++){
                arr[i][j]=count++;
            }
            for(;j>starty;j--){
                arr[i][j]=count++;
            }
            for(;i>startx;i--){
                arr[i][starty]=count++;
            }
            startx++;
            starty++;
            offset+=2;
            loop--;
        }
        if(n%2==1){
            int mid=n/2;
            arr[mid][mid]=count;
        }
        return arr;
    }
}

遇到的困难
没有想到起始点是要一直变化的，而且循环要做–操作，比如n=3，那么n/2=1所以当做完一次循环之后就结束了。

leetcode 977 有序数组平方

看到题目的第一想法
看到题目的第一想法就是把每一项求平方之后然后sort一下。
看完题解后的想法
但是显然这不是考察的意图。使用双指针，头一个，尾一个，然后求平方比大小。
分别让两个指针做++或–操作，但是思路刚开始外面使用一个循环来控制，这里逻辑是对的，但是没有注意到slow<fast还是slow<=fast，可以举例，当slow<fast时，最后会剩余一个元素没有加到数组中会造成失败。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int slow=0;
        int fast=nums.length-1;
        int[] arr = new int[nums.length];
        for(int i=nums.length-1;i>=0 && slow<fast;){
            if(nums[slow]*nums[slow]>nums[fast]*nums[fast]){
                arr[i]=nums[slow]*nums[slow];
                slow++;
            }else{
                arr[i]=nums[fast]*nums[fast];
                fast--;
            }
            i--;
        }
        return arr;
    }
}

还有一种情况就是，我没有注意到循环的是从高到低还是从低到高。这里是有讲究的，因为题目要求最后以从小到大的形式输出数组，所以我们需要把最大的数放到最后，然后依次往前，这样返回数组就是从小到大的。注意下面也是犯了没有slow<=fast的情况。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int slow=0;
        int fast=nums.length-1;
        int[] arr = new int[nums.length];
        for(int i=0;i<nums.length && slow<fast;){
            if(nums[slow]*nums[slow]<nums[fast]*nums[fast]){
                arr[i]=nums[slow]*nums[slow];
                slow++;
            }else{
                arr[i]=nums[fast]*nums[fast];
                fast--;
            }
            i++;
        }
        return arr;
    }
}

修改代码后，让其可以覆盖到所有的元素

class Solution {
    public int[] sortedSquares(int[] nums) {
        int slow=0;
        int fast=nums.length-1;
        int[] arr = new int[nums.length];
        for(int i=nums.length-1;i>=0 && slow<=fast;){
            if(nums[slow]*nums[slow]>nums[fast]*nums[fast]){
                arr[i]=nums[slow]*nums[slow];
                slow++;
            }else{
                arr[i]=nums[fast]*nums[fast];
                fast--;
            }
            i--;
        }
        return arr;
    }
}

遇到的困难
一个是没有注意过slow<=fast这个条件，到低是小于还是小于等于。而且循环的遍历条件要注意。

leetcode 209 长度最小子数组

看到题目的第一想法
第一想法是使用双指针，两个指针，一个不断的向前读取元素，求和，另一个只要当元素等于target的时候就再做++操作。但是这里取大于还是大于等于不清楚。
for(fast=slow;slow<fast && fast<nums.length;fast++){
sum+=nums[fast];
if(sum==target){
minlength=fast-slow+1;
result=result>minlength?minlength:result;
slow++;
}else if(sum>target){
slow++;
}
}
这里逻辑看上去没毛病，其实仔细推一下，每次把slow的值赋给fast，然后又要求slow<fast，这是错误的。不能操作指针。
错误代码如下：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength;
        int sum=0;
        int result=Integer.MAX_VALUE;
        int slow=0;
        for(int fast=slow;slow<=fast && fast<nums.length;fast++){
            sum+=nums[fast];
            if(sum==target){
                minLength=fast-slow+1;
                result=result>minLength?minLength:result;
                slow++;
            }else if(sum>target){
                slow++;
            }
        }
        return result==Integer.MAX_VALUE?0:result;
    }
}

看完题解后的想法
要采用双指针，和我的想法一样，但是再做操做的时候，只要出现大于等于target就把sum-=nums[slow++];减去nums[slow]的值，而且注意，可能这里的值剪完之后依然大于target，所以必须放到while循环内处理。
正确代码如下

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength;
        int sum=0;
        int result=Integer.MAX_VALUE;
        int slow=0;
        for(int fast=0;slow<=fast && fast<nums.length;fast++){
            sum+=nums[fast];
            while(sum>=target){
                minLength=fast-slow+1;
                result=result>minLength?minLength:result;
                sum-=nums[slow++];
            }
        }
        return result==Integer.MAX_VALUE?0:result;
    }
}