Cybay
0%

数组

发表于 更新于 分类于 Valine：
数组

双指针

删除排序数组中的重复项

Leetcode链接

通过一个快指针和一个慢指针在一个for循环中完成删除

时间复杂度O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int fa,slow=0;
        if(nums.size()==0)   return 0;
        for(fa=1;fa<nums.size();++fa)
        {
            if(nums[fa]>nums[slow])
                nums[++slow]=nums[fa];
        }
        return slow+1;
    }
};
比较含退格的字符串

Leetcode链接

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i=s.size()-1,j=t.size()-1;
        int ns=0,nt=0;//记录s与t中#的数量
        while(1)
        {
        while(i>=0)//从后向前消除s的#
        {
            if(s[i]=='#')   ns++;
            else
            {
                if(ns>0)    ns--;
                else    break;
            }
            i--;
        }
        while(j>=0)//从后向前消除t的#
        {
            if(t[j]=='#')   nt++;
            else
            {
                if(nt>0)    nt--;
                else    break;
            }
            j--;
        }
        if(i<0||j<0)    break;//当某个字符串遍历完时退出
        if(s[i]!=t[j])  return false;//在某处字符不同可判定不相等
        i--;j--;
        }
        if(i==-1&&j==-1)//字符，长度均相等
            return true;
        return false;
    }
};
反转字符串中的单词
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//去除多余空格后，先将字符串全反转，再逐一反转单词
class Solution {
public:
    string reverseWords(string s) {
        int i=0,len=s.length(),slow;
        while(s[i]==' ')//去除前置空格
            ++i;
        s[0]=s[i++];
        for(slow=1;i<len;++i)//快慢指针，删除多余空格
        {
            if(s[i]==s[i-1]&&s[i]==' ')
                continue;
            s[slow++]=s[i];
        }
        //处理最后有空格的情况
        if(slow-1>0&&s[slow-1]==' ')
            s.resize(slow-1);
        else
            s.resize(slow);
        reverse(s.begin(),s.end());
        auto k=s.begin();
        for(auto c=s.begin();c!=s.end();++c)
        {
            if(*c==' ')
            {
                reverse(k,c);
                k=c+1;
            }
        }
        reverse(k,s.end());
        return s;
    }
};

滑动窗口

长度最小的子数组

leetcode209

暴力解法 用两个for循环，时间复杂度O(n^2);

滑动窗口法：

​ 用两个指针，形成一个范围，根据范围内数组元素的和进行指针的移动。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int min=1<<30;
        int i=0,j=0,sum=0;
        while(i<nums.size())// i在前
        {
            sum+=nums[i];
            while(target<=sum)
            {
                int k=i-j+1;
                if(k<min) min=k;
                sum-=nums[j++];
            }
            ++i;
        }
        if(min!=1<<30) return min;
        return 0;
    }
};
水果成篮

leetcode904

使用 unordered_map，在超过三个数时移动指针

如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int ret=0;
        unordered_map<int,int> m;
        int slow=0;
        for(int fast=0;fast<fruits.size();++fast)
        {
            m[fruits[fast]]++;
            while(m.size()>2){
                m[fruits[slow]]--;
                if(m[fruits[slow]]==0)
                    m.erase(fruits[slow]);
                slow++;
            }
            
            if(ret<fast-slow+1)
                ret=fast-slow+1;
        }
        return ret;
    }
};