头像

wzc1995

ByteDance Ltd.




离线:20小时前



wzc1995
20小时前

题目描述

给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

diagonal_traverse.png

样例

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出:[1,2,4,7,5,3,6,8,9]

限制

  • 给定矩阵中的元素总数不会超过 100000

算法

(模拟) $O(mn)$
  1. 正对角线遍历,可以按照每个对角线坐标的和枚举。

时间复杂度

  • 每个位置仅遍历一次,故总时间复杂度为 $O(mn)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        const int m = matrix.size();
        if (m == 0) return {};
        const int n = matrix[0].size();
        vector<int> ans(m * n);
        int cnt = 0;

        for (int s = 0; s <= m + n - 2; s++) {
            if (s % 2 == 1) {
                for (int i = max(0, s - n + 1); i <= min(m - 1, s); i++)
                    ans[cnt++] = matrix[i][s - i];
            } else {
                for (int i = min(m - 1, s); i >= max(0, s - n + 1); i--)
                    ans[cnt++] = matrix[i][s - i];
            }
        }
        return ans;
    }
};



wzc1995
20小时前

题目描述

有一个密钥字符串 S,只包含字母,数字以及 '-'(破折号)。其中,N'-' 将字符串分成了 N+1 组。

给定一个数字 K,请你重新格式化字符串,使每个分组恰好包含 K 个字符。特别地,第一个分组包含的字符个数必须小于等于 K,但至少要包含 1 个字符。两个分组之间需要用 '-'(破折号)隔开,并且将所有的小写字母转换为大写字母。

给定非空字符串 S 和数字 K,按照上面描述的规则进行格式化。

样例

输入:S = "5F3Z-2e-9-w", K = 4
输出:"5F3Z-2E9W"
解释:字符串 S 被分成了两个部分,每部分 4 个字符;
      注意,两个额外的破折号需要删掉。
输入:S = "2-5g-3-J", K = 2
输出:"2-5G-3J"
解释:字符串 S 被分成了 3 个部分。
按照前面的规则描述,第一部分的字符可以少于给定的数量,其余部分皆为 2 个字符。

限制

  • S 的长度可能很长,请按需分配大小。K 为正整数。
  • S 只包含字母数字(a-zA-Z0-9)以及破折号 '-'
  • S 非空。

算法

(模拟) $O(n)$
  1. 先将字符串全部去除 '-'
  2. 然后再对字符串进行重新分组,注意一下分情况讨论。

时间复杂度

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

空间复杂度

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

C++ 代码

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        int n = 0;
        for (int i = 0; i < S.size(); i++)
            if (S[i] != '-') {
                if (S[i] >= 'a' && S[i] <= 'z')
                    S[i] = S[i] - 'a' + 'A';
                S[n++] = S[i];
            }

        if (n == 0)
            return "";

        int first = n % K;
        if (first == 0)
            first = K;

        string res = S.substr(0, first);
        int counter = 0;
        for (int i = first; i < n; i++) {
            if (counter % K == 0)
                res += '-';
            res += S[i];
            counter++;
        }

        return res;
    }
};



wzc1995
1天前

题目描述

给定圆的半径和圆心的 xy 坐标,写一个在圆中产生均匀随机点的函数 randPoint

说明

  • 输入值和输出值都将是 浮点数
  • 圆的半径和圆心的 xy 坐标将作为参数传递给类的构造函数。
  • 圆周上的点也认为是在圆中。
  • randPoint 返回一个包含随机点的 x 坐标和 y 坐标的大小为 2 的数组。

样例

输入: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
输入: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

输入语法说明

  • 输入是两个列表:调用成员函数名和调用的参数。
  • Solution 的构造函数有三个参数,圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint 没有参数。输入参数是一个列表,即使参数为空,也会输入一个 [] 空列表。

算法

(矩形内采样) $O(1)$
  1. 在圆外切矩形内撒点采样。
  2. 如果采样的点在圆内,返回;否则重新采样。
  3. 由于二维的每一维都是均匀分布的,所以结果也是均匀分布的。

时间复杂度

  • 平均每轮需要 $\frac{4}{\pi} = 1.273$ 次采样。

空间复杂度

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

C++ 代码

class Solution {
private:
    double r, x, y;

public:
    Solution(double radius, double x_center, double y_center) {
        r = radius;
        x = x_center;
        y = y_center;
    }

    vector<double> randPoint() {
        while (1) {
            double cx = 2 * r * rand() / RAND_MAX - r + x;
            double cy = 2 * r * rand() / RAND_MAX - r + y;
            if ((cx - x) * (cx - x) + (cy - y) * (cy - y) <= r * r)
                return {cx, cy};
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */

算法2

(直接采样) $O(1)$
  1. 考虑直接在圆内撒点采样。
  2. 圆内的点有两个参数,距离圆心的距离和角度。
  3. 距离圆心的距离是二维的,需要在 [0, r^2] 内采样然后开方,才能保证是均匀分布。
  4. 角度直接在 [0, 2 * pi] 内采样就可以。
  5. 最后计算在当前距离和角度下的二维坐标。

时间复杂度

  • 每一轮仅需要随机一次。

空间复杂度

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

C++ 代码

class Solution {
private:
    double r, x, y;

public:
    Solution(double radius, double x_center, double y_center) {
        r = radius;
        x = x_center;
        y = y_center;
    }

    vector<double> randPoint() {
        double cr = r * sqrt(1.0 * rand() / RAND_MAX);
        double angle = 2 * M_PI * rand() / RAND_MAX;
        double cx = x + cr * cos(angle), cy = y + cr * sin(angle);
        return {cx, cy};
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */



wzc1995
3天前

题目描述

给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数,则向前移动 k 个索引。相反,如果是负数 -k,则向后移动 k 个索引。因为数组是环形的,所以可以假设最后一个元素的下一个元素是第一个元素,而第一个元素的前一个元素是最后一个元素。

确定 nums 中是否存在循环(或周期)。循环必须在相同的索引处开始和结束并且循环长度大于 1。此外,一个循环中的所有运动都必须沿着同一方向进行。换句话说,一个循环中不能同时包括向前的运动和向后的运动。

样例

输入:[2,-1,1,2,2]
输出:true
解释:存在循环,按索引 0 -> 2 -> 3 -> 0。循环长度为 3。
输入:[-1,2]
输出:false
解释:按索引 1 -> 1 -> 1 ... 的运动无法构成循环,因为循环的长度为 1。
根据定义,循环的长度必须大于 1。
输入:[-2,1,-1,-2,-2]
输出:false
解释:按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环,
因为按索引 1 -> 2 的运动是向前的运动而按索引 2 -> 1 的运动是向后的运动。
一个循环中的所有运动都必须沿着同一方向进行。

限制

  • -1000 <= nums[i] <= 1000
  • nums[i] != 0
  • 0 <= nums.length <= 5000

进阶

  • 你能写出时间时间复杂度为 $O(n)$ 和额外空间复杂度为 $O(1)$ 的算法吗?

算法

(路径标记寻环) $O(n)$
  1. 首先将每个位置模 n,去掉那些走到自己的点。
  2. 对于每个非 0 位置开始寻环
    • 按照题目描述,如果当前位置大于 0,则寻前进环,访问到已经访问过得点或者值为负的点结束;否则寻倒退环,访问到已经访问过得点或者值为正的点结束。
    • 重点是寻环过程需要记录已经访问过的点,此时可以做一个特殊标记(例如遍历过的位置加一个大的 offset);如果又回到了特殊标记过的位置,则说明有环,返回 true
    • 如果没有走到特殊标记过的位置,说明不存在环;此时,需要再走一遍刚才走过的路径,把路径上的所有点请 0(防止再被访问)。

时间复杂度

  • 每个点最多被访问常数,故总时间复杂度为 $O(n)$。

空间复杂度

  • 在原数组上做标记,故仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    bool checkForward(int start, vector<int> &nums) {
        const int offset = 10000;
        const int n = nums.size();
        int i = start;
        do {
            int j = (i + nums[i] + n) % n;
            nums[i] += offset;
            i = j;
        } while (nums[i] > 0 && nums[i] <= 1000);

        if (nums[i] > 1000)
            return true;

        i = start;
        do {
            int j = (i + nums[i] - offset + n) % n;
            nums[i] = 0;
            i = j;
        } while (nums[i] > 0);

        return false;
    }

    bool checkBackward(int start, vector<int> &nums) {
        const int offset = 10000;
        const int n = nums.size();
        int i = start;
        do {
            int j = (i + nums[i] + n) % n;
            nums[i] += offset;
            i = j;
        } while (nums[i] < 0);

        if (nums[i] > 1000)
            return true;

        i = start;
        do {
            int j = (i + nums[i] - offset + n) % n;
            nums[i] = 0;
            i = j;
        } while (nums[i] < 0);

        return false;
    }

public:
    bool circularArrayLoop(vector<int>& nums) {
        const int n = nums.size();
        for (int i = 0; i < n; i++)
            nums[i] %= n;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0)
                continue;

            if (nums[i] > 0 && checkForward(i, nums))
                return true;

            if (nums[i] < 0 && checkBackward(i, nums))
                return true;
        }
        return false;
    }
};

算法2

(快慢指针寻环) $O(n)$
  1. 和算法 1 类似,只不过采用了经典的快慢指针寻环。

时间复杂度

  • 每个点最多被访问常数,故总时间复杂度为 $O(n)$。

空间复杂度

  • 在原数组上做标记,故仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    bool checkForward(int start, vector<int> &nums) {
        const int n = nums.size();
        int slow = start, fast = (start + nums[start] + n) % n;
        while (1) {
            slow = (slow + nums[slow] + n) % n;
            if (nums[slow] <= 0) break;

            fast = (fast + nums[fast] + n) % n;
            if (nums[fast] <= 0) break;

            fast = (fast + nums[fast] + n) % n;
            if (nums[fast] <= 0) break;

            if (slow == fast)
                return true;
        };

        int i = start;
        while (nums[i] > 0) {
            int j = (i + nums[i] + n) % n;
            nums[i] = 0;
            i = j;
        }
        return false;
    }

    bool checkBackward(int start, vector<int> &nums) {
        const int n = nums.size();
        int slow = start, fast = (start + nums[start] + n) % n;
        while (1) {
            slow = (slow + nums[slow] + n) % n;
            if (nums[slow] >= 0) break;

            fast = (fast + nums[fast] + n) % n;
            if (nums[fast] >= 0) break;

            fast = (fast + nums[fast] + n) % n;
            if (nums[fast] >= 0) break;

            if (slow == fast)
                return true;
        };

        int i = start;
        while (nums[i] < 0) {
            int j = (i + nums[i] + n) % n;
            nums[i] = 0;
            i = j;
        }
        return false;
    }

public:
    bool circularArrayLoop(vector<int>& nums) {
        const int n = nums.size();
        for (int i = 0; i < n; i++)
            nums[i] %= n;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0)
                continue;

            if (nums[i] > 0 && nums[(i + nums[i] + n) % n] > 0 && checkForward(i, nums))
                return true;

            if (nums[i] < 0 && nums[(i + nums[i] + n) % n] < 0 && checkBackward(i, nums))
                return true;
        }
        return false;
    }
};




wzc1995
6天前

题目描述

给定平面上 n 对不同的点,回旋镖 是由点表示的元组 (i, j, k),其中 ij 之间的距离和 ik 之间的距离相等(需要考虑元组的顺序)。

找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。

样例

输入:[[0,0],[1,0],[2,0]]
输出:2
解释:两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

算法

(哈希表) $O(n^2)$
  1. 枚举 $i$,然后遍历所有的回旋镖,计算距离并用哈希表记录每种距离的出现次数。

时间复杂度

  • 假设哈希表单次操作的时间复杂度为常数,总时间复杂度为 $O(n^2)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        const int n = points.size();
        int ans = 0;
        for (const auto &p : points) {
            unordered_map<int, int> tot;
            for (const auto &q : points) {
                int d = (p[0] - q[0]) * (p[0] - q[0]) +
                    (p[1] - q[1]) * (p[1] - q[1]);
                ans += tot[d];
                tot[d]++;
            }
        }
        return ans * 2;
    }
};



wzc1995
6天前

题目描述

给你一个数组 intervalsintervals[i] = [start_i, end_i],且每一个 start_i 都是 不同的

区间 i右区间 是另一个区间 j,满足 start_j >= end_istart_j最小的

返回一个数组,包含每一个区间 i右区间 下标。如果区间 i右区间 不存在,则在下标 i 的位置放入 -1

样例

输入:[[1,2]]
输出:[-1]
解释:集合中只有一个区间,所以输出 -1。
输入:[[3,4], [2,3], [1,2]]
输出:[-1, 0, 1]
解释:对于 [3,4],没有满足条件的右区间。
对于 [2,3],区间 [3,4] 具有最小的右起点;
对于 [1,2],区间 [2,3] 具有最小的右起点。
输入:[[1,4], [2,3], [3,4]]
输出:[-1, 2, -1]
解释:对于区间 [1,4] 和 [3,4],没有满足条件的右区间。
对于 [2,3],区间 [3,4] 有最小的右起点。

限制

  • 1 <= intervals.length <= 2 * 10^4
  • intervals[i].length == 2
  • -10^6 <= starti <= endi <= 10^6
  • 每个区间的起始下标都是 不同的

算法

(排序,二分) $O(n \log n)$
  1. 将区间按照起始点从小到大排序。
  2. 遍历区间,对于每个区间 $i$,二分查找区间 $j$,满足 start_j >= start_istart_j 最小。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 对于每个区间二分查找,故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储排序前的下标以及答案。

C++ 代码

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        const int n = intervals.size();
        for (int i = 0; i < n; i++)
            intervals[i].push_back(i);

        sort(intervals.begin(), intervals.end());

        vector<int> ans(n, -1);
        for (int i = 0; i < n; i++) {
            int l = i + 1, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (intervals[mid][0] < intervals[i][1])
                    l = mid + 1;
                else
                    r = mid;

            }
            if (l < n)
                ans[intervals[i][2]] = intervals[l][2];
        }
        return ans;
    }
};



wzc1995
7天前

题目描述

n 座城市,编号从 1n。编号为 xy 的两座城市直接连通的前提是:xy 的公因数中,至少有一个 严格大于 某个阈值 threshold。更正式地说,如果存在整数 z,且满足以下所有条件,则编号 xy 的城市之间有一条道路:

  • x % z == 0
  • y % z == 0
  • z > threshold

给定两个整数 nthreshold,以及一个待查询数组,请你判断每个查询 queries[i] = [a_i, b_i] 指向的城市 a_ib_i 是否连通(即,它们之间是否存在一条路径)。

返回数组 answer,其中 answer.length == queries.length。如果第 i 个查询中指向的城市 a_ib_i 连通,则 answer[i]true;如果不连通,则 answer[i]false

样例

ex1.jpg

输入:n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
输出:[false,false,true]
解释:每个数的因数如下:
1:   1
2:   1, 2
3:   1, 3
4:   1, 2, 4
5:   1, 5
6:   1, 2, 3, 6
所有大于阈值的的因数已经加粗标识,只有城市 3 和 6 共享公约数 3,因此结果是: 
[1,4]   1 与 4 不连通
[2,5]   2 与 5 不连通
[3,6]   3 与 6 连通,存在路径 3--6

tmp.jpg

输入:n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
输出:[true,true,true,true,true]
解释:每个数的因数与上一个例子相同。
但是,由于阈值为 0,所有的因数都大于阈值。
因为所有的数字共享公因数 1,所以所有的城市都互相连通。

ex3.jpg

输入:n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
输出:[false,false,false,false,false]
解释:只有城市 2 和 4 共享的公约数 2 严格大于阈值 1,所以只有这两座城市是连通的。
注意,同一对节点 [x, y] 可以有多个查询,并且查询 [x,y] 等同于查询 [y,x]。

限制

  • 2 <= n <= 10^4
  • 0 <= threshold <= n
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 1 <= a_i, b_i <= cities
  • a_i != b_i

算法

(素数筛,并查集) $O(n \log \log n + Q)$
  1. 通过古典的筛素数的方式发现连通关系,即从 i = threshold + 1 开始,如果 $i$ 没有被筛过,则将 2 * i, 3 * i, ... 的数组都标记被筛过,且通过并查集合并 (i, 2 * i), (i, 3 * i)
  2. 每一轮中被筛掉的数字,都会在同一个连通块中。
  3. 查询时直接查询并查集。

时间复杂度

  • 普通筛法的时间复杂度为 $O(n \log \log n)$。
  • 假设并查集单次操作的时间复杂度为常数,总时间复杂度为 $O(n \log \log n + Q)$。

空间复杂度

  • 需要 $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)
            return;
        if (sz[fx] < sz[fy]) {
            f[fx] = fy;
            sz[fy] += sz[fx];
        } else {
            f[fy] = fx;
            sz[fx] += sz[fy];
        }
    }

public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        f.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            f[i] = i;
            sz[i] = 1;
        }

        vector<bool> isFiltered(n + 1, false);

        for (int i = threshold + 1; i <= n; i++) {
            if (isFiltered[i])
                continue;

            for (int j = i + i; j <= n; j += i) {
                merge(i, j);
                isFiltered[j] = true;
            }
        }

        vector<bool> ans;
        for (const auto &q : queries)
            ans.push_back(find(q[0]) == find(q[1]));

        return ans;
    }
};



wzc1995
7天前

题目描述

假设你是球队的经理。对于即将到来的锦标赛,你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和

然而,球队中的矛盾会限制球员的发挥,所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员,则存在矛盾。同龄球员之间不会发生矛盾。

给定两个列表 scoresages,其中每组 scores[i]ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数

样例

输入:scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出:34
解释:你可以选中所有球员。
输入:scores = [4,5,6,5], ages = [2,1,2,1]
输出:16
解释:最佳的选择是后 3 名球员。注意,你可以选中多个同龄球员。
输入:scores = [1,2,3,5], ages = [8,9,10,1]
输出:6
解释:最佳的选择是前 3 名球员。

限制

  • 1 <= scores.length, ages.length <= 1000
  • scores.length == ages.length
  • 1 <= scores[i] <= 10^6
  • 1 <= ages[i] <= 1000

算法1

(排序,动态规划) $O(n^2)$
  1. 将所有人按照分数为第一关键字,年龄为第二关键字从小到大排序。(反之亦可)
  2. 此时,问题可以转换为,求当前数组的权值最大的不降子序列。
  3. 设状态 $f(i)$ 表示以第 $i$ 个为结尾时,所能得到的最大得分。
  4. 初始时,$f(i) = scores(i)$。
  5. 转移时,对于 $f(i)$,枚举 $j < i$,如果 $ages(j) \le ages(i)$,则转移 $f(i) = \max(f(i), f(j) + scores(i))$。
  6. 最终答案为 $\max(f(i))$。

时间复杂度

  • 排序需要 $O(n \log n)$ 的时间。
  • 动态规划状态数为 $O(n)$,转移需要 $O(n)$ 的时间。
  • 故总时间复杂度为 $O(n^2)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储排序后的数组以及动态规划的状态。

C++ 代码

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        const int n = scores.size();
        vector<int> rank(n);
        for (int i = 0; i < n; i++)
            rank[i] = i;

        sort(rank.begin(), rank.end(), [&](int x, int y){
            if (scores[x] != scores[y])
                return scores[x] < scores[y];
            return ages[x] < ages[y];
        });

        vector<int> f(n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            f[i] = scores[rank[i]];
            for (int j = 0; j < i; j++)
                if (ages[rank[j]] <= ages[rank[i]])
                    f[i] = max(f[i], f[j] + scores[rank[i]]);

            if (ans < f[i])
                ans = f[i];
        }

        return ans;
    }
};

算法2

(二维偏序,树状数组) $O(n \log (n + m))$
  1. 典型的二维偏序问题,先从小到大双关键字排序。
  2. 第一维已经通过排序解决,第二维可以使用优化过的动态规划,即树状数组解决。
  3. 由于第二维的范围为 [1, 1000],所以可以不必离散化。
  4. 树状数组 bits(x) 记录 [1, x] 中的得分最大值。
  5. 遍历排序后的数组时,首先查询位置小于等于 ages(i) 的最大值 tot,然后用 tot + scores(i) 去更新位置 ages(i)

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 设树状数组的最大范围为 $m$,求解过程的时间复杂度为 $O(n \log m)$。
  • 故总时间复杂度为 $O(n \log (n + m))$。

空间复杂度

  • 需要 $O(n + m)$ 的额外空间存储排序后的数组和树状数组。

C++ 代码

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

class Solution {
private:
    int m;
    vector<int> bits;

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

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

public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        const int n = scores.size();
        vector<int> rank(n);
        for (int i = 0; i < n; i++)
            rank[i] = i;

        sort(rank.begin(), rank.end(), [&](int x, int y){
            if (scores[x] != scores[y])
                return scores[x] < scores[y];
            return ages[x] < ages[y];
        });

        m = 1000;
        bits.resize(m + 1, 0);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int tot = query(ages[rank[i]]);
            update(ages[rank[i]], tot + scores[rank[i]]);
            ans = max(ans, tot + scores[rank[i]]);
        }

        return ans;
    }
};



wzc1995
7天前

题目描述

给定一个字符串 s 以及两个整数 ab。其中,字符串 s 的长度为偶数,且仅由数字 09 组成。

你可以在 s 上按任意顺序多次执行下面两个操作之一:

  • 累加:将 a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = "3456"a = 5,则执行此操作后 s 变成 "3951"
  • 轮转:将 s 向右轮转 b 位。例如,s = "3456"b = 1,则执行此操作后 s 变成 "6345"

请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。

如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样定义:在 ab 出现不同的第一个位置上,字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。例如,"0158" 字典序比 "0190" 小,因为不同的第一个位置是在第三个字符,显然 '5' 出现在 '9' 之前。

样例

输入:s = "5525", a = 9, b = 2
输出:"2050"
解释:执行操作如下:
初态:"5525"
轮转:"2555"
累加:"2454"
累加:"2353"
轮转:"5323"
累加:"5222"
累加:"5121"
轮转:"2151"
累加:"2050"
无法获得字典序小于 "2050" 的字符串。
输入:s = "74", a = 5, b = 1
输出:"24"
解释:执行操作如下:
初态:"74"
轮转:"47"
累加:"42"
轮转:"24"
无法获得字典序小于 "24" 的字符串。
输入:s = "0011", a = 4, b = 2
输出:"0011"
解释:无法获得字典序小于 "0011" 的字符串。
输入:s = "43987654", a = 7, b = 3
输出:"00553311"

限制

  • 2 <= s.length <= 100
  • s.length 是偶数。
  • s 仅由数字 09 组成。
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

算法

(宽度优先搜索 / BFS) $O(n^2)$
  1. 将每种字符串看做点,在能变换的字符串之间连边。
  2. 然后宽度优先遍历整个图,记录下来遍历过程中字符串字典序最小的。

时间复杂度

  • 共有 $O(n)$ 个点,每次变换需要 $O(n)$ 的时间计算与之相连的点,以及判断是否遍历过,故总时间复杂度为 $O(n^2)$。

空间复杂度

  • 需要 $O(n^2)$ 的额外空间存储队列以及哈希表。

C++ 代码

class Solution {
private:
    string rotate(const string &u, int d) {
        string v;
        for (int i = u.size() - d; i < u.size(); i++)
            v.push_back(u[i]);

        for (int i = 0; i < u.size() - d; i++)
            v.push_back(u[i]);

        return v;
    }

    string add(const string &u, int d) {
        string v(u);
        for (int i = 1; i < u.size(); i += 2)
            v[i] = (v[i] - '0' + d) % 10 + '0';
        return v;
    }

public:
    string findLexSmallestString(string s, int a, int b) {
        unordered_set<string> seen;
        queue<string> q;

        q.push(s);
        seen.insert(s);
        string ans(s);
        while (!q.empty()) {
            string u = q.front();
            q.pop();
            if (ans > u) ans = u;

            string v = add(u, a);
            if (seen.find(v) == seen.end()) {
                seen.insert(v);
                q.push(v);
            }

            v = rotate(u, b);
            if (seen.find(v) == seen.end()) {
                seen.insert(v);
                q.push(v);
            }
        }

        return ans;
    }
};



wzc1995
7天前

题目描述

给定一个字符串 s,请你返回 两个相同字符之间的最长子字符串的长度,计算长度时不含这两个字符。如果不存在这样的子字符串,返回 -1

子字符串 是字符串中的一个连续字符序列。

样例

输入:s = "aa"
输出:0
解释:最优的子字符串是两个 'a' 之间的空子字符串。
输入:s = "abca"
输出:2
解释:最优的子字符串是 "bc"。
输入:s = "cbzxy"
输出:-1
解释:s 中不存在出现出现两次的字符,所以返回 -1。
输入:s = "cabbac"
输出:4
解释:最优的子字符串是 "abba" ,其他的非最优解包括 "bb" 和 ""。

限制

  • 1 <= s.length <= 300
  • s 只含小写英文字母。

算法

(哈希表) $O(n)$
  1. 建立一个哈希表记录每个字符最早出现的位置。
  2. 遍历数组,如果当前字符不是第一次出现,那么用当前位置减去第一次出现的位置再减 1 来更新答案。

时间复杂度

  • 遍历一次数组,故时间复杂度为 $O(n)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        vector<int> firstSeen(26, -1);
        const int n = s.size();
        int ans = -1;

        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (firstSeen[c] == -1)
                firstSeen[c] = i;
            else
                ans = max(ans, i - firstSeen[c] - 1);
        }

        return ans;
    }
};