Leet Code初级算法-数组

发表于 阅读次数：
本文字数： 10k 阅读时长 ≈ 9 分钟

Snipaste_2023-01-08_01-58-08

Leet Code初级算法-数组

1、删除排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致

不要使用额外的空间，你必须在原地修改输入数组** 并在使用 O(1) 额外空间的条件下完成

示例1

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

思路

使用双指针

  • 如果右指针指向的值等于左指针指向的值，左指针不动
  • 如果右指针指向的值不等于左指针指向的值，那么左指针往右移一步，然后再把右指针指向的值赋给左指针

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int removeDuplicates(int[] nums) {

       // 检验数组临界值
        if(null == nums || nums.length == 0){
            return 0;
        }
        // 左指针指向位置
        int left = 0;

        // 声明一个右指针，开始移动右指针，
        for(int right = 1; right < nums.length; right++){
            // 右指针指向的位置与左指针指向的位置数据进行比较，如果相同右指针继续右移，如果不同，左指针向右移动一位并且将右指针指向的数据进行赋值
            if(nums[right] != nums[left]){
                nums[++left] = nums[right];
            }
        }
        // 因为小标是从0开始的，所以长度需要进行+1，这里要++left，你懂得，不懂的去看下++i和i++的区别
        return ++left;
    }

2、买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例1

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

示例2

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

思路

首先购买股票要获取利润，所以检验卖出的比前一天购入的大于0，统计总获取利润即可

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxProfit(int[] prices) {
        // 检验数组临界值
        // 检验数组临界值
        if(null == prices || prices.length == 1){
            return 0;
        }

        // 初始化获取的利润
        int max = 0;
        
        // 循环每天的股票详情
        for(int i = 0; i < prices.length - 1; i++){
            // 进行校验，检验获取购买股票获取的利润
            if(prices[i] < prices[i + 1]){
                max = max + prices[i + 1] - prices[i];
            }
        }
        
        // 返回获取的利润
        return max;
    }

3、旋转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例1

1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

思路

思路1，临时数组的方式

声明一个临时数组的方式，将数组放到新的数组里面，然后将其放入对应位置即可，关键算法**(i + k) % length**

思路2，反转的形式

数组反转的形式，就是你可以将数组反转，全反转先后都行，然后在根据指定位置进行反转

思路3，看成是一个环

把数组看成是一个环，然后把当前值保存在下一个位置，保存之前把下一个位置的值给记录下来，

实现代码

声明一个临时数组的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void rotate(int[] nums, int k) {

        /**
        声明一个临时数组的方式
         */
        // 声明一个新的数组长度
        int length = nums.length;

        // 声明一个新的数组
        int array[] = new int[length];

        // 将原数组存入新的数组中
        for(int i = 0; i < length; i++){
            array[i] = nums[i];
        }

        // 将新的数组中的数据存入对应移动后的位置
        for(int i = 0; i < length; i++){
            nums[(i + k) % length] = array[i];
        }
}

数组反转的方式

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
public void rotate(int[] nums, int k) {
		/**
        数组反转的形式
         */
        // 获取数组的长度
        int length = nums.length;
        // 对数组长度区域拿到在数组范围内的移动位置k
        k %= length;
        // 数组全部反转
        reverse(nums,0,length - 1);
        // 反转前k个元素
        reverse(nums,0,k - 1);
        // 反转剩余的元素
        reverse(nums,k,length - 1);
}
/**
    反转的方式的反转方法
     */
public void reverse(int[] nums,int start,int end){
    // 循环遍历、交换位置
    while(start < end){
        int temp = nums[start];
        nums[start++] = nums[end];
        nums[end--] = temp;
    }
}

数组看做成环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void rotate(int[] nums, int k) {
    /**
        将数组看成一个环
         */
    int hold = nums[0];
    int index = 0;
    int length = nums.length;
    boolean[] visited = new boolean[length];
    for (int i = 0; i < length; i++) {
        index = (index + k) % length;
        if (visited[index]) {
            //如果访问过，再次访问的话，会出现原地打转的现象，不能再访问当前元素了，我们直接从他的下一个元素开始
            index = (index + 1) % length;
            hold = nums[index];
            i--;
        } else {
            //把当前值保存在下一个位置，保存之前要把下一个位置的值给记录下来
            visited[index] = true;
            int temp = nums[index];
            nums[index] = hold;
            hold = temp;
        }
    }
}

4、存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例1

1
2
输入：nums = [1,2,3,1]
输出：true

示例2

1
2
输入：nums = [1,2,3,4]
输出：false

思路

思路1，双指针遍历

给数组先排序，然后使用双指针遍历一下

思路2，Set集合

使用Set集合，将数据添加到Set集合中，因为Set集合数据不允许重复

实现代码

双指针遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean containsDuplicate(int[] nums) {
    // 声明一个左指针
    int left = 0;
    // 排序
    Arrays.sort(nums);
    // 移动右指针
    for(int right = 1; right <= nums.length - 1; right++){
        // 如果移动右指针过程中没有遇见相同的值，则将左指针向右移动一位，据需进行判断
        if(nums[left] != nums[right]){
            left++;
        }else{
            return true;
        }
    }
    return false;
}

Set集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean containsDuplicate(int[] nums) {
    
    // 使用HashSet集合，因为HashSet集合不允许有重复值，声明一个Set集合
    Set<Integer> set = new HashSet();

    // 遍历数组
    for(int num : nums){
        // 插入数据，如果插入失败，说明出现重复值，反之则没有出现重复值
        if(!set.add(num)){
            return true;
        }
    }

    return false;
}

5、只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例1

1
2
输入：nums = [2,2,1]
输出：1

示例2

1
2
输入：nums = [4,1,2,1,2]
输出：4

思路

思路1，做异或

连续做异或

异或规则

a ^ 0 = a

a ^ a = 0

a ^ b ^ c = a ^ c ^ b

大白话：与0异或是自己本身，相同异或为0，多个异或符合交换律

思路2，Set集合

使用Set集合，因为Set集合数据不允许重复

实现代码

异或

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int singleNumber(int[] nums) {

    /**
        连续做异或
        异或规则
        a ^ 0 = a
        a ^ a = 0
        a ^ b ^ c = a ^ c ^ b
        大白话：与0异或是自己本身，相同异或为0，多个异或符合交换律
         */
    // 声明一个结果
    int result = 0;

    // 循环遍历并做异或
    for(int num : nums){
        result ^= num;
    }
    // 返回异或后的结果
    return result;
}

Set集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int singleNumber(int[] nums) {
    /**
        使用Set集合，因为Set集合数据不允许重复
         */
    // 声明一个Set集合
    Set<Integer> set = new HashSet();

    // 循环遍历
    for(int num : nums){
        // 向Set集合中添加值，如果不允许添加则说明数据重复，则移除次值
        if(!set.add(num)){
            set.remove(num);
        }
    }
    // 因为添加之后Set集合中只有一个数据，所以拿到这个数据即可
    return (int)(set.toArray()[0]);
}

6、两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例1

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例2

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

思路

思路1

现将两个数组排序，然后声明连个指针，判断两个数组大小，然后一次移动相对应指针即可，相等时，存入List集合，然后转成新的数组即可

思路2

先将一个数组存入Map集合中，key为数组值，value为出现的次数，然后遍历第二个数组，将第二个数组存入map集合，如果存在，则存入List集合中，并将出现的次数减少1，不存在则存入map集合中

实现代码

两个指针

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
public int[] intersect(int[] nums1, int[] nums2) {

        /**
        两个指针处理
         */
        // 声明List
        List<Integer> list = new ArrayList();

        // 声明两个变量
        int i = 0;

        int j = 0;

        // 将两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        // 遍历两个数组
        while(i < nums1.length && j < nums2.length){
            // 当第一个数组大于第二个数组时将第二个数组的指针后移
            if(nums1[i] > nums2[j]){
                j++;
            // 当第一个数组小于第二个数组时将第一个数组的指针后移
            }else if(nums1[i] < nums2[j]){
                i++;
            }else{
            // 当两个数组相等时，添加到集合中，两个指针后移
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        // 声明新的并声明长度为List集合的长度
        int[] array = new int[list.size()];

        // 将集合中的元素放入到数组中
        for(int k = 0; k < array.length; k++){
            array[k] = list.get(k);
        }
        
        // 返回数组
        return array;
    }

map集合

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
public int[] intersect(int[] nums1, int[] nums2) {

        /**
        使用Map集合方式
         */
        // 声明一个Map集合
        Map<Integer,Integer> map = new HashMap();

        // 声明一个List集合
        List<Integer> list = new ArrayList();

        // 遍历数组1
        for(int i = 0; i < nums1.length; i++){
            // 将数组中元素存入Map，key为数组元素，value为数组元素出现的次数
            map.put(nums1[i],map.getOrDefault(nums1[i], 0) + 1);
        }

        // 遍历数组2
        for(int i = 0; i < nums2.length; i++){
            // 判断数组2中元素是否在Map集合中，如果存在
            if(map.getOrDefault(nums2[i], 0) > 0){
                // 将存在的元素存入list集合中，说明是两个数组的交集
                list.add(nums2[i]);
                // 将map集合中对应的数据出现的次数-1
                map.put(nums2[i],map.get(nums2[i]) - 1);
            }
        }

        // 声明新的数组，长度为list集合的长度
        int[] array = new int[list.size()];

        // 将集合中的元素存入数组中
        for(int i = 0; i < array.length; i++){
            array[i] = list.get(i);
        }

        // 返回数组
        return array;
    }

7、加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例1

1
2
3
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

思路

从最后一位开始遍历数组，如果最后一位不为9，将最后一位+1，如果为9，标记为0，继续，如果元素都为9，则扩充数组长度将第一位元素设置为1即可

实现代码

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[] plusOne(int[] digits) {

        // 遍历数组
        for(int i = digits.length - 1; i >= 0; i--){
            // 判断最后一个值是否为9，如果不为9则+1返回，如果为9，则将其设置为0，继续遍历
            if(digits[i] != 9){
                digits[i]++;
                return digits;
            }else {
                digits[i] = 0;
            }
        }

        // 走到这里说明数组全部为9，则需要扩充数组长度
        int[] array = new int[digits.length + 1];

        // 讲数组第一个元素设置为1
        array[0] = 1;

        // 返回扩充后的数组
        return array;

    }

8、移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例1

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

思路

思路1

双指针，如果指针指向位置不为0，则两个指针都向后移，否则只移动i指针，然后从从index指针开始,后面的内容赋值为0即可

思路2

交换位置，只要不为0，就开始交换位置

实现代码

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void moveZeroes(int[] nums) {
        
        /**
        双指针遍历，不为0即赋值后面的新值，后面全部赋值为0
         */
        // 声明指针指向0位置
        int index = 0;
        // 遍历数组
        for(int i = 0; i < nums.length; i++){
            // 如果指针指向位置不为0，则两个指针都向后移，否则只移动i指针
            if(nums[i] != 0){
                nums[index++] = nums[i];
            }
        }

        // 从index指针开始,后面的内容赋值为0即可
        while(index < nums.length){
            nums[index++] = 0;
        }
    }

交换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void moveZeroes(int[] nums) {
        
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            //只要不为0就往前挪
            if (nums[j] != 0) {
                //i指向的值和j指向的值交换
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;

                i++;
            }
        }
    }

9、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例1

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例2

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

思路

思路1

暴力破解法 两遍for循环

思路2

Map集合，判断target - 当前值是否能在map中取出，能取出则返回符合条件的下标和当前下标，反之将当前值当做key，当前下标记为value

实现代码

两遍for循环

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


        /**
        暴力破解法 两遍for循环
         */
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }

        return new int[]{-1,-1};

Map集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum(int[] nums, int target) {

        // 声明一个Map集合
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 判断target - 当前值是否能在map中取出，能取出则符合条件
            if (map.get(target - nums[i]) != null) {
                // 返回符合条件的下标和当前下标
                return new int[]{map.get(target - nums[i]), i};
            }
            // 将当前值当做key，当前下标记为value
            map.put(nums[i], i);
        }
        // 为0时返回0
        return new int[]{0, 0};
    }

10、有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例

数独示例1.png

输入：board =
[[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出：true

思路

现有知识不理解、有大佬懂得可以教一教我

实现代码

11、旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

思路

想将二位数组上下交换位置，然后按照对角线进行交换即可

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void rotate(int[][] matrix) {
        /**
        二位数组交换顺序
         */
        // 循环遍历将上下数组交换顺序
        for(int i = 0; i < matrix.length / 2; i++){
            int[] temp = matrix[i];
            matrix[i] = matrix[matrix.length - i - 1];
            matrix[matrix.length - i - 1] = temp;
        }
        
        // 按照对角线交换顺序
        for(int i = 0; i < matrix.length - 1; i++){
            for(int j = i + 1; j < matrix.length; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

正确的开始 微小的长进 然后持续 嘿 我是小博 带你一起看我目之所及的世界……

-------------本文结束 感谢您的阅读-------------

本文标题:Leet Code初级算法-数组

文章作者:小博

发布时间:2023年01月08日 - 02:25

最后更新:2023年01月08日 - 02:27

原始链接:https://codexiaobo.github.io/posts/2501102455/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。