力扣第 449 场周赛

本文最后更新于 2 分钟前,文中所描述的信息可能已发生改变。

3545. 不同字符数量最多为 K 时的最少删除数 - 力扣(LeetCode)

解题思路

哈希表,按个数排序,求和即可

示例代码

python
class Solution:
    def minDeletion(self, s: str, k: int) -> int:
        return sum(sorted(Counter(s).values())[:-k])

3546. 等和矩阵分割 I - 力扣(LeetCode)

解题思路

二维前缀和,按行和按列遍历

不用当然也可以,用一维前缀和,代码复用

示例代码

python
class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        n, m = len(grid), len(grid[0])
        pre = PrefixSum2D(grid)
        for i in range(n - 1):
            if pre.find(0, 0, i, m - 1) == pre.find(i + 1, 0, n - 1, m - 1):
                return True
        for j in range(m - 1):
            if pre.find(0, 0, n - 1, j) == pre.find(0, j + 1, n - 1, m - 1):
                return True
        return False
python
class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        def check(grid: List[List[int]]) -> bool:
            n, m = len(grid), len(grid[0])
            pre = [sum(row) for row in grid]
            tot = sum(pre)
            s = 0
            for i in range(n - 1):
                s += pre[i]
                if 2 * s == tot:
                    return True
            return False
        return check(grid) or check(list(zip(*grid)))
py
from typing import List


class PrefixSum2D:
    __slots__ = ["m", "n", "pre"]

    def __init__(self, mat: List[List[int]]):
        self.m = m = len(mat)
        self.n = n = len(mat[0])
        self.pre = pre = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(mat):
            for j, v in enumerate(row):
                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + v

    def find(self, r1: int, c1: int, r2: int, c2: int) -> int:
        """查询以(r1,c1)为左上角,(r2,c2)为右下角的矩形区间内所有值的和"""
        return self.pre[r2 + 1][c2 + 1] - self.pre[r2 + 1][c1] - self.pre[r1][c2 + 1] + self.pre[r1][c1]

3547. 图中边值的最大和 - 力扣(LeetCode)

解题思路

错题一道 【更新】题目是错的,但是赛时通过了,思路如下

单链或成环,优先分配环,小环价值更高,其次单链,短链价值更低

所以只需要考虑长度,无需在意具体的节点

节点值从最值开始分配,具体实现可以用队列,优雅一些,数组确实丑陋

示例代码

python
class Solution:
    def maxScore(self, n: int, edges: List[List[int]]) -> int:
        d = [0] * n
        g = defaultdict(list)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
            d[x] += 1
            d[y] += 1

        def dfs(x: int) -> int:
            res = 1
            vis[x] = True
            for y in g[x]:
                if vis[y]: continue
                res += dfs(y)
            return res

        ans = 0
        st, ed = 1, n
        vis = [False] * n
        h1, h2 = [], []

        for i, x in enumerate(d):
            if x == 1 and not vis[i]:
                h1.append(dfs(i))
        for i, b in enumerate(vis):
            if d[i] == 0:
                st += 1
                continue
            if not b:
                h2.append(dfs(i))

        h1.sort()
        h2.sort(reverse=True)
        for l in h2:
            p = [0] * l
            i = j = 0
            for k in range(l):
                if k % 2:
                    j -= 1
                    p[j % l] = ed
                else:
                    p[i] = ed
                    i += 1
                ed -= 1
            ans += sum(p[i] * p[(i + 1) % l] for i in range(l))

        for l in h1:
            p1 = [0] * ((l + l % 2) // 2)
            p2 = [0] * (l // 2)
            for i in range((l + l % 2) // 2):
                p1[i] = st + i * 2
            for i in range(l // 2):
                p2[i] = st + 1 + i * 2
            p = p1 + p2[::-1]
            st += l
            ans += sum(x * y for x, y in pairwise(p))

        return ans

3548. 等和矩阵分割 II - 力扣(LeetCode)

解题思路

枚举,代码复用更容易解决问题

赛后是用二维前缀和,磨了半小时才做出来

特判单列的矩阵,分割线处也可以删除

单行矩阵只考虑最前端和最后段,其余直接比较个数大小,看上去就很蠢

复盘时参考灵神代码,就是抄了

参考:式子变形 + 分类讨论 + 复用代码(Python/Java/C++/Go)

示例代码

python
class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        tot = sum(sum(row) for row in grid)

        def check(b: List[List[int]]) -> bool:
            n, m = len(b), len(b[0])

            def cal(a: List[List[int]]) -> bool:
                st = {0}
                s = 0
                for i, row in enumerate(a[:-1]):
                    for j, x in enumerate(row):
                        s += x
                        if i > 0 or j == 0 or j == m - 1:
                            st.add(x)
                    if m == 1:
                        if s * 2 == tot or s * 2 - tot == a[0][0] or s * 2 - tot == row[0]:
                            return True
                        continue
                    if s * 2 - tot in st:
                        return True
                    if i == 0:
                        st.update(row)
                return False

            return cal(b) or cal(b[::-1])

        return check(grid) or check(list(zip(*grid)))
python
class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        def cal(grid) -> bool:
            n, m = len(grid), len(grid[0])
            pre = PrefixSum2D(grid)
            cnt = Counter()
            for row in grid:
                cnt.update(Counter(row))
            for i in range(n - 1):
                t1 = pre.find(0, 0, i, m - 1)
                t2 = pre.find(i + 1, 0, n - 1, m - 1)
                t = abs(t1 - t2)
                if t == 0: return True
                if m == 1:
                    if t1 - t2 == grid[0][0] or t1 - t2 == grid[i][0] and i >= 1: return True
                    if t2 - t1 == grid[-1][0] or t2 - t1 == grid[i + 1][0] and i < n - 2: return True
                else:
                    if i == 0:
                        if t1 > t2:
                            for j in (0, m - 1):
                                if t == grid[i][j]:
                                    return True
                        elif n > 2:
                            tmp = Counter(grid[0])
                            if cnt[t] > tmp[t]:
                                return True
                    if i == n - 2:
                        if t2 > t1:
                            for j in (0, m - 1):
                                if t == grid[i + 1][j]:
                                    return True
                        elif n > 2:
                            tmp = Counter(grid[-1])
                            if cnt[t] > tmp[t]:
                                return True

                    if 0 < i < n - 2 and cnt[t]:
                        return True
            return False
        return cal(grid) or cal(list(zip(*grid)))
LeetCode Biweekly Contest 156
LeetCode Weekly Contest 448