当前位置 博文首页 > 文章内容

    三分恶的博客:LeetCode通关:数组十七连,真是不简单

    作者:21344 栏目:未分类 时间:2021-11-25 22:19:33

    分门别类刷算法,坚持,进步!

    刷题路线参考:https://github.com/chefyuan/algorithm-base

          https://github.com/youngyangyang04/leetcode-master/

    大家好,我是老三,一个刷题困难户,接下来我们开始数组类型算法的刷题之旅!

    数组

    数组基础

    数组基本上是我们最熟悉的数据结构了,刚会写“Hello World”不久,接着就是“杨辉三角”之类的练习。

    数组基本结构

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

    数组结构

    上图是一个字符数组的例子。

    因为内存空间连续,所以可以直接通过下标获取对应的元素。

    但是删除就麻烦一点,相当于填坑,一个元素被移走,留下的坑,需要其它元素来填上。

    删除元素

    在Java中,多维数组的存储本质上也是一个行优先的一维数组。

    数组是引用传递

    我们都知道,在Java中的 “=” 用在基本数据类型上,是值传递,用在引用数据类型上,是引用传递。

    这一块展开可以写一篇文章,我们只简单看个例子:

    public class ArrayTest {
    
        public static void main(String[] args) {
            int[] array = {1, 2, 3};
            int[] newArray = array;
            newArray[1] = 0;
            //结果: 1 0 3
            printArray(array);
            //结果: 1 0 3
            printArray(newArray);
        }
    
    
        static void printArray(int[] data) {
            for (int d : data) {
                System.out.print(d + " ");
            }
            System.out.println();
        }
    }
    

    大家可以看到,newArray改变了,array也跟着变了。

    为什么呢?

    在Java中,数组是引用数组类型。array、newArray都是存储在栈中的引用,它们指向堆中真正存储的数组对象。

    所以改变了newArray,实际是改变了newArray指向的数组。

    数组引用传递

    这一点是我们刷题需要注意的,复制数组需要在循环中一个个复制。

    好了,接下来,让我们愉快地开始刷题吧!

    二分查找

    LeetCode704. 二分查找

    ☕ 题目:704. 二分查找 (https://leetcode-cn.com/problems/binary-search/)

    ❓ 难度:简单

    📕 描述:

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

    题目示例

    💡 思路:

    二分查找可以说我们都很熟了。

    因为数组是有序的,所以定义三个指针,low、high、mid,每次与中间指针指向的元素nums[mid]比较,

    • 相等,命中

    • 比nums[mid]大,目标元素就在(mid,high]区间;

    • 比 nums[mid]小,目标元素就在 [low,mid)区间

    二分查找

          /**
         * 704. 二分查找
         *
         * @param nums
         * @param target
         * @return
         */
        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (target == nums[mid]) {
                    return mid;
                } else if (target > nums[mid]) {
                    //target在(mid,high]区间
                    //右移
                    left = mid + 1;
                } else if (target < nums[mid]) {
                    //target 在[low,mid)区间
                    //左移
                    right = mid - 1;
                }
            }
            return -1;
        }
    

    但是这个代码还有一处问题,在哪呢?

    int mid = (left + right) / 2;

    这个地方可能会因为left和right数值太大导致内存溢出,所以应该写为int mid = left + ((right - left) >> 1);

    修改之后代码如下:

        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                 int mid=left+((right-left)>>1);
                if (target == nums[mid]) {
                    return mid;
                } else if (target > nums[mid]) {
                    //target在(mid,high]区间
                    //右移
                    left = mid + 1;
                } else if (target < nums[mid]) {
                    //target 在[low,mid)区间
                    //左移
                    right = mid - 1;
                }
            }
            return -1;
        }
    

    ⏰ 时间复杂度:O(logn)

    LeetCode35. 搜索插入位置

    ☕ 题目:35. 搜索插入位置 (https://leetcode-cn.com/problems/search-insert-position/)

    ❓ 难度:简单

    📕 描述:

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    请必须使用时间复杂度为 O(log n) 的算法。

    题目示例

    💡 思路:

    二分查找比较简单,但写对还要费点功夫,再做一道基本一样的题巩固一下。

    这道题基本一样,插入的位置可能有四种情况:

    二叉树插入位置

    • target<nums[0] : 在最左侧插入
    • target>nums[length-1] :在最右侧插入
    • target=nums[i] : 和数组中元素相同,插入位置i
    • nums[i]<target<nums[i+1] :在i位置之后插入

    代码如下:

        /**
         * 35. 搜索插入位置
         *
         * @param nums
         * @param target
         * @return
         */
        public int searchInsert(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            //target小于最左侧,或者大于最右元素
            if (target < nums[left]) {
                return 0;
            }
            if (target > nums[right]) {
                return right + 1;
            }
            while (left <= right) {
                int mid=left+((right-left)>>1);
                if (target == nums[mid]) {
                    //和数组元素相等
                    return mid;
                } else if (target > nums[mid]) {
                    //右侧
                    left = mid + 1;
                } else if ((target < nums[mid])) {
                    //左侧
                    right = mid - 1;
                }
            }
            // 在某个元素之后插入
            //因为退出条件是left==right,所以返回left或者right都可以
            return left;
        }
    

    ⏰ 时间复杂度:O(logn)

    LeetCode34. 在排序数组中查找元素的第一个和最后一个位置

    ☕ 题目:34. 在排序数组中查找元素的第一个和最后一个位置 (https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

    ❓ 难度:中等

    📕 描述:

    给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

    如果数组中不存在目标值 target,返回 [-1, -1]。

    进阶:

    • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

    题目示例

    💡 思路:

    看到时间复杂度 O(log n) ,数组有序,我们知道,二分查找该上场了。

    但是这道题有点不一样,它需要寻找边界。

    那我们怎么办呢?

    这就引入了寻找边界的二分查找。

    这道题的思路是什么呢?

    我们分别用二分查找来寻找左边界和右边界。

    一般的二分查找:

      if (nums[mid] == target) {
           return mid;
      }else if (nums[mid] < target) {
          left  = mid + 1;
      }else if (nums[mid] > target) {
          right = mid - 1;
      }
    

    注意,我们这里的返回条件是 nums[mid] == target,但是寻找边界的时候就不能这样了,因为我们不能确定mid是不是我们的边界。

    以寻找左边界为例,条件是 target <= nums[mid]的时候,我们接着往左移动。

    寻找右边界也类似。

    代码如下:

        public int[] searchRange(int[] nums, int target) {
            //左边界
            int leftBound = leftBound(nums, target);
            //右边界
            int rightBound = rightBound(nums, target);
            //不存在情况
            if (rightBound < leftBound) {
                return new int[]{-1, -1};
            }
            return new int[]{leftBound, rightBound};
        }
    
        /**
         * @return int
         * @Description: 求左边界
         */
        int leftBound(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                //往左移动
                if (target <= nums[mid]) {
                    right = mid - 1;
                } else if (target > nums[mid]) {
                    //向右移动
                    left = mid + 1;
                }
            }
            return left;
        }
    
        /**
         * @return int
         * @Description: 求右边界
         */
        int rightBound(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                //往右移动
                if (target >= nums[mid]) {
                    left = mid + 1;
                } else if (target < nums[mid]) {
                    //往左移动
                    right = mid - 1;
                }
            }
            return right;
        }
    

    ⏰ 时间复杂度:O(logn)

    双指针

    LeetCode27. 移除元素

    ☕ 题目:27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)

    ❓ 难度:简单

    📕 描述:

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

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

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

    说明:

    为什么返回数值是整数,但输出的答案是数组呢?

    请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

    你可以想象内部操作如下:

    // nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
    int len = removeElement(nums, val);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }
    

    💡 思路

    暴力解法

    暴力解法没什么好说的,和上道题类似,找到要删除的元素,把它后面的元素全部向前移动一位。

    暴力解法

    这里有两点需要注意:

    • 需要先定义变量 length 获取数组长度,因为后面我们的返回的数组长度是改变的

    • 每找到一个需要删除的值的时候,需要 i–,防止出现多个需要删除的值在一起的情况,然后漏删

    代码如下:

     public int removeElement(int[] nums, int val) {
            int length = nums.length;
            int i = 0;
            for (; i < length; i++) {
                if (nums[i] == val) {
                    for (int j = i; j < length - 1; j++) {
                        nums[j] = nums[j + 1];
                    }
                    //防止漏删
                    i--;
                    //数组长度减一
                    length--;
                }
            }
            return length;
        }
    

    ⏰ 时间复杂度:O(n²)。

    双指针法

    双指针法,是数组和链表题中非常常用的一种方法。

    这道题用双指针法怎么解决呢?

    定义两个指针,一个前,一个后。没有找到目标的时候front和after一起移动,找到目标的时候,after停下来,front接着移动,把front指向的值赋给after指向的值。

    这样一来,双指针就通过一个循环完成了双循环完成的事情。

    双指针法

    代码如下:

        public int removeElement(int[] nums, int val) {
            //定义前后指针
            int front = 0;
            int after = 0;
            for (; front < nums.length; front++) {
                if (val != nums[front]) {
                    nums[after] = nums[front];
                    after++;
                }
            }
            return after;
        }
    

    ⏰ 时间复杂度:O(n)。

    LeetCode26. 删除有序数组中的重复项

    ☕ 题目:27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)

    ❓ 难度:简单

    📕 描述:

    给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

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

    说明:

    为什么返回数值是整数,但输出的答案是数组呢?

    请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

    你可以想象内部操作如下:

    // nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
    int len = removeDuplicates(nums);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }
    

    题目示例

    💡 思路

    趁着上一道题劲儿还没缓过来,赶紧做一道基本一样的巩固一下。

    直接上代码:

        public int removeDuplicates(int[] nums) {
            int front = 1;
            int after = 1;
            for (; front < nums.length; front++) {
                if (nums[front] != nums[front - 1]) {
                    nums[after] = nums[front];
                    after++;
                }
            }
            return after;
        }
    

    ⏰ 时间复杂度:O(n)。

    LeetCode283. 移动零

    ☕ 题目:283. 移动零 (https://leetcode-cn.com/problems/move-zeroes/)

    ❓ 难度:简单

    📕 描述:

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

    示例:

    输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]
    

    说明:

    1. 必须在原数组上操作,不能拷贝额外的数组。
    2. 尽量减少操作次数

    💡 思路

    继续沿着上一道题的思路。

    • 第一步:我们可以把为零的元素先给它删掉,怎么删呢?就是LeetCode26的两个指针的删除方式
    • 第二步:但是我们这是将零移动到末尾,怎么办呢?我们把通过移动方式删除,导致数组末尾的坑用零填上就行了。

    移动零

    代码如下:

        /**
         * @return void
         * @Description: 283. 移动零
         * @author 三分恶
         * @date 2021/7/30 7:44
         */
        public void moveZeroes(int[] nums) {
            int after = 0;
            int front = 0;
            //移动元素
            for (; front < nums.length; front++) {
                if (nums[front] != 0) {
                    nums[after] = nums[front];
                    after++;
                }
            }
            //将末尾元素置为0
            for (; after < nums.length; after++) {
                nums[after] = 0;
            }
        }
    

    ⏰ 时间复杂度:O(n)。

    LeetCode977. 有序数组的平方

    ☕ 题目:977. 有序数组的平方 (https://leetcode-cn.com/problems/squares-of-a-sorted-array/)

    ❓ 难度:简单

    📕 描述:

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

    题目示例

    💡 思路

    暴力排序法

    这道题一看,最直观的做法是什么呢?

    先求数字平方的数组,然后再把新数组排序。

    代码也好写:

        /**
         * @return int[]
         * @Description: 977. 有序数组的平方-暴力法
         * @author 三分恶
         * @date 2021/7/30 8:03
         */
        public int[] sortedSquares(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                nums[i] *= nums[i];
            }
            //快排,时间复杂度O(nlogn)
            Arrays.sort(nums);
            return nums;
        }
    

    ⏰ 时间复杂度:遍历时间复杂度O(n),快排时间复杂度O(nlogn),所以时间复杂度O(n+nlogn)。

    💡 思路

    双指针法

    我们连写几道双指针了,这道题能不能用双指针实现呢?

    我们分析一下,这个数组在取平方之前,是有序的,那么它绝对值最大的数一定是在两端的。

    所以我们可以定义两个指针,一个指向最左端,一个指向最右端,比较两者平方的大小,大的平方放入结果数组,并移动指针。

    有序数组的平方

    代码如下:

       /**
         * @return int[]
         * @Description: 977. 有序数组的平方-双指针法
         * @author 三分恶
         * @date 2021/7/30 8:29
         */
        public int[] sortedSquares(int[] nums) {
            int left = 0;
            int right = nums.length - 1;
            int[] result = new int[nums.length];
            int r = nums.length - 1;
            while (left <= right) {
                int leftRes = nums[left] * nums[left];
                int rightRes = nums[right] * nums[right];
                //右边大
                if (leftRes <= rightRes) {
                    result[r] = rightRes;
                    right--;
                } else {
                    //左边大
                    result[r] = leftRes;
                    left++;
                }
                r--;
            }
            return result;
        }
    

    ⏰ 时间复杂度:O(n)。

    两数之和

    LeetCode1. 两数之和

    ☕ 题目:1. 两数之和 (https://leetcode-cn.com/problems/two-sum/)

    ❓ 难度:简单

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

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

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

    题目示例

    💡 思路:

    暴力解法

    上来我们先来个最简单的暴力解法,大家应该都知道冒泡排序吧,类似的两层循环。

    两层循环

    代码写起来也很简单:

        public int[] twoSum(int[] nums, int target) {
            int[] result = new int[2];
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[i] + nums[j] == target) {
                        result[0] = i;
                        result[1] = j;
                        return result;
                    }
                }
            }
            return result;
        }
    

    ⏰ 时间复杂度:看到这个双循环,就知道时间复杂度O(n²)。

    哈希辅助法

    时间复杂度O(n²)多少有点过了,这道题的重点是两个元素相加之和的判断。

    我们可以用一个Hash集合把元素存起来,这样一来遍历一遍就够了,例如目标和9,当前元素2,只需要判断集合里是否有元素7就行了。

        public int[] twoSum(int[] nums, int target) {
            HashMap<Integer, Integer> map = new HashMap<>(16);
            int[] result = new int[2];