数组类型

发表于 更新于 分类于 阅读次数： Valine：

刷题路线和资料来自：代码随想录知识星球 | 代码随想录 (programmercarl.com)

理论基础

数组在Java中的存储与赋值机制Java中基本数据类型赋值机制与数组的赋值机制 | 偷掉月亮 (moonshuo.cn)

可以知道在Java中数组值存储在堆中，而在栈空间中存储的是数组的地址，与基本数据类型不同

image-20220331123609262

二分查找

704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while (left<=right){
            int mid =(left+right)/2;
            if (nums[mid]==target){
                return mid;
            }
            if (target>nums[mid]){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return -1;
    }
}

上面的二分查找用法是两边都闭合的，所以可以肯定int right=nums.length-1;如果是两边的闭合不同，需要使right值取值不同。

移除元素

27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)

巧妙交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
每一次找到之后，将找到的数与最后一个数交换，并将length--，防止死循环，同时i--，将交换过来的数在检查一次！！！
class Solution {
   public int removeElement(int[] nums, int val) {
        int length=nums.length;
        for (int i=0;i<length;i++){
            if (nums[i]==val){
                int temp=nums[length-1];
                nums[nums.length-1]=nums[i];
                nums[i]=temp;
                i--;
                length--;
            }
        }
        return length;
    }
}

双指针法

快慢指针都从0开始，如果遇到目标的数，看快指针增加一，满指针不改变，但是一旦遇到不是目标的数，慢指针立即接受快指针的数，将的目标数覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeElement(int[] nums, int val) {

        // 快慢指针
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;

    }
}

有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode） (leetcode-cn.com)

暴力解法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] sortedSquares(int[] nums) {
        int length=nums.length;
        for (int i=0;i<length;i++){
            nums[i]=nums[i]*nums[i];
        }
        Arrays.sort(nums);
        return nums;
        
    }
}

双指针

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) {
        int length=nums.length;
        int []array=new int[length];
        int right=array.length-1;
        int flag=array.length-1;
        int left=0;
        while (right>=left) {
            if (Math.abs(nums[right]) >= Math.abs(nums[left])) {
                array[flag]=nums[right]*nums[right];
                flag--;
                right--;
            }
            else {
                array[flag]=nums[left]*nums[left];
                flag--;
                left++;
            }

        }
        return array;
    }
}

长度最小的子数组

暴力解法

这里是求连续的数组，所以可以确定开始的位置，和结束的位置，就可以确定所有的情况，不需要去考虑太多情况

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
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int length=nums.length;
        int result=length;
        boolean flag=false;
        for (int i=0;i<length;i++){
            int sum=0;
            for (int j=i;j<length;j++){
                sum=sum+nums[j];
                if (sum>=target){
                    if (result>=j-i+1){
                        flag=true;
                        result=j-i+1;
                        break;
                    }
                }
            }
        }
        if(flag){
            return result;
            }else{
                return 0;
            }
    }
}

滑动窗口

我的错误解法，忽略的窗口滑动过程中窗口的逐渐缩小的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minSubArrayLen(int target, int[] nums) {
    int slowIndex;
    int fastIndex=0;
    int result=nums.length;
    int sum=0;
    boolean flag=false;
    for (slowIndex=0;fastIndex<nums.length;fastIndex++){
        sum=sum+nums[fastIndex];
        if (sum>=target&&result>=fastIndex-slowIndex+1){
            flag=true;
            sum=sum-nums[slowIndex]-nums[fastIndex];
            result=fastIndex-slowIndex+1;
            slowIndex++;
            fastIndex--;
        }

    }
    if(flag){
        return result;
    }else{
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        //利用result的赋值巧妙赋值避开result=num.length的错误
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

代码随想录 (programmercarl.com)

螺旋矩阵

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.Arrays;

public class Solution {
    /*我们
    1.首先需要确定在何时转弯
    2.向什么方向放生转弯*/
    public int[][] generateMatrix(int n) {
        int [][]array=new int[n][n];
        //代表当前填充的数
        int num=1;
        //代表每一组已经填充的数
        int count=0;
        //flag代表圈数
        int flag=0;
        //代表方向
        int position=1;
        int hang=n;
        int temp=n;
        if (n%2!=0){
            array[n/2][n/2]=hang*hang;
        }
        while (num<=hang*hang&&temp>0){
            count=0;
            if (position==1){
            while (count<temp-1){
                array[flag][flag+count]=num;
                num++;
                count++;
                }
                position++;
            }
            else if (position==2){
            while (count<temp-1) {
                array[count+flag][n - flag-1] = num;
                num++;
                count++;
                }
            position++;
            }
            else if (position==3){
                while (count<temp-1){
                    array[n-flag-1][n-count-flag-1]=num;
                    count++;
                    num++;
                }
                position++;
            }
            else if (position==4){
                while (count<temp-1){
                    array[n-count-flag-1][flag]=num;
                    num++;
                    count++;
                }
                position=1;
                flag++;
                temp=temp-2;
            }
            else {break;}

        }

        return array;
    }



    public static void main(String[] args) {
       Solution solution=new Solution();
       System.out.println(Arrays.deepToString(solution.generateMatrix(3)));
       //System.out.println(solution.minSubArrayLe2(4, new int[]{1,4,4}));
    }
}

在判断时候，一定要对其进行分组，并且注意二维数组的行列等等

总结

  1. 对于数组要删除的元素，是不能完成删除的，但是可以将这个进行覆盖，利用双指针方法可以巧妙将删除的数进行覆盖（图片来自代码随想录 (programmercarl.com)），当然也可以将其和最后的一个交换。27.移除元素-双指针法

  2. 而对于要求数组连续的值，可以使用双指针的变形，滑动窗口方法进行破解。图片来自代码随想录 (programmercarl.com)

    209.长度最小的子数组

  3. 而对于螺旋矩阵，需要思路清晰，分析好每一个方向的情况，同样比较复杂的其他情况要进行分类。