双指针

4. 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] sortedSquares(int[] nums) {
    if(nums.length ==1){
        nums[0]=nums[0]*nums[0];
        return nums;
    }
    int right =nums.length-1;
    int[]arr = new int[right+1];
    //1.刚开始直接在原数组上面进行修改发现偶数长度的数组无法正确返回
    //2.一开始没有正确理解双指针的含义，将j和right混淆惹
    //i和j分别为左右指针，right为数组的下标，并new了一个新数组进行排序返回
    for(int i =0,j = nums.length-1;i<=j;){
        if(nums[i]*nums[i] < nums[j]*nums[j]){
            arr[right--] = nums[j]*nums[j];
            j--;
        }else{
            arr[right--] = nums[i] *nums[i];
            i++;
        }
    }
    return arr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func sortedSquares(nums []int) []int {
    //新建数组语法：make
    len := len(nums)
    ans := make([]int,len)
    i , j ,n := 0,len-1,len-1
    for  ; i <= j ; {
        lm,rm := nums[i]*nums[i] , nums[j]*nums[j]
        if lm < rm {
            ans[n] = rm
            j--
        }else{
            ans[n] = lm
            i++
        }
        n--
    }
    return ans
}

犯了一个错误：

  • ans := make([]int, len) 创建了一个长度为 len，容量与长度相同的切片。这意味着切片的初始容量被设置为 len，并且切片中的所有元素都被初始化为整数类型的零值（0）。

  • ans := make([]int, 0, len) 创建了一个长度为 0，容量为 len 的切片。这意味着切片的初始长度为 0，但其容量为 len。这样做的好处是可以在之后通过追加元素的方式动态地增加切片的长度，而不需要重新分配内存空间。

滑动窗口

文章：代码随想录 (programmercarl.com)

视频：拿下滑动窗口！ | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili

【收获】

  • 需要使用while来持续维持滑动窗口中sum的值小于目标值

  • 滑动窗口的思想：使用一个for循环进行遍历，如何移动起始位置

1
for( j  ...) //j指向的是终止位置
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 sum = 0 ;
        int right =0;
        int res = nums.length+1;//修正：不会出现比数组长度还大的结果，所以不用初始化为Integer.MAX_VALUE
        //一开始混淆了j是终止位置的含义，把j当作是左指针，right当作右指针
        //后面返过去看了视频的伪代码之后发现，j为右指针，right是左指针
        for(int j = 0 ; j < nums.length;j++){
            sum += nums[j];
            //通过while来循环获取子串的最短长度
            while(sum >= target){
                int len = j - right +1;
                res = Math.min(res,len);
                sum -= nums[right];
                right++;
            }
        }
        return res == nums.length+1? 0:res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func minSubArrayLen(target int, nums []int) int {
    sum , ans := 0,len(nums)+1 //ans不会出现比数组长度还大的结果，所以初始化为len+1就很合适！
    i,j := 0,0
    
    for ;j<len(nums);j++ {
        sum += nums[j]
        for target <= sum {
            l := j - i + 1
            //避免了写min函数的定义
            if ans > l{  //取最小值，写的时候写反惹（哽住）
                ans = l
            }
            sum -= nums[i]
            i++
        }
    }
    if ans == len(nums)+1 {
        return 0
    }
    return ans
}

【一条插播】

img

第一百题终于达到啦~！虽然说现在已经大三了，一百题这个进度已经处于落后位置惹。

但是没有关系！从现在开始，一定能学好算法的！

(图片我是真的传不上来呜呜呜)

螺旋矩阵

文章：6. 螺旋矩阵II

视频讲解：一入循环深似海 | LeetCode：59.螺旋矩阵II_哔哩哔哩_bilibili

遵循循环不变量原则

量：对边的每一条处理规则

本题统一使用左闭右开的处理规则

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
43
class Solution {
    public int[][] generateMatrix(int n) {
        int[][]a = new int[n][n];
        //x y 用来放起始位置
        int start =0; //每次循环的开始点
        int count =1;
        int loop = 0;  //新增维持while循环
        //int offset = 0;   和loop的功能一样的
        int mid = n/2;
        int i,j;//ij提出来
        while(loop++ < n/2){
            //1->3横向
            //不是n-1,是减去边缘（边缘数值会变化）
            for(j =start;j < n-loop;j++ ){
                a[start][j] = count++;
            }
            //3->5竖向
            for(i=start ;i < n-loop;i++){
                a[i][j] = count++;
            }
            //5->7横向
            //不是>=0,需要控制边缘
            for(;j >= loop;j-- ){
                a[i][j] = count++;
            }
            //7->9竖向
            //不是>=0,需要控制边缘
            for(;i >=loop;i--){
                a[i][j] = count++;
            }
            
            /*startx++;
            starty++;
            loop--;
            offset+=1;*/
            start++;
        }
        if(n%2 == 1 ){
                a[mid][mid] = count;
        }
        return a;
    }
}
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
43
func generateMatrix(n int) [][]int {
	startx , starty := 0,0
    //对整型的赋值!
    var mid int = n/2
    var loop int = n/2
    offset := 1
    counts := 1
    //声明
    a := make([][]int,n)
    //完成对int[][]的初始化
    for i:=0;i<n;i++{
        a[i] = make([]int,n)
    }
    for loop >0{
        i,j := startx,starty
        //注意：该处不应该使用短变量声明:= ，因为我们要将j的值带出下列的函数体
        for j = starty;j < n-offset ; j++{  
            a[startx][j] = counts
            counts++
        }
        for i = startx ; i < n-offset;i++{
            a[i][j] = counts
            counts++
        }
        for ;j>starty;j--{
            a[i][j] = counts
            counts++
        }
        for ;i> startx;i--{
            a[i][j] = counts
            counts++
        }
        startx++
        starty++
        loop-- //别写错惹
        offset++
    }
    //不要漏了
    if(n%2 ==1 ){
        a[mid][mid] = counts
    }
    return a
}

【算法总结】

  • 双指针注意不要混淆左右指针的用途
    • 涉及数组修改，可以考虑将值存储到新的数组里面，而不是在原数组的基础上修改
  • 滑动窗口注意不要混淆初始指针和新增指针的用途
    • 比较最小值时可以考虑将res初始化为len(nums)+1，因为值都不会比len(nums)+1大
  • 螺旋数组需要分清每个变量的用途，清晰的控制数组边缘，while循环里面的每个变量要清楚其作用范围

【语言总结】

  •  //声明
    a := make([][]int,n)
 //对整型的赋值!
    var mid int = n/2
    var loop int = n/2
 
//注意：该处不应该使用短变量声明:= ，因为我们要将j的值带出下列的函数体
    for j = starty;j < n-offset ; j++{  
        a[startx][j] = counts
        counts++
    }