双指针问题
本文最后更新于70 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com

26.删除有序数组的重复项

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数

 class Solution {
 public:
     int removeDuplicates(vector<int>& nums) {
         int slowidx = 0;
         for(int fastidx = 0;fastidx < nums.size();fastidx++){
             if(nums[fastidx]!=nums[slowidx]){
                 slowidx++;
                 nums[slowidx]=nums[fastidx];
            }
        }
         return slowidx+1;
         
    }
 };

283.移除零

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

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

 class Solution {
 public:
     void moveZeroes(vector<int>& nums) {
         int slow = 0;
         for(int fast = 0;fast<nums.size();fast++){
             if(nums[fast] != 0){
                 swap(nums[slow],nums[fast]);
                 slow++;
            }
        }
    }
 };

太好了是交换函数

844.比较含退格的字符串

给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。# 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。

示例 1:

 输入:s = "ab#c", t = "ad#c"
 输出:true
 解释:s 和 t 都会变成 "ac"。

示例 2:

 输入:s = "ab##", t = "c#d#"
 输出:true
 解释:s 和 t 都会变成 ""。

示例 3:

 输入:s = "a#c", t = "b"
 输出:false
 解释:s 会变成 "c",但 t 仍然是 "b"。

提示:

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

方法一:重构字符串(栈)

遍历原字符串,遇到非退格符则在新字符串末尾插入该字符,遇到退格符则删除新字符串末尾的元素(删除元素前需判空)

 class Solution {
 public:
     bool backspaceCompare(string s, string t) {
         return build(s) == build(t);
         
    }
 ​
     string build(string str){
         string ret;
         for(char ch : str){
             if(ch != '#'){
                 ret.push_back(ch);
            }
             else if(ret.size() != 0){
                 ret.pop_back();
            }
        }
         return ret;
    }
 };

时间复杂度:O(N+M),其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。

空间复杂度:O(N+M),其中 N 和 M 分别为字符串 S 和 T 的长度。主要为还原出的字符串的开销。 链接:https://leetcode.cn/problems/backspace-string-compare/solutions/451606/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/

方法二:双指针法

一个字符是否会被删掉,只取决于该字符后面的退格符,而与该字符前面的退格符无关。因此当我们逆序地遍历字符串,就可以立即确定当前字符是否会被删掉。

具体地,我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符:

若该字符为退格符,则我们需要多删除一个普通字符,我们让 skip 加 1,i–(删去退格符)

若该字符为普通字符:

若 skip 为 0,则说明当前字符不需要删去;

若 skip 不为 0,则说明当前字符需要删去,我们让 skip 减 1,i–(删去无效字符)

这样,我们定义两个指针,分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串,直到两字符串能够各自确定一个字符,然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等,或遍历完字符串为止。 链接:https://leetcode.cn/problems/backspace-string-compare/solutions/451606/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/

  • 外层 while 循环的每一次迭代,就是从两个字符串中各找到一个有效字符,然后比较它们。
  • 内层循环用于找到有效字符(i,j指向有效字符)
  • 内层二个for循环后就找到了有效字符,然后进行比较判断
    • 二个字符串都没遍历完:当有效字符不相等,说明整个有效字符串不相等,返回false。当有效字符相等,则进入下一次循环
    • 一个字符串遍历完,另一个没有遍历完:说明有效字符串长度不等,无需再判断,直接返回false
  • i–,j–,进入下一次外层循环
 class Solution {
 public:
     bool backspaceCompare(string s, string t) {
         int i = s.size()-1;
         int j = t.size()-1;
         int skips = 0;
         int skipt = 0;
         while(i >= 0 ||  j>= 0){
 ​
             //下面二个for循环为了找到二个字符串各自的有效字符(从后往前)
             while(i >= 0){
                 if(s[i] == '#'){
                     i--;
                     skips++;
                }
                 else if(skips>0){
                     skips--;
                     i--;
                }
                 else{
                     break;
                }
            }
 ​
             while(j >= 0){
                 if(t[j] == '#'){
                     j--;
                     skipt++;
                }
                 else if(skipt>0){
                     skipt--;
                     j--;
                }
                 else{
                     break;
                }
            }
 ​
             //如果都没遍历完,说明目前有效字符一样长,二个有效字符进行比较,不相同返回false
             if(i >=0 &&j >= 0){
                 if(s[i] != t[j]){
                     return false;
                }
            }
             //如果有一串字符串已经遍历完,另一串还没有,说明有效字符长度不一样,不可能相等,返回false
             else{
                 if(i >= 0 || j >= 0){
                     return false;
                }
            }
 ​
             //找到了一个有效字符后,接着找下一个有效字符(外层循环一次就相当于找到一个有效字符)
             i--;
             j--;
 ​
 ​
        }
         return true;
         
    }
 ​
 };

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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]

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶:

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

方法一:快速排序

先把各元素平方放到新数组,再用快排函数

 class Solution {
 public:
     vector<int> sortedSquares(vector<int>& nums) {
         vector<int>ans;
         for(int num:nums){
             ans.push_back(num * num);
        }
         sort(ans.begin(),ans.end());
         return ans;
    }
 };
  • 时间复杂度:O(nlogn),其中 n 是数组 nums 的长度。
  • 空间复杂度:O(logn)。除了存储答案的数组以外,我们需要 O(logn) 的栈空间进行排序。

方法二:双指针

使用两个指针分别指向位置 0 和 n−1,每次比较两个指针对应的数,选择较大的那个逆序放入ans容器并移动指针。

 class Solution {
 public:
     vector<int> sortedSquares(vector<int>& nums) {
         int n = nums.size();
         vector<int>ans(n);
         int i = 0;
         int j = n-1;
         int pos = j;
         while(i <= j){
             if(nums[i]*nums[i] < nums[j]*nums[j]){
                 ans[pos] = nums[j]*nums[j];
                 j--;
            }
             else {
                 ans[pos] = nums[i]*nums[i];
                 i++;
            }
             pos--;
        }
         return ans;
    }
 };
  • 时间复杂度:O(n),其中 n 是数组 nums 的长度。
  • 空间复杂度:O(1)。除了存储答案的数组以外,我们只需要维护常量空间。

动画演示:【LeetCode】【Manim动画】977. 有序数组的平方哔哩哔哩bilibili

文末附加内容
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇