2

「算法刷题」数组之双指针专项汇总（力扣版）

 1 year ago
source link: https://magicdeveloperdrl.github.io/2022/06/11/%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98-%E6%95%B0%E7%BB%84%E4%B9%8B%E5%8F%8C%E6%8C%87%E9%92%88%E4%B8%93%E9%A1%B9%E6%B1%87%E6%80%BB-%E5%8A%9B%E6%89%A3%E7%89%88.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

「算法刷题」数组之双指针专项汇总（力扣版）

Jun 11, 2022 • MRL Liu

​ 本文记录作者刷题过程中与双指针相关的题目。

1、删除数组中的元素

（1）删除数组中的某个（所有的）目标值

27. 移除元素（简单难度）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n=nums.size();
        // 数组中至少有0个元素
        int slow=0; // 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
        int fast = 0;// 快指针，负责遍历整个数组
        while(fast < n)
        {
            //快指针不等于目标值时
            if (nums[fast] != val) 
            {
                nums[slow] = nums[fast];//快指针指向的数覆盖给慢指针指向的数
                slow++;//慢指针+1
                fast++; //快指针+1
            }
            // 快指针等于目标值时，快指针+1
            else{
                fast++;//快指针+1
            }
        }
        return slow;//返回慢指针
    }
};

（2）删除有序数组中的重复项

26. 删除有序数组中的重复项（简单难度）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        // 数组中至少有1个元素
        int slow=1;// 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
        int fast=1;// 快指针，负责遍历整个数组
        while(fast<n){
            // 快指针和上一个元素不同时，
            if(nums[fast]!=nums[slow-1]){
                nums[slow]=nums[fast];// 快指针元素覆盖慢指针元素
                slow++;//慢指针前进
                fast++;//快指针前进
            }
            // 快指针和上一个元素相同时，快指针前进
            else{
                fast++;
            }
        }
        return slow;
    }
};

80. 删除有序数组中的重复项 II（中等难度）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        if(n<=2) return n;
        // 数组中至少有2个元素
        int slow=2;// 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
        int fast=2;// 快指针，负责遍历整个数组
        while(fast<n){
            // 快指针不等于
            if(nums[fast]!=nums[slow-2]){
                nums[slow]=nums[fast];
                slow++;
                fast++;
            }
            else{
                fast++;
            }
        }
        return slow;
    }
};

2、移动数组中的元素

283. 移动零（简单难度）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        // 数组中至少有0个元素
        int slow=0;// 慢指针,[0,low),指向移动后的区间的最后一个元素的后一个索引
        int fast=0;// 快指针，负责遍历整个数组
        while(fast<n){
            // 如果快指针不为0
            if(nums[fast]!=0){
                swap(nums[slow],nums[fast]);// 快慢交换
                slow++;
                fast++;
            }
            else{
                fast++;
            }
        }
    }
};

75. 颜色分类（中等难度）

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return;
        // 整个数组需要分成3个区间:
        int zero = 0;//[0,zero)，红色元素,存放0
        int one = 0;//[zero,one)，白色元素，存放1,同时负责遍历
        int two = n-1;// [one,two)，篮色元素，存放2
        while (one < n) {
            // 如果当前元素==0,移动到头部
            if (nums[one] == 0&&zero<one) {
                swap(nums[one], nums[zero]);//
                zero++;
            }
            // 如果当前元素==2,移动到表尾
            else if (nums[one] == 2&& one<two) {
                swap(nums[one], nums[two]);
                two--;
            }
            // 如果当前元素==1，跳过
            else {
                one++;
            }
        }
        //quickSort(nums,0,nums.size()-1);
    }
}

215. 数组中的第K个最大元素（中等难度）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        return quickFind(nums,k-1,0,len-1);//从大到小排序，第k大就是第k-1个索引，返回第k-1个索引的值
    }
    // 快排法
    int quickFind(vector<int>& nums, int k,int left,int right){
        int index = partition(nums,left,right);//开始分区
        // 结束分区
        if(index==k){
            return nums[index];//first是基准值索引，表示第first个
        }
        else if(index>k){
            return quickFind(nums, k,left,index-1);
        }
        else {
            return quickFind(nums, k,index+1,right);
        }
    }
    // 分区函数
    int partition (vector<int> &nums, int first, int last) {
        int key = nums[first];//默认第一个为基准值
        while (first < last) {
            // 从右往左找到第一个小于key的值
            while (first < last && nums[last] <= key) --last;
            nums[first] = nums[last];
            // 从左往右找到第一个大于key的值
            while (first < last && nums[first] >= key) ++first;
            nums[last] = nums[first];
        }
        nums[first] = key;// 基准值归位
        return first;// 返回索引
    } 
};

905. 按奇偶排序数组（简单难度）

class Solution {
public:
    /*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
    左指针寻找奇数值，右指针寻找偶数值，当符合交换条件时，进行两数交换；
    否则指针继续左右运动，寻找符合条件的奇偶值。
    当两指针相遇时，结束循环。*/
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left=0;//左指针
        int right=nums.size()-1;//右指针
        // 遍历数组[left,right],
        while(left<right){
            // 如果左指针指向奇数，右指针指向偶数，就交换两个数
            if (nums[left] % 2 > nums[right] % 2) {
                swap(nums[left],nums[right]);
            }
            // 如果左指针指向偶数，左指针移动
            if (nums[left] % 2 == 0) left++;
            // 如果右指针指向奇数，右指针移动
            if (nums[right] % 2 == 1) right--;
        }
        return nums;
    }
};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面（简单难度）

class Solution {
public:
    /*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
    左指针寻找偶数值，右指针寻找奇数值，当符合交换条件时，进行两数交换；
    否则指针继续左右运动，寻找符合条件的奇偶值。
    当两指针相遇时，结束循环。*/
    vector<int> exchange(vector<int>& nums) {
        int left=0;//左指针
        int right=nums.size()-1;//右指针
        // 遍历数组[left,right],
        while(left<right){
            // 如果左指针指向偶数，右指针指向奇数，就交换两个数
            if (nums[left] % 2 < nums[right] % 2) {
                swap(nums[left],nums[right]);
            }
            // 如果左指针指向奇数，左指针移动
            if (nums[left] % 2 == 1) left++;
            // 如果右指针指向偶数，右指针移动
            if (nums[right] % 2 == 0) right--;
        }
        return nums;
    }
};

922. 按奇偶排序数组 II（简单难度）

class Solution {
public:
    /*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
    遍历所有偶数索引*/
    vector<int> sortArrayByParityII(vector<int>& nums) {
        //
        int n = nums.size();
        int j = 1;//奇数索引
        // 遍历整个数组的所有偶数索引
        for (int i = 0; i < n; i += 2) {
            // 如果偶数索引上的数是奇数
            if (nums[i] % 2 == 1) {
                // 连续遍历整个数组的所有奇数索引，找到一个数是偶数
                while (nums[j] % 2 == 1) j += 2;
                swap(nums[i], nums[j]);//交换两个数
            }
        }   
        return nums;
    }
};

3、查找排序数组中的2个数

剑指 Offer 57. 和为s的两个数字（简单难度）

剑指 Offer II 006. 排序数组中两个数字之和（简单难度）

class Solution {
public:
    /*解析：这道题在一个排序数组中查找2个数，使其和为target
    提到排序，可能会选用二分查找法，二分查找法确实可以结合使用
    但是这道题难度简单，用普通的双指针就可以搞定
    排序数组的特点可以作为移动左右指针的依据，和较小右移左指针，和较小左移右指针
    */
    vector<int> twoSum(vector<int>& nums, int target) {
        int left=0;//左指针
        int right=nums.size()-1;//右指针
        int sum=0;
        while(left<=right){
            sum=nums[left]+nums[right];
            // 如果两数和==target，直接返回
            if(sum==target) return {nums[left],nums[right]};
            // 如果两数和>target，说明应该降低两数和，右指针左移即可
            else if(sum>target) right--;
            // 如果两数和<target，说明应该增加两数和，左指针右移即可
            else left++;
        }
        return {nums[left],nums[right]};
    }
};

4、其他问题

977. 有序数组的平方（简单难度）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size();
        vector<int> res(n,0);
        int k=n-1;
        int left=0;
        int right=n-1;
        while(left<=right){
            // 左右指针，谁大加谁
            if((nums[left]*nums[left])<(nums[right]*nums[right]))  {
                res[k--]=nums[right]*nums[right];
                right--;
            }
            else{
                res[k--] = nums[left]*nums[left];
                left++;
            }
        }
        return res;
    }
};

169. 多数元素（简单难度）

class Solution {
public:
    int majorityElement1(vector<int>& nums) {
        // 统计nums中每个数组元素出现的频率
        unordered_map<int,int> dict;// nums中每个数，出现频率
        for(int num:nums) dict[num]++;
        //建立哈希数组找其中出现次数大于n/2的数
        int n=nums.size();
        for(auto it=dict.begin();it!=dict.end();++it){
            if(it->second>n/2)
                return it->first;
        }
        return 0;
    }
    // 方法二
    int majorityElement(vector<int>& nums) {
        if (nums.size()==1) return nums[0];
        //排序
        sort(nums.begin(),nums.end());
        vector<int> res;
        // 使用双指针查找所有可能的众数
        int cur=0;//当前数
        int count=0;//计数器
        int maxCount=0;//最大计数
        int slow=0; //慢指针
        int fast=1;// 快指针
        //统计前一个数和后一个数相同的频率
        while(fast<nums.size()){
            //如果当前数与前一个数相同
            if(nums[fast]==nums[slow]) {
                count++;
                cur= nums[fast];//记录快指针手中的数
                slow++;
                fast++;
            }
            //如果当前数与前一个数不相同
            else{
                count=1;
                slow++;
                fast++;
            }
            //如果计数超过最大计数
            if(count>maxCount){
                maxCount=count;//更新最大计数
                res.clear();//清空众数数组（之前的失效）
                res.push_back(cur);//将当前数加入众数数组
            }
            //如果计数等于最大计数
            else if(count==maxCount){
                res.push_back(cur);//将当前数加入众数数组
            }
        }
        return res[0];
    }
};

941. 有效的山脉数组

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        int N = arr.size();
        int i = 0;
        // 递增扫描
        while (i+1<N&&arr[i]<arr[i+1]) i++;
        // 最高点不能是数组的第一个位置或最后一个位置
        if(i==0||i==N-1) return false;
        // 递减扫描
        while(i+1<N&&arr[i]>arr[i + 1]) i++;
        return i == N-1;
    }
};

189. 轮转数组

class Solution {
public:
    // 方法一：使用额外数组
    void rotate1(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> res(n);
        int j=0;
        for(int i=0;i<n;i++){
            j=(i+k)%n;
            res[j]=nums[i];
        }
        nums.assign(res.begin(), res.end());
    }
    // 方法二：数组反转
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();// 1 2 3 4 5 6 7,k=3
        k = k%n;
        reverse(nums.begin(), nums.end());// 反转[0,n-1] 7 6 5 4 3 2 1
        reverse(nums.begin(), nums.begin()+k);// 反转[0,k-1] 5 6 7 4 3 2 1
        reverse(nums.begin()+k, nums.end());// 反转[k,n-1] 5 6 7 1 2 3 4
    }
};

11. 盛最多水的容器

class Solution {
public:
    /* 左右指针分别从数组两端出发，容量的高为min(height[left],height[right])
    容量的长为right-left，则容量可以计算出来
    移动左右指针时，谁小移动水*/
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int res = 0;
        while (left < right) {
            int area =min(height[left], height[right])*(right-left);
            res = max(res, area);
            if (height[left]<= height[right]) ++left;
            else --right;
        }
        return res;
    }
};

238. 除自身以外数组的乘积

class Solution {
public:
    /*原      数组：  [1       2       3       4]
      左部分的乘积：   1       1      1*2    1*2*3
      右部分的乘积： 2*3*4    3*4      4      1
      结        果：1*2*3*4  1*3*4   1*2*4  1*2*3*1*/
    vector<int> productExceptSelf(vector<int>& a) {
        int n=a.size();
        vector<int> res(n,1);
        // 左遍历
        int left=1;// [0,i-1]的累乘
        for(int i=0;i<n;i++){
            res[i]=left;
            left*=a[i];
        }
        // 右遍历
        int right=1;// [i+1,n-1]的累乘
        for(int i=n-1;i>=0;i--){
            res[i]*=right;
            right*= a[i]; 
        }
        return res;
    }
};

392. 判断子序列

bool isSubsequence(string s, string t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i<n&&j<m) {
            if (s[i] == t[j]) i++;
            j++;
        }
        return i == n;
    }

581. 最短无序连续子数组

class Solution {
public:
   /*从左往右遍历,max记录的是0到i最大的数，
   如果第i个位置比max小，证明第i位置元素不正确，
   因为它前面有个比它大的数,记录下标high=i
   从右往左遍历，min记录的是n-1到i最小的数，
   如果第i位置元素比min大，证明第i位置元素不正确,
   因为它后面有比它小的数，记录下标low=i
   区间[low,high]即为所求*/
    int findUnsortedSubarray(vector<int>& nums) {
        int n=nums.size();
        if(n<=1) return 0;
        int max=nums[0];// 记录正序遍历中的最大值
        int min=nums[n-1];// 记录反序遍历中的最小值
        int low=1,high=0;// 最短无序连续子区间就是[low,high]
        for(int i=1;i<=n-1;++i){
            if(nums[i]>=max) max=nums[i];// 注意=
            else high=i;
        }
        for(int i=n-2;i>=0;--i){
            if(nums[i]<=min) min=nums[i];// 注意=
            else low=i;
        }
        // 子区间可能不存在，需要讨论
        return low<=high?high-low+1:0;
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK