On the shoulders of giants.

biweekly-contest-27

通过翻转子数组使两个数组相等

给你两个长度相同的整数数组 target 和 arr 。

每一步中,你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。

如果你能让 arr 变得与 target 相同,返回 True;否则,返回 False 。

示例 1:

输入:target = [1,2,3,4], arr = [2,4,1,3]
输出:true
解释:你可以按照如下步骤使 arr 变成 target:
1- 翻转子数组 [2,4,1] ,arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ,arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ,arr 变成 [1,2,3,4]
上述方法并不是唯一的,还存在多种将 arr 变成 target 的方法。

示例 2:

输入:target = [7], arr = [7]
输出:true
解释:arr 不需要做任何翻转已经与 target 相等。

示例 3:

输入:target = [1,12], arr = [12,1]
输出:true

示例 4:

输入:target = [3,7,9], arr = [3,7,11]
输出:false
解释:arr 没有数字 9 ,所以无论如何也无法变成 target 。

示例 5:

输入:target = [1,1,1,1,1], arr = [1,1,1,1,1]
输出:true

提示:

  • target.length == arr.length
  • 1 <= target.length <= 1000
  • 1 <= target[i] <= 1000
  • 1 <= arr[i] <= 1000
题解

排序后,比较种类是否相同。

时间复杂度:\(O(n^2)\)

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        int n = target.size();
        sort(target.begin(), target.end());
        sort(arr.begin(), arr.end());
        for(int i = 0; i < n; i++) {
            if(target[i] != arr[i]) return false;
        }
        return true;
    }
};

检查一个字符串是否包含所有长度为 K 的二进制子串

给你一个二进制字符串 s 和一个整数 k 。

如果所有长度为 k 的二进制字符串都是 s 的子串,请返回 True ,否则请返回 False 。

示例 1:

输入:s = "00110110", k = 2
输出:true
解释:长度为 2 的二进制串包括 "00","01","10" 和 "11"。它们分别是 s 中下标为 0,1,3,2 开始的长度为 2 的子串。

示例 2:

输入:s = "00110", k = 2
输出:true

示例 3:

输入:s = "0110", k = 1
输出:true
解释:长度为 1 的二进制串包括 "0" 和 "1",显然它们都是 s 的子串。

示例 4:

输入:s = "0110", k = 2
输出:false
解释:长度为 2 的二进制串 "00" 没有出现在 s 中。

示例 5:

输入:s = "0000000001011100", k = 4
输出:false

提示:

  • 1 <= s.length <= 5 * 10^5
  • s 中只含 0 和 1 。
  • 1 <= k <= 20
题解

长度为 k 的二进制总数为:\(2^k\) 个,直接提取原字符串中的所有长度为 k 的子字符串放入集合中,判断个数是否为 \(2^k\) 。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    int get_val(string s) {
        int n = s.length(), result = 0, p = 1;
        for(int i = n - 1; 0 <= i; i--, p <<= 1) {
            result = (s[i] - '0') * p + result;
        }
        return result;
    }
    bool hasAllCodes(string s, int k) {
        int n = s.length(), total = 0;
        vector<bool> vis(1 << k);
        string tmp = "";
        tmp = s.substr(0, k - 1);
        for(int i = k - 1; i < n; i++) {
            tmp = tmp + s[i];
            int val = get_val(tmp);
            if(!vis[val]) {
                vis[val] = true;
                total++;
            }
            tmp.erase(tmp.begin());
        }
        return total == (1 << k);
    }
};

课程安排 IV

你总共需要上 n 门课,课程编号依次为 0 到 n-1 。

有的课会有直接的先修课程,比如如果想上课程 0 ,你必须先上课程 1 ,那么会以 [1,0] 数对的形式给出先修课程数对。

给你课程总数 n 和一个直接先修课程数对列表 prerequisite 和一个查询对列表 queries 。

对于每个查询对 queries[i] ,请判断 queries[i][0] 是否是 queries[i][1] 的先修课程。

请返回一个布尔值列表,列表中每个元素依次分别对应 queries 每个查询对的判断结果。

注意:如果课程 a 是课程 b 的先修课程且课程 b 是课程 c 的先修课程,那么课程 a 也是课程 c 的先修课程。

示例 1:

输入:n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出:[false,true]
解释:课程 0 不是课程 1 的先修课程,但课程 1 是课程 0 的先修课程。

示例 2:

输入:n = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出:[false,false]
解释:没有先修课程对,所以每门课程之间是独立的。

示例 3:

输入:n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出:[true,true]

示例 4:

输入:n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
输出:[false,true]

示例 5:

输入:n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
输出:[true,false,true,false]

提示:

  • 2 <= n <= 100
  • 0 <= prerequisite.length <= (n * (n - 1) / 2)
  • 0 <= prerequisite[i][0], prerequisite[i][1] < n
  • prerequisite[i][0] != prerequisite[i][1]
  • 先修课程图中没有环。
  • 先修课程图中没有重复的边。
  • 1 <= queries.length <= 10^4
  • queries[i][0] != queries[i][1]

题解

Floyd 传递闭包。

时间复杂度:\(O(n^3)\)

class Solution {
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<int>> g(n, vector<int> (n));
        vector<bool> result(queries.size());
        for(auto edge : prerequisites) {
            g[edge[0]][edge[1]] = 1;
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    g[i][j] |= g[i][k] & g[k][j];
                }
            }
        }
        for(int i = 0; i < queries.size(); i++) {
            if(g[queries[i][0]][queries[i][1]]) result[i] = true;
        }
        return result;
    }
};

摘樱桃 II

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃,机器人 1 从左上角格子 (0,0) 出发,机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则,返回两个机器人能收集的最多樱桃数目:

  • 从格子 (i,j) 出发,机器人可以移动到格子 (i+1, j-1)(i+1, j) 或者 (i+1, j+1) 。
  • 当一个机器人经过某个格子时,它会把该格子内所有的樱桃都摘走,然后这个位置会变成空格子,即没有樱桃的格子。
  • 当两个机器人同时到达同一个格子时,它们中只有一个可以摘到樱桃。
  • 两个机器人在任意时刻都不能移动到 grid 外面。
  • 两个机器人最后都要到达 grid 最底下一行。

示例 1:

输入:grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出:24
解释:机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为: 12 + 12 = 24 。

示例 2:

输入:grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出:28
解释:机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为: 17 + 11 = 28 。

示例 3:

输入:grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出:22

示例 4:

输入:grid = [[1,1],[1,1]]
输出:4

提示:

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100 
题解

动态规划,设 \(dp_{x,a,b}\) 为两个机器人分别走到 (x,a) 和 (x,b) 的最大数目。

有动态转移方程:\(dp_{x,a,b}=\max dp_{x-1,a+k,b+t}+cost(x,a,b)\)

其中 \(k,t \in [-1,1]\) ,\(cost(x,a,b)\) 为机器人在 \((x,a),(x,b)\) 中取得到的数目。

时间复杂度:\(O(nm^2)\)

const int N = 70 + 5;
class Solution {
public:
    int dp[N][N][N];
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        memset(dp, -1, sizeof(dp));
        dp[1][1][m] = grid[0][0] + grid[0][m - 1];
        for(int r = 2; r <= n; r++) {
            for(int i = 1; i <= m; i++) {
                for(int j = 1; j <= m; j++) {
                    int Max = -1;
                    for(int k = -1; k <= 1; k++) {
                        for(int t = -1; t <= 1; t++) {
                            Max = max(Max, dp[r - 1][i + k][j + t]);
                        }
                    }
                    if(Max == -1) continue;
                    dp[r][i][j] = Max + grid[r - 1][i - 1] + grid[r - 1][j - 1];
                    if(i == j) dp[r][i][j] -= grid[r - 1][i - 1];
                }
            }
        }
        int result = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= m; j++) {
                result = max(result, dp[n][i][j]);
            }
        }
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注