算法题记录 12

1206.设计跳表（困难）

不使用任何库函数，设计一个 跳表 。

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中。

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

在本题中，你的设计应该要包含这些函数：

bool search(int target) : 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

涉及知识点

跳表

解决思路

跳表是一个不怎么被提及，但是效率很高，并且在工业界被广泛使用的数据结构，其核心思想跟操作系统中的多级页表类似，都是采用空间换时间的策略。对于这类特殊的数据结构，进行记忆熟悉保证能复现、使用即可。

class Node:
    def __init__(self,val=0):
        self.val=val
        self.right=None
        self.down=None

class Skiplist:

    def __init__(self):
        left=[Node(-1) for _ in range(16)]
        right=[Node(20001) for _ in range(16)]
        for i in range(15):
            left[i].right=right[i]
            left[i].down=left[i+1]
            right[i].down=right[i+1]
        left[-1].right=right[-1]
        self.head=left[0]

    def search(self, target: int) -> bool:
        cur=self.head
        while cur:
            if cur.right.val>target:
                cur=cur.down
            elif cur.right.val<target:
                cur=cur.right
            else:
                return True
        return False

    def add(self, num: int) -> None:
        cur=self.head
        stack=[]

        while cur:
            if cur.right.val>=num:
                stack.append(cur)
                cur=cur.down
            else:
                cur=cur.right
        
        pre=None
        while stack:
            cur=stack.pop()
            node=Node(num)
            node.right=cur.right
            cur.right=node
            if pre:
                node.down=pre
            pre=node
            if random.randint(0,1):
                break

    def erase(self, num: int) -> bool:
        cur=self.head
        is_removed=False
        while cur:
            if cur.right.val>=num:
                if cur.right.val==num:
                    is_removed=True
                    cur.right=cur.right.right
                cur=cur.down
            else:
                cur=cur.right
        return is_removed

3240.最少翻转次数使二进制矩阵回文2（2080）

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。

你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。

涉及知识点

分类讨论

解决思路

该题要讨论的比较复杂，涉及奇偶分析。根据题意，我们可以锁定任意矩形的四角必定为一样的值。若mxn矩阵为边为偶数的矩形，那么就不需要讨论其他情况了。如果边长一奇数、一偶数，那我们要单独判断中间一列或一行的回文。如果是边长都为奇数，那么我们要判断中间一列和中间一行的回文。而锁定任意矩形四角时，0、1的个数都为4的倍数，所以不关1的个数能否被4整除的事。我们只需要对中间的特殊列、行进行奇偶分析即可，如果此时镜像位置相同的1的个数能被4整除，那么镜像位置不同的数对中把1全换成0即可。如果不被4整除，我们考虑两种情况：镜像位置不同的数个数>0，此时需要一对1，而不同的数代表有一个0和一个1，我们只需要把0变成1即可，其它的对数都变成0.如果镜像位置不同的数个数=0，也就是说现在全是1，但是多了一对1。我们就随便选一队1换成0即可。

class Solution:
    def minFlips(self, a: List[List[int]]) -> int:
        m, n = len(a), len(a[0])
        ans = 0
        for i in range(m // 2):
            row, row2 = a[i], a[-1 - i]
            for j in range(n // 2):
                cnt1 = row[j] + row[-1 - j] + row2[j] + row2[-1 - j]
                ans += min(cnt1, 4 - cnt1)  # 全为 1 或全为 0

        if m % 2 and n % 2:
            # 正中间的数必须是 0
            ans += a[m // 2][n // 2]

        diff = cnt1 = 0
        if m % 2:
            # 统计正中间这一排
            row = a[m // 2]
            for j in range(n // 2):
                if row[j] != row[-1 - j]:
                    diff += 1
                else:
                    cnt1 += row[j] * 2
        if n % 2:
            # 统计正中间这一列
            for i in range(m // 2):
                if a[i][n // 2] != a[-1 - i][n // 2]:
                    diff += 1
                else:
                    cnt1 += a[i][n // 2] * 2

        return ans + (diff if diff else cnt1 % 4)

999.可以被一步捕获的棋子数（1318）

给定一个 8 x 8 的棋盘，只有一个 白色的车，用字符 ‘R’ 表示。棋盘上还可能存在白色的象 ‘B’ 以及黑色的卒 ‘p’。空方块用字符 ‘.’ 表示。

车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃掉 棋子。

注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。

返回白车 攻击 范围内 兵的数量。

涉及知识点

表格

解决思路

秒答题，要模拟车的移动解题可以，记录象和卒的位置进行数学判断也可以。

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        SIZE=8
        for i,row in enumerate(board):
            for j,c in enumerate(row):
                if c=='R':
                    x0,y0=i,j
        ans=0
        for dx,dy in (0,-1),(0,1),(-1,0),(1,0):
            x,y=x0+dx,y0+dy
            while 0<=x<SIZE and 0<=y<SIZE and board[x][y]=='.':
                x+=dx
                y+=dy
            if 0<=x<SIZE and 0<=y<SIZE and board[x][y]=='p':
                ans+=1
        return ans

2286.以组为单位订音乐会的门票（2470）

一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：

同一组的 k 位观众坐在 同一排座位，且座位连续 。
k 位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。
由于观众非常挑剔，所以：

只有当一个组里所有成员座位的排数都 小于等于 maxRow ，这个组才能订座位。每一组的 maxRow 可能 不同 。
如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
请你实现 BookMyShow 类：

BookMyShow(int n, int m) ，初始化对象，n 是排数，m 是每一排的座位数。
int[] gather(int k, int maxRow) 返回长度为 2 的数组，表示 k 个成员中 第一个座位 的排数和座位编号，这 k 位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的 r 和 c 满足第 r 排中 [c, c + k - 1] 的座位都是空的，且 r <= maxRow 。如果 无法 安排座位，返回 [] 。
boolean scatter(int k, int maxRow) 如果组里所有 k 个成员 不一定 要坐在一起的前提下，都能在第 0 排到第 maxRow 排之间找到座位，那么请返回 true 。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有 k 个成员的座位，请返回 false 。

涉及知识点

线段树

解决思路

无论怎么卖票都不会出现空隙
一个[m] * n 数组记录每排左到哪了
一个区间极小线段树（m - 区间极小就是区间的最大连座数），给 gather 用
一个区间和线段树，给 scatter 用
外加一个minFull指针，也是给 scatter 用的，记录从左往右已经卖完票的最大排号
线段树的实现可以上leetcode看解析。

class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        self.min = [0] * (2 << n.bit_length())  # 相比 4n 空间更小
        self.sum = [0] * (2 << n.bit_length())

    # 线段树：把下标 i 上的元素值增加 val
    def update(self, o: int, l: int, r: int, i: int, val: int) -> None:
        if l == r:
            self.min[o] += val
            self.sum[o] += val
            return
        m = (l + r) // 2
        if i <= m:
            self.update(o * 2, l, m, i, val)
        else:
            self.update(o * 2 + 1, m + 1, r, i, val)
        self.min[o] = min(self.min[o * 2], self.min[o * 2 + 1])
        self.sum[o] = self.sum[o * 2] + self.sum[o * 2 + 1]

    # 线段树：返回区间 [L,R] 内的元素和
    def query_sum(self, o: int, l: int, r: int, L: int, R: int) -> int:
        if L <= l and r <= R:
            return self.sum[o]
        res = 0
        m = (l + r) // 2
        if L <= m:
            res = self.query_sum(o * 2, l, m, L, R)
        if R > m:
            res += self.query_sum(o * 2 + 1, m + 1, r, L, R)
        return res

    # 线段树：返回区间 [0,R] 中 <= val 的最靠左的位置，不存在时返回 -1
    def find_first(self, o: int, l: int, r: int, R: int, val: int) -> int:
        if self.min[o] > val:
            return -1  # 整个区间的元素值都大于 val
        if l == r:
            return l
        m = (l + r) // 2
        if self.min[o * 2] <= val:
            return self.find_first(o * 2, l, m, R, val)
        if R > m:
            return self.find_first(o * 2 + 1, m + 1, r, R, val)
        return -1

    def gather(self, k: int, maxRow: int) -> List[int]:
        # 找第一个能倒入 k 升水的水桶
        r = self.find_first(1, 0, self.n - 1, maxRow, self.m - k)
        if r < 0:  # 没有这样的水桶
            return []
        c = self.query_sum(1, 0, self.n - 1, r, r)
        self.update(1, 0, self.n - 1, r, k)  # 倒水
        return [r, c]

    def scatter(self, k: int, maxRow: int) -> bool:
        # [0,maxRow] 的接水量之和
        s = self.query_sum(1, 0, self.n - 1, 0, maxRow)
        if s > self.m * (maxRow + 1) - k:
            return False  # 水桶已经装了太多的水
        # 从第一个没有装满的水桶开始
        i = self.find_first(1, 0, self.n - 1, maxRow, self.m - 1)
        while k:
            left = min(self.m - self.query_sum(1, 0, self.n - 1, i, i), k)
            self.update(1, 0, self.n - 1, i, left)  # 倒水
            k -= left
            i += 1
        return True

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。