首页 C++ 算法

[toc]

# 4 寻找两个正序数组的中位数

类似于二分，可以递归解，每次可以排除 K/2 个元素，以 A,B K/2 为初始条件递归， K=(M+N)/2
1. A[K/2] < B[K/2] 那么总共小于 B [K/2] 的元素个数严格小于 K, 即 A [K/2] 之前的数据全部不可能是中位数
2. A[K/2] > B[K/2] 同上，B [K/2] 之前的不可能是中位数
3. A[K/2] == B[K/2] 则表示 A/B 之中最小的那个必是中位数 1/2 每次去掉 K/2 个元素后的剩余数组可以当做同样的子问题来处理，即剩余元素中寻找中位数

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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if(tot%2 == 0){
            int left = find(nums1,0,nums2,0,tot/2);
            int right = find(nums1,0,nums2,0,tot/2 + 1);
            return (left + right) / 2.0;
        }else{
            return find(nums1,0,nums2,0,tot/2 + 1);
        }
    }

    int find(vector<int>& nums1,int i,vector<int>& nums2,int j,int k){
        if(nums1.size() - i > nums2.size() - j) return find(nums2,j,nums1,i,k);
        if(k==1){
            if(nums1.size()==i) return nums2[j];
            else return min(nums1[i],nums2[j]);
        }
        if(nums1.size()==i){
            return nums2[j+k-1];
        }
        int si = min(i+k/2,(int)nums1.size()),sj = j+k-k/2;
        if(nums1[si-1] > nums2[sj - 1]){
            return find(nums1,i,nums2,sj,k-(sj-j));
        }else
            return find(nums1,si,nums2,j,k-(si-i));
    }
};

# 5. 最长回文串

方法一：枚举中心点，双指针扩展
方法二：枚举边界点，双指针向内缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i=0;i<s.size();++i){
            int l = i-1,r=i+1;  //奇数
            while(l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;
            if(res.size() < r-l-1) res = s.substr(l+1,r-l-1);

            l = i,r = i+1; //偶数
            while(l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;
            if(res.size() < r-l-1) res = s.substr(l+1,r-l-1);
        }
        return res;
    }
};

# 10. 正则表达式匹配 (闫式 DP 分析法)

  1. 状态表示 (经验) 1.1 f (i,j)
    集合: s (1i) 与 p (1j) 的匹配方案 存储的值 (bool): 是否存在一个合法方案
  2. 状态计算 (推理) 2.1 情况 p [j]≠’*’ => (s [i] 是否等于 p [j] p [j] = . ) s 前 i-1 个字符和 p 前 j-1 个字符也要匹配
    p [j] = * => 考虑 * 匹配了多少个字符，直接枚举 * 的个数 (这部分可以用完全背包优化，而且由于子问题已解决，只需要考虑最多两个字符的情况)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isMatch(string s, string p) {
        int n =s.size(),m = p.size();
        s = ' ' + s,p = ' ' + p;
        vector<vector<bool>> f(n+1,vector<bool>(m+1));
        f[0][0] = true;

        for(int i=0;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(j+1 <=m && p[j+1] == '*') continue;
                if(i && p[j]!='*'){
                    //第i和j需要匹配上
                    f[i][j] = f[i-1][j-1] && (s[i]==p[j]  p[j]=='.');
                }else if(p[j]=='*'){
                    //第i与j匹配等价于前面的i与j-2是否匹配上,或者i-1与j前面的第i和j-1匹配
                    f[i][j] = f[i][j-2]  i && f[i-1][j] && (s[i] == p[j-1]  p[j-1] == '.');
                }
            }
        }
        return f[n][m];
    }
};

# 22 括号生成

性质:
- 1. 任意前缀中 ‘(‘数量大于等于’)’
- 2. 左右括号总数量相等
只要满足上面两个，就是一个合法序列 扩展:
n 个左括号和右括号可能的合法匹配序列是卡塔兰数

# 23. 合并 K 个升序链表

思路和合并两个升序链表一致，只是循环来做的话，时间复杂度是 O (N*K), 但是可以优化，即使用堆进行优化，首次将 K 个元素放到堆中，每次取第一个元素后位移指针，加入，继续取。这样

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    struct Cmp{
        bool operator() (ListNode* a,ListNode* b){
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>, Cmp> heap;

        auto dummy = new ListNode(-1),tail = dummy;

        for(auto l : lists) if(l) heap.push(l);

        while(heap.size()){
            auto t = heap.top();
            heap.pop();
            tail = tail->next = t;
            if(t->next) heap.push(t->next);
        }
        return dummy->next;
    }
};

# 25 K 个一组反转链表

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        for(auto p = dummy;;){
           auto q = p;
           for(int i=0;i<k && q;++i){
               q=q->next;
           } 
           if(!q) break;
           auto a = p->next,b = a->next;
           for(int i=0;i<k-1;++i){
               auto c = b->next;
               b->next = a;
               a = b,b = c;
           }
           auto c= p->next;
           p->next = a,c->next = b;
           p = c;
        }
        return dummy->next;
    }
};

# 28 找出字符串中第一个匹配项的下标 (KMP)

# KMP Next 数组

Next 数组之前一直没学明白，最近看明白了 首先我们需要考虑一点，如果每次匹配一个字符就失败，直到所有字符匹配完全成功的匹配次数实际上最多 N 次，即遍历一次字符串，这个本身是合理的时间复杂度。但是最差的情况是什么呢？AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB 匹配 AAAAAAAAAAAAAAAAB 会发现，后面一个字符串，每匹配一次，就要完整的遍历一次，直到最后一次匹配才会成功，这个时间复杂度就退化到了 O (N*M)
而 Next 数组实际上是优化这种情况的，将字符串直接移动到合适的位置，减少最多次数的匹配
Next 的含义是：所有 P (1~i) 相等的前缀和后缀中，长度的最大值，单位是长度

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 strStr(string s, string p) {
        int n= s.size(),m = p.size();
        s = ' ' + s,p = ' ' + p;
        vector<int> next(m+1);
        //求M的next数组
        for(int i=2,j=0;i<=m;++i){
            while(j&&p[i]!=p[j+1]) j = next[j];
            if(p[i]==p[j+1]) j++;
            next[i] = j;
        }

        for(int i=1,j=0;i<=n;++i){
            while(j&&s[i]!=p[j+1]) j = next[j];
            if(s[i]==p[j+1]) j++;
            if(j==m) return i-m;
        }
        return -1;
    }

};

# 31. 下一个排列

找规律，下一个 permutation 序列

  1. 前到后降序的不用管
  2. 第一个前到最后一个后升序的需要交换，交换后从第一个前到最后都是降序的
  3. 反转子区间 (子问题)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //下一个序列.
        //1. 找到第一个升序子列,交换位置,
        //2. 如果都是降序,那么下一个是反转

        int k = nums.size() - 1;
        while(k>0 && nums[k-1] >=nums[k]) k--;
        if(k<=0){
            reverse(nums.begin(),nums.end());
        }else{
            //存在升序,前向遍历找第一个升序(实际上当前的就是升序)
            int t = k;
            while(t < nums.size() && nums[t]>nums[k-1]) t++;
            swap(nums[t-1],nums[k-1]);
            reverse(nums.begin()+k,nums.end());
        }
    }
};

# 32. 最长有效括号

  1. 两个重要的性质来自 22题 :
1
2
3
- 1. 任意前缀中 '('数量大于等于')'  
- 2. 左右括号总数量相等  
只要满足上面两个,就是一个合法序列
  1. 可以证明当右括号数量严格小于等于左括号数量时才是合法序列
  2. 遍历时使用栈维护序列，右括号 pop, 左括号 push, 如果右括号时，栈内没有元素了，证明此时左括号小于了右括号数量，重新开始计数
  3. 找到所有区间内最大的连续串即可

证明
1. 连续序列必然存在在左括号大于右括号的子序列当中
2. 不可能存在跨越两个子序列的情况 如上图，A 点前面左括号严格大于等于右括号，A 点时左括号小于右括号 (已知)

  1. 假设存在一个区间：从 B 出发跨越 A 点，且可能存在合法子串 (左括号严格大于等于右括号)
  2. 则 B 到 A 点的左括号必然大于等于右括号
  3. 由于 A 点到前面是左括号小于右括号，由于 2, 所以 B 点到前面那段的左括号必然小于右括号才能使已知成立

第 3 条与性质 1 相悖，所以假设不成立

即得到结论:

  1. 连续序列必然存在在左括号大于右括号的子序列当中
  2. 不可能存在跨越两个子序列的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int res = 0;
        for(int i = 0,start = -1;i<s.size();++i){
            if(s[i] == '(') stk.push(i);
            else{
                if(stk.size()){
                    stk.pop();
                    if(stk.size()){
                        res=max(res,i-stk.top());
                    }else{
                        res = max(res,i - start);
                    }
                }else{
                    start = i;
                }
            }
        }
        return res;
    }
};

# 33. 搜索旋转数组

  1. 二分的概念可以扩展到具有相同性质的序列的二分

如，通常的二分查找都是根据序列的升降来判断的，在这道题中，可以针对序列是否大于 nums [0] 这一概念来进行二分，直到找到两个旋转段的分界点

  1. 二分找到两个旋转段的分界点
  2. 判断 target 可能在哪个段上，对段进行二分
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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //第一次二分: 找到分段点(因为两段共同满足一个性质,大于nums[0]的在第一段,小于nums[0]的在第二段,根据这个性质可以对整个数组进行二分)
        int l=0,r = nums.size()-1;
        while(l<r){
            int mid = (l + r + 1)>>1;
            if(nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        //判断target在哪个分段
        if(target >=nums[0]) l = 0;
        else l = r + 1,r = nums.size() - 1;

        //二分找出答案
        while(l<r){
            int mid = (l + r) >>1;
            if(nums[mid] >= target ) r = mid;
            else l = mid + 1;
        }

        if(nums[r] == target) return r;
        return -1;
    }
};

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

这道题也可以类似于上一题，找两个二段性

  1. 第一个区间 <= target
  2. 第二个区间 >= target

根据这两个二段性来进行二分

# 35. 搜索输入的位置

二分二段性条件是被选中位置大于等于 target
需要特判 0 点
另外，根据这道题发现了一个需要注意的问题
1. 破坏 l,r 中点的只能有一个，就是 l=mid+1 或者 r=mid-1 2. 最后结果最好用未破坏中点的那个 l=mid、r=mid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums[0]>=target) return 0;

        int l = 0,r = nums.size()-1;
        while(l<r){
            int mid = (l+r+1) >> 1;

            if(nums[mid] >= target) r = mid-1;
            else l = mid;
        }

        return l+1;
    }
};
更新于

请我喝[茶]~(￣▽￣)~*

Solvarg 微信支付

微信支付

Solvarg 支付宝

支付宝

Solvarg 贝宝

贝宝