【C++ 算法进阶】算法提升十七

寻找二维数组中是否存在某个数

题目

给定你一个二维数组 数组的每一行都有序 每一列也都有序

现在给你一个数 请问该二维数组中是否存在这个数

题目分析

因为这个二维数组每一行 每一列都是有序的 所以说我们可以从右上角开始查询这个数组中是否存在一个元素

假设右上角的数大于我们要找的数则说明这列不可能存在 我们左边去找

假设右上角的数小于我们要找的数则说明这一行不可能存在 我们往下面去找

依次往复 最后如果到越界都没有找到不存在

寻找二维数组中第K小的数

题目

给定你一个二维数组 数组的每一行都有序 每一列也都有序

现在要求这个数组中第K小的数

题目分析

假设我们现在给定一个数字K 根据题目一的思路 从右上角开始找我们很轻松就能找到有多少个数小于K 并且能找到小于等于K且最接近K的数字是什么

如果说我们能找出小于等于M 并且距离M最接近的数字是多少 那么我们通过不断的二分 就可以找到数组中第K小的数

代码

class Solution {
public:
    bool check(vector<vector<int>>& matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

字符串s子序列组成t （动态规划）

题目

给定一个字符串s和字符串t

现在请问字符串s的子序列有多少中可能性能组成字符串t

题目分析

涉及到两个字符串的问题我们就要想到样本对应模型的动态规划

我们假设一个普遍位置的 dp[i][j] i表示字符串s0~i位置 j表示字符串t的0到j位置

dp[i][j]的值则表示有多少中方法

一般样本对应模型都要从末尾位置来分析

我们假设末尾位置不参与

则实际上我们要求的就是dp[I-1][J]

我们假设末尾位置参与 这种可能性要求末尾位置的值和t位置末尾位置的值一样

此时我们要求的是dp[I-1][J-1]

最后将两个可能性相加即可

不同的子序列 （观察）

题目

本题为LC原题

题目分析

假设没有重复的字符的话 我们每次添加新字符时就相当于将原来的所有集合再乘以2 就能得到新加字符后的总集合

可以如果有重复集合的话 则我们需要减去上次重现该字符时新家的字符个数 就是下面代码中出现的newall

代码

class Solution {
public:
    int distinctSubseqII(string s) {
        int mod = 1000000007;
        unordered_map<char , int> mapCount;

        int all = 1;
        for (int i = 0; i < s.size(); i++) {
            int lnNewAll = all;
            int lnCurAll = all;
            lnCurAll = (lnCurAll + lnNewAll) % mod;
            lnCurAll = ( lnCurAll + mod - (mapCount.count(s[i]) == 1 ?  mapCount[s[i]] : 0) ) % mod;
            all = lnCurAll;
            mapCount[s[i]] = lnNewAll;
        }

        return (all + mod - 1) % mod;
    }
};