365天挑战LeetCode1000题——Day 037 元素和小于等于阈值的正方形的最大边长 + 满足条件的子序列数目

---

1292. 元素和小于等于阈值的正方形的最大边长

这题需要用到前缀和，官方的题解讲得不错

代码实现（部分看题解）

class Solution {
    
private:
    bool validate(vector<vector<int>>& _mat, int threshold,
    int x1, int y1, int x2, int y2) {
    
        return _mat[x2][y2] - _mat[x1 - 1][y2] - _mat[x2][y1 - 1]
        + _mat[x1 - 1][y1 - 1] <= threshold;
    }
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
    
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> _mat(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
    
            for (int j = 1; j <= n; j++)
                _mat[i][j] = _mat[i - 1][j] + _mat[i][j - 1] -
                _mat[i - 1][j - 1] + mat[i - 1][j - 1];
        }
        int l = 0;
        int r = min(m, n);
        while (l < r) {
    
            int mid = (l + r + 1) >> 1;
            bool flag = false;
            for (int i = 1; i <= m - mid + 1; i++) {
    
                for (int j = 1; j <= n - mid + 1; j++) {
    
                    if (validate(_mat, threshold, i, j, i + mid - 1,
                    j + mid - 1)) {
    
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }
            if (flag) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

---

1498. 满足条件的子序列数目

这题对于子序列数目需要做一个预处理，否则会超过上限

代码实现（部分看题解）

class Solution {
    
private:
    static constexpr int P = int(1E9) + 7;
    static constexpr int MAX_N = int(1E5) + 5;
    void pretreatment(vector<int>& po) {
    
        int f = 1;
        po.push_back(f);
        for (int i = 1; i < MAX_N; i++) {
    
            f = f * 2 % P;
            po.push_back(f);
        }
    }
public:
    int numSubseq(vector<int>& nums, int target) {
    
        vector<int> po;
        pretreatment(po);
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long ans = 0;
        for (int i = 0; i < n; i++) {
    
            if (2 * nums[i] > target) break;
            int t = target - nums[i];
            int bound = upper_bound(nums.begin() + i, nums.end(), t) -
            nums.begin();
            ans += po[bound - i - 1];
        }
        return ans % P;
    }
};