代码随想录刷题笔记(DAY1)

2023-12-28 04:46:53

前言:因为学校的算法考试让我认识了卡哥,为了下学期冲击大厂实习的理想,我加入了卡哥的算法训练营,从今天开始我每天会更新自己的刷题笔记,与大家一起打卡,一起共勉!

Day 1

01. 二分查找 (No. 704)

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

1.1 笔记

二分法基本上每个学过算法的人都遇到过这个问题,它的思路和代码都很简单但是写的时候经常出错,主要是因为下面两点:

  1. 外层的 while 的区间是多少?
  2. 我检测完 middle 的值之后,更新区间是否应该包含这个 middle?

我们在代码提交通过后可能就没有考虑过这个问题,或者说随便改改通过了也扔一边了,今天来具体的解决一下这个问题。

首先我们要清楚搜索区间,很多朋友会感觉很简单,这不就是一开始定义的 leftright 吗?其实,我们还要考虑这两个数的区间,是左闭右闭、左闭右开亦或是左开右闭,这才是影响我们上面两个问题的关键因素。

按照比较好理解的左闭右闭举例:[right, left],也就是我们的搜索区间是左闭右闭的,举个例子,[1, 1] 是有意义的,所以 whilerightleft 是可以取到相等的,因为在左闭右闭的前提下,这样取是有意义的。

那来解决第二个问题,新的区间是否应该包含 middle?同样来检验这个区间的合理性,如果包含 middle 的话,比如说,我们通过计算发现nums[mid] 的值要大于target这时候就需要往左边去遍历,也就是比 nums[mid] 小的部分,但这时候有如果按照左闭右闭的区间,其实是包含了这个 nums[mid] 的元素的,这就违背了我们去比它小的部分查找的初衷,所以在这种情况下要取 mid + 1

1.2 代码
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        // 左闭右闭的情况
        while(left <= right) {
            int mid = left + right;
            if (nums[mid] > target) {
                // 向左边查找元素
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

1.3 其他情况

剩下的还有左闭右开和左开右闭的情况,这时候我们仍然考虑区间的准确性,比如这时候 [1, 1) 就没有数学意义了,所以我们的 while 中不能再取等于。

以左闭右开为例子来看这个问题:这时候如果说 nums[mid] 比目标值要大的话,向左边查找,这时候写出区间来就是
[left, mid) 还是上面的那个考虑,这时候因为搜索的区间不包含 mid 所以是可以加等于号的。

看到这里兴致冲冲的去写代码,提交发现报错了,这是什么问题呢?

 		while(left < right) {
            int mid = (int)((left + right) / 2.0 + 0.5);
            if (nums[mid] > target) {
                // 向左边查找元素
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

因为这时候你的眼里只有这个 while 函数,没有注意到当是开区间的时候 right 是可以等于 nums[length] - 1 的,修改后的代码就是这样的

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                // 向左边查找元素
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

写到这里又有顿悟的感觉,自己去试了试左开右闭的情况,不就是把 left = -1 如何把下面的 +1 去掉就好了。

一提交,又报错了。。。

这又是什么原因呢?为什么上面两种情况没有出现问题呢?

首先出现了时间超时肯定是这个 left 卡在了 mid 每次继续都卡在这个位置

这时候关注到这个 mid 的计算方法,很容易发现是向下取整的,在左闭右闭的情况下,左右都不会取到这个 mid 所以不用考虑卡住的情况,左开右闭的情况下,虽然右区间可以取到 mid 但向下取整是保证这个右边界是一直向左靠拢的,但如果是左区间向下取整的话,就有可能会出现卡住的情况:

举个例子:

那为了保证不卡住,解决方法就是更改这个 mid 为向上取整,这样就能保证左区间是持续向右的了。

class Solution {
    public int search(int[] nums, int target) {
        int left = -1;
        int right = nums.length - 1;
        // 左闭右闭的情况
        while(left < right) {
            int mid = (int)((left + right) / 2.0 + 0.5);
            if (nums[mid] > target) {
                // 向左边查找元素
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

OK!通过

02. 移除元素 (No. 27)

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

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

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

2.1 笔记

这个题目主要考察我们对数组结构的理解,暴力的解法也很容易想出来,就是我们遇到了等于 val 的元素的话,就将这个数组整体向前移动一位,这时候最后一个元素就变为我们不需要的元素,所以遍历的结尾要减去 1,同时还需要注意的问题就是如果两个连续都是不需要的元素的话,要将 i 仍然保留在当前位置左相同的操作,否则就会漏删元素。

2.2 代码
class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            // 循环遍历数组
            if (nums[i] == val) {
                len--;
                N--;
                for (int j = i; j < nums.length - 1; j++) {
                    nums[j] = nums[j + 1];
                }             
            }
            if (nums[i] == val) {
                i--;
            }
        }
        return len;
    }
}
2.3 拓展 —— 双指针法

这道题可以通过双指针思想来解决这个问题,设置一个快慢指针,快指针去遍历这个数组,取到不为 val 的元素后将快指针的内容赋值给慢指针,然后将慢指针加一,这样一直循环直到数组结尾,快指针中取到的元素的个数就是结果数组的元素总数,当快指针遍历完数组后,慢指针指向的最后一个元素就是结果数组的最后一个元素,所以我们返回慢指针的索引也是最终的结果。

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = 0;
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                len++;
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return len; // return slow;
    }
}

文章来源:https://blog.csdn.net/weixin_74895237/article/details/135258161
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。