ITADN
joric/oneliners
代码 动态 Issues 合并请求 版本
joric/oneliners · 文件 下载 ZIP
文件最后提交记录最后更新时间
README.md
以下内容由 AI 翻译，如有问题请点此提交 issue 反馈

一行代码

仅供参考，这不仅仅是 README.md，仓库中还有超过一千个解决方案。统计数据也在这里。

  • 如果你找到了更短的解决方案（同样通过在线测试，即没有 MLE，没有 TLE），请将其发布到 issues 部分。

为什么选择 Python

Python 几乎总是比其他语言更短（并且拥有相关的库）。当然，也有例外。

Python (3.14)：

return(k-1).bit_count()&1

Ruby 或 Scala 有时能胜过它，因为它们不需要 return 语句。Ruby 3.2.10 在这里更长：

(k-1).to_s(2).count('1')&1

Ruby 3.3+ 在 Leetcode 更新启动器后可以更短，因此在简单任务中可能在字符数上占优：

(k-1).count_ones&1

即使是 C++ 有时也比 Python 更短（但大多数情况下并非如此）。在这个特定情况下，它只短了一个字符：

return popcount(k-1u)&1;

请注意，u 和 ; 在此处是必需的。如果我在其他语言中找到更短的解决方案，我通常会在注释中添加它。

Leetcode 特定事项

Leetcode 以通配符方式导入模块，因此您无需指定模块名称。有一些例外情况：

  • 不带前缀的单个 bisect() 会触发 object is not callable，请使用 bisect.bisect() 或 bisect_left()。
  • 您必须指定 re.sub，因为不带前缀的 sub 是 operator.sub。
  • 默认的 pow 是 __builtins__['pow']（最多支持 3 个参数，包括模数），而不是 math.pow。

例如，Leetcode 头部包含 import * from math，因此我们使用 comb() 而不是 math.comb()：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m+n-2, n-1)

您还可以使用 __import__('module').func 来表示未列出的模块（即 numpy、scipy 和 sortedcontainers）。

class Solution:
    def checkStraightLine(self, p):
        return __import__('numpy').linalg.matrix_rank([[1]+x for x in p])<3

有时你可以省去对返回类型的强制转换，例如 Leetcode 会自动将键和混合类型转换为列表。


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return dict(Counter(nums).most_common(k))

它还会自动评估生成器（2023 年 8 月起停止工作，expected return type integer[]）：

class Solution:
    def countBits(self, n: int) -> List[int]:
        return map(int.bit_count,range(n+1))

您也可以将值的链表作为 ListNode('a,b,...') 返回。这一用法非常具体，但有时很有用。

class Solution:
    def addTwoNumbers(self, a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
        f=lambda n:n and n.val+10*f(n.next)or 0;return ListNode(','.join([*str(f(a)+f(b))][::-1]))

Leetcode 还提供了用于列表和树的 serialize 和 deserialize 函数：

class Solution:
    def reverseList(self, h: Optional[ListNode]) -> Optional[ListNode]:
        return h and h.deserialize(str(eval(h.serialize(h))[::-1]))

还有 has_cycle 函数：

class Solution:
    def hasCycle (self, h: Optional[ListNode]) -> bool:
        return ListNode.has_cycle(h)

还有 _*_node_to_array 和 _array_to_*_node 函数：

class Solution:
    def isPalindrome(self, h: ListNode) -> bool:
        return(s:=type(h)._list_node_to_array(h))==s[::-1]
class Solution:
    def sortList(self, h: Optional[ListNode]) -> Optional[ListNode]:
        t=ListNode;return t._array_to_list_node(sorted(t._list_node_to_array(h)))

class Solution:
    def sortList(self, h: Optional[ListNode]) -> Optional[ListNode]:
        t=ListNode;return t.deserialize(str(sorted(eval(t.serialize(h)))))

您也可以将完整的预处理后的 solution 文件转储出来，自行检查所有导入（参见 gist）：

with open(__file__, 'rt') as f: print(f.read())

解决方案驱动程序代码将所有结果写入 user.out 文件，因此我们可以这样使用它：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        from zlib import decompress
        from base64 import b64decode
        open('user.out', 'wb').write(decompress(b64decode('eJzdkMEVwCAIQ++dggFyEKi2zuLr/mtItZb63KAc\
kpfwuVAYFK6tCIjNPH1KncodJMuBTqWTYUGe89hNX1Kd/K2Nh1iM3mYbkMlpIaFrvvcCaVwCH+YB3FSHVu5xXDc='))),exit(0)

目前没有经过批准的方法来获取 LeetCode 中所有问题的测试用例。 不过，你可以利用 LeetCode 会显示导致代码失败的测试用例这一事实。 上述解决方案不太可靠，因为测试和环境可能会发生变化，但它相当快速。

你可以使用 shell 命令探索沙箱，例如（参见 gist）：

import subprocess
print(subprocess.run(["ls", "-la", "/"]))

您还可以使用 atexit 设置自己的执行时间：

__import__('atexit').register(lambda: open("display_runtime.txt", "w").write("0")) # 0..2147483647

See https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/25646 (we have decided not to allocate development resources to fixing it at this time.)

两行减

一些 leetcode 题目可以在函数声明层面解决。

class Solution:searchInsert=bisect_left
class Solution:permute=permutations
class Solution:sortArray=sorted
class Solution:bulbSwitch=isqrt
class Solution:search=contains
class Solution:myPow=pow

请注意，它仅适用于内置函数，这些函数可以省略 self 参数。 这是 CPython 的内置功能：

你不能像那样使用自己的函数，而不跳过第一个参数。

class Solution:reverseWords=lambda _,s:' '.join(w[::-1]for w in s.split())

它不一定更短，因为 lambda 不能分号。

在某些情况下，你甚至不需要写 "class Solution:"，例如：

Codec=TreeNode

最短

让我们假设函数声明为零行。

class Solution:
    def accountBalanceAfterPurchase(self, x: int) -> int:
        return(104-x)//10*10
class Solution:
    def majorityElement(self, n: List[int]) -> int:
        return mode(n)
class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return m*n//2
class Solution:
    def numberOfMatches(self, n: int) -> int:
        return~-n
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return 1

考虑到类型自动转换在 2024 年停止工作：

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return 2>1

你也可以这样写：

class Solution:stoneGame=truth
class Solution:
    def isStrictlyPalindromic(self, n: int) -> bool:
        0

这是一个单符号解法。注意这里没有返回运算符，可以是 pass，因为函数返回 None。你也可以这样做：

class Solution:isStrictlyPalindromic=not_

Lambdas

虚构的（匿名的）lambda 可以嵌套。例如，你可以将 lambda 用作参数：

  • (lambda a,b,c: code)(a,b,c) 变为 (lambda a,b,c: code)(lambda a: code, lamda b: code, lambda c: code)

在 Python 3 中，由于 PEP 3113，你不能解包 lambda 元组，不过，如果你的 lambda 是扁平的，则存在升级路径：

  • Python 2 中的 lambda (x, y): x + y 在 Python 3 中变为 lambda xy:(lambda x,y: x+y)(*xy)。

你还可以将多个元组解包为 lambda xy,ab:(lambda x,y,a,b: x+y+a+b)(*(xy+ab))。

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        return sum(reduce(lambda x,_:(lambda a,e,i,o,u:(e+i+u,a+i,e+o,i,i+o))(*x),[0]*(n-1),[1]*5))
            %(10**9+7)

有时你可以使用 starmap 来解包元组：

class Solution:
    def lenLongestFibSubseq(self, n: List[int]) -> int:
        s={*n};return(0,t:=max(starmap(f:=lambda a,b,c=2:s&{a+b}and f(b,a+b,c+1)or c,
            combinations(n,2))))[t>2]

生成器

生成器表达式 (x for y in z) 内存效率较高，因为它们仅需为所产出的单个值分配内存。如果你不关心内存占用，可以使用方括号将其变为列表推导式，从而自动执行循环。 你还可以根据返回值，使用 all()、any() 或 sum() 来耗尽生成器。 当 g 是生成器函数时，你还可以使用 [*g] 语法代替 list(g) 来节省几个字符。 生成器长度 len(list(g)) 可以以恒定内存计算为 sum(1 for _ in g)。

生成器展开 [*g] 在初始化部分可能使用尾随逗号 *g,（少 1 个字符）。

class Solution:
    def maxAbsoluteSum(self, a: List[int]) -> int:
        a=[*accumulate([0]+a)];return max(a)-min(a)

class Solution:
    def maxAbsoluteSum(self, a: List[int]) -> int:
        a=*accumulate([0]+a),;return max(a)-min(a)

迭代器

生成器提供了一种简单、内置的方式来创建迭代器实例。 迭代器是具有 __iter__ 和 __next__ 方法的对象。 iter() 方法为给定的参数返回一个迭代器。 每次访问迭代器都会前进一步。 可能有用，例如，如果不将字符串转换为迭代器，此解决方案将不起作用：

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        s=iter(s);return sum(c not in s for c in t)

你还可以使用 iter() 将列表拆分为块。[iter(s)]*n 技巧将列表拆分为大小为 n 的片段：

class Solution:
    def minChanges(self, s: str) -> int:
        return sum(map(ne,s[::2],s[1::2]))

class Solution:
    def minChanges(self, s: str) -> int:
        return sum(map(ne,s:=iter(s),s))

class Solution:
    def minChanges(self, s: str) -> int:
        return sum(map(ne,*[iter(s)]*2))

字典

从 Python 3.7 开始，字典的顺序保证为插入顺序。

一个简单的哈希表由基于哈希函数计算结果以伪随机顺序排列的键值对组成。 Python dict 的传统实现使用稀疏数组，其中包含大量未使用的空间。 新实现使用密集数组和稀疏数组的组合， 密集数组存储键值对，而稀疏数组存储指向该密集数组的索引。

计数器

计数器（collections.Counter()）可以被更新，类似于 dict.update()，它比计数器求和快得多。 例如，c[i]+=1 等价于 c.update([i])，c[i]-=1 是 c.update({i:-1})。 要删除一个键，可以使用 .pop 方法（与 del 相同），它比 popitem() 更短。

请注意，c.update({i:x}) 和 setitem(c,i,c[i]+x) 的行为不同。如果 x 为负数且计数变为 <=0，该键将被移除。

您也可以手动移除零值和负值（有官方方法，参见 文档）：

c = Counter({1:1,2:0,3:-1}); print(c:=+c) #{1: 1}, same as c += Counter()

自 Python 3.7 起，作为 dict 的子类，Counter 继承了记住插入顺序的能力。


class Solution:
    def reductionOperations(self, n: List[int]) -> int:
        return sum(i*v for i,(_,v)in enumerate(sorted(Counter(n).items())))

class Solution:
    def reductionOperations(self, n: List[int]) -> int:
        return sum(i*v for i,v in enumerate(Counter(sorted(n)).values()))

从 Python 3.10 开始，你可以使用 total() 来计算计数的总和。

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        return sum((Counter(s)-Counter(t)).values())

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        return(Counter(s)-Counter(t)).total()

有时你可以用 set 和 count 替换 Counter（而且速度更快）：

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        return sum(x&1 for x in Counter(s).values())<=k<=len(s)

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        return sum(1&s.count(x)for x in set(s))<=k<=len(s)
class Solution:
    def minimumLength(self, s: str) -> int:
        return sum(2-x%2 for x in Counter(s).values())

class Solution:
    def minimumLength(self, s: str) -> int:
        return sum(2-s.count(x)%2 for x in set(s))

与 dict 不同，python set 并不保持插入顺序。存在一些实现了有序集合的模块。

在许多问题中，你可以使用 SortedList 来代替堆。

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        r,q = inf,[]
        for a in nums:
            heappush(q,a%2 and -a*2 or -a)
        m = -max(q)
        while len(q) == len(nums):
            a = -heappop(q)
            r = min(r, a - m)
            if a%2==0:
                m = min(m, a//2)
                heappush(q, -a//2)
        return r

from sortedcontainers import SortedList

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        s,r = SortedList(i*2 if i & 1 else i for i in nums),inf
        while True:
            r = min(r,s[-1]-s[0])
            if 1&s[-1]: break
            s.add(s.pop()//2)
        return r

class Solution:
    def minimumDeviation(self, a: List[int]) -> int:
        s,r=__import__('sortedcontainers').SortedList(i*(1+i%2)for i in a),inf;
        return next(r for _ in count()if[r:=min(r,s[-1]-s[0])]and 1&s[-1]or s.add(s.pop()//2))

海象运算符

颇具争议的海象运算符（:=）在 Python 3.8 中引入（PEP-572， 当 Guido van Rossum 辞职）， 可用于定义或更新变量或函数（主要用于递归函数）。

你可以使用 Y 组合子在一行内定义并调用递归函数，例如：

return (lambda y,x:y(y,x))(lambda f,x:1 if x==0 else x*f(f,x-1),5)

但海象运算符的语法要简洁得多：

return (f:=lambda x:1 if x==0 else x*f(x-1))(5)

许多单行代码如果没有它（或者更准确地说，使用嵌套 lambda 时）将难以实现（或者非常困难）。 有时你甚至不需要额外的括号，例如在 map(f:=x,y) 或 next(g,f:=x) 中，因此它可能比用分号分隔的操作符更短。

class Solution:
    def numOfMinutes(self, n: int, h: int, m: List[int], t: List[int]) -> int:
        return max(map(f:=cache(lambda i:~i and t[i]+f(m[i])),m))
class Solution(object):
    def guessNumber(self, n: int) -> int:
        l,r = 1, n
        while l <= r:
            m = (l + r) // 2
            res = guess(m)
            if res == 0:
                return m
            elif res > 0:
                l = m + 1
            else:
                r = m - 1
        return 0

class Solution:
    def guessNumber(self, n: int) -> int:
        return (f:=lambda l,h:h if l+1==h else f(m,h) if guess(m:=(l+h)//2)>0 else f(l,m))(0,n)
class Solution:
    def reverse(self, x: int) -> int:
        r, x = 0, abs(x)
        while x:
            r = r*10 + x%10
            x //= 10
        return ((x>0)-(x<0))*min(2**31, r)

class Solution:
    def reverse(self, x: int) -> int:
        return ((x>0)-(x<0))*min(2**31,(f:=lambda r,x:f(r*10 + x%10, x//10) if x else r)(0,abs(x)))
class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        return nsmallest(k,(f:=Counter(words)).keys(),lambda x:(-f[x],x))

设置值

你可以使用 __setattr__ 用于字典，或使用 __setitem__ 用于列表（这两个成员函数都返回 None）。 你也可以使用 operator 模块中的 setattr 或 setitem 函数， 例如 c[x]=1 等同于 setitem(c,x,1)。

class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int, isLeft: bool = True) -> TreeNode:
        if d == 1:
            return TreeNode(v, root if isLeft else None, root if not isLeft else None)
        if not root:
            return None
        root.left = self.addOneRow(root.left, v, d - 1, True)
        root.right = self.addOneRow(root.right, v, d - 1, False)
        return root

class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int, isLeft: bool = True) -> TreeNode:
        return TreeNode(v, root if isLeft else None, root if not isLeft else None) if d==1 else \
        setattr(root,'left', self.addOneRow(root.left, v, d - 1, True)) or \
        setattr(root,'right', self.addOneRow(root.right, v, d - 1, False)) or root if root else None
class Solution(object):
    def deleteMiddle(self, head):
        def f(a, b):
            if not b:
                return a.next
            a.next = f(a.next, b.next.next) if b.next else f(a.next, b.next)
            return a
        return f(head, head.next)

class Solution(object):
    def deleteMiddle(self, head):
        return (f:=lambda a,b:setattr(a,'next',f(a.next, b.next.next) if b.next
            else f(a.next, b.next)) or a if b else a.next)(head, head.next)

请注意，setitem 也支持切片：

# TLE, too slow
class Solution:
    def countPrimes(self, n):
        g=range(2,n);return len(reduce(lambda r,x:r-set(range(x**2,n,x))if x in r else r,g,set(g)))

class Solution:
    def countPrimes(self, n):
        a = [0,0]+[1]*(n-2)
        for i in range(2,int(n**0.5)+1):
            if a[i]:
                a[i*i:n:i] = [0]*len(a[i*i:n:i])
        return sum(a)

class Solution:
    def countPrimes(self, n):
        return sum(reduce(lambda a,i:a[i] and setitem(a,slice(i*i,n,i),[0]*len(a[i*i:n:i])) or a,
            range(2,int(n**0.5)+1), [0,0]+[1]*(n-2)))

你也可以这样计算质数：

class Solution:
    def primeSubOperation(self, a: List[int]) -> bool:
        m,p=1,[0]+[i for i in range(2,999)if all(i%j for j in range(2,i))];\
        return all(m<(m:=x-p[bisect_right(p,x-m)-1]+1)for x in a)

Note slices can extend the list implicitly, e.g.:

a = [0,1,2]
a[3:4] = [3] # the result is [0,1,2,3]

不过请注意，切片不会将列表扩展到超出切片大小的范围：

a = [0,1]
a[3:4] = [3,4] # the result is [0,1,3,4], NOT [0,1,?,3,4] (!)

示例：

class Solution:
    def longestObstacleCourseAtEachPosition(self, o: List[int]) -> List[int]:
        d = []
        for e in o:
            i = bisect_right(d,e)
            if i==len(d):
                d.append(0)
            d[i] = e
            yield i+1

class Solution:
    def longestObstacleCourseAtEachPosition(self, o: List[int]) -> List[int]:
        d = []
        for e in o:
            i = bisect_right(d,e)
            d[i:i+1] = [e]
            yield i+1

class Solution:
    def longestObstacleCourseAtEachPosition(self, o: List[int]) -> List[int]:
        d=[];return[setitem(d,slice(i:=bisect_right(d,e),i+1),[e])or i+1for e in o]

有时（非常频繁地）exec 比 setitem 更短。

ParkingSystem=type('',(),{'__init__':lambda s,a,b,c:setattr(s,'p',[0,a,b,c]),'addCar':lambda s,t:\
    setitem(s.p,t,s.p[t]-1)or s.p[t]>=0})

ParkingSystem=type('',(),{'__init__':lambda s,a,b,c:setattr(s,'p',[0,a,b,c]),'addCar':lambda s,t:\
    exec('s.p[t]-=1')or s.p[t]>=0})
class Solution:
    def maximumEnergy(self, e: List[int], k: int) -> int:
        [setitem(e,i,e[i]+e[i+k])for i in range(len(e)-k)[::-1]];return max(e)

class Solution:
    def maximumEnergy(self, e: List[int], k: int) -> int:
        exec('for i in range(len(e)-k):e[~i-k]+=e[~i]');return max(e)

类

你可以在一行中编写一个类或子类的实现。

MyHashSet=type('',(set,),{'remove':set.discard,'contains':set.__contains__})
MyStack=type('',(list,),{'push':list.append,'top':lambda s:s[-1],'empty':lambda s:not s})
ProductOfNumbers=type('',(list,),{'__init__':lambda s:list.__init__(s,[1]),'add':lambda s,x:
s.append(s[-1]*x)if x else s.__init__(),'getProduct':lambda s,k:s[k:]and s[-1]//s[~k]or 0})

自 Python 3.7 起，Counter 子类化失败，type() doesn't support MRO entry resolution; use types.new_class()。

当你尝试使用 types.new_class() 时，它会提示 TypeError: .__init_subclass__() takes no keyword arguments')。

可以通过先创建类，然后单独向其添加方法来避免此问题，例如：

с=Counter;с.insert=lambda s,x:s.update({x})or s[x]<2;с.remove=lambda s,x:s.pop(x,0);
с.getRandom=lambda s:choice([*s]);RandomizedSet=с

有时（并非总是）你可以跳过 __init__ 并使用静态属性。

UndergroundSystem=type('',(),{'h':{},'m':{},'checkIn':lambda s,i,v,t:setitem(s.m,i,(v,t)),
    'checkOut':lambda s,i,d,w:(v:=s.m[i][0])and setitem(s.h,(v,d),[*map(sum,zip(s.h.pop((v,d),
    (0,0)),(w-s.m[i][1],1)))]),'getAverageTime':lambda s,v,d:truediv(*s.h[v,d])})

二分查找

二分查找可以使用内置的 bisect 方法替代。 自定义二分查找可以使用元素获取器对象或键函数（自 Python 3.10 起）。 标准库中的 bisect 实现位于 bisect.py（你必须熟练掌握它）。


class Solution:
    def guessNumber(self, n: int) -> int:
        l,r = 1, n
        while l <= r:
            m = (l + r) // 2
            res = guess(m)
            if res == 0:
                return m
            elif res > 0:
                l = m + 1
            else:
                r = m - 1
        return 0

class Solution:
    def guessNumber(self, n: int) -> int:
        return bisect_left(type('',(),{'__getitem__':lambda _,i: -guess(i)})(), 0, 1, n)

class Solution:
    def guessNumber(self, n: int) -> int:
        return bisect_left(range(n), 0, key=lambda num: -guess(num))

请注意，内置方法不支持负左边距，因此你必须从结果中减去它：

class Solution:
    def kthSmallestProduct(self, a: List[int], b: List[int], k: int) -> int:
        f=lambda x:sum(bisect_right(b,x//y)if y>0 else len(b)-bisect_left(b,ceil(x/y))if y<0 else
            (x>=0)*len(b)for y in a)
        l,r = -10**10-1, 10**10+1
        while l < r:
            m = (l + r)//2
            if f(m) >= k:
                r = m
            else:
                l = m + 1
        return l

class Solution:
    def kthSmallestProduct(self, a: List[int], b: List[int], k: int) -> int:
        f=lambda x:sum(bisect_right(b,x//y)if y>0 else len(b)-bisect_left(b,ceil(x/y))if y<0 else
            (x>=0)*len(b)for y in a)
        return bisect_left(range(2*(r:=10**10)),k,key=lambda i:f(i-r))-r

Range

Python 3 中的 Range 支持随机访问，因此你可以使用一个较长的硬编码范围来节省几个字符。

class Solution:
    def repairCars(self, r: List[int], c: int) -> int:
        return bisect_left(range(c*c*min(r)),c,key=lambda m:sum(isqrt(m//x)for x in r))

class Solution:
    def repairCars(self, r: List[int], c: int) -> int:
        return bisect_left(range(1<<47),c,key=lambda m:sum(isqrt(m//x)for x in r))

While 循环

While 循环不太适合单行写法。你可以使用 next() 函数配合一个无限的 count() 生成器。 请注意，默认参数会最先执行，因此你可以用它来编写启动代码（它不会在末尾重新计算）。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i,x in enumerate(nums):
            if target-x in seen:
                return seen[target-x], i
            seen[x] = i
        return False

class Solution:
    def twoSum(self, n: List[int], t: int) -> List[int]:
        return next(((m[t-x],i)for i,x in enumerate(n)if t-x in m or setitem(m,x,i)),m:={})
class Solution:
    def breakPalindrome(self, s: str) -> str:
        for i in range(len(s) // 2):
            if s[i] != 'a':
                return s[:i] + 'a' + s[i + 1:]
        return s[:-1] + 'b' if s[:-1] else ''

class Solution:
    def breakPalindrome(self, s: str) -> str:
        return next((s[:i]+'a'+s[i+1:]for i in range(len(s)//2)if s[i]!='a'),s[:-1]and s[:-1]+'b')
class Solution:
    def isPossible(self, target: List[int]) -> bool:
        s = sum(target)
        q = [-a for a in target]
        heapify(q)
        while True:
            x = -heappop(q)
            if x==1:
                return True
            if s==x:
                return False
            d = 1 + (x-1) % (s-x)
            if x==d:
                return False
            s = s - x + d
            heappush(q, -d)

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        return (s:=sum(target),q:=[-a for a in target],heapify(q)) and next((x==1 for _ in count()
        if (x:=-heappop(q))==1 or s==x or (d:=1+(x-1)%(s-x))==x or not (s:=s-x+d,heappush(q,-d))),1)

你也可以使用 takewhile()，它同样是一个生成器，因此你需要对其进行展开（例如使用 repeat(0)）。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        r, d = [], deque()
        for i, n in enumerate(nums):
            while d and n>=nums[d[-1]]:
                d.pop()
            d.append(i)
            if d[0] == i-k:
                d.popleft()
            r.append(nums[d[0]])
        return r[k-1:]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        return (d:=deque()) or reduce(lambda r,p:(
            any(takewhile(lambda _:d and p[1]>=nums[d[-1]] and d.pop(), repeat(0))),
            d.append(p[0]), d[0]==p[0]-k and d.popleft(), r.append(nums[d[0]])) and r,
            enumerate(nums), [])[k-1:]

您也可以尝试使用 any() 或 all() 作为 while 循环，而不是 next()，它可能更短。 您可以确保该表达式从不返回 None，使用 []（[None] 求值为 True）。


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones.sort()
        while len(stones) > 1:
            insort(stones,stones.pop() - stones.pop())
        return stones[0]

class Solution:
    def lastStoneWeight(self, s: List[int]) -> int:
        return next((s[0] for _ in count() if not s[1:] or insort(s,s.pop()-s.pop())),s.sort())

class Solution:
    def lastStoneWeight(self, s: List[int]) -> int:
        return (s.sort(),all(s[1:] and [insort(s,s.pop()-s.pop())] for _ in count()),s[0])[2]

您还可以使用 exec 来评估多行代码。与 eval 不同，它不限于单个字符串。

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        return next((r for _ in count()if not(n and(r:=r^n,n:=n//2))),r:=0)

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        r=[0];exec('while n:\n r[0]^=n\n n//=2');return r[0]

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        return(f:=lambda n:n and n^f(n//2))(n)

Swap

要交换值，你可以使用 exec（a,b=b,a 的内联版本）或一个临时变量（t:=a,a:=b,b:=t）。

请注意，eval 仅接受单个表达式，并返回给定表达式的值， 而 exec 会忽略其代码的返回值，并始终返回 None，其使用对使用它的函数的编译后字节码没有影响。 但它确实会影响现有变量。

示例：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        def fn(t,b):
            red, white, blue = t
            return (swap:=lambda a,x,y:exec('a[x],a[y]=a[y],a[x]'),(swap(nums,red,white),
            (red+1,white+1,blue))[1] if nums[white]==0 else ((red,white+1,blue) if nums[white]==1
            else (swap(nums,white,blue),(red,white,blue-1))[1]))[1]
        reduce(fn, nums, [0,0,len(nums)-1])

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        (s:=lambda a,x,y:(t:=a[x],setitem(a,x,a[y]),setitem(a,y,t),a)[3],
        f:=lambda a,i,j,k:(f(s(a,i,j),i+1,j+1,k) if a[j]==0 else f(a,i,j+1,k) if a[j]==1
        else f(s(a,j,k),i,j,k-1)) if i<=j<=k else None)[1](nums,0,0,len(nums)-1)

你也可以在这里尝试一个交换函数（但它相当长，我并没有使用它）：

swap = lambda a,x,y:(lambda f=a.__setitem__:(f(x,(a[x],a[y])),f(y,a[x][0]),f(x,a[x][1])))()

Map

你可以使用 map 来做很多事情，例如遍历相邻的单元格。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i,j):
            if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]:
                grid[i][j] = 0
                return 1 + sum(map(dfs,(i+1,i,i-1,i),(j,j+1,j,j-1)))
            return 0
        return max(dfs(i,j) for i in range(len(grid)) for j in range(len(grid[0])))

class Solution:
    def maxAreaOfIsland(self, g: List[List[int]]) -> int:
        return max((f:=lambda i,j:setitem(g[i],j,0) or 1 + sum(map(f,(i+1,i,i-1,i),(j,j+1,j,j-1)))
            if 0<=i<len(g) and 0<=j<len(g[0]) and g[i][j] else 0)(i,j)
            for i in range(len(g)) for j in range(len(g[0])))

尽管使用复数来表示二维地图更简短（由 Stephan Pochmann 引入）：

class Solution:
    def maxAreaOfIsland(self, grid):
        grid = {i + j*1j: val for i, row in enumerate(grid) for j, val in enumerate(row)}
        def area(z):
            return grid.pop(z, 0) and 1 + sum(area(z + 1j**k) for k in range(4))
        return max(map(area, set(grid)))

class Solution:
    def maxAreaOfIsland(self, grid):
        return max(map(a:=lambda z: g.pop(z, 0) and 1 + sum(a(z + 1j**k) for k in range(4)),
            set(g:= {i + j*1j: val for i, row in enumerate(grid) for j, val in enumerate(row)})))

复数通常非常有用，可作为二维坐标：

class Solution:
    def isPathCrossing(self, p: str) -> bool:
        z=0;return len(p)>=len({0,*{z:=z+1j**'NESW'.find(c)for c in p}})

你可以使用 !=0 而不是 bool()（少 3 个字符），或 >[]（省去额外空格）将列表或元组转换为 True。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        grid = {i + j*1j:int(val) for i,row in enumerate(grid) for j,val in enumerate(row)}
        def f(z):
            return grid.pop(z,0) and bool([f(z + 1j**k) for k in range(4)])
        return sum(map(f, set(grid)))

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        return sum(map(f:=lambda z:g.pop(z,0) and [f(z + 1j**k) for k in range(4)]!=0,
            set(g:={i + j*1j:int(x) for i,row in enumerate(grid) for j,x in enumerate(row)})))
class Solution:
    def closedIsland(self, grid: List[List[str]]) -> int:
        g = {i+j*1j:1-x for i,r in enumerate(grid) for j,x in enumerate(r)}
        f = lambda z:g.pop(z,0) and [f(z+1j**k) for k in range(4)]!=0
        sum(f(z) for z in set(g) if not(0<z.real<len(grid)-1 and 0<z.imag<len(grid[0])-1))
        return sum(map(f,set(g)))

class Solution:
    def closedIsland(self, grid: List[List[str]]) -> int:
        return (g:={i+j*1j:1-x for i,r in enumerate(grid) for j,x in enumerate(r)},
            f:=lambda z:g.pop(z,0) and [f(z+1j**k) for k in range(4)]!=0,[f(z) for z in set(g)
            if not(0<z.real<len(grid)-1 and 0<z.imag<len(grid[0])-1)]) and sum(map(f,set(g)))
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def f(z,r):
            if x:=g.pop(z,0):
                if x==3 and not g:
                    r = r + 1
                for k in range(4):
                    r = f(z + 1j**k, r)
                g.update({z:x})
            return r
        g = {i + j*1j:x+1 for i, row in enumerate(grid) for j,x in enumerate(row) if x!=-1}
        return f(next(z for z,x in g.items() if x==2),0)

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        return (g:={i + j*1j:x+1 for i, row in enumerate(grid) for j,x in enumerate(row)
        if x!=-1}) and (f:=lambda z,r:[(x:=g.pop(z,0)) and (x==3 and not g and (r:=r+1),
        [r:=f(z + 1j**k,r) for k in range(4)],g.update({z:x}))] and r)
        (next(z for z,x in g.items() if x==2), 0)

BFS

DFS 通常比 BFS 更短，但并非总是如此。 该循环可以进行大幅度的大小优化。它通常是 all()、any()，或者是用于解包队列的递归函数， 但它也可以是一个单一的列表推导式。技巧在于队列每次并不会被重新迭代，而是从上一个索引继续。

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        g,s,q,r = defaultdict(list),set(),[1],inf
        for u,v,w in roads:
            g[u].append((v,w))
            g[v].append((u,w))
        while q:
            u = q.pop()
            for v,w in g[u]:
                r = min(r,w)
                if v not in s:
                    q.append(v)
                    s.add(v)
        return r

class Solution:
    def minScore(self, n: int, r: List[List[int]]) -> int:
        g=defaultdict(list);[g[u].append((v,w))or g[v].append((u,w))for u,v,w in r];
        q=[1];return min(q.append(v)or w for u in q for v,w in g.pop(u,[]))

Unicode Find

Unicode find（并非 Union Find）是解决图问题的史上最佳技巧。 其核心思想是在 Unicode 空间中使用字符串替换。由 Stephan Pochmann 提出。

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        t = ''.join(map(chr, range(1001)))
        for u,v in edges:
            if t[u]==t[v]:
                return [u,v]
            t = t.replace(t[u],t[v])

class Solution:
    def findRedundantConnection(self, e: List[List[int]]) -> List[int]:
        t=''.join(map(chr,range(1001)));
        return next([u,v]for u,v in e if t[u]==(t:=t.replace(t[u],t[v]))[u])

另一个例子：


class Solution:
    def swimInWater(self, g: List[List[int]]) -> int:
        n = len(g)
        t,r = ''.join(map(chr,range(n*n))),range(n)
        for w,i,j in sorted((g[i][j],i,j)for i,j in product(r,r)):
            for x,y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                if n>y>=0<=x<n and g[x][y]<=w:
                    t = t.replace(t[i*n+j],t[x*n+y])
            if t[0]==t[-1]:
                return w
        return 0

class Solution:
    def swimInWater(self, g: List[List[int]]) -> int:
        n=len(g);t,r=''.join(map(chr,range(n*n))),range(n);return next((w for w,i,j in
        sorted((g[i][j],i,j)for i,j in product(r,r))if[t:=t.replace(t[i*n+j],t[x*n+y]) for x,y
        in((i+1,j),(i-1,j),(i,j+1),(i,j-1)) if n>y>=0<=x<n and g[x][y]<=w]and t[0]==t[-1]),0)

另一个例子（Q4 位于 https://leetcode.com/contest/weekly-contest-392）：

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        t,c = ''.join(map(chr,range(n))),{}
        for u,v,w in edges:
            t = t.replace(t[u],t[v])
        for u,v,w in edges:
            c[t[u]] = c.get(t[u],w)&w
        return [0 if u==v else c[t[u]] if t[u]==t[v] else -1 for u,v in query]

class Solution:
    def minimumCost(self, n: int, e: List[List[int]], q: List[List[int]]) -> List[int]:
        t,c=''.join(map(chr,range(n))),{};all(t:=t.replace(t[u],t[v])for u,v,_ in e);
        [setitem(c,t[u],c.get(t[u],w)&w)for u,v,w in e];
        return[u!=v and t[u]!=t[v]and-1or c[t[u]]for u,v in q]

缓存

缓存装饰器，@lru_cache 或 @cache（自 Python 3.9 起）可作为内联函数使用 cache(lambda ...)。 本质上，这是一种内置的备忘录化。根据问题的不同，可将计算复杂度从指数级降低到二次方或线性。 装饰器的源代码位于 functools.py。 你也可以实现缓存装饰器的 C++ 版本。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        @cache
        def dfs(i, k, sell):
            return 0 if k==0 or i==len(prices) \
            else max(dfs(i+1, k-1, 0) + prices[i], dfs(i+1, k, 1)) if sell \
            else max(dfs(i+1, k, 1)-prices[i], dfs(i+1, k, sell))
        return dfs(0, k, 0)

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        return (f:=cache(lambda i,k,s:0 if k==0 or i==len(prices)
            else max(f(i+1,k-s,1-s)+prices[i]*(2*s-1),f(i+1,k,s))))(0,k,0)
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @cache
        def f(n):
            return min([1 + f(n-c) for c in coins]) if n>0 else 0 if n==0 else inf
        x = f(amount)
        return x if x!=inf else -1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        return (lambda x:x if x!=inf else -1)((f:=cache(lambda n:
            min([1+f(n-c) for c in coins]) if n>0 else 0 if n==0 else inf))(amount))

有时需要在测试之间使用 cache_clear 重置缓存，以避免 Memory Limit Exceeded 错误。

class Solution:
    def lengthOfLongestSubsequence(self, a: List[int], t: int) -> int:
        return(a.sort(),r:=(f:=cache(lambda i,b:b and -inf if b<0 or i<0 else
            max(1+f(i-1,b-a[i]),f(i-1,b))))(len(a)-1,t),f.cache_clear())and(-1,r)[r>0]

您也可以指定 maxsize 选项为 f=lru_cache(maxsize)(lambda ...)，以应对内存问题：


class Solution:
    def shortestCommonSupersequence(self, a: str, b: str) -> str:
        return(f:=lru_cache(9**5)(lambda i,j:a[i:]and b[j:]and(a[i]==b[j]and a[i]+f(i+1,j+1)
            or min(a[i]+f(i+1,j),b[j]+f(i,j+1),key=len))or a[i:]or b[j:]))(0,0)

Cache 装饰器不支持列表参数，但你可以解包列表而无需转换为元组：

class Solution:
    def predictTheWinner(self, n: List[int]) -> bool:
        return(f:=cache(lambda*t:t and max(t[0]-f(*t[1:]),t[-1]-f(*t[:-1]))or 0))(*n)>=0

Reduce

使用它来展平循环。

class Solution:
    def lengthOfLongestSubstring(self, s):
        start, res, h = 0, 0, {}
        for i, c in enumerate(s):
            start = max(start, h.get(c,0))
            res = max(res, i - start + 1)
            h[c] = i + 1
        return res

class Solution:
    def lengthOfLongestSubstring(self, s):
        def fn(a,b):
            start, res, h = a
            i, c = b
            start = max(start, h.get(c,0))
            res = max(res, i - start + 1)
            h[c] = i + 1
            return start,res,h
        return reduce(fn,enumerate(s),[0,0,{}])[1]

class Solution:
    def lengthOfLongestSubstring(self, s):
        return reduce(lambda a,b:(s:=max(a[0],a[2].get(b[1],0)),max(a[1],b[0]-s+1),
            {**a[2],b[1]:b[0]+1}),enumerate(s),(0,0,{}))[1]


class Solution:
    def lengthOfLongestSubstring(self, s):
        return reduce(lambda a,b:(lambda t,r,h,i,c:(s:=max(t,h.get(c,0)),max(r,i-s+1),
            {**h,c:i+1}))(*a,*b),enumerate(s),(0,0,{}))[1]

另一个例子：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        def fn(a,b):
            r, s = a
            i, p = b
            return (max(r,i-s[-2][0]), s[:-1]) if p==')' and s[-1][1]=='(' else (r, s+[(i,p)])
        return reduce(fn, enumerate(s), (0,[(-1, ')')]))[0]

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        return reduce(lambda a,b:(max(a[0],b[0]-a[1][-2][0]),a[1][:-1]) if b[1]==')'
            and a[1][-1][1]=='(' else (a[0],a[1]+[b]),enumerate(s),(0,[(-1,')')]))[0]

产品

itertools 中的 product 函数有时很方便。


class Solution:
    def nthUglyNumber(self, n: int) -> int:
        return sorted(2**a*3**b*5**c for a in range(32)for b in range(20)for c in range(14))[n-1]

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        return sorted(2**a*3**b*5**c for a,b,c in product(*map(range,(32,20,14))))[n-1]

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        return sorted(2**a*3**b*5**c for a,b,c in product(*[range(32)]*3))[n-1]

组合

可在任何地方替代嵌套循环使用。示例：

class Solution:
    def countPrefixSuffixPairs(self, w: List[str]) -> int:
        r=range(len(w))
        return sum(i<j and w[j].startswith(w[i])and w[j].endswith(w[i])for i in r for j in r)

class Solution:
    def countPrefixSuffixPairs(self, w: List[str]) -> int:
        return sum(b.startswith(a)and b.endswith(a)for a,b in combinations(w,2))

class Solution:
    def countPrefixSuffixPairs(self, w: List[str]) -> int:
        return sum(a==b[:len(a)]==b[-len(a):]for a,b in combinations(w,2))

如果需要在循环之间进行赋值，你仍然可以将嵌套循环重写为单个聚合：

class Solution:
    def longestBalanced(self, a: list[int]) -> int:
        return max(max((o,e)[x&1].add(x)or-~j*(len(o)==len(e))
            for j,x in enumerate(a[i:]))for i in range(len(a))if(o:={*()},e:={*()}))

class Solution:
    def longestBalanced(self, a: list[int]) -> int:
        return max((o,e)[x&1].add(x)or-~j*(len(o)==len(e))
            for i in range(len(a))if(o:={*()},e:={*()})for j,x in enumerate(a[i:]))
class Solution:
    def longestBalanced(self, s: str) -> int:
        return max(max(j+1 for j,x in enumerate(s[i:])
            if c.update([x])or len({*c.values()})<2)for i in range(len(s))if[c:=Counter()])

class Solution:
    def longestBalanced(self, s: str) -> int:
        return max(j+1 for i in range(len(s))if[c:=Counter()]for j,x in enumerate(s[i:])
            if c.update([x])or len({*c.values()})<2)

分号

没人会阻止你使用分号，但你仍然需要转换 while 和 for 循环。

示例：

class Solution:
    def swapNodes(self, h: Optional[ListNode], k: int) -> Optional[ListNode]:
        q = h
        i = 1
        d = {}
        while q:
            d[i] = q
            q = q.next
            i += 1
        d[k].val, d[i-k].val = d[i-k].val, d[k].val
        return h

class Solution:
    def swapNodes(self, h: Optional[ListNode], k: int) -> Optional[ListNode]:
        q=h;i=1;d={};all(q and(setitem(d,i,q),q:=q.next,i:=i+1) for _
            in count());d[k].val,d[i-k].val=d[i-k].val,d[k].val;return h

class Solution:
    def swapNodes(self, h: Optional[ListNode], k: int) -> Optional[ListNode]:
        l=[h]+[h:=h.next for _ in[1]*10**5if h];a,b=l[k-1],l[~k];a.val,b.val=b.val,a.val;return l[0]

数学技巧

许多 LeetCode 题目使用斐波那契数列，该数列可以通过多种不同的方法计算。


# generating function

class Solution:
    def fib(self, n: int) -> int:
        p=[0]*(n+2)
        p[1]=1
        for i in range(n):
            p[i+1]+=p[i]
            p[i+2]+=p[i]
        return p[n]

class Solution:
    def fib(self, n: int) -> int:
        a,b = 0,1
        for _ in range(n):
            a,b = b,a+b
        return a 

# classic Binet, https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html

class Solution:
    def fib(self, n: int) -> int:
        phi = (1 + sqrt(5)) / 2
        return round(pow(phi, n) / sqrt(5))

class Solution:
    def fib(self, n: int) -> int:
        n-=1;r=5**.5;return round(((1+r)/2)**-~n/r)

class Solution:
    def fib(self, n: int) -> int:
        r=5**.5;return round(((1+r)/2)**n/r)

# polynomial expontiation, https://blog.paulhankin.net/fibonacci2/

class Solution:
    def fib(self, n: int) -> int:
        x = 1 << (n + 2)
        return pow(x, n+1, x**2 - x - 1) % x

class Solution:
    def fib(self, n: int) -> int:
        x=1<<32;return x**~-n*x*x//(x*x+~x)%x

class Solution:
    def fib(self, n: int) -> int:
        x=9**n;return x**-~n//(x*x+~x)%x

class Solution:
    def fib(self, n: int) -> int:
        return pow(x:=2<<n,n+1,x*x+~x)%x

# (a*X + b) % X = b implies that (a*X + b) // X = a

class Solution:
    def fib(self, n: int) -> int:
        return pow(x:=2<<n,n,x*x+~x)//x
class Solution:
    def climbStairs(self, n: int) -> int:
        a=b=1
        for _ in range(n):
            a,b = b,a+b
        return a

class Solution:
    def climbStairs(self, n):
        return pow(x:=2<<n,n+2,x*x+~x)%x
class Solution:
    def tribonacci(self, n):
        a,b,c = 1,0,0
        for _ in range(n):
            a,b,c = b,c,a+b+c
        return c

# https://mathworld.wolfram.com/TribonacciNumber.html

class Solution:
    def tribonacci(self, n: int) -> int:
        return round((599510/325947)**n*39065/116186)

class Solution:
    def tribonacci(self, n: int) -> int:
        return pow(x:=2<<n,n+2,~-x*x*x+~x)%x

阶乘

Leetcode 仅有一个全局的 math 导入，其中包含 factorial()。如果你愿意，可以使用 lambda。

f=lambda x:x<2or x*f(x-1)
prod(range(1,x+1))
factorial(x)

正则表达式

许多问题可以用单个正则表达式解决：

class Solution:
    def sortVowels(self, s: str) -> str:
        return re.sub(t:='(?i)[aeiou]',lambda m,v=sorted(findall(t,s)):heappop(v),s)
class Solution:
    def isValid(self, w: str) -> bool:
        return match('^(?=.*[aeiou])(?=.*[^0-9aeiou])[a-z0-9]{3,}$',w,I)
class Solution:
    def makeGood(self, s: str) -> str:
        [s:=re.sub(r'(.)(?!\1)(?i:\1)','',s)for _ in s];return s
class Solution:
    def clearDigits(self, s: str) -> str:
        [s:=re.sub('\D\d','',s)for _ in s];return s
class Solution:
    def isCircularSentence(self, s: str) -> bool:
        return not re.search('(.) (?!\\1)',s+' '+s)

Accumulate

itertools.accumulate 有许多用途，请记住它支持除默认 "sum" 之外的任何函数。

class Solution():
    def stalinSort(self, a: List[int]) -> List[int]:
        return [x for i,x in enumerate(a)if x>=max(a[:i+1])]

class Solution():
    def stalinSort(self, a: List[int]) -> List[int]:
        return compress(a,map(ge,a,accumulate(a,max)))

Kadane

对于 Kadane 类问题，你需要维护几个计数器。你可以直接在推导式中使用 max。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur_max, max_till_now = 0, -inf
        for c in nums:
            cur_max = max(c, cur_max + c)
            max_till_now = max(max_till_now, cur_max)
        return max_till_now

class Solution:
    def maxSubArray(self, n: List[int]) -> int:
        return max(accumulate(n,lambda c,x:max(c+x,x)))

class Solution:
    def maxSubArray(self, n: List[int]) -> int:
        c=0;return max(c:=max(c+x,x)for x in n)

如果存在更多计数器，您可以使用海象运算符将中间计数器与目标计数器的计算合并。


class Solution:
    def maxAscendingSum(self, n: List[int]) -> int:
        p=c=0;return max((c:=x+c*(x>p),p:=x)[0]for x in n)

class Solution:
    def maxAscendingSum(self, n: List[int]) -> int:
        p=c=0;return max(c:=x+c*(x>p)+0*(p:=x)for x in n)

class Solution:
    def maxAscendingSum(self, n: List[int]) -> int:
        p=c=0;return max(c:=x+c*(p<(p:=x))for x in n)

星号运算符

你可以使用星号运算符 * 来节省几个字符。 一个 * 表示“将此展开为列表”，两个 ** 表示“将此展开为字典”。 注意，使用 ** 时只能展开字典，例如 {'a':1, **dict}。

class Solution:
    def checkStraightLine(self, p):
        (a,b),(c,d)=p[:2];return all((x-a)*(d-b)==(c-a)*(y-b)for x,y in p)

class Solution:
    def checkStraightLine(self, p):
        (a,b),(c,d),*_=p;return all((x-a)*(d-b)==(c-a)*(y-b)for x,y in p)

将可迭代对象转换为列表有一种简洁的方法，例如 x=[*g] 等于 *x,=g（少 1 个字符）。或者展开列表：

class Solution:
    def findMaxAverage(self, n: List[int], k: int) -> float:
        s=[0]+[*accumulate(n)];return max(map(sub,s[k:],s))/k

class Solution:
    def findMaxAverage(self, n: List[int], k: int) -> float:
        s=[0,*accumulate(n)];return max(map(sub,s[k:],s))/k

您还可以使用此语法来解包可迭代对象，例如 a,*b,c=range(5) 表示 a=1;b=[2,3,4];c=5。

class Solution:
    def waysToSplitArray(self, a: list[int]) -> int:
        return sum(map((sum(a)/2).__le__,accumulate(a[:-1])))

class Solution:
    def waysToSplitArray(self, a: list[int]) -> int:
        *p,s=accumulate(a);return sum(map((s/2).__le__,p))

旋转

数组旋转问题发表于《编程珠玑》（1983 年 9 月刊第 624-625 页](https://dl.acm.org/doi/pdf/10.1145/358172.358176)）。

这个问题看起来一直很难，直到你终于想出正确的顿悟。让我们将其视为将数组 AB 转换为数组 BA，但让我们也假设我们有一个子程序，可以反转数组中指定部分的元素。

将字符串 "ABCDEFGH" 向左旋转 i=3 个字符（n 为字符串长度，索引从 1 开始）：

reverse(1, i)    /* CBADEFGH */
reverse(i+1, n)  /* CBAHGFED */
reverse(1, n)    /* DEFGHABC */

这种将十元素数组向上旋转五个位置（图 1）的实现来自 Doug Mcllroy；请尝试一下。 反转代码在时间和空间上都很高效，并且如此简短和简单，以至于很难出错。

这正是 Kernighan 和 Plauger 在其书中文本编辑器中使用的代码。Brian Kernighan 报告说，这段代码在首次执行时确实正确运行，而他们之前用于类似任务的代码包含几个 bug。 这段代码也用于几个文本编辑器，包括 UNIX 编辑器 ed。

# rotate array AKA Doug Mcllroy, Programming Pearls
# reverse parts at split point then reverse whole array
# you can do it in a reverse order to change direction
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i+1, j-1
        n = len(nums)
        k = k % n
        reverse(0, n-1)
        reverse(0, k-1)
        reverse(k, n-1)
        return nums

但这相当次优。反转三次是最简单的方法，但每个元素恰好移动两次，时间复杂度为 O(N)，空间复杂度为 O(1) 也可以以 O(N) 时间和 O(1) 空间对数组进行循环移位，使每个元素恰好移动一次 (https://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position).

# GCD solution, true O(n)
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        shift = n - (k % n)
        for i in range(gcd(n, shift)):
            j = i
            while (k := (j + shift) % n) != i:
                nums[j],nums[k] = nums[k],nums[j]
                j = k

其他方式：

# using built-in reverse function
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k = k % len(nums)
        nums[:k] = reversed(nums[:k])
        nums[k:] = reversed(nums[k:])
        nums.reverse()

# not inplace
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        [nums.insert(0,nums.pop()) for _ in range(k)]

# deque built-in rotate method
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        nums[:]=(q:=deque(nums)).rotate(k) or q

# minified
class Solution:
    def rotate(self, a: List[int], k: int) -> None:
        k%=len(a);a[:]=a[-k:]+a[:-k]

这里还有需要判断字符串是否被旋转的问题。技巧是在字符串与其副本拼接后的字符串中进行搜索。

如果 s 由重复的部分组成，那么在某一点它应该等于其自身的旋转版本。 检查 s 是否为 (s+s)[1:-1] 的子串，基本上就完成了检查 s 的所有旋转版本（除了 s+s 本身）的全部工作， 只需一次操作（通常由 SIMD 加速）。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s+s)[1:-1]
class Solution:
    def check(self, a: List[int]) -> bool:
        return sum(map(gt,a,a[1:]+a))<2

Itemgetter

请注意，key=itemgetter(n) 与 key=lambda x:x[n] 长度相同，但可读性略好。 itemgetter 的性能也优于 lambda（最高可达 2 倍，因为涉及 lambda 的创建）。

有时，您可以通过将参数转换为元组来在比较操作中省略 key=itemgetter(0)（短 15 个字符）。


class Solution:
    def jobScheduling(self, s: List[int], e: List[int], p: List[int]) -> int:
        a=sorted(zip(s,e,p));return(f:=cache(lambda i:i-len(a)and max(f(
            bisect_left(a,a[i][1],key=itemgetter(0)))+a[i][2],f(i+1))))(0)

class Solution:
    def jobScheduling(self, s: List[int], e: List[int], p: List[int]) -> int:
        a=sorted(zip(s,e,p));return(f:=cache(lambda i:i-len(a)and max(f(
            bisect_left(a,(a[i][1],)))+a[i][2],f(i+1))))(0)

Pop

你也可以使用 map(list.pop, v) 代替 [x[-1] for x in v] 来收集列表的最后一个元素。

class Solution:
    def findDiagonalOrder(self, n: List[List[int]]) -> List[int]:
        return map(list.pop,sorted([i+j,j,t]for i,r in enumerate(n)for j,t in enumerate(r)))

Zip

使用 zip 从元组列表中获取元素通常更简短，但并非总是如此：

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        return {*range(n)}-{*[*zip(*edges)][1]}

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        return {*range(n)}-{j for _,j in edges}

比较链

Python 支持比较链。你可以在单个条件中使用诸如 0<=i<n、m>j>=0<=i<n、m>j>-1<i<n 和 a!=b!=c 这样的表达式。

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        def f(v,w,j=0):
            for i in range(len(v)):
                if j<len(w) and v[i]==w[j]:
                    j += 1
                elif v[i-1:i+2] != v[i]*3 != v[i-2:i+1]:
                    return False
            return j==len(w)
        return sum(f(s,w) for w in words)

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        return sum((f:=lambda v,w,j=0:next((0 for i in range(len(v)) if not(j<len(w) and v[i]==w[j]
            and (j:=j+1))and v[i-1:i+2]!=v[i]*3!=v[i-2:i+1]),1) and j==len(w))(s,w) for w in words)

Python 按照 and 运算符的顺序处理多参数比较，因此你可以使用更简短的形式：

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n>0 and log(n,4)%1==0

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n>0==log(n,4)%1

你可以检查是否有任何数字为负数，如 x|y<0，或者两个数字是否都非零，如 x|y。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        return (f:=cache(lambda i,j:i|j<0 and inf or grid[i][j]+(i|j and min(f(i,j-1),f(i-1,j)))))
            (len(grid)-1,len(grid[0])-1)

在可能的情况下，你可以使用位运算 &,| 代替 and,or。如果 0<=x<=2，你可以使用 x&1 代替 x==1。


class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        return (f:=cache(lambda a,b:a==b or any((f(a[:i],b[:i]) and f(a[i:],b[i:]))
            or (f(a[i:],b[:-i]) and f(a[:i],b[-i:])) for i in range(1,len(a)))))(s1,s2)

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        return (f:=cache(lambda a,b:a==b or any((f(a[:i],b[:i])&f(a[i:],b[i:]))
            |(f(a[i:],b[:-i])&f(a[:i],b[-i:])) for i in range(1,len(a)))))(s1,s2)

按位取反

~ 会反转每一位。因此，~x 表示 -x-1。你可以将其用作反向索引，即对于 i=0，a[~i] 表示 a[-1]，等等，或者直接用 ~x 替换 -x-1。

对于整数 n，你可以将 n+1 写为 -~n，将 n-1 写为 ~-n。这使用了相同数量的字符，但可以通过间接方式减少空格或用于运算符优先级的括号。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        r=range(n);return[[4*(n-(a:=min(min(i,n-i-1),min(j,n-j-1))))
            *a+(i+j-2*a+1,4*(n-2*a-1)-(i+j-2*a)+1)[i>j] for j in r] for i in r]

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        r=range(n);return[[4*(n-(a:=min(i,j,~i+n,~j+n)))
            *a+(i+j-2*a+1,4*n-6*a-i-j-3)[i>j]for j in r]for i in r]

If-Else

你可以用 x-y and z 替换 0 if x==y else z，这有点反直觉，但更短。

条件 x if c else y 可以写成 c and x or y，它更短但依赖于 x（x 不应为 0）。

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n,v,q = len(board),{1:0},[1]
        def f(i):
            x = (i - 1)%n
            y = (i - 1)//n
            c = board[~y][~x if y%2 else x]
            return c if c>0 else i
        for i in q:
            for j in range(i+1, i+7):
                k = f(j)
                if k==n*n:
                    return v[i]+1
                if k not in v:
                    v[k] = v[i]+1
                    q.append(k)
        return -1

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        return (n:=len(board),v:={1:0},q:=[1]) and next((v[i]+1 for i in q for j in range(i+1,i+7)
            if (k:=(x:=(j-1)%n,y:=(j-1)//n) and ((c:=board[~y][y%2 and ~x or x])>0 and c or j))==n*n
            or (k not in v and (v.update({k:v[i]+1}) or q.append(k)))),-1)

Boolean

你可以将布尔值用作列表的索引，即使是嵌套的：(a,(b,c)[u==w])[x==y]，或者你可以将布尔值相乘。

class Solution:
    def removeStars(self, s: str) -> str:
        return reduce(lambda r,c:(r[:-1],r+c)[c>'*'],s)
class Solution:
  def simplifyPath(self, path: str) -> str:
    return'/'+'/'.join(reduce(lambda r,p:(r+[p]*('.'!=p!=''),r[:-1])[p=='..'],path.split('/'),[]))

有时你可以使用 any() 代替 bool()（少 1 个字符）：

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        return bool({*s}&{*'aeiou'})

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        return any({*s}&{*'aeiou'})

Cmp

Python 3 缺少 cmp（三路比较）和符号函数（copysign(bool(x),x) 太长了），但你可以使用 (x>0)-(x<0) 来实现 sign(x) 以及使用 (a>b)-(a<b) 来实现 cmp(a,b)。注意，你可以原生地使用 -1,0,1 索引来访问 Python 列表。

class Solution:
    def stoneGameIII(self, v: List[int]) -> str:
        f=cache(lambda i:i<len(v)and max(sum(v[i:i+k])-f(i+k)for k in(1,2,3)));x=f(0);
        return('Tie','Alice','Bob')[(x>0)-(x<0)]
        # return(('Tie','Bob')[x<0],'Alice')[x>0] # or like this (1 char shorter)

你可以将写作 lambda x:(x>0)-(x<0) 的 cmp 替换为 0..__le__ 或 .0.__le__（短 11 个字符）。

class Solution:
    def rearrangeArray(self, n: List[int]) -> List[int]:
        n.sort(key=lambda x:(x>0)-(x<0));return chain(*zip(n[len(n)//2:],n))

class Solution:
    def rearrangeArray(self, n: List[int]) -> List[int]:
        n.sort(key=0..__le__);return chain(*zip(n[len(n)//2:],n))

您可以将 x>0 谓词替换为 0..__lt___ 函数，并将 x!=0 替换为 operator.truth 或仅使用 bool：

class Solution:
    def mergeNodes(self, h: Optional[ListNode]) -> Optional[ListNode]:
        return h.deserialize(str([sum(v)for k,v in groupby(eval(h.serialize(h)),bool)if k]))

Cmp 作为排序键可以进一步简化为一个元组 (x>p,x==p)。

class Solution:
    def pivotArray(self, a: List[int], p: int) -> List[int]:
        return sorted(a,key=lambda x:(x>p,x==p))

众数

使用 statistics.mode（离散或名义数据的最常见值）时，许多内容都会变得更简短。

class Solution:
    def findMissingAndRepeatedValues(self, g: List[List[int]]) -> List[int]:
        return sum(a:=sum(g,[]))-sum({*a}),(n:=len(a))*(n+1)//2-sum({*a})

class Solution:
    def findMissingAndRepeatedValues(self, g: List[List[int]]) -> List[int]:
        return mode(a:=sum(g,[])),comb(len(a)+1,2)-sum({*a})
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        t=sum({*nums});return sum(nums)-t,comb(len(nums)+1,2)-t

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        return mode(nums),comb(len(nums)+1,2)-sum({*nums})
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return mode(nums)
# https://youtu.be/pKO9UjSeLew (Joma Tech: If Programming Was An Anime)
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]
        return hare

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        return mode(nums)

在大多数情况下，mode() 可以替代（底层的）Counter.most_common() 函数：


class Solution:
    def repeatedNTimes(self, a: List[int]) -> int:
        return Counter(a).most_common(1)[0][0]

class Solution:
    def repeatedNTimes(self, a: List[int]) -> int:
        return mode(a)

Encode

你可以使用 s.encode() 代替 ord 或 map(ord,s)。它的长度相同，但无需生成评估。

class Solution:
    def scoreOfString(self, s: str) -> int:
        return sum(abs(x-y)for x,y in pairwise(map(ord,s)))

class Solution:
    def scoreOfString(self, s: str) -> int:
        return sum(map(abs,map(sub,s:=s.encode(),s[1:])))

计数

你可以使用 count() 来替换 enumerate 表达式中的 map（短 4-7 个字符）：

class Solution:
    def maximumImportance(self, n: int, r: List[List[int]]) -> int:
        return sum(v*(n-i)for i,(_,v)in enumerate(Counter(chain(*r)).most_common()))

class Solution:
    def maximumImportance(self, n: int, r: List[List[int]]) -> int:
        return-sum(map(mul,count(-n),sorted(Counter(chain(*r)).values())[::-1]))

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, h: List[int], v: List[int]) -> int:
        return min(1+max(Counter(starmap(sub,enumerate(sorted(w)))).values())for w in(h,v))**2

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, h: List[int], v: List[int]) -> int:
        return min(1+max(Counter(map(sub,sorted(w),count())).values())for w in(h,v))**2

Starmap

Starmap 创建一个迭代器，该迭代器使用从可迭代对象中获取的参数来计算函数。 当参数已经“预压缩”为元组时，使用它代替 map()（参见 itertools.starmap）。

使用 starmap 和 pairwise 将函数应用于可迭代对象，可以通过 map 完成（短 12 个字符）：

class Solution:
    def findArray(self, p: List[int]) -> List[int]:
        return starmap(xor,pairwise([0]+p))

class Solution:
    def findArray(self, p: List[int]) -> List[int]:
        return map(xor,p,[0]+p)

很多时候，你可以用 map 替换 zip，它以相同的方式求值可迭代对象：

class Solution:
    def minMovesToSeat(self, s: List[int], t: List[int]) -> int:
        return sum(abs(a-b)for a,b in zip(*map(sorted,(s,t))))

class Solution:
    def minMovesToSeat(self, s: List[int], t: List[int]) -> int:
        return sum(map(abs,map(sub,*map(sorted,(s,t)))))

你也可以将 starmap 和 enumerate 替换为 map 和 count()（短 7 个字符）。

class Solution:
    def countBadPairs(self, a: List[int]) -> int:
        return sum(x*(len(a)-x)for x in Counter(starmap(sub,enumerate(a))).values())//2

class Solution:
    def countBadPairs(self, a: List[int]) -> int:
        return sum(x*(len(a)-x)for x in Counter(map(sub,a,count())).values())//2

Comb

你可以将组合函数（二项式）n*(n-1)//2 写为 comb(n,2)，或者用 ~-n 替换 (n-1) 以省略括号。

class Solution:
    def tupleSameProduct(self, a) -> int:
        return sum(8*comb(n,2)for n in Counter(starmap(mul,combinations(a,2))).values())

class Solution:
    def tupleSameProduct(self, a) -> int:
        return sum(4*n*(n-1)for n in Counter(starmap(mul,combinations(a,2))).values())

class Solution:
    def tupleSameProduct(self, a) -> int:
        return sum(~-n*n*4for n in Counter(starmap(mul,combinations(a,2))).values())

Numpy

你可以使用 numpy.convolve 进行滑动窗口操作，它通常比 reduce 或列表推导式更简洁：

class Solution:
    def maxSatisfied(self, c: List[int], g: List[int], m: int) -> int:
        t,a=0,[*map(mul,c,g)];[t:=(t,w:=sum(a[i:i+m]))[w>t]for i in range(len(c)-m+1)]
        return t+sum(c)-sum(a)

class Solution:
    def maxSatisfied(self, c: List[int], g: List[int], m: int) -> int:
        return max(__import__('numpy').convolve(a:=[*map(mul,c,g)],[1]*m))+sum(c)-sum(a)

Ceil

你可以将 ceil(x/k) 替换为 -(-x//k)（短 1 个字符）：

class Solution:
    def maxKelements(self, a: List[int], k: int) -> int:
        a.sort();return sum((x:=a.pop(),insort(a,ceil(x/3)))[0]for _ in range(k))

class Solution:
    def maxKelements(self, a: List[int], k: int) -> int:
        a.sort();return sum((x:=a.pop(),insort(a,-(-x//3)))[0]for _ in range(k))

Prod

在 Python 中，prod() 函数（在 math 模块中可用，从 Python 3.8 开始）用于计算可迭代对象中所有元素的乘积。 不幸的是，你无法使用带步长的单个切片来表示索引 0、1、-1。

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        return max((v:=sorted(nums))[-1]*v[-2]*v[-3], v[0]*v[1]*v[-1])

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        return max(prod((v:=sorted(nums))[-3:]), v[0]*v[1]*v[-1])

Join

''.join(map(str,a)) 可以用格式字符串乘法和解包 '%d'*len(a)%(*a,) 替代（少 2 个字符）：

class Solution:
    def numMagicSquaresInside(self, g: List[List[int]]) -> int:
        return sum(r[j+1]==5>q[j]%2+4!="".join(map(str,q[j:j+3]+[r[j+2],*s[j:j+3][::-1],r[j]]))in
        (t:='43816729'*2)+t[::-1]for q,r,s in zip(g,g[1:],g[2:])for j in range(len(q)-2))

class Solution:
    def numMagicSquaresInside(self, g: List[List[int]]) -> int:
        return sum(r[j+1]==5>q[j]%2+4!='%d'*8%(*q[j:j+3],r[j+2],*s[j:j+3][::-1],r[j])in
        (t:='43816729'*2)+t[::-1]for q,r,s in zip(g,g[1:],g[2:])for j in range(len(q)-2))

class Solution:
    def plusOne(self, d: List[int]) -> List[int]:
        return[*map(int,str(int(''.join(map(str,d)))+1))]

class Solution:
    def plusOne(self, d: List[int]) -> List[int]:
        return[*map(int,str(int('%d'*len(d)%(*d,))+1))]

表格

运算符

这些运算符在全局命名空间中可用（Leetcode 默认包含 "operator" 模块）。

运算语法功能
一元
取反（算术）- aneg(a)
取反（逻辑）not anot_(a)
正号+ apos(a)
真值测试objtruth(obj)
按位取反~ ainvert(a)
二元
加法a + badd(a, b)
连接seq1 + seq2concat(seq1, seq2)
包含测试obj in seqcontains(seq, obj)
除法a / btruediv(a, b)
除法a // bfloordiv(a, b)
按位与a & band_(a, b)
按位异或a ^ bxor(a, b)
按位或a | bor_(a, b)
幂运算a ** bpow(a, b)
恒等a is bis_(a, b)
恒等a is not bis_not(a, b)
索引删除del obj[k]delitem(obj, k)
索引obj[k]getitem(obj, k)
左移a << blshift(a, b)
取模a % bmod(a, b)
乘法a * bmul(a, b)
矩阵乘法a @ bmatmul(a, b)
右移a >> brshift(a, b)
字符串格式化s % objmod(s, obj)
减法a - b