On the shoulders of giants.

weekly-contest-188

用栈操作构建数组

给你一个目标数组 target 和一个整数 n。每次迭代,需要从  list = {1,2,3..., n} 中依序读取一个数字。

请使用下述操作来构建目标数组 target

  • Push:从 list 中读取一个新元素, 并将其推入数组中。
  • Pop:删除数组中的最后一个元素。
  • 如果目标数组构建完成,就停止读取更多元素。

题目数据保证目标数组严格递增,并且只包含 1n 之间的数字。

请返回构建目标数组所用的操作序列。

题目数据保证答案是唯一的。

示例 1:

输入:target = [1,3], n = 3
输出:["Push","Push","Pop","Push"]
解释: 
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组,然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]

示例 2:

输入:target = [1,2,3], n = 3
输出:["Push","Push","Push"]

示例 3:

输入:target = [1,2], n = 4
输出:["Push","Push"]
解释:只需要读取前 2 个数字就可以停止。

示例 4:

输入:target = [2,3,4], n = 4
输出:["Push","Pop","Push","Push","Push"]

提示:

  • 1 <= target.length <= 100
  • 1 <= target[i] <= 100
  • 1 <= n <= 100
  • target 是严格递增的
题解

实际与 n 无关,只与最大的数 x 有关。

遍历 \([1,x]\),如果缺了数字那么就是 Push & Pop,如果不缺就是 Push

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

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> result;
        for(int x = 1, y = 0; x <= target.back(); x++) {
            if(target[y] == x) {
                result.push_back("Push");
                y++;
            } else {
                result.push_back("Push");
                result.push_back("Pop");
            }
        }
        return result;
    }
};

形成两个异或相等数组的三元组数目

给你一个整数数组 arr

现需要从数组中取三个下标 ijk ,其中 (0 <= i < j <= k < arr.length)

ab 定义如下:

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

注意:^ 表示 按位异或 操作。

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

示例 1:

输入:arr = [2,3,1,6,7]
输出:4
解释:满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)

示例 2:

输入:arr = [1,1,1,1,1]
输出:10

示例 3:

输入:arr = [2,3]
输出:0

示例 4:

输入:arr = [1,3,5,7,9]
输出:3

示例 5:

输入:arr = [7,11,12,9,5,2,7,17,22]
输出:8

提示:

  • 1 <= arr.length <= 300
  • 1 <= arr[i] <= 10^8
题解

满足区间加法(类似,异或)。

\(a == b\),等价于,\(a \oplus b == 0\)。

就是区间内异或为零,我们遍历区间,进行判断计数即可。

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

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size(), result = 0;
        vector<int> bit(n + 1);
        for(int i = 1; i <= n; i++) {
            bit[i] = bit[i - 1] ^ arr[i - 1];
            // cout << i << " : " << bit[i] << endl;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = i + 1; j <= n; j++) {
                if((bit[j] ^ bit[i - 1]) != 0) continue;
                result += j - i;
            }
        }
        return result;
    }
};

收集树上所有苹果的最少时间

给你一棵有 n 个节点的无向树,节点编号为 0 到 n-1 ,它们中有一些节点有苹果。通过树上的一条边,需要花费 1 秒钟。你从 节点 0 出发,请你返回最少需要多少秒,可以收集到所有苹果,并回到节点 0 。

无向树的边由 edges 给出,其中 edges[i] = [fromi, toi] ,表示有一条边连接 from 和 toi 。除此以外,还有一个布尔数组 hasApple ,其中 hasApple[i] = true 代表节点 i 有一个苹果,否则,节点 i 没有苹果。

示例 1:

输入:n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
输出:8 
解释:上图展示了给定的树,其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。

示例 2:

输入:n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
输出:6
解释:上图展示了给定的树,其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。

示例 3:

输入:n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
输出:0

提示:

  • 1 <= n <= 10^5
  • edges.length == n-1
  • edges[i].length == 2
  • 0 <= fromi, toi <= n-1
  • fromi < toi
  • hasApple.length == n
题解

遍历这棵树,计算子树 R 收集所需最小时间。

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

const int N = 1E5 + 10, M = 2 * N;
class Solution {
public:
    vector<int> g[N];
    vector<bool> flag;
    int reacher(int x, int p) {
        int sumTime = 0, n = g[x].size();
        for(int i = 0; i < n; i++) {
            if(g[x][i] == p) continue;
            int y = g[x][i];
            int ans = reacher(y, x);
            if(ans == 0) ans = (flag[y] ? 2 : 0);
            if(ans == 0) continue;
            sumTime += ans;   
        }
        return sumTime == 0 ? 0 : sumTime + 2;
    }
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        flag = hasApple;
        for(auto edge : edges) {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
        }
        return max(0, reacher(0, -1) - 2);
    }
};

切披萨的方案数

给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。

切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。

示例 1:

输入:pizza = ["A..","AAA","..."], k = 3
输出:3 
解释:上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。

示例 2:

输入:pizza = ["A..","AA.","..."], k = 3
输出:1

示例 3:

输入:pizza = ["A..","A..","..."], k = 1
输出:1

提示:

  • 1 <= rows, cols <= 50
  • rows == pizza.length
  • cols == pizza[i].length
  • 1 <= k <= 10
  • pizza 只包含字符 'A' 和 '.' 。
题解

动态规划,设 \(dp_{x,y,z}\) 为 区域 \(G(i,j),i \in [x,n],j \in [y,m]\) 切了 z 下的方案数。

我们用前缀和去判断一个区域是否有苹果,因为要判断左边部分和上边部分,根据转移方程,我们前缀和应该是 \([x:n],[y:m]\) 的,而不是 \([1,x],[1,y]\)。

有动态转移方程:\(dp_{x,y,z}=\sum dp_{i,y,z-1} + \sum dp_{x,j,z-1},i \in [x + 1, n], j \in [y + 1, m]\)

时间复杂度:\(O(knm(n+m))\)

const int N = 50 + 5, K = 10 + 5, MOD = 1E9 + 7;
class Solution {
public:
    int sum[N][N], dp[N][N][K];
    int cal(int x, int y) {
        return sum[x + 1][y] + sum[x][y + 1] - sum[x + 1][y + 1];
    }
    int ways(vector<string>& pizza, int k) {
        int n = pizza.size(), m = pizza[0].length();
        for(int i = n; 0 < i; i--) {
            for(int j = m; 0 < j; j--) {
                sum[i][j] = cal(i, j) + (pizza[i - 1][j - 1] == 'A');
                if(sum[i][j] != 0) dp[i][j][0] = 1;
            }
        }
        for(int z = 1; z < k; z++) {
            for(int x = n; 0 < x; x--) {
                for(int y = m; 0 < y; y--) {
                    for(int i = x + 1; i <= n; i++) {
                        if(sum[x][y] == sum[i][y]) continue;
                        dp[x][y][z] = (dp[x][y][z] + dp[i][y][z - 1]) % MOD;
                    }
                    for(int j = y + 1; j <= m; j++) {
                        if(sum[x][y] == sum[x][j]) continue;
                        dp[x][y][z] = (dp[x][y][z] + dp[x][j][z - 1]) % MOD;
                    }
                }
            }
        }
        return dp[1][1][k - 1];
    }
};
Share

You may also like...

发表评论

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