LeetCode精选200道--数组篇

简介: LeetCode精选200道--数组篇

前言


写这类文章的目的就是为了提高算法能力,找个好工作


资源


刷题网站


代码随想录 (programmercarl.com)


画图软件


OneNote


笔记软件


Typoral


数组理论基础


数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力

首先要知道数组在内存中的存储方式,这样才能真正理解数组相关的面试题

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标下对应的数据。

image.png

数组中有两点需要注意:

  • 数组下标是从0开始的
  • 数组内存空间地址是连续的

因为数组的内存空间是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址

如下所示

image.png

数组的元素是不能删的,只能覆盖

Ok,来个二维数组

image.png

Java中的二维数组可能是这样排列的

同一行是连续的,不同行的地址是不连续的

image.png


二分查找


给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。


思路


这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件

二分查找涉及的很多的边界条件,逻辑比较简单,就是要注意对区间的定义要清楚写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。


public class Binaryforarrays {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,7,9,12,45};
        int i = Binaryforarrays.search1(nums, 12);
        System.out.println(i);
    }
    public static int search1(int[] nums,int target){
        if (target < nums[0] || target > nums[nums.length - 1]){
            return -1;
        }
        int start = 0,end = nums.length - 1;
        while (start <= end){
            int mid = start + ((end - start) >> 1);
            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] < target){
                start = mid + 1;
            }else if (nums[mid] > target){
                end = mid -1;
            }
        }
        return -1;
    }
}


对于int mid = start + ((end - start) >> 1)解释


首先,(end-start)>>1中的>>是java中的位运算符,作用是按位向右移动一位。

什么是按位右移2位?

就是把一个数转化为2进制,左操作数按位右移右操作数指定的位数

例如:60转化为2进制为111100,那么60>>2相当于把数向右移动两位就变成了1111,1111对应10进制数就是15,所以60>>2得到15

好,也就是说(end-start)>>1就是除2,移动两位就是除4...

为什么不写除2,除4?这样写更专业!


为什么要加start


因为经过二分法分割,索引初始值不在是从0开始了


对于start = mid + 1解释


start不直接等于mid是因为前面有nums[mid] == target的判断,mid不是目标值的索引才会有下面的判断


移除元素


给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1)O(1)O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。


思路


数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。

我们用双指针法, 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。


https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/7dc4d506743343cab58f4e408a5e65da~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp


  • 时间复杂度:O(n)O(n)O(n)
  • 空间复杂度:O(1)O(1)O(1)


/**
 * 返回数组中的重复元素,并返回移出后数组的新长度
 */
public class SolutionRemoveElement {
    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;
    }
    public static void main(String[] args) {
        int[] nums = {3, 2, 2, 3};
        int val = 2;
        SolutionRemoveElement solutionRemoveElement = new SolutionRemoveElement();
        int i = solutionRemoveElement.removeElement(nums, val);
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
        System.out.println(i);
    }
}

image.png


画图理解


这个双指针后面会应用到很多,碰到这种情况多debug和自己画图理解即可

下面是我画的图

image.png

初始情况都执行索引为0的元素3

然后开始循环判断,第一个数不为目标值val所以快慢指针同时移动

第二个数是目标值,快指针继续移动,慢指针不移动

第三个数是目标值,快指针继续移动,慢指针不移动

第四个值不是目标值,快指针所在的值赋给满指针所在的值所以整个数组变成了3323,快慢指针同时移动

快指针索引等于了数组的长度停止循环,返回满指针索引


有序数组的平方


给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1: 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]

示例 2: 输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]


思路


这个图思路很清晰了,不用多解释

此时的时间复杂度为O(n)O(n)O(n)

package com.caq.array;
public class SolutionSquareAnOrderArray {
    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                result[index--] = nums[left] * nums[left];
                left++;
            } else{
                result[index--] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {-3, -2, 1, 2, 3};
        SolutionSquareAnOrderArray solutionSquareAnOrderArray = new SolutionSquareAnOrderArray();
        int[] ints = solutionSquareAnOrderArray.sortedSquares(nums);
        for (int anInt : ints) {
            System.out.print(anInt+" ");
        }
    }
}
1 4 4 9 9


长度最小的子数组


给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

输入:s = 7, nums = [2,3,1,2,4,3] 输出:2

解释:子数组 [4,3] 是该条件下的长度最小的子数组。


滑动窗口


所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果

滑动窗口也是双指针的一种,此题的时间复杂度为O(n)


思路


其实有这个好的平台我们直接去记住它这个动态,然后用代码去实现这个动态图

我想这可能是入门最快的方式


public class SlidingWindows {
    public int minSlidingWindows(int s, int[] nums) {
        int left = 0, right, sum = 0;
        int result = Integer.MAX_VALUE;
        for (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;
    }
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        SlidingWindows slidingWindows = new SlidingWindows();
        int i = slidingWindows.minSlidingWindows(7, nums);
        System.out.println(i);
    }
}


Integer.MAX_VALUE


image.png

result初始值设为2的31次方-1


Math.min


比较a,b的大小,返回值为小的那个数。

right - left + 1

这个算的是最小子数组的长度,为啥要加1呢,因为数组索引是从0开始的

就像是0到5有5-0+1个数一样,如果是1到5那就是5个数


螺旋矩阵


给定一个正整数 n,生成一个包含 1 到 n^2所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

本题并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。

这里给一个官方的结题思路,里面的动态图能很好的帮助我们理解!

螺旋矩阵 II - 螺旋矩阵 II - 力扣(LeetCode) (leetcode-cn.com)


思路


用的是官方解答的第二种方法,按层打印

看了好几遍都不明白,然后不断debug还是不行。

后来在纸上自己画了一遍给的动画图,然后手写程序,手动debug一下就明白了

image.png

中间的if(left < right && top < bottom)这是干什么的呢?

因为整体的思想right,left,top,bottom循环一轮就会往里面缩,加上这条进行判断缩小后不在继续打印了就打印打n的平方

然后还有个关键点是打印的时候要保证左开右闭或者左闭右开的原则,什么意思,第一行打印的时候,可以=right

但是打印第三行的时候right != left

上下打印也是一样,往下移动的时候=底部,那么往上移动的时候要!=top

看了好几天总于看明白了,还是太浮躁了,慢慢来~

描述的不好,以后会继续努力!!!

public class SpiralMatrix {
    public static void main(String[] args) {
        SpiralMatrix sm = new SpiralMatrix();
        int[][] ints = sm.generateMatrix3(3);
        for (int[] anInt : ints) {
            for (int i : anInt) {
                System.out.print(i + "\t");
            }
            System.out.println();
        }
    }
    public int[][] generateMatrix3(int n) {
        int num = 1;
        int[][] matrix = new int[n][n];     //定义一个二维数组
        int left = 0, right = n - 1, top = 0, bottom = n - 1;       //按层模拟
        while (left <= right && top <= bottom) {
//            将第一行赋值完成
            for (int column = left; column <= right; column++) {//column列
                matrix[top][column] = num;
                num++;
            }
//            将第二行赋值
            for (int row = top + 1; row <= bottom; row++) { //row行
                matrix[row][right] = num;
                num++;
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    matrix[bottom][column] = num;
                    num++;
                }
                for (int row = bottom; row > top; row--) {
                    matrix[row][left] = num;
                    num++;
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }
}


总结篇


基础回顾


数组是存放在连续内存空间上的相同类型数据的集合。

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。

数组的元素是不能删的,只能覆盖。


二分法


循环不变量原则,只有在循环中坚持对区间的定义,才能清楚的把握循环中的各种细节。

二分法是算法面试中的常考题,建议通过这道题目,锻炼自己手撕二分的能力


双指针法


双指针法(快慢指针法):通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。


滑动窗口


数组操作中的另一个重要思想:滑动窗口。滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n2)O(n^2)O(n2)的暴力解法降为O(n)O(n)O(n)

二维数据在内存中不是 3*4 的连续地址空间,而是四条连续的地址空间组成!


模拟行为


模拟类的题目在数组中很常见,不涉及到什么算法,就是单纯的模拟,十分考察大家对代码的掌控能力。

在这道题目中,我们再一次介绍到了循环不变量原则,其实这也是写程序中的重要原则。

相信大家又遇到过这种情况: 感觉题目的边界调节超多,一波接着一波的判断,找边界,踩了东墙补西墙,好不容易运行通过了,代码写的十分冗余,毫无章法,其实真正解决题目的代码都是简洁的,或者有原则性的,大家可以在这道题目中体会到这一点



相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
41 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
4月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
123 2
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
39 1
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
4月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
22 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
69 0