头像

wzc1995

ByteDance Ltd.


访客:552088

离线:3天前



wzc1995
4天前

题目描述

给你一个奇怪的打印机,它有如下两个特殊的打印规则:

  • 每一次操作时,打印机会用同一种颜色打印一个矩形的形状,每次打印会覆盖矩形对应格子里原本的颜色。
  • 一旦矩形根据上面的规则使用了一种颜色,那么 相同的颜色不能再被使用

给你一个初始没有颜色的 m x n 的矩形 targetGrid,其中 targetGrid[row][col] 是位置 (row, col) 的颜色。

如果你能按照上述规则打印出矩形 targetGrid,请你返回 true,否则返回 false

样例

sample_1_1929.png

输入:targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
输出:true

sample_2_1929.png

输入:targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
输出:true
输入:targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
输出:false
解释:没有办法得到 targetGrid ,因为每一轮操作使用的颜色互不相同。
输入:targetGrid = [[1,1,1],[3,1,3]]
输出:false

限制

  • m == targetGrid.length
  • n == targetGrid[i].length
  • 1 <= m, n <= 60
  • 1 <= targetGrid[row][col] <= 60

算法

(拓扑排序) $O(c(mn + c))$
  1. 对于每种颜色 $u$,求出其左上的位置和右下的位置。然后遍历以这两个位置确定的子矩形,对于其中的其他颜色 $v$,建立一条 $u$ 到 $v$ 的边。
  2. 拓扑排序,判断是否存在环。

时间复杂度

  • 假设共有 $c$ 种颜色,每种颜色需要 $O(mn)$ 的时间构建边,这需要 $O(cmn)$ 的时间复杂度,共有 $O(c^2)$ 条边。
  • 拓扑排序的时间复杂度等于边数,故总时间复杂度为 $O(c(mn + c))$。

空间复杂度

  • 需要 $O(c^2)$ 的额外空间存储整张图和存储拓扑排序的数据结构。

C++ 代码

class Solution {
private:
    int m, n, c;

    void build(int u, const vector<vector<int>> &targetGrid,
               vector<vector<int>> &graph, vector<int> &indeg) {
        int x1 = INT_MAX, y1 = INT_MAX, x2 = INT_MIN, y2 = INT_MIN;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (targetGrid[i][j] == u) {
                    x1 = min(x1, i); y1 = min(y1, j);
                    x2 = max(x2, i); y2 = max(y2, j);
                }

        if (x1 == INT_MAX)
            return;

        vector<bool> vis(c + 1, false);
        vis[u] = true;
        for (int i = x1; i <= x2; i++)
            for (int j = y1; j <= y2; j++) {
                int v = targetGrid[i][j];
                if (vis[v]) continue;
                vis[v] = true;
                graph[u].push_back(v);
                indeg[v]++;
            }
    }

public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        m = targetGrid.size();
        n = targetGrid[0].size();
        c = 60;

        vector<vector<int>> graph(c + 1);
        vector<int> indeg(c + 1, 0);

        for (int i = 1; i <= c; i++) {
            build(i, targetGrid, graph, indeg);
        }

        queue<int> q;
        for (int i = 1; i <= c; i++) {
            if (indeg[i] == 0)
                q.push(i);
        }

        int tot = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            tot++;

            for (int v : graph[u]) {
                indeg[v]--;
                if (indeg[v] == 0)
                    q.push(v);
            }
        }

        return tot == c;
    }
};



wzc1995
4天前

题目描述

给你一个正整数数组 nums,请你移除 最短 子数组(可以为 ),使得剩余元素的 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组,如果无法满足题目要求,返回 -1

子数组 定义为原数组中连续的一组元素。

样例

输入:nums = [3,1,4,2], p = 6
输出:1
解释:nums 中元素和为 10,不能被 p 整除。我们可以移除子数组 [4],剩余元素的和为 6。
输入:nums = [6,3,5,2], p = 9
输出:2
解释:我们无法移除任何一个元素使得和被 9 整除,最优方案是移除子数组 [5,2],剩余元素为 [6,3],和为 9。
输入:nums = [1,2,3], p = 3
输出:0
解释:和恰好为 6 ,已经能被 3 整除了。所以我们不需要移除任何元素。
输入:nums = [1,2,3], p = 7
输出:-1
解释:没有任何方案使得移除子数组后剩余元素的和被 7 整除。
输入:nums = [1000000000,1000000000,1000000000], p = 3
输出:0

限制

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= p <= 10^9

算法

(前缀和,哈希表) $O(n)$
  1. 先求出数组整体的和 $tot$。如果 $tot$ 本身能被 $p$ 整除,返回 0。
  2. 定义哈希表记录当前位置之前的所有前缀和模 $p$ 后所对应的最大位置。
  3. 对于当前前缀和 $sum$,求出需要从当前前缀中保留多少才能使得剩余的部分能被 $p$ 整除。定义 $r := (p - (tot - sum) \text{%} p) \text{%} p$。
  4. 如果在哈希表中发现了 $r$,则说明可以保留部分前缀,然后需要去掉的部分的长度为 $i - mp(r)$。
  5. 最后如果发现需要去掉全部数组,返回 -1。

时间复杂度

  • 遍历数组常数次,哈希表的单次操作时间复杂度为常数,故总时间复杂度为 $O(n)$。

空间复杂度

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

C++ 代码

#define LL long long

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        const int n = nums.size();
        LL tot = 0;
        for (int i = 0; i < n; i++)
            tot += nums[i];

        if (tot % p == 0)
            return 0;

        LL sum = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;

        int ans = n;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            int r = (p - (tot - sum) % p) % p;

            if (mp.find(r) != mp.end())
                ans = min(ans, i - mp[r]);

            mp[sum % p] = i;
        }

        if (ans == n)
            ans = -1;
        return ans;
    }
};



wzc1995
4天前

题目描述

有一个整数数组 nums,和一个查询数组 requests,其中 requests[i] = [start_i, end_i]。第 i 个查询求 nums[start_i] + nums[start_i + 1] + ... + nums[end_i - 1] + nums[end_i] 的结果,start_iend_i 数组索引都是 从 0 开始 的。

你可以任意排列 nums 中的数字,请你返回所有查询结果之和的最大值。

由于答案可能会很大,请你将它对 10^9 + 7 取余 后返回。

样例

输入:nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
输出:19
解释:一个可行的 nums 排列为 [2,1,3,4,5],并有如下结果:
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为:8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1],并有如下结果:
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5 = 8
总和为:11 + 8 = 19,这个方案是所有排列中查询之和最大的结果。
输入:nums = [1,2,3,4,5,6], requests = [[0,1]]
输出:11
解释:一个总和最大的排列为 [6,5,4,3,2,1],查询和为 [11]。
输入:nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
输出:47
解释:一个和最大的排列为 [4,10,5,3,2,1],查询结果分别为 [19,18,10]。

限制

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= requests.length <= 10^5
  • requests[i].length == 2
  • 0 <= start_i <= end_i < n

算法

(贪心,差分) $O(n \log n)$
  1. 统计每个位置被覆盖的次数,按照次数的高低依次分配数字,次数和数字相乘。
  2. 统计被覆盖次数可以采用差分,然后求前缀和的方式。

时间复杂度

  • 统计被覆盖次数的时间复杂度为 $O(n)$。
  • 排序的时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储覆盖次数的数组。

C++ 代码

#define LL long long

class Solution {
public:
    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
        const int n = nums.size();
        const int mod = 1000000007;
        vector<int> p(n, 0);

        for (const auto &r : requests) {
            p[r[0]]++;
            if (r[1] + 1 < n)
                p[r[1] + 1]--;
        }

        for (int i = 1; i < n; i++)
            p[i] += p[i - 1];

        sort(nums.begin(), nums.end());
        sort(p.begin(), p.end());

        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = (ans + (LL)(p[i]) * nums[i]) % mod;

        return ans;
    }
};



wzc1995
4天前

题目描述

给你一个正整数数组 arr,请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr所有奇数长度子数组的和

样例

输入:arr = [1,4,2,5,3]
输出:58
解释:所有奇数长度子数组和它们的和为:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
示例 2:

输入:arr = [1,2]
输出:3
解释:总共只有 2 个长度为奇数的子数组,[1] 和 [2]。它们的和为 3 。
示例 3:

输入:arr = [10,11,12]
输出:66

限制

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000

算法1

(暴力枚举) $O(n^2)$
  1. 枚举起点。对于每个起点,枚举终点,对于每个奇数长度的终点,累加当前的区间和。

时间复杂度

  • 共有 $O(n^2)$ 对区间,故总时间复杂度为 $O(n^2)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        const int n = arr.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if ((j - i + 1) % 2 == 1)
                    ans += sum;
            }
        }
        return ans;
    }
};

算法2

(数学) $O(n)$
  1. 对于每个位置计算覆盖这个位置的区间个数。
  2. 假设当前位置左半段的长度(包含当前位置)为 $l$,右半段的长度(包含当前位置)为 $r$。
  3. 将 $l$ 和 $r$ 分别分为两类,一类是距离当前位置为奇数的点 $lOdd$ 和 $rOdd$,一类是距离当前位置为偶数的点 $lEven$ 和 $rEven$。其 $lOdd \times rOdd + lEven \times rEven$ 就可以构造出长度为奇数的区间。

时间复杂度

  • 每个位置仅需要常数的时间计算区间的个数,故总时间复杂度为 $O(n)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        const int n = arr.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            int l = i + 1, r = n - i;
            int lOdd = l / 2, rOdd = r / 2;
            int lEven = l - lOdd, rEven = r - rOdd;
            ans += arr[i] * (lOdd * rOdd + lEven * rEven);
        }

        return ans;
    }
};



wzc1995
5天前

题目描述

秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点,景点编号为 1N。此外,他们还选择了 N 条小路,满足任意两个景点之间都可以通过小路互相到达,且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图,记作二维数组 edges,数组中以 [a,b] 形式表示景点 a 与景点 b 之间有一条小路连通。

小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣,小扣的目标是尽可能延后被小力追到的时间。游戏开始前,两人分别站在两个不同的景点 startAstartB。每一回合,小力先行动,小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一:

  • 移动至相邻景点
  • 留在原地

如果小力追到小扣(即两人于某一时刻出现在同一位置),则游戏结束。若小力可以追到小扣,请返回最少需要多少回合;若小力无法追到小扣,请返回 -1

注意:小力和小扣一定会采取最优移动策略。

样例

1597991318-goeHHr-image.png

输入:edges = [[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]], startA = 3, startB = 5
输出:3
解释:
第一回合,小力移动至 2 号点,小扣观察到小力的行动后移动至 6 号点;
第二回合,小力移动至 5 号点,小扣无法移动,留在原地;
第三回合,小力移动至 6 号点,小力追到小扣。返回 3。

1597991157-QfeakF-image.png

输入:edges = [[1,2],[2,3],[3,4],[4,1]], startA = 1, startB = 3
输出:-1
解释:
小力如果不动,则小扣也不动;否则小扣移动到小力的对角线位置。这样小力无法追到小扣。

限制

  • edges 的长度等于图中节点个数。
  • 3 <= edges.length <= 10^5
  • 1 <= edges[i][0], edges[i][1] <= edges.lengthedges[i][0] != edges[i][1]
  • 1 <= startA, startB <= edges.lengthstartA != startB

算法

(图论,图上寻环) $O(n)$
  1. 注意到边的个数等于点的个数,且是一个连通图,所以这个图中有且仅有一个简单环,环的长度大于等于 3。
  2. 如果环的长度大于 3,且 B 可以比 A 先到环上,则可以证明 A 无法追到 B。否则,A 一定可以追到 B。
  3. 具体实现如下
    • 求出 A 和 B 到每个点的最短距离。
    • 通过 BFS 或者 DFS 找到唯一的环。
    • 如果环大于 3 且存在一个环上的点 x,满足 A 到 x 的最短距离严格大于 B 到 x 的最短距离加 1,则返回 -1。这是因为 B 可以逃到 x 上且过程中 A 无法追到。
    • 其他情况下,初始化答案为 1。然后枚举任意一个点 x,如果满足 A 到 x 的最短距离严格大于 B 到 x 的最短距离加 1,则点 x 可以作为 B 最后的被追到的点,用 A 到 x 的距离更新答案。

时间复杂度

  • 预处理和找环的的时间复杂度均为 $O(n)$。
  • 枚举点时,判断每个点的复杂度为常数,故总时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储预处理的数据结构。

C++ 代码

class Solution {
private:
    vector<vector<int>> graph;
    stack<int> st;
    vector<bool> inCycle;
    int cycleSize;

    void bfs(int s, vector<int> &dis) {
        dis[s] = 0;
        queue<int> q;
        q.push(s);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : graph[u])
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
        }
    }

    bool dfs(int u, int fa, vector<bool> &inStack) {
        st.push(u);
        inStack[u] = true;

        for (int v : graph[u]) {
            if (v == fa) continue;
            if (inStack[v]) {
                int x;
                do {
                    x = st.top();
                    st.pop();
                    cycleSize++;
                    inCycle[x] = true;
                } while (x != v);

                return true;
            }

            if (dfs(v, u, inStack))
                return true;
        }

        inStack[u] = false;
        st.pop();
        return false;
    }

public:
    int chaseGame(vector<vector<int>>& edges, int startA, int startB) {
        const int n = edges.size();
        graph.resize(n + 1);
        for (const auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        vector<int> disA(n + 1, INT_MAX), disB(n + 1, INT_MAX);
        bfs(startA, disA);
        bfs(startB, disB);

        vector<bool> inStack(n + 1, false);
        inCycle.resize(n + 1, 0);
        cycleSize = 0;
        dfs(1, 0, inStack);

        if (cycleSize > 3) {
            for (int i = 1; i <= n; i++)
                if (inCycle[i] && disA[i] > disB[i] + 1)
                    return -1;
        }

        int ans = 1;
        for (int i = 1; i <= n; i++)
            if (disA[i] > disB[i] + 1)
                ans = max(ans, disA[i]);

        return ans;
    }
};



wzc1995
8天前

题目描述

给定一个 points 数组,表示 2D 平面上的一些点,其中 points[i] = [x_i, y_i]

连接点 [x_i, y_i] 和点 [x_j, y_j] 的费用为它们之间的 曼哈顿距离|x_i - x_j| + |y_i - yj|,其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时,才认为所有点都已连接。

样例

d.png
c.png

输入:points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出:20
解释:我们可以按照上图所示连接所有点得到最小总费用,总费用为 20。
注意到任意两个点之间只有唯一一条路径互相到达。
输入:points = [[3,12],[-2,5],[-4,1]]
输出:18
输入:points = [[0,0],[1,1],[1,0],[-1,1]]
输出:4
输入:points = [[-1000000,-1000000],[1000000,1000000]]
输出:4000000
输入:points = [[0,0]]
输出:0

限制

  • 1 <= points.length <= 1000
  • -10^6 <= x_i, y_i <= 10^6
  • 所有点 (x_i, y_i) 两两不同。

算法

(最小生成树) $O(n^2)$
  1. 完全图下的最小生成树,推荐使用 Prim 算法。

时间复杂度

  • $n$ 次迭代,每次需要 $n$ 次循环找最短距离,故总时间复杂度为 $O(n^2)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储 Prim 算法的数据结构。

C++ 代码

class Solution {
private:
    int calc(vector<int> &x, vector<int> &y) {
        return abs(x[0] - y[0]) + abs(x[1] - y[1]);
    }

public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        const int n = points.size();
        vector<bool> vis(n, false);
        vector<int> dis(n, INT_MAX);
        int ans = 0;

        dis[0] = 0;
        for (int i = 0; i < n; i++) {
            int mindis = INT_MAX;
            int m = -1;
            for (int j = 0; j < n; j++)
                if (!vis[j] && mindis > dis[j]) {
                    mindis = dis[j];
                    m = j;
                }

            vis[m] = true;
            ans += mindis;
            for (int j = 0; j < n; j++)
                dis[j] = min(dis[j], calc(points[m], points[j]));
        }

        return ans;
    }
};



wzc1995
9天前

题目描述

给定两个字符串 st,请你通过若干次以下操作将字符串 s 转化成字符串 t

  • 选择 s 中一个 非空 子字符串并将它包含的字符就地 升序 排序。

比方说,对括号所示的子字符串进行操作可以由 "1(4234)" 得到 "1(2344)"

如果可以将字符串 s 变成 t,返回 true。否则,返回 false

一个 子字符串 定义为一个字符串中连续的若干字符。

样例

输入:s = "84532", t = "34852"
输出:true
解释:你可以按以下操作将 s 转变为 t :
"84532" (从下标 2 到下标 3)-> "84352"
"84352" (从下标 0 到下标 2) -> "34852"
输入:s = "34521", t = "23415"
输出:true
解释:你可以按以下操作将 s 转变为 t:
"34521" -> "23451"
"23451" -> "23415"
输入:s = "12345", t = "12435"
输出:false
输入:s = "1", t = "2"
输出:false

限制

  • s.length == t.length
  • 1 <= s.length <= 10^5
  • st 都只包含数字字符,即 '0''9'

算法

(逆序,冒泡排序) $O(n)$
  1. 题目中的操作与每次操作相邻的两个数字等价,所以这个过程可以看做是一个冒泡排序的过程。
  2. 考虑 $t$ 中的第一个数字 d,其一定是从 $s$ 中的最近的 d 排序过来的。假设 d 在 $s$ 中的坐标为 $j$,现在需要保证从 $s(0)$ 到 $s(j-1)$ 中不存在一个数字比 d 小,否则就无法排序 d 到最开头。
  3. 如果可以将 d 排到 $t$ 的最开头。则考虑下一个新的数字,以及其在 $s$ 中的位置,同时判断能否排序时,也无需再考虑上上一个 d
  4. 初始化 10 个队列,每个队列中记录当前队列所代表的数字在 $s$ 中的位置。然后遍历字符串 $t$,按照以上规则判断即可。

时间复杂度

  • 初始化队列的时间复杂度为 $O(n)$。字符串 $t$ 遍历一次,遍历时每个位置最多枚举 10 个数字,故总时间复杂度为 $O(n)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    bool isTransformable(string s, string t) {
        const int n = s.size();
        vector<queue<int>> pos(10);
        for (int i = 0; i < n; i++) {
            pos[s[i] - '0'].push(i);
        }

        for (int i = 0; i < n; i++) {
            int x = t[i] - '0';
            if (pos[x].empty()) return false;

            for (int y = 0; y < x; y++)
                if (!pos[y].empty() && pos[y].front() < pos[x].front())
                    return false;

            pos[x].pop();
        }

        return true;
    }
};



wzc1995
10天前

题目描述

给定一份 n 位朋友的亲近程度列表,其中 n 总是 偶数

对每位朋友 ipreferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。换句话说,排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 0n-1 之间的整数表示。

所有的朋友被分成几对,配对情况以列表 pairs 给出,其中 pairs[i] = [x_i, y_i] 表示 x_iy_i 配对,且 y_ix_i 配对。

但是,这样的配对情况可能会是其中部分朋友感到不开心。在 xy 配对且 uv 配对的情况下,如果同时满足下述两个条件,x 就会不开心:

  • xu 的亲近程度胜过 xy,且
  • ux 的亲近程度胜过 uv

返回 不开心的朋友的数目

样例

输入:
n = 4
preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]]
pairs = [[0, 1], [2, 3]]

输出:2

解释:
朋友 1 不开心,因为:
- 1 与 0 配对,但 1 与 3 的亲近程度比 1 与 0 高,且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心,因为:
- 3 与 2 配对,但 3 与 1 的亲近程度比 3 与 2 高,且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。
输入:
n = 2
preferences = [[1], [0]]
pairs = [[1, 0]]

输出:0

解释:朋友 0 和 1 都开心。
输入:
n = 4
preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]]
pairs = [[1, 3], [0, 2]]

输出:4

限制

  • 2 <= n <= 500
  • n 是偶数。
  • preferences.length == n
  • preferences[i].length == n - 1
  • 0 <= preferences[i][j] <= n - 1
  • preferences[i] 不包含 i
  • preferences[i] 中的所有值都是独一无二的。
  • pairs.length == n/2
  • pairs[i].length == 2
  • x_i != y_i
  • 0 <= x_i, y_i <= n - 1
  • 每位朋友都 恰好 被包含在一对中。

算法

(暴力枚举) $O(n^2)$
  1. 求出每个人的对每个朋友的排名。
  2. 枚举所有不重复两对朋友,判断是否存在题目描述的情况。

时间复杂度

  • 求出排名的时间复杂度为 $O(n^2)$。
  • 共 $O(n^2)$ 对朋友,枚举判断的总时间复杂度为 $O(n^2)$。

空间复杂度

  • 仅需要 $O(n^2)$ 的额外空间存储每个人对每个朋友的排名。

C++ 代码

class Solution {
private:
    bool check(int x, int y, int u, int v, const vector<vector<int>> &rk) {
        return rk[x][u] < rk[x][y] && rk[u][x] < rk[u][v];
    }

public:
    int unhappyFriends(int n, vector<vector<int>>& preferences,
                       vector<vector<int>>& pairs) {
        vector<vector<int>> rk(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n - 1; j++)
                rk[i][preferences[i][j]] = j;

        int ans = 0;
        for (int i = 0; i < pairs.size(); i++) {
            int x = pairs[i][0], y = pairs[i][1];
            bool unhappy_x = false, unhappy_y = false;
            for (int j = 0; j < pairs.size(); j++) {
                if (i == j) continue;

                int u = pairs[j][0], v = pairs[j][1];
                if (!unhappy_x && (check(x, y, u, v, rk) || check(x, y, v, u, rk))) {
                    unhappy_x = true;
                    ans++;
                }
                if (!unhappy_y && (check(y, x, u, v, rk) || check(y, x, v, u, rk))) {
                    unhappy_y = true;
                    ans++;
                }

                if (unhappy_x && unhappy_y) break;
            }
        }

        return ans;
    }
};



wzc1995
10天前

题目描述

给定一个大小为 rows x cols 的矩阵 mat,其中 mat[i][j]01,请返回矩阵 mat 中特殊位置的数目。

特殊位置定义:如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0(行和列的下标均从 0 开始),则位置 (i, j) 被称为特殊位置。

样例

输入:mat = [[1,0,0],
            [0,0,1],
            [1,0,0]]
输出:1
解释:(1,2) 是一个特殊位置,因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0。
输入:mat = [[1,0,0],
            [0,1,0],
            [0,0,1]]
输出:3
解释:(0,0), (1,1) 和 (2,2) 都是特殊位置。
输入:mat = [[0,0,0,1],
            [1,0,0,0],
            [0,1,1,0],
            [0,0,0,0]]
输出:2
输入:mat = [[0,0,0,0,0],
            [1,0,0,0,0],
            [0,1,0,0,0],
            [0,0,1,0,0],
            [0,0,0,1,1]]
输出:3

限制

  • rows == mat.length
  • cols == mat[i].length
  • 1 <= rows, cols <= 100
  • mat[i][j]01

算法

(预处理) $O(mn)$
  1. 预处理每行每列的总和。
  2. 如果当前位置为 1,且当前行的总和为 1 且当前列的总和也为 1,则这是个特殊位置。

时间复杂度

  • 遍历数组两次,故总时间复杂度为 $O(mn)$。

空间复杂度

  • 需要 $O(m + n)$ 的空间存储预处理的总和。

C++ 代码

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> row(m, 0), col(n, 0);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                row[i] += mat[i][j];
                col[j] += mat[i][j];
            }

        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j] == 1 && row[i] == 1 && col[j] == 1)
                    ans++;

        return ans;
    }
};



wzc1995
10天前

题目描述

小扣打算去秋日市集,由于游客较多,小扣的移动速度受到了人流影响:

  • 小扣从 x 号站点移动至 x + 1 号站点需要花费的时间为 inc
  • 小扣从 x 号站点移动至 x - 1 号站点需要花费的时间为 dec

现有 m 辆公交车,编号为 0m-1。小扣也可以通过搭乘编号为 i 的公交车,从 x 号站点移动至 jump[i]*x 号站点,耗时仅为 cost[i]。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。

假定小扣起始站点记作 0,秋日市集站点记作 target,请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大,最终答案需要对 1000000007 (1e9 + 7) 取模。

注意:小扣可在移动过程中到达编号大于 target 的站点。

样例

输入:target = 31, inc = 5, dec = 3, jump = [6], cost = [10]
输出:33
解释:
小扣步行至 1 号站点,花费时间为 5;
小扣从 1 号站台搭乘 0 号公交至 6 * 1 = 6 站台,花费时间为 10;
小扣从 6 号站台步行至 5 号站台,花费时间为 3;
小扣从 5 号站台搭乘 0 号公交至 6 * 5 = 30 站台,花费时间为 10;
小扣从 30 号站台步行至 31 号站台,花费时间为 5;
最终小扣花费总时间为 33。
输入:target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]
输出:26
解释:
小扣步行至 1 号站点,花费时间为 4;
小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台,花费时间为 4;
小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台,花费时间为 3;
小扣从 33 号站台步行至 34 站台,花费时间为 4;
小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台,花费时间为 4;
小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台,花费时间为 7;
最终小扣花费总时间为 26。

限制

  • 1 <= target <= 10^9
  • 1 <= jump.length, cost.length <= 10
  • 2 <= jump[i] <= 10^6
  • 1 <= inc, dec, cost[i] <= 10^6

算法

(记忆化搜索) $O(\log target)$
  1. 分析一下有意义的转移点,对于当前的 target 来说,有两种转移方式
    • 直接从 0 走到 target
    • 搭乘一趟公交车到距离 target 最近的站点
  2. 这里两种转移方式的原因是,如果搭乘公交车不如走路快,则就会一直走路。一旦发现搭乘公交车比走路快,那就尽可能的搭乘公交车。
  3. 使用哈希表记录一下访问过的 target,加速转移。

时间复杂度

  • 转移点大概有 $O(\log target)$ 个,每个转移点最多访问一次,故总时间复杂度为 $O(\log target)$。

空间复杂度

  • 需要 $O(\log target)$ 的额外空间存储哈希表和系统栈。

C++ 代码

#define LL long long

class Solution {
private:
    unordered_map<int, LL> seen;

    LL solve(int target, int inc, int dec,
             const vector<int> &jump, const vector<int> &cost) {

        if (target == 0) return 0;
        if (seen.find(target) != seen.end()) return seen[target];

        const int m = jump.size();

        LL res = (LL)(target) * inc;
        for (int i = 0; i < m; i++) {
            int d = target / jump[i], r = target % jump[i];
            res = min(res, solve(d, inc, dec, jump, cost)
                            + cost[i] + (LL)(r) * inc);
            if (d+1 < target)
                res = min(res, solve(d+1, inc, dec, jump, cost) 
                                + cost[i] + (LL)(jump[i] - r) * dec);
        }

        return seen[target] = res;
    }

public:
    int busRapidTransit(int target, int inc, int dec,
                        vector<int>& jump, vector<int>& cost) {
        const int mod = 1000000007;
        return solve(target, inc, dec, jump, cost) % mod;
    }
};