526互联

第 367 场周赛(双指针,集合（upper_bound&lower_bound），前后缀分解)

发布时间 2023-10-18 19:57:30作者: 深渊之巅

2903. 找出满足差值条件的下标 I

2905. 找出满足差值条件的下标 II

这两个题只有数据范围上面的差距

 这个题我们大体思路是维护双指针，枚举数字，维护集合。

这是灵神视频的代码

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        max_idx = min_idx = 0
        for j in range(indexDifference, len(nums)):
            i = j - indexDifference
            if nums[i] > nums[max_idx]:
                max_idx = i
            if nums[i] < nums[min_idx]:
                min_idx = i

            if abs(nums[j] - nums[max_idx]) >= valueDifference:
                return [max_idx, j]
            if abs(nums[j] - nums[min_idx]) >= valueDifference:
                return [min_idx, j]

        return [-1, -1]

这是自己写时候的代码--真的维护了个集合

class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        int n = nums.size();
         vector<int> res(2, -1);
        set<int> st;
        unordered_map<int, int> mp;
        int l;
        for(int r = indexDifference; r < n; r ++ ) {
            l = r - indexDifference;
            st.insert(nums[l]);
            mp[nums[l]] = l;
            //找到大于等于一个数的最小数
            int tmp = nums[r] + valueDifference;
            auto upper = st.lower_bound(tmp);
            if(upper != st.end()) {
                res[0] = mp[*upper];
                res[1] = r;
                break;
            }
            
            //找到小于等于一个数的最大数
            //upper_bound找到第一个大于tmp的数字，将返回的迭代器--就可找到小于等于一个数的最大数
            tmp = nums[r] - valueDifference;
            auto lower = st.upper_bound(tmp);
            if(lower != st.begin()) {
                lower -- ;
                res[0] = mp[*lower];
                res[1] = r;
                break;
            }
        }
        return res;
    }
};

 

 

2906. 构造乘积矩阵

二维前后缀分解题目

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n, m = len(grid), len(grid[0])

        MOD = 12345
        p = [[0] * m for _ in range(n)]

        suf = 1
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                p[i][j] = suf
                suf = suf * grid[i][j] % MOD

        pre = 1
        for i in range(n):
            for j in range(m):
                p[i][j] = p[i][j] * pre % MOD
                pre = pre * grid[i][j] % MOD
        
        return p