做网站时会遇到什么问题如何自己开一个平台

当前位置： 首页 > news >正文

做网站时会遇到什么问题,如何自己开一个平台,企业网站建设对企业的宣传作用,网站推广昔年下拉博客题目描述 这是 LeetCode 上的 「2736. 最大和查询」 #xff0c;难度为 「困难」。 Tag : 「排序」、「离散化」、「树状数组」 给你两个长度为 n、下标从 0 开始的整数数组 nums1 和 nums2#xff0c;另给你一个下标从 1 开始的二维数组 queries#xff0c;其中 。 对于第… 题目描述 这是 LeetCode 上的 「2736. 最大和查询」 难度为 「困难」。 Tag : 「排序」、「离散化」、「树状数组」 给你两个长度为 n、下标从 0 开始的整数数组 nums1 和 nums2另给你一个下标从 1 开始的二维数组 queries其中 。 对于第 i 个查询在所有满足 且 的下标 j ( ) 中找出 的 最大值 如果不存在满足条件的 j 则返回 。 返回数组 answer其中 answer[i] 是第 i 个查询的答案。 示例 1 输入nums1  [4,3,1,2], nums2  [2,4,9,5], queries  [[4,1],[1,3],[2,5]]输出[6,10,7]解释对于第 1 个查询xi  4 且 yi  1 可以选择下标 j  0 此时 nums1[j]  4 且 nums2[j]  1 。nums1[j]  nums2[j] 等于 6 可以证明 6 是可以获得的最大值。对于第 2 个查询xi  1 且 yi  3 可以选择下标 j  2 此时 nums1[j]  1 且 nums2[j]  3 。nums1[j]  nums2[j] 等于 10 可以证明 10 是可以获得的最大值。对于第 3 个查询xi  2 且 yi  5 可以选择下标 j  3 此时 nums1[j]  2 且 nums2[j]  5 。nums1[j]  nums2[j] 等于 7 可以证明 7 是可以获得的最大值。因此我们返回 [6,10,7] 。 示例 2 输入nums1  [3,2,5], nums2  [2,3,4], queries  [[4,4],[3,2],[1,1]]输出[9,9,9]解释对于这个示例我们可以选择下标 j  2 该下标可以满足每个查询的限制。 示例 3 输入nums1  [2,1], nums2  [2,3], queries  [[3,3]]输出[-1]解释示例中的查询 xi  3 且 yi  3 。对于每个下标 j 都只满足 nums1[j]  xi 或者 nums2[j]  yi 。因此不存在答案。  提示 离散化 排序 树状数组 根据题意两个等长的数组 num1 和 nums2只能是相同下标的元素凑成一对。 我们不妨用两个一维数组 nums1 和 nums2 构建出一个二维数组 nums方便后续处理其中 。 同时对 queries 进行简单拓展构建新的二维数组 nq目的是对原有下标信息进行记录其中 此处构建新 nq 的作用下文会说。 好了现在我们有两个新的数组 nums 和 nq接下来所有讨论都会针对新数组进行。 我希望你牢牢记住** 是对 nums1 和 nums2 的简单合并而 是对 queries 原有下标的拓展记录**。 做完简单的预处理工作后来思考一个前置问题 假设其他内容不变要求从满足「 且 」调整为仅需满足「 」我们会如何求解 一个简单的做法 对 nums 中的第一维即 和 nq 中第一维即 排倒序 从前往后处理每个询问 同时使用变量 idx 对 nums 进行扫描若满足 时将 idx 右移同时记录已被扫描的数对和 。 当 idx 不能再后移时说明当前所有满足 要求的数对已被扫描完在记录的数对和中取最大值即是当前询问 的答案 此处解释了为什么需要构造新数组 nq因为询问处理是按照排序后进行但在 ans 中需要映射回原有顺序。 重复步骤 直到处理完所有询问。 搞定前置问题后回到原问题需要满足「 且 」要求。 进一步思考排序 调整询问顺序只能解决其中一维限制要求另一维该如何处理 或者更加直接的问题如何在被记录的所有数对和 中找出那些满足 的最大数对和。 不失一般性假设当前处理到的是 其中 的限制要求通过前置问题的排序方式解决了。另外的 「 我们希望作为“位置信息”数对和 作为“值信息”进行记录」。 由于条件 我们需要对将要作为“位置信息”添加到树状数组的 和 进行离散化将其映射到 范围内。 对于每个询问都需要找到已遍历过的大于 的位置上的最大值把离散化后的值域换成数组坐标相当于求后缀最大值后缀最大值可通过相反数变成求前缀最大值。 能够实现类似的前缀操作支持“单点修改”和“区间查询”的数据结构是「树状数组」。 Java 代码 class Solution {    int sz;    int[] tr;    int lowbit(int x) {        return x  -x;    }    void add(int a, int b) {        for (int i  a; i  sz; i  lowbit(i)) tr[i]  Math.max(tr[i], b);    }    int query(int x) {        int ans  -1;        for (int i  x; i  0; i - lowbit(i)) ans  Math.max(ans, tr[i]);        return ans;    }    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {        int n  nums1.length, m  queries.length;        // 构建新的 nums 和 nq        int[][] nums  new int[n][2];        for (int i  0; i  n; i) nums[i]  new int[]{nums1[i], nums2[i]};        int[][] nq  new int[m][3];        for (int i  0; i  m; i) nq[i]  new int[]{queries[i][0], queries[i][1], i};        // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化构建映射字典, 将原值映射到 [0, m - 1])        SetInteger set  new HashSet();        for (int[] x : nums) set.add(x[1]);        for (int[] q : nq) set.add(q[1]);        ListInteger list  new ArrayList(set);        Collections.sort(list);        sz  list.size();        MapInteger, Integer map  new HashMap();        for (int i  0; i  sz; i) map.put(list.get(i), i);        // 调整询问顺序, 解决其中一维限制        Arrays.sort(nums, (a,b)-b[0]-a[0]);        Arrays.sort(nq, (a,b)-b[0]-a[0]);        tr  new int[sz  10];        Arrays.fill(tr, -1);        int[] ans  new int[m];        int idx  0;         for (int[] q : nq) {            int x  q[0], y  q[1], i  q[2];            // 扫描所有满足 nums[idx][0]  x 的数对, 添加到树状数组中其中离散值作为位置信息, 数对和作为值信息            while (idx  n  nums[idx][0]  x) {                add(sz - map.get(nums[idx][1]), nums[idx][0]  nums[idx][1]);                idx;            }            ans[i]  query(sz - map.get(y)); // 查询树状数组中的最值        }        return ans;    }} C 代码 class Solution {public:    int sz;    vectorint tr;    int lowbit(int x) {        return x  -x;    }    void add(int a, int b) {        for (int i  a; i  sz; i  lowbit(i)) tr[i]  max(tr[i], b);    }    int query(int x) {        int ans  -1;        for (int i  x; i  0; i - lowbit(i)) ans  max(ans, tr[i]);        return ans;    }    vectorint maximumSumQueries(vectorint nums1, vectorint nums2, vectorvectorint queries) {        int n  nums1.size(), m  queries.size();        // 构建新的 nums 和 nq        vectorvectorint nums(n, vectorint(2));        vectorvectorint nq(m, vectorint(3));        for (int i  0; i  n; i) {            nums[i][0]  nums1[i]; nums[i][1]  nums2[i];        }        for (int i  0; i  m; i) {            nq[i][0]  queries[i][0]; nq[i][1]  queries[i][1]; nq[i][2]  i;        }                // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化构建映射字典, 将原值映射到 [0, m - 1])        unordered_setint set;        for (auto x : nums) set.insert(x[1]);        for (auto q : nq) set.insert(q[1]);        vectorint list(set.begin(), set.end());        sort(list.begin(), list.end());        sz  list.size();        mapint, int map;        for (int i  0; i  sz; i) map[list[i]]  i;                // 调整询问顺序, 解决其中一维限制        sort(nums.begin(), nums.end(),  {            return a[0]  b[0];        });        sort(nq.begin(), nq.end(),  {            return a[0]  b[0];        });                tr.resize(sz  10, -1);                vectorint ans(m);        int idx  0;        for (auto q : nq) {            int x  q[0], y  q[1], i  q[2];            // 扫描所有满足 nums[idx][0]  x 的数对, 添加到树状数组中其中离散值作为位置信息, 数对和作为值信息            while (idx  n  nums[idx][0]  x) {                add(sz - map[nums[idx][1]], nums[idx][0]  nums[idx][1]);                idx;            }            ans[i]  query(sz - map[y]); // 查询树状数组中的最值        }        return ans;    }}; Python 代码 class Solution:    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) - List[int]:        sz  0        tr  []        def lowbit(x):            return x  -x        def add(a, b):            i  a            while i  sz:                tr[i]  max(tr[i], b)                i  lowbit(i)        def query(x):            ans, i  -1, x            while i  0:                ans  max(ans, tr[i])                i - lowbit(i)            return ans                n, m  len(nums1), len(queries)        # 构建新的 nums 和 nq        nums  [(nums1[i], nums2[i]) for i in range(n)]        nq  [(queries[i][0], queries[i][1], i) for i in range(m)]                #  对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化构建映射字典, 将原值映射到 [0, m - 1])        unique_set  set()        for x in nums:            unique_set.add(x[1])        for q in nq:            unique_set.add(q[1])        unique_list  list(unique_set)        unique_list.sort()        sz  len(unique_list)        mapping  {val: idx for idx, val in enumerate(uniquelist)}                # 调整询问顺序, 解决其中一维限制        nums.sort(keylambda x: x[0], reverseTrue)        nq.sort(keylambda x: x[0], reverseTrue)                tr  [-1] * (sz  10)                ans  [0] * m        idx  0        for x, y, i in nq:            # 扫描所有满足 nums[idx][0]  x 的数对, 添加到树状数组中其中离散值作为位置信息, 数对和作为值信息            while idx  n and nums[idx][0]  x:                add(sz - mapping[nums[idx][1]], nums[idx][0]  nums[idx][1])                idx  1            ans[i]  query(sz - mapping[y])  # 查询树状数组中的最值        return ans TypeScript 代码 function maximumSumQueries(nums1: number[], nums2: number[], queries: number[][]): number[] {    let sz  0;    let tr  [];    const lowbit  function(x: number): number {        return x  -x;    }    const add  function(a: number, b: number): void {        for (let i  a; i  sz; i  lowbit(i)) tr[i]  Math.max(tr[i], b);    }    const query  function(x: number): number {        let ans  -1;        for (let i  x; i  0; i - lowbit(i)) ans  Math.max(ans, tr[i]);        return ans;    }    const n  nums1.length, m  queries.length;    // 构建新的 nums 和 nq    const nums  Array.from({ length: n }, (, i)  [nums1[i], nums2[i]]);    const nq  Array.from({ length: m }, (_, i)  […queries[i], i]);    // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化构建映射字典, 将原值映射到 [0, m - 1])    const set: Setnumber  new Set();    for (const x of nums) set.add(x[1]);    for (const q of nq) set.add(q[1]);    const list: number[]  […set];    list.sort((a, b)  a - b);    sz  list.length;    const mapping  new Map();    for (let i  0; i  sz; i) mapping.set(list[i], i);            // 调整询问顺序, 解决其中一维限制    nums.sort((a, b)  b[0] - a[0]);    nq.sort((a, b)  b[0] - a[0]);    tr  Array(sz  10).fill(-1);    const ans  Array(m).fill(0);    let idx  0;    for (let [x, y, i] of nq) {        // 扫描所有满足 nums[idx][0]  x 的数对, 添加到树状数组中其中离散值作为位置信息, 数对和作为值信息        while (idx  n  nums[idx][0]  x) {            add(sz - mapping.get(nums[idx][1])!, nums[idx][0]  nums[idx][1]);            idx;        }        ans[i]  query(sz - mapping.get(y)!); // 查询树状数组中的最值    }    return ans;}; 时间复杂度令 nums1 长度为 queries 长度为 构建 nums 和 nq 的复杂度为 离散化复杂度为 对 nums 和 nq 的排序复杂度为 构建答案复杂度为 。整体复杂度为 空间复杂度 进阶 本题解讲述了「从一维到二维偏序问题」时可通过「一维排序一维树状数组」求通解。 那三维偏序问题呢是否存在通用的解决思路。 答一维排序一维归并一维树状数组。 最后 这是我们「刷穿 LeetCode」系列文章的第 No.2736 篇系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题我们将先把所有不带锁的题目刷完。 在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode 。 在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地