514周赛-①Q1-贪心②Q2-DFS③Q3-DP预处理+二分答案+二维前缀和④Q4-线段树#

第 514 场周赛 - 力扣（LeetCode）

Q1-贪心#

题目#

给你两个整数数组 prices 和 discounts。

prices[i] 表示第 ith 件商品的价格，discounts[j] 表示一个折扣百分比。

你可以按照以下规则使用折扣：

每个折扣最多只能用于一件商品。
每件商品最多只能使用一个折扣。
商品也可以不使用任何折扣。

如果将 d% 的折扣应用于价格为 p 的商品，则其最终价格为 (p * (100 - d)) / 100。最终价格 不进行四舍五入 。

请以最优方式分配折扣，并返回所有商品最终价格之和的最小值 。与实际答案的误差在 10-5 以内的结果都将被接受。

贪心#

最优的做法是把最大的折扣用在最贵的商品上，证明方法为排序不等式

1
class Solution:
2
    def minPrice(self, a: list[int], b: list[int]) -> float:
3
        a.sort(reverse = True)
4
        b.sort(reverse = True)
5
        ans = 0
6
        n,m = len(a),len(b)
7
        for i in range(n):
8
            if i < m:
9
                ans += a[i]*(100 - b[i])
10
            else:
11
                ans += a[i]*100
12
        return ans/100

1
class Solution {
2
public:
3
    double minPrice(vector<int>& prices, vector<int>& discounts) {
4
        sort(prices.begin(),prices.end(),greater<int>());
5
        sort(discounts.begin(),discounts.end(),greater<int>());
6
        long long ans = 0;
7
        for(int i = 0;i < prices.size();i++){
8
            if(i < discounts.size()){
9
                ans += prices[i]*(100 - discounts[i]);
10
            }
11
            else{
12
                ans += prices[i]*100;
13
            }
14
        }
15
        return double(ans/100.0);
16
    }
17
};

Q2-DFS#

题目#

给你一个长度为 n 的整数数组 parent，它表示一棵根节点编号为 0、节点编号范围为 0 到 n - 1 的有根树。

该树以节点 0 为 根节点，因此 parent[0] = -1。对于每个满足 1 <= i <= n - 1 的节点 i，parent[i] 表示节点 i 的父节点。

另给定一个长度为 n 的整数数组 nums，其中 nums[i] 表示节点 i 的值。

对于深度为 d 的节点 i，其权重定义为 nums[i] * (h - d + 1)，其中 h 表示树的高度。

返回树中所有节点的 权重之和 。

节点的深度定义为从根节点到该节点的路径上包含的节点数量，其中根节点的深度为 1。

树的高度定义为所有节点深度的最大值。

DFS#

1
class Solution {
2
public:
3
    long long weightedSum(vector<int>& parent, vector<int>& nums) {
4
        int n = parent.size();
5
        vector<vector<int>> g(n);
6
        for (int i = 1; i < n; i++) {
7
            g[parent[i]].push_back(i);
8
        }
9
        vector<int> depth(n);
10

11
        auto dfs = [&](this auto&& dfs, int x) -> int {
12
            int h = 0;
13
            for (int y : g[x]) {
14
                depth[y] = depth[x] + 1;
15
                h = max(h, dfs(y));
16
            }
17
            return h + 1;
18
        };
19
        int h = dfs(0);
20

21
        long long ans = 0;
22
        for (int i = 0; i < n; i++) {
23
            ans += 1LL * nums[i] * (h - depth[i]);
24
        }
25
        return ans;
26
    }
27
};

1
class Solution:
2
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
3
        # 二叉树的最大深度
4
        n = len(nums)
5
        g = [[] for _ in range(n)]
6
        for i in range(1,n):
7
            g[parent[i]].append(i)
8
        d = [0]*n
9
        def dfs(node):
10
            for gg in g[node]:
11
                d[gg] = d[node] + 1
12
                dfs(gg)
13
        dfs(0)
14
        h = max(d)
15
        ans = 0
16
        for i in range(n):
17
            ans += nums[i]*(h - d[i] + 1)
18
        return ans

BFS#

1
class Solution {
2
public:
3
    long long weightedSum(vector<int>& parent, vector<int>& nums) {
4
        int n = nums.size();
5
        vector<int> depth(n);
6
        vector<vector<int>> g(n);
7
        for(int i = 1;i < n;i++){
8
            g[parent[i]].push_back(i);
9
        }
10
        int h = 1;
11
        depth[0] = 1;
12
        queue<int> q;
13
        q.push(0);
14
        while(!q.empty()){
15
            int u = q.front();
16
            q.pop();
17
            for(int v : g[u]){
18
                if(depth[u] + 1 > depth[v]){
19
                    depth[v] = depth[u] + 1;
20
                    q.push(v);
21
                    h = max(h,depth[v]);
22
                }
23
            }
24
        }
25
        long long ans = 0;
26
        for(int i = 0;i < n;i++){
27
            ans += 1LL * nums[i] *(h - depth[i] + 1);
28
        }
29
        return ans;
30
    }
31
};

1
class Solution:
2
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
3
        n = len(nums)
4
        g = [[] for _ in range(n)]
5
        for i in range(1,n):
6
            g[parent[i]].append(i)
7

8
        d = [0]*n
9
        d[0] = 1
10
        q = deque([0])
11
        h = 1
12
        while q:
13
            u = q.popleft()
14
            for v in g[u]:
15
                d[v] = d[u] + 1
16
                h = max(h,d[v])
17
                q.append(v)
18
        ans = 0
19
        for i in range(n):
20
            ans += nums[i] * (h - d[i] + 1)
21
        return ans

Q3-DP预处理+二分答案+二维前缀和#

题目#

给你一个大小为 m × n 的二维整数矩阵 mat，其中：

mat[r][c] == 1 表示位于行 r 和列 c 的单元格是可用的。
mat[r][c] == 0 表示它不可用。

你的任务是找到满足以下条件的两个子矩阵 ：

这两个子矩阵都必须是边长为 k 的正方形。
这两个子矩阵不能共享任何单元格。
每个子矩阵只能覆盖 mat[r][c] == 1 的单元格。

返回单个正方形的最大可能面积。如果无法选择两个这样的正方形，则返回 0。

一个子矩阵 (x1, y1, x2, y2) 包括所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的单元格 mat[x][y] 。

二分答案+二维前缀和#

如何快速判断某个位置能否放下边长为 k 的全1正方形？

用 DP 预处理：dp[i][j] 表示以 (i,j) 为右下角的最大全1正方形边长

则 (i,j) 作为左上角能放下边长为 k 的正方形 ⇔ dp[i+k-1][j+k-1] >= k

如何判断两个正方形不重叠？

两个矩形不重叠 ⇔ 一个在另一个的上/下/左/右方

即：存在一条水平或垂直的线将它们分开

如何快速判断某个区域内是否存在至少一个合法正方形？

用二维前缀和标记所有合法的左上角位置

任意矩形区域内的合法正方形数量可在 O(1) 内查询

1
class Solution:
2
    def maxArea(self, mat: List[List[int]]) -> int:
3
        m, n = len(mat), len(mat[0])
4
        dp = [[0] * n for _ in range(m)]
5
        for i in range(m):
6
            for j in range(n):
7
                if mat[i][j] == 1:
8
                    if i == 0 or j == 0:
9
                        dp[i][j] = 1
10
                    else:
11
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
12

13
        def f(k: int) -> bool:
14
            if k == 0:
15
                return True
16

17
            # 标记合法左上角
18
            can = [[0] * n for _ in range(m)]
19
            for i in range(m - k + 1):
20
                for j in range(n - k + 1):
21
                    if dp[i + k - 1][j + k - 1] >= k:
22
                        can[i][j] = 1
23

24
            # 二维前缀和
25
            pre = [[0] * (n + 1) for _ in range(m + 1)]
26
            for i in range(m):
27
                row_sum = 0
28
                for j in range(n):
29
                    row_sum += can[i][j]
30
                    pre[i+1][j+1] = pre[i][j+1] + row_sum
31

32
            # 查询矩形内是否有合法正方形
33
            def ok(r1: int, c1: int, r2: int, c2: int) -> bool:
34
                if r1 > r2 or c1 > c2:
35
                    return False
36
                r1, c1 = max(r1, 0), max(c1, 0)
37
                r2, c2 = min(r2, m - 1), min(c2, n - 1)
38
                if r1 > r2 or c1 > c2:
39
                    return False
40
                return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1] > 0
41

42
            # 检查是否存在两个不重叠的正方形
43
            for i in range(m - k + 1):
44
                for j in range(n - k + 1):
45
                    if not can[i][j]:
46
                        continue
47

48
                    if ok(0, 0, i - k, n - 1):      # 上方
49
                        return True
50
                    if ok(i + k, 0, m - 1, n - 1):  # 下方
51
                        return True
52
                    if ok(0, 0, m - 1, j - k):      # 左方
53
                        return True
54
                    if ok(0, j + k, m - 1, n - 1):  # 右方
55
                        return True
56
            return False
57

58
        # 二分搜索最大边长
59
        l, r = 0, min(m, n) + 1
60
        while l + 1 < r:
61
            mid = (l + r) // 2
62
            if f(mid):
63
                l = mid
64
            else:
65
                r = mid
66
        return l * l

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4

5
class Solution {
6
public:
7
    int maxArea(vector<vector<int>>& mat) {
8
        int m = mat.size();
9
        int n = mat[0].size();
10

11
        // DP 预处理：以 (i,j) 为右下角的最大全1正方形边长
12
        vector<vector<int>> dp(m, vector<int>(n, 0));
13
        for (int i = 0; i < m; i++) {
14
            for (int j = 0; j < n; j++) {
15
                if (mat[i][j] == 1) {
16
                    if (i == 0 || j == 0) {
17
                        dp[i][j] = 1;
18
                    } else {
19
                        dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
20
                    }
21
                }
22
            }
23
        }
24

25
        // 判定函数：能否放置两个边长为 k 的不重叠全1正方形
26
        auto f = [&](int k) -> bool {
27
            if (k == 0) return true;
28

29
            // 标记合法左上角
30
            vector<vector<int>> can(m, vector<int>(n, 0));
31
            for (int i = 0; i <= m - k; i++) {
32
                for (int j = 0; j <= n - k; j++) {
33
                    if (dp[i + k - 1][j + k - 1] >= k) {
34
                        can[i][j] = 1;
35
                    }
36
                }
37
            }
38

39
            // 二维前缀和
40
            vector<vector<int>> pre(m + 1, vector<int>(n + 1, 0));
41
            for (int i = 0; i < m; i++) {
42
                int row_sum = 0;
43
                for (int j = 0; j < n; j++) {
44
                    row_sum += can[i][j];
45
                    pre[i + 1][j + 1] = pre[i][j + 1] + row_sum;
46
                }
47
            }
48

49
            // 查询矩形 (r1,c1) 到 (r2,c2) 内是否有合法正方形
50
            auto ok = [&](int r1, int c1, int r2, int c2) -> bool {
51
                if (r1 > r2 || c1 > c2) return false;
52
                r1 = max(r1, 0);
53
                c1 = max(c1, 0);
54
                r2 = min(r2, m - 1);
55
                c2 = min(c2, n - 1);
56
                if (r1 > r2 || c1 > c2) return false;
57
                return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1] > 0;
58
            };
59

60
            // 检查是否存在两个不重叠的正方形
61
            for (int i = 0; i <= m - k; i++) {
62
                for (int j = 0; j <= n - k; j++) {
63
                    if (!can[i][j]) continue;
64

65
                    if (ok(0, 0, i - k, n - 1)) return true;      // 上方
66
                    if (ok(i + k, 0, m - 1, n - 1)) return true;  // 下方
67
                    if (ok(0, 0, m - 1, j - k)) return true;      // 左方
68
                    if (ok(0, j + k, m - 1, n - 1)) return true;  // 右方
69
                }
70
            }
71
            return false;
72
        };
73

74
        // 二分搜索最大边长
75
        int l = 0, r = min(m, n) + 1;
76
        while (l + 1 < r) {
77
            int mid = (l + r) / 2;
78
            if (f(mid)) {
79
                l = mid;
80
            } else {
81
                r = mid;
82
            }
83
        }
84

85
        return l * l;
86
    }
87
};

音乐

音乐

514周赛-①Q1-贪心②Q2-DFS③Q3-DP预处理+二分答案+二维前缀和④Q4-线段树#

Q1-贪心#

题目#

贪心#

Q2-DFS#

题目#

DFS#

BFS#

Q3-DP预处理+二分答案+二维前缀和#

题目#

二分答案+二维前缀和#

Q4-线段树#

#

文章分享

音乐

目录

音乐

音乐

[算法训练] 514周赛-①Q1-贪心②Q2-DFS③Q3-DP预处理+二分答案+二维前缀和④Q4-线段树

514周赛-①Q1-贪心②Q2-DFS③Q3-DP预处理+二分答案+二维前缀和④Q4-线段树#

Q1-贪心#

题目#

贪心#

Q2-DFS#

题目#

DFS#

BFS#

Q3-DP预处理+二分答案+二维前缀和#

题目#

二分答案+二维前缀和#

Q4-线段树#

#

文章分享

音乐

目录