LeetCode Hot100 详细题解

每日一题

10/19

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里，每一轮：

如果队列最前面的学生喜欢栈顶的三明治，那么会 拿走它 并离开队列。
否则，这名学生会 放弃这个三明治 并回到队列的尾部。

这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

tag

队列

抽象

学生列表是个轮换的队列【循环队列】
而三明治列表反而是一个【固定栈】

思路

学生可以任意取
但是三明治不行
也就是说，三明治[i]如果是0，所有喜欢0的学生都没了，那就会被卡住

算法

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        cnt=Counter(students)
        for j in sandwiches:
            if cnt[j]!=0:
                cnt[j]-=1
            else:
                return cnt[1-j]
        return 0

10/20

第K个语法符号

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

tag

位运算
抽象

思路

索引是从1开始的，且都是源自1行的0。

第n行的第x个元素，是由第 $n-1$ 行的 $floor(\frac{x+1}{2})$ 元素生成的。

且满足：当 $x$ 时奇数，若是由0生成的 $01$ ，则 $x$ 为0，否则为1，若是由1生成的10，则x为1，否则为0.

于是我们发现，假设第 $n$ 行的第 $x$ 个元素为 $num1$ ，则它可以由第 $n-1$ 行的第 $floor(\frac{x+1}{2})$ 个元素生成而来，且满足：

$num1=(x\&1)\wedge1\wedge num2$

这里说明下，如果num2是0，当num1为奇数，则其值为0，否则为1。当num2是1，那么num1是奇数时，其值为1，否则为0。

说一个好玩的，关于

$y\wedge 1\wedge x$

y异或1后，原先是0的变成1，原先是1的变成0，奇偶换位。

实现

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        return (not (k & 1) ) ^ self.kthGrammar(n - 1, (k + 1) // 2)

或者是

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        return ((k & 1)^1 ) ^ self.kthGrammar(n - 1, (k + 1) // 2)