力扣第 462 场周赛

684
Contest
LeetCode
本文最后更新于 3 分钟前，文中所描述的信息可能已发生改变。

3643. 垂直翻转子矩阵 - 力扣（LeetCode） ​

解题思路 ​

双指针，按题意交换子数组即可

示例代码 ​

python
class Solution:
    def reverseSubmatrix(self, grid: List[List[int]], x: int, y: int, k: int) -> List[List[int]]:
        for i in range(k // 2):
            grid[x + i][y: y + k], grid[x + k - i - 1][y: y + k] = grid[x + k - i - 1][y: y+k], grid[x + i][y: y + k]
        return grid

3644. 排序排列 - 力扣（LeetCode） ​

解题思路 ​

贪心，找出下标与元素值不相等的元素相与即可，证明见参考

参考：构造 + 严谨证明（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def sortPermutation(self, nums: List[int]) -> int:
        if nums[0]:
            return 0
        ans = -1
        for i, x in enumerate(nums):
            if i != x:
                ans &= x
        return max(ans, 0)

3645. 最优激活顺序得到的最大总和 - 力扣（LeetCode） ​

解题思路 ​

贪心或模拟，将数组排序，用堆模拟激活后活跃状态元素个数变化即可，或者用 limit[i] 分组，取limit[i]个最大值之和

参考：阅读理解题/脑筋急转弯（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def maxTotal(self, value: List[int], limit: List[int]) -> int:
        h = []
        ans = 0
        cnt = 0
        li = [(y, x) for x, y in zip(value, limit)]
        li.sort(key=lambda p: (p[0], -p[1]))

        for y, x in li:
            if cnt >= y:
                continue
            heappush(h, (y, x))
            cnt = max(len(h), cnt)
            while h and cnt >= h[0][0]:
                heappop(h)
            ans += x
        return ans
python
class Solution:
    def maxTotal(self, value: List[int], limit: List[int]) -> int:
        groups = defaultdict(list)
        for lim, v in zip(limit, value):
            groups[lim].append(v)

        ans = 0
        for lim, a in groups.items():
            a.sort()
            ans += sum(a[-lim:])
        return ans

3646. 下一个特殊回文数 - 力扣（LeetCode） ​

解题思路 ​

预处理，枚举全排列，确保每个msk奇数个数小于 1，通过全排列生成回文数，一共 2296 个，然后主函数中二分查找即可

示例代码 ​

python
def dfs(i, cnt, msk, odd):
    global msks
    if cnt == odd == 0:
        msks.add(msk)
        return
    if i > 9 or cnt <= 0:
        return
    dfs(i + 1, cnt, msk, odd)
    dfs(i + 1, cnt - i, msk | (1 << i), odd - i % 2)
    return

msks = set()
for i in range(1, 17):
    dfs(1, i, 0, i % 2)

digits = set()
for msk in msks:
    odd = 0
    perm = []
    for i in range(msk.bit_length()):
        if msk >> i & 1:
            perm.extend([i] * (i // 2))
            if i % 2:
                odd = i
    odd = str(odd) if odd else ''
    for p in permutations(perm):
        t = ''.join(map(str, p))
        digits.add(int(t + odd + t[::-1]))

digits = sorted(digits)

class Solution:
    def specialPalindrome(self, n: int) -> int:
        idx = bisect_right(digits, n)
        return digits[idx]
Contest Summary
力扣第 162 场双周赛