头像

wzc1995

ByteDance Ltd.




离线:3天前



wzc1995
4天前

题目描述

给定一个整数 n,请你找到满足下面条件的一个序列:

  • 整数 1 在序列中只出现一次。
  • 2n 之间每个整数都恰好出现两次。
  • 对于每个 2n 之间的整数 i,两个 i 之间出现的距离恰好为 i

序列里面两个数 a[i]a[j] 之间的 距离,我们定义为它们下标绝对值之差 |j - i|

请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下,一定存在解。

一个序列 a 被认为比序列 b(两者长度相同)字典序更大的条件是:ab 中第一个不一样的数字处,a 序列的数字比 b 序列的数字大。比方说,[0,1,9,0][0,1,5,6] 字典序更大,因为第一个不同的位置是第三个数字,且 95 大。

样例

输入:n = 3
输出:[3,1,2,3,2]
解释:[2,3,2,1,3] 也是一个可行的序列,但是 [3,1,2,3,2] 是字典序最大的序列。
输入:n = 5
输出:[5,3,1,4,3,5,2,4,2]

限制

  • 1 <= n <= 20

算法

(递归回溯) $O(n!)$
  1. 暴力递归回溯,对当前没有放置数字过的位置,枚举还尚未填充的数字,并一次性填充两个相同的数。

时间复杂度

  • 理论时间复杂度为 $O(n!)$,但实际上由于限制很多,暴搜可以很快出答案。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储求解的过程和递归的系统栈。

C++ 代码

class Solution {
private:
    vector<bool> used;
    vector<int> cur;

    bool solve(int x, int n) {
        if (x == 2 * n - 1) {
            return true;
        }
        if (cur[x] != -1) {
            return solve(x + 1, n);
        }

        for (int i = n; i >= 2; i--) {
            if (used[i]) continue;
            if (x + i < 2 * n - 1 && cur[x + i] == -1) {
                cur[x] = cur[x + i] = i;
                used[i] = true;
                if (solve(x + 1, n)) {
                    return true;
                }
                used[i] = false;
                cur[x] = cur[x + i] = -1;
            }
        }

        if (!used[1]) {
            cur[x] = 1;
            used[1] = true;
            if (solve(x + 1, n))
                return true;
            cur[x] = -1;
            used[1] = false;
        }
        return false;
    }

public:
    vector<int> constructDistancedSequence(int n) {
        used.resize(n + 1, false);
        cur.resize(2 * n - 1, -1);
        solve(0, n);
        return cur;
    }
};



wzc1995
4天前

题目描述

给定一个字符串 s 和两个整数 xy。你可以执行下面两种操作任意次。

  • 删除子字符串 "ab" 并得到 x 分。比方说,从 "cabxbae" 删除 "ab",得到 "cxbae"
  • 删除子字符串 "ba" 并得到 y 分。比方说,从 "cabxbae" 删除 "ba",得到 "cabxe"

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

样例

输入:s = "cdbcbbaaabab", x = 4, y = 5
输出:19
解释:
- 删除 "cdbcbbaaa[ba]b" 中的 "ba",得到 s = "cdbcbbaaab",加 5 分。
- 删除 "cdbcbbaa[ab]" 中的 "ab",得到 s = "cdbcbbaa",加 4 分。
- 删除 "cdbcb[ba]a" 中的 "ba",得到 s = "cdbcba",加 5 分。
- 删除 "cdbc[ba]" 中的 "ba",得到 s = "cdbc",加 5 分。
总得分为 5 + 4 + 5 + 5 = 19。
输入:s = "aabbaaxybbaabb", x = 5, y = 4
输出:20

限制

  • 1 <= s.length <= 10^5
  • 1 <= x, y <= 10^4
  • s 只包含小写英文字母。

算法1

(贪心,栈) $O(n)$
  1. 如果 x >= y,则可以先消除 "ab" 然后消除 "ba"。否则,先消除 "ba" 然后消除 "ab"
  2. 贪心的正确性:每次删除都会同时减少一个 a 和一个 b,最终的删掉 abba 的总数是固定的。不妨假设 x >= y(否则可以交换 ab 以及 xy),则先删除了 ba 可能导致之后的某个 ab 无法删除,从而丢掉高分。
  3. 消除操作可以依靠栈进行。

时间复杂度

  • 遍历两次字符串,故总时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储栈和临时字符串。

C++ 代码

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        stack<char> st;
        int ans = 0;
        for (char c : s) {
            if (x >= y && !st.empty() && st.top() == 'a' && c == 'b') {
                ans += x;
                st.pop();
            } else if (x < y && !st.empty() && st.top() == 'b' && c == 'a') {
                ans += y;
                st.pop();
            } else {
                st.push(c);
            }
        }
        string t;
        while (!st.empty()) {
            t.push_back(st.top());
            st.pop();
        }
        for (char c : t) {
            if (!st.empty() && st.top() == 'a' && c == 'b') {
                ans += y;
                st.pop();
            } else if (!st.empty() && st.top() == 'b' && c == 'a') {
                ans += x;
                st.pop();
            } else {
                st.push(c);
            }
        }
        return ans;
    }
};

算法2

(贪心) $O(n)$
  1. 贪心思路同 1。
  2. 遍历过程中,不妨假设 x >= y,聚焦在每一组连续的 ab 的子串上。
  3. 对于一组子串,从左到右遍历过程中,用两个变量分别记录 ab 的个数,具体如下:
    • 如果当前为 a,则 a 的个数加 1。
    • 如果当前为 b,则考虑是否有剩余的 a 与其匹配,即 a 的个数是否大于 0,这是因为 a 的个数大于 0 一定说明当前位置除去 ab 以后,是以 a 结尾的。
      • 如果有,则 a 的个数减 1,答案加上 x
      • 如果没有,则 b 的个数加 1。
    • 子串遍历结束后,剩下的都是可以组成 ba 的情况,答案累加 ab 中较少的个数乘 y

时间复杂度

  • 遍历字符串最多两次,故总时间复杂度为 $O(n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        const int n = s.size();
        if (x < y) {
            for (int i = 0; i < n; i++) {
                if (s[i] == 'a') s[i] = 'b';
                else if (s[i] == 'b') s[i] = 'a';
            }
            swap(x, y);
        }

        int ans = 0, ta = 0, tb = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'a') {
                ta++;
            } else if (s[i] == 'b') {
                if (ta > 0) {
                    ta--;
                    ans += x;
                } else {
                    tb++;
                }
            } else {
                ans += min(ta, tb) * y;
                ta = tb = 0;
            }
        }
        return ans + min(ta, tb) * y;
    }
};



wzc1995
4天前

题目描述

Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。

最开始,他在周一的时候存入 1 块钱。从周二到周日,他每天都比前一天多存入 1 块钱。在接下来每一个周一,他都会比 前一个周一 多存入 1 块钱。

给定 n,请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。

样例

输入:n = 4
输出:10
解释:第 4 天后,总额为 1 + 2 + 3 + 4 = 10。
输入:n = 10
输出:37
解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37。
注意到第二个星期一,Hercy 存入 2 块钱。
输入:n = 20
输出:96
解释:第 20 天后,总额为
(1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96。

限制

  • 1 <= n <= 1000

算法

(数学) $O(1)$
  1. 令 $m = \frac{n}{7}$ 为完整的周数,$r = n \% 7$ 为最后一个不完整周的天数。
  2. 通过等差数列求和,可以分别计算出完整的周所获得的钱数。同样,通过等差数列求和,计算出最后一个不完整的周所获得的钱数。

时间复杂度

  • 直接用公式计算,故时间复杂度为常数。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int totalMoney(int n) {
        const int m = n / 7;
        const int r = n % 7;
        return 28 * m + 7 * (m - 1) * m / 2 + 
            (m + 1 + m + r) * r / 2;
    }
};



wzc1995
5天前

题目描述

未知 整数数组 arrn 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded,其中 encoded[i] = arr[i] XOR arr[i + 1]。例如,arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3]

给定编码后的数组 encoded 和原数组 arr 的第一个元素 firstarr[0])。

请解码返回原数组 arr。可以证明答案存在并且是唯一的。

样例

输入:encoded = [1,2,3], first = 1
输出:[1,0,2,1]
解释:若 arr = [1,0,2,1],那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
输入:encoded = [6,2,7,3], first = 4
输出:[4,2,0,7,4]

限制

  • 2 <= n <= 10^4
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 10^5
  • 0 <= first <= 10^5

算法

(数学) $O(n)$
  1. 根据异或的性质,得到 arr[i + 1] = arr[i] XOR encoded[i],然后遍历解码。

时间复杂度

  • 遍历一遍数组即可解码,故总时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        const int n = encoded.size();
        vector<int> ans(n + 1);
        ans[0] = first;

        for (int i = 1; i <= n; i++)
            ans[i] = ans[i - 1] ^ encoded[i - 1];
        return ans;
    }
};



wzc1995
5天前

题目描述

给定链表的头节点 head 和一个整数 k

交换 链表正数第 k 个节点和倒数第 k 个节点的值后,返回链表的头节点(链表1 开始索引)。

样例

linked1.jpg

输入:head = [1,2,3,4,5], k = 2
输出:[1,4,3,2,5]
输入:head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出:[7,9,6,6,8,7,3,0,9,5]
输入:head = [1], k = 1
输出:[1]
输入:head = [1,2], k = 1
输出:[2,1]
输入:head = [1,2,3], k = 2
输出:[1,2,3]

限制

  • 链表中节点的数目是 n
  • 1 <= k <= n <= 10^5
  • 0 <= Node.val <= 100

算法1

(三次遍历) $O(n)$
  1. 先遍历一次求出链表的长度 n
  2. 然后分别找到第 k 个节点和第 n - k + 1 个节点,并交换其值。

时间复杂度

  • 遍历链表三次,故总时间复杂度为 $O(n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

/**
 * 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 {
private:
    ListNode* find(ListNode *head, int k) {
        int i = 1;
        for (ListNode *p = head; p != nullptr; p = p->next, i++)
            if (i == k)
                return p;

        return nullptr;
    }

public:
    ListNode* swapNodes(ListNode* head, int k) {
        int n = 0;
        for (ListNode *p = head; p != nullptr; p = p->next)
            n++;

        ListNode *p = find(head, k);
        ListNode *q = find(head, n - k + 1);
        swap(p->val, q->val);
        return head;
    }
};

算法2

(两次遍历) $O(n)$
  1. 先找到第 $k$ 个节点 $p$。
  2. 此时 $p$ 后还有 $n - k$ 个节点。记录 $p$ 的一个副本 $pc$。
  3. 令 $pc$ 和 $q$ 同时移动,直到 $pc->next$ 为空。
  4. 此时 $p$ 是第 $k$ 个节点,$q$ 是倒数第 $k$ 个节点。

时间复杂度

  • 遍历链表两次,故总时间复杂度为 $O(n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

/**
 * 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:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode *p = head;
        while (--k) p = p->next;

        ListNode *pc = p, *q = head;
        while (pc->next) {
            q = q->next;
            pc = pc->next;
        }
        swap(p->val, q->val);
        return head;
    }
};



wzc1995
5天前

题目描述

给定两个整数数组 sourcetarget,长度都是 n。还有一个数组 allowedSwaps,其中每个 allowedSwaps[i] = [a_i, b_i] 表示你可以交换数组 source 中下标为 a_ib_i(下标从 0 开始)的两个元素。注意,你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

相同长度的两个数组 sourcetarget 间的 汉明距离 是元素不同的下标数量。形式上,其值等于满足 source[i] != target[i](下标从 0 开始)的下标 i0 <= i <= n-1)的数量。

在对数组 source 执行 任意 数量的交换操作后,返回 sourcetarget 间的 最小汉明距离

样例

输入:
source = [1,2,3,4]
target = [2,1,4,5]
allowedSwaps = [[0,1],[2,3]]
输出:1
解释:source 可以按下述方式转换:
- 交换下标 0 和 1 指向的元素:source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素:source = [2,1,4,3]
source 和 target 间的汉明距离是 1,二者有 1 处元素不同,在下标 3。
输入:
source = [1,2,3,4]
target = [1,3,2,4]
allowedSwaps = []
输出:2
解释:不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2,二者有 2 处元素不同,在下标 1 和下标 2。
输入:
source = [5,1,2,4,3]
target = [1,5,4,2,3]
allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出:0

限制

  • n == source.length == target.length
  • 1 <= n <= 10^5
  • 1 <= source[i], target[i] <= 10^5
  • 0 <= allowedSwaps.length <= 10^5
  • allowedSwaps[i].length == 2
  • 0 <= a_i, b_i <= n - 1
  • a_i != b_i

算法

(并查集,哈希表) $O(n)$
  1. 将下标 0n - 1 按照 allowedSwaps 进行分组,[x, y] 表示下标 x 和下标 y 在同一组。由于可以任意多次操作,所以在同一组内的下标之间可以任意交换值。
  2. 通过并查集可以计算出分组。
  3. 对于每个组,通过哈希表求出 sourcetarget 的不同值的差距。

时间复杂度

  • 假设并查集 find 的时间为常数,则分组的时间为 $O(n)$。
  • 分组后,通过哈希表计算差距的总时间也为 $O(n)$。
  • 故总时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储并查集数据结构和哈希表。

C++ 代码

class Solution {
private:
    vector<int> f, sz;

    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (sz[fx] < sz[fy]) {
                f[fx] = fy;
                sz[fy] += sz[fx];
            } else {
                f[fy] = fx;
                sz[fx] += sz[fy];
            }
        }
    }

public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target,
                            vector<vector<int>>& allowedSwaps) {

        const int n = source.size();
        f.resize(n);
        sz.resize(n, 1);
        for (int i = 0; i < n; i++)
            f[i] = i;

        for (const auto &e : allowedSwaps)
            merge(e[0], e[1]);

        vector<vector<int>> mp(n);
        for (int i = 0; i < n; i++)
            mp[find(i)].push_back(i);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            unordered_map<int, int> seen;
            for (int j : mp[i]) {
                seen[source[j]]++;
                seen[target[j]]--;
            }
            for (const auto &it : seen)
                ans += abs(it.second);
        }
        return ans / 2;
    }
};



wzc1995
5天前

题目描述

给定一个整数数组 jobs,其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人,且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案,使工人的 最大工作时间 得以 最小化

返回分配方案中尽可能 最小最大工作时间

样例

输入:jobs = [3,2,3], k = 3
输出:3
解释:给每位工人分配一项工作,最大工作时间是 3。
输入:jobs = [1,2,4,7,8], k = 2
输出:11
解释:按下述方式分配工作:
1 号工人:1、2、8(工作时间 = 1 + 2 + 8 = 11)
2 号工人:4、7(工作时间 = 4 + 7 = 11)
最大工作时间是 11。

限制

  • 1 <= k <= jobs.length <= 12
  • 1 <= jobs[i] <= 10^7

算法1

(状态压缩动态规划,子集枚举) $O(n \cdot 2^n + k \cdot 3^n)$
  1. 设状态 $f(i, s)$ 表示 $k$ 个人完成状态为 $s$ 的任务时的最小的最大工作时间。其中,$i$ 的有效下标从 1 开始,$s$ 的范围是 $0$ 到 $2^n - 1$。
  2. 初始时,$f(0, 0) = 0$,其余为正无穷。
  3. 转移时,对于 $f(i, s)$,枚举 $s$ 的非空子集 $sub$,令第 $i$ 个人完成 $sub$,转移 $f(i, s) = \min(f(i, s), \max(f(i - 1, s - sub), sum[sub]))$。其中 $sum$ 可以预处理出来。
  4. 最终答案为 $f(k, 2^n - 1)$。

时间复杂度

  • 预处理需要 $O(n \cdot 2^n)$ 的时间。
  • 动态规划状态数为 $O(k \cdot 2^n)$,对于每个人,总的转移时间为 $O(3^n)$。
  • 故总时间复杂度为 $O(n \cdot 2^n + k \cdot 3^n)$

空间复杂度

  • 需要 $O(k \cdot 2^n)$ 的空间存储预处理数组和状态。

C++ 代码

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        const int n = jobs.size();
        const int INF = 1000000000;
        vector<vector<int>> f(k + 1, vector<int>(1 << n, INF));
        vector<int> sum(1 << n, 0);

        for (int s = 0; s < (1 << n); s++)
            for (int i = 0; i < n; i++)
                if (s & (1 << i))
                    sum[s] += jobs[i];

        f[0][0] = 0;
        for (int i = 1; i <= k; i++)
            for (int s = 0; s < (1 << n); s++)
                for (int sub = s; sub > 0; sub = (sub - 1) & s)
                    f[i][s] = min(f[i][s], max(f[i - 1][s ^ sub], sum[sub]));

        return f[k][(1 << n) - 1];
    }
};

算法2

(二分答案,状态压缩动态规划) $O(n \cdot 2^n \cdot \log S)$
  1. 求最大值最小,可以通过二分答案转判定性问题,二分的下界为所有工作的最大值,上界为工作的时间总和 $S$。
  2. 假设当前的限定值为 $lim$,求此时最少需要多少个人。
  3. 设状态 $f(s)$ 表示完成状态为 $s$ 时,所需要的最少人数,以及最后一个人已经占用的时间。
  4. 初始时,$f(0) = (0, +\infty)$,其余为 $(0, +\infty)$。
  5. 转移时,对于 $f(s)$,枚举某个工作 $i$,判断 $f(s - 2^i)$ 的状态如何转移到 $f(s)$,并更新 $f(s)$ 的最小值。
  6. 最终返回的值为 $f(2^n - 1).first$。

时间复杂度

  • 二分的区间为 $S$。
  • 每次动态规划的状态数为 $O(2^n)$,转移时间为 $O(n)$。
  • 故总时间复杂度为 $O(n \cdot 2^n \cdot \log S)$。
  • 其实可以进一步优化,由于待定的答案一定是 $2^n$ 种组合中的一个,所以时间复杂度可以优化为 $O(n \cdot 2^n \log 2^n) = O(n^2 \cdot 2^n)$。

空间复杂度

  • 需要 $O(2^n)$ 的空间存储状态。

C++ 代码

#define INF 1000000000

class Solution {
private:
    int calc(int lim, const vector<int> &jobs) {
        const int n = jobs.size();
        vector<pair<int, int>> f(1 << n, make_pair(INF, INF));
        f[0].first = 0;
        f[0].second = INF;

        for (int s = 1; s < (1 << n); s++) {
            for (int i = 0; i < n; i++) {
                if (!(s & (1 << i)))
                    continue;
                pair<int, int> t;
                if (f[s ^ (1 << i)].second + jobs[i] > lim) {
                    t.first = f[s ^ (1 << i)].first + 1;
                    t.second = jobs[i];
                } else {
                    t.first = f[s ^ (1 << i)].first;
                    t.second = f[s ^ (1 << i)].second + jobs[i];
                }
                f[s] = min(f[s], t);
            }
        }
        return f[(1 << n) - 1].first;
    }

public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int l = 0, r = INF;
        for (int x : jobs)
            if (l < x)
                l = x;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (calc(mid, jobs) <= k) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};



wzc1995
11天前

题目描述

给定一个数组 target,包含若干 互不相同 的整数,以及另一个整数数组 arrarr 可能 包含重复元素。

每一次操作中,你可以在 arr 的任意位置插入任一整数。比方说,如果 arr = [1,4,1,2],那么你可以在中间添加 3 得到 [1,4,3,1,2]。你可以在数组最开始或最后面添加整数。

请你返回 最少 操作次数,使得 target 成为 arr 的一个子序列。

一个数组的 子序列 指的是删除原数组的某些元素(可能一个元素都不删除),同时不改变其余元素的相对顺序得到的数组。比方说,[2,7,4][4,2,3,7,2,1,4] 的子序列(加粗元素),但 [2,4,2] 不是子序列。

样例

输入:target = [5,1,3], arr = [9,4,2,3,4]
输出:2
解释:你可以添加 5 和 1,使得 arr 变为 [5,9,4,1,2,3,4],target 为 arr 的子序列。
输入:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出:3

限制

  • 1 <= target.length, arr.length <= 10^5
  • 1 <= target[i], arr[i] <= 10^9
  • target 不包含任何重复元素。

算法

(贪心,动态规划,树状数组) $O(n \log n)$
  1. 由于 target 不含有重复数字,故其本身可以当做一种排列。
  2. target(i) 映射到 i + 1,然后在 arr 上,对着映射关系求出最长上升子序列。因为插入一个数字的代价为 1,所以直接寻找最长上升子序列就是全局最优。
  3. $n$ 减去最长上升子序列的长度就是答案。

时间复杂度

  • 构造哈希表的时间复杂度为 $O(n)$。
  • 用树状数组优化的最长上升子序列的时间复杂度为 $O(n \log n)$。
  • 故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储哈希表和树状数组。

C++ 代码

#define max(x, y) ((x) > (y) ? (x) : (y))

class Solution {
private:
    vector<int> f;

    void update(int x, int y, int n) {
        for (; x <= n; x += x & -x)
            f[x] = max(f[x], y);
    }

    int query(int x) {
        int ma = 0;
        for (; x; x -= x & -x)
            ma = max(ma, f[x]);
        return ma;
    }

public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        const int n = target.size();
        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++)
            mp[target[i]] = i + 1;

        f.resize(n + 1, 0);
        const int m = arr.size();

        int res = 0;
        for (int i = 0; i < m; i++) {
            if (mp.find(arr[i]) == mp.end())
                continue;
            int x = mp[arr[i]];
            int t = query(x - 1) + 1;
            update(x, t, n);
            if (t > res)
                res = t;
        }

        return n - res;
    }
};



wzc1995
12天前

题目描述

我们称一个分割整数数组的方案是 好的,当它满足:

  • 数组被分成三个 非空 连续子数组,从左至右分别命名为 leftmidright
  • left 中元素和小于等于 mid 中元素和,mid 中元素和小于等于 right 中元素和。

给定一个 非负 整数数组 nums,请你返回 好的 分割 nums 方案数目。由于答案可能会很大,请你将结果对 10^9 + 7 取余后返回。

样例

输入:nums = [1,1,1]
输出:1
解释:唯一一种好的分割方案是将 nums 分成 [1] [1] [1]。
输入:nums = [1,2,2,2,5,0]
输出:3
解释:nums 总共有 3 种好的分割方案:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
输入:nums = [3,2,1]
输出:0
解释:没有好的分割方案。

限制

  • 3 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^4

算法

(前缀和、双指针) $O(n)$
  1. 求出原数组的前缀和数组。
  2. 对于每个给定的第二分割点 $i$,找到第一分割点的上下界 $l$ 和 $r$,使得根据在第一分割点范围内的点都满足条件。
  3. 注意到,第一分割点的下界控制 $mid \le right$,上界控制 $left \le mid$,且上下界都是随着 $i$ 单调不减的,故可以使用双指针维护。

时间复杂度

  • 预处理的时间复杂度为 $O(n)$。
  • 统计答案的时间复杂度为 $O(n)$。
  • 故总时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储前缀和数组。
  • 可以通过动态维护部分和,优化掉前缀和数组,使空间复杂度降为常数。

C++ 代码

class Solution {
public:
    int waysToSplit(vector<int>& nums) {
        const int n = nums.size();
        vector<int> sum(n + 1, 0);
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + nums[i - 1];

        const int mod = 1000000007;
        int ans = 0;
        for (int i = 3, r = 2, l = 2; i <= n; i++) {
            while (r < i && sum[r - 1] <= sum[i - 1] - sum[r - 1]) r++;
            while (l < i && sum[i - 1] - sum[l - 1] > sum[n] - sum[i - 1]) l++;
            ans = (ans + max(0, r - l)) % mod;
        }
        return ans;
    }
};



wzc1995
12天前

题目描述

大餐 是指 恰好包含两道不同餐品 的一餐,其美味程度之和等于 2 的幂。

你可以搭配 任意 两道餐品做一顿大餐。

给定一个整数数组 deliciousness,其中 deliciousness[i] 是第 i 道餐品的美味程度,返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 10^9 + 7 取余。

注意,只要餐品下标不同,就可以认为是不同的餐品,即便它们的美味程度相同。

样例

输入:deliciousness = [1,3,5,7,9]
输出:4
解释:大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ,都是 2 的幂。
输入:deliciousness = [1,1,1,3,3,3,7]
输出:15
解释:大餐的美味程度组合为 3 种 (1,1) ,9 种 (1,3) ,和 3 种 (1,7) 。

限制

  • 1 <= deliciousness.length <= 10^5
  • 0 <= deliciousness[i] <= 2^20

算法

(哈希表) $O(n \log S)$
  1. 用哈希表统计每种数字出现的次数。
  2. 对于数字 $x$,枚举 2 的幂次,求出方案数。
  3. 最后通过除以 2 来去掉重复计算的部分。

时间复杂度

  • 哈希表统计的时间复杂度为 $O(n)$。
  • 对于每种数字,需要 $O(\log S)$ 的时间统计答案。其中 $S$ 为最大的数字。
  • 故总时间复杂度为 $O(n \log S)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

#define LL long long

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        unordered_map<int, int> meals;

        for (int x : deliciousness)
            meals[x]++;

        LL ans = 0;
        for (const auto &m : meals)
            for (int i = (1 << 21); i > 0 && i >= m.first; i >>= 1)
                if (meals.find(i - m.first) != meals.end()) {
                    if (i == 2 * m.first)
                        ans += (LL)(m.second - 1) * m.second;
                    else
                        ans += (LL)(meals[i - m.first]) * m.second;
                }

        const int mod = 1000000007;
        return ans / 2 % mod;
    }
};