Timothy Wu 收录于 Leetcode刷题记录

2022-04-08 约 2400 字预计阅读 5 分钟 - 次阅读

数组：专题刷题记录

数组专题，包括二分查找

二分查找相关

704 二分查找

704-二分查找

这里原文所说的两种二分查找的区间写法我觉得是要注意一下的。我之前没有注意这个，一直都是写的第一种，但是经常会有问题（比如下面这个，实际上是没有判断相等，导致看起来比较累赘）

对于二分查找来说，边界条件非常重要。关键点有两个，一个是二分查找区间是否是闭区间，另一个是二分查找后区间该如何移动。解决了这两个问题，二分查找应该是没有难度的。

具体代码如下：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while(left<right){
            if(nums[(left+right)/2] < target){
                left = (left+right)/2+1;
            }else if(nums[(left+right)/2] > target){
                right = (left+right)/2-1;
            }else{
                return (left+right)/2;
            }
        }
        if(left<nums.size() && nums[left] == target){
            return left;
        }else if(right>=0 && nums[right]==target){
            return right;
        }else {
            return -1;
        }
    }
};

35 搜索插入位置

简单题，基本和二分查找是一样的

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0, right=nums.size()-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid] < target){
                left = mid+1;
            }else if(nums[mid] > target){
                right = mid-1;
            }else{
                return mid;
            }
        }
        return left;
    }
};

int main(void){
    Solution s;
    vector<int> nums{-1,0,3,5,9,12};
    cout<<s.searchInsert(nums,8)<<endl;
    return 0;
}

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

中等难度，感觉有点麻烦。肯定是使用二分法，但是由于目标不唯一，需要对经典的二分法进行一定的修改。这里只写了最简单的改进版本，但如果是用很多的相同数据该算法会迅速退化。对于这种情况，目前我只想出可以找前一个和后一个数对其进行二分查找，从而获取两端的方法。

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        // 最简单的实现：二分找到后进行扩大搜索
        bool isFound = false;
        int index = -1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid] < target){
                left = mid+1;
            }else if(nums[mid] > target){
                right = mid-1;
            }else{
                isFound = true;
                index = mid;
                break;
            }

        }
        if(!isFound){
            return vector<int>{-1,-1};
        }else{
            int l=index,r=index;
            while(l>=0 && nums[l] == target) l--;
            while(r<nums.size() && nums[r] == target) r++;
            return vector<int>{l+1,r-1};
        }
    }
};

int main(void){
    Solution s;
    vector<int> nums{};
    vector<int> result(s.searchRange(nums,0));
    cout<<result[0]<<" "<<result[1]<<endl;
    return 0;
}

分别二分查找两个边界的方法,source

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};

移除元素

27 移除元素

要求原地移除数组中的指定元素。一个很自然的想法就是双指针。

具体来说，可以假定现在有两个数组，一个旧的原始数组old，一个新的去除元素的数组new。一个很自然的想法是将old中的数据一个个拷贝到new上，如果中间有需要删除的目标数据就跳过。又因为这个步骤是顺序的，所以其实并不需要新数组new，可以直接在旧数组上完成。

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int np = 0, op = 0;
        for(;op<nums.size();op++){
            if(nums[op] == val){
                continue;
            }else{
                if(np!=op)
                    nums[np] = nums[op];
                np++;
            }
        }
        return np;
    }
};

283 移动零

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int val = 0;
        int np = 0, op = 0;
        for(;op<nums.size();op++){
            if(nums[op] == val){
                continue;
            }else{
                if(np!=op)
                    nums[np] = nums[op];
                np++;
            }
        }
        for(;np<nums.size();np++){
            nums[np] = 0;
        }
    }
};

长度最小的子数组

209 长度最小的子数组

原题，给定一个target，要求计算原数组中长度最小的连续子数组，使得子数组中元素之和大于target。尽管是中等题，但难度还是不小。

一个比较初步的想法是双重循环比较，这个一定是能够算出来，但是时间复杂度为O(n^2)，应该是过不了的（但可以检验答案）。

另外一个想法是用树的想法，自顶向下构建一个二叉树（原节点为二叉树的叶子），然后向上计算和。如果说某个节点的和大于target，那在这个节点下将可能存在大于target的子数组。这个想法的问题是真正的连续子数组可能刚好横跨了两个二叉树的区域，计算起来会比较困难。稍微改进一点的想法是采用模拟构造的方法，即第一层为全部的子节点，第二层为全部的连续两个节点，以此类推……这样子确实能够解决跨界问题，但是其时间复杂度可能会退化为n^2级别。

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        vector<int> arr(nums); // arr[i]表示从i开始的累计和
        for(int i=1;i<=nums.size();i++){ // 代表子数组长度为i时
            for(int j=0;j<nums.size()-i+1;j++){
                if(arr[j]>=target){ // 如果大于target
                    return i;
                }

                // 更新j
                if(j+i<nums.size()){
                    arr[j] += nums[j+i];
                }
            }
        }
        return 0;
    }
};

虽然通过了，但是仅超过了5.07%，速度比较慢。

题解提到使用滑动窗口方法。具体来说，先使用滑动窗口探索到一个可行解，再不断优化这个可行解。

探索可行解的方法为设置一个滑动窗口，一直扩大直到达到target（或者超过数组长度后发现不可能）。扩展可行解的方法为每次向右扩展，然后尝试向左收缩。

显而易见，滑动窗口方法的复杂度是O(n)的，在最不利的情况下，左区间指针和右区间指针也只是遍历了两遍数组而没有其他的操作。我自己写了一个滑动窗口版的代码，感觉比题解的版本要累赘很多。滑动窗口法的精髓在于两个指针是如何运动的，如何描述两个指针运动之间的切换。我这个版本明显就没有描述好，第一个部分其实是多余的。


class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(nums.size() == 0){
            return 0;
        }

        int left = 0, right = 0; // 使用闭区间
        int cur_val = nums[0];
        int min_len = nums.size();
        // 获得第一个滑动窗口
        if(nums[0] >= target){
            return 1;
        }

        for(right=right+1;right<nums.size();right++){
            cur_val += nums[right];
            if(cur_val>=target){
                break;
            }
        }
        if(cur_val<target){
            return 0;
        }
        min_len = right-left+1;
        if(right+1>=nums.size()){
            while(left<nums.size() && cur_val - nums[left] >= target){
                cur_val -= nums[left];
                left++;
            }
            if(right-left+1 < min_len){
                min_len = right-left+1;
            }
            return min_len;
        }

        // 尝试扩展，首先扩展一位
        for(right=right+1;right<nums.size();right++){
            cur_val += nums[right];
            while(left<nums.size() && cur_val - nums[left] >= target){
                cur_val -= nums[left];
                left++;
            }
            if(right-left+1 < min_len){
                min_len = right-left+1;
            }

        }
        return min_len;
    }
};

904 水果成篮

这个难度明显要高了一截，但思路总体都是相同的。题目的概要意思就是求一个连续子数组使得其和最大，但是这个连续子数组有一个要求，即其中只能包含两种类型的数字。显而易见，也可以使用滑动窗口法过一遍。唯一的问题在于左区间的指针更新逻辑会有些不一样，因为涉及到只有两个不同元素这个限制，因此更新的时候采用从右区间出发的方法。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left=0,right=0;
        map<int,bool> cur; // 当前已有的水果种类
        int max_len = 0;
        for(;right<fruits.size();right++){
            if(cur.find(fruits[right]) == cur.end()){ // 假如没有找到
                if(cur.size()>=2){ // 如果此时已经满了，则需要从right移动探测新的left
                    int rest_ele = fruits[right-1];
                    left = right-1;
                    while(left>=0&&fruits[left]==rest_ele) left--;
                    cur.erase(fruits[left]); // delete old
                    cur[fruits[right]] = true; // and replace to new
                    left += 1;
                }else{// 反之，则只需要将该元素加入
                    cur[fruits[right]] = true;
                }
            }
            // 反之，如果已经找到该元素，则直接继续搜索即可
//            cout<<left<<" "<<right<<endl;
            if(right-left+1>max_len){
                max_len = right-left+1;
            }
        }
        return max_len;
    }
};

int main(void){
    Solution s;
    vector<int> nums{0,1,1,4,3};
    cout<<s.totalFruit(nums)<<endl;
    return 0;
}

Leetcode数组专题