Shortest-LeetCode-Python-Solutions

Leet Code 刷题笔记 - - 不求最快最省，但求最短最优雅，Shorter is better here.

Last updated Mar 14, 2026

1.1k

Stars

197

Forks

Issues

Stars/day

Attention Score

View on GitHub ↗ Open in github.dev

Topics

#elegant #leetcode #leetcode-python #leetcode-solutions #python #python3 #shortest

Language breakdown

No language data available.

▸ Files click to expand

README

:snake: Shortest-LeetCode-Python-Solutions

Leet Code 刷题笔记 - - 不求最快最省，但求最短最优雅 :herb:，Shorter is better here.

前言

项目持续更新中，优先使用 python3，不支持的题目使用 python2 代替，如果您有更短更优雅的解法希望分享的话欢迎联系更新~ [直接发issue 或 fork，记得留下署名和联系方式 :panda_face:] 鉴于追求的主题，此项目收录 1.在代码量(不是行数)上明显优于现有解的最短代码 2.思路更高效的一般解法（作为补充放在首选解之后） [题目自带的代码不计入代码量]
如果您对当前解析有任何疑问，咱们 issue 见~
由于CSDN博客更新需要人工审核比较慢，所以迁移到github上，优先更新github内容。
为了快速找到题目可以按 [Ctrl键 + F键] 输入题目序号或名字定位。
欢迎加入QQ交流群：902025048 ∷二维码群内提供更多相关资料~

:trophy: 里程碑

:penguin: 腾讯精选练习（50题: 25简单 21中等 4困难）代码行数总计：140行平均：2.8行 :bookmark_tabs: 题目详情 :calendar: 2019/05/05
🧬 数据结构

- 🐤 队列 & 栈（5 章节 32 栏目）高可读，不含VIP解锁题 :bookmarktabs: 题目详情 :calendar: 2019/05/31 - 🐑 数组和字符串（5 章节 29 栏目）高可读 :bookmarktabs: 题目详情 :calendar: 2019/06/15 - 🦌 链表（5 章节 26 栏目）高可读 :bookmarktabs: 题目详情 :calendar: 2019/06/25 - 🦎 哈希表（5 章节 35 栏目）高可读，不含VIP解锁题 :bookmarktabs: 题目详情 :calendar: 2019/07/07 - 🐄 二分查找（8 章节 30 栏目）高可读，不含VIP解锁题 :bookmarktabs: 题目详情 :calendar: 2019/07/30 - 🦉 二叉树（3 章节 16 栏目）高可读 :bookmarktabs: 题目详情 :calendar: 2019/09/21 - 🐦 二叉搜索树（3 章节 16 栏目）高可读 :bookmarktabs: 题目详情 :calendar: 2019/11/15 - 🐈 N叉树（3 章节 7 栏目）高可读，不含VIP解锁题 :bookmarktabs: 题目详情 :calendar: 2019/11/17

⏱ 递归 I（5 章节 28 栏目）高可读 :bookmarktabs: 题目详情 :calendar: 2019/11/28

题库解析

此专栏追求代码的精简和技巧性，默认已看过题目，🤡 没看过的话点标题可以跳转链接，咱们一起体验炫酷的 Python

点击展开折叠

2. Add Two Numbers 5行

# Definition for singly-linked list. class ListNode:
     def init(self, x):
         self.val = x
         self.next = None

class Solution:     def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:         if not (l1 or l2): return ListNode(1) if carry else None         l1, l2 = l1 or ListNode(0), l2 or ListNode(0)         val = l1.val + l2.val + carry         l1.val, l1.next = val % 10, self.addTwoNumbers(l1.next, l2.next, val > 9)         return l1

int(True) 等于 1
None or 7 等于 7
用 carry 记录是否应该进位

3. Longest Substring Without Repeating Characters 3行

class Solution:     def lengthOfLongestSubstring(self, s: str) -> int:         i, r, d = 0, 0, {}         for j, c in enumerate(s): i, r, d[c] = max(i, d.get(c, -1) + 1), max(r, j - i), j         return max(r, len(s) - i)

双指针滑动窗口
i 代表起始位置，r 记录最优解，d 是一个字典，记录所有字符最后出现的位置
每次迭代过程中，遇到遇见过的字符时，i 就会变为那个字符上一次出现位置 + 1，r 记录上一次应该达到的全局最大值，所以最后需要再比较一次

4. Median of Two Sorted Arrays 5行

class Solution:     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:         a, b, m = *sorted((nums1, nums2), key=len), (len(nums1) + len(nums2) - 1) // 2         self.class.getitem = lambda self, i: m-i-1 < 0 or a[i] >= b[m-i-1]         i = bisect.bisect_left(self, True, 0, len(a))         r = sorted(a[i:i+2] + b[m-i:m-i+2])         return (r[0] + r[1 - (len(a) + len(b)) % 2]) / 2

本题思路与官方题解类似，时间复杂度O(log(min(m, n)))，没看过的话建议先大体了解一下
python 中 bisect 模块针对的是 list, 如果直接构造 list，时间复杂度为 O(min(m, n))，因此我们修改当前类的魔法方法伪造 list
在一个有序递增数列中，中位数左边的那部分的最大值一定小于或等于右边部分的最小值
如果总数组长度为奇数，m 代表中位数的索引，否则 m 代表用于计算中位数的那两个数字的左边一个。比如输入为[1,2]，[3]，那么m应该为[1,2,3]中位数2的索引1，如果输入为[1,3]，[2,4]，那么m应该为[1,2,3,4]中2的索引1
使用二分搜索找到 m 对应的值在a或b中对应的索引，也就是说，我们要找的中位数或中位数左部应该是 a[i] 或者 b[m-i]
bisect.bisect_left 搜索列表中保持列表升序的情况下，True应该插入的位置（从左侧），比如 [F,F,T] 返回 2，[F,F] 返回 2
这里保证 a 是 nums1 和 nums2 中较短的那个，是为了防止二分搜索的时候索引越界
sorted返回一个list，假设返回值是 [nums1, nums2]，那么前面加个 * 号就代表取出列表的所有内容，相当于一个迭代器，结果相当于直接写 nums1, nums2

5. Longest Palindromic Substring 5行

class Solution:     def longestPalindrome(self, s: str) -> str:         r = ''         for i, j in [(i, j) for i in range(len(s)) for j in (0, 1)]:             while i > -1 and i + j < len(s) and s[i] == s[i + j]: i, j = i - 1, j + 2             r = max(r, s[i + 1:i + j], key=len)         return '' if not s else r

遍历字符串的每个索引 i，判断能否以 s[i] 或 s[i:i+j+1] 为中心向往拓展回文字符串

7. Reverse Integer 2行

class Solution:
    def reverse(self, x):
        r = x // max(1, abs(x)) * int(str(abs(x))[::-1])
        return r if r.bit_length() < 32 or r == -2**31 else 0

x // max(1, abs(x))意味着 0：x为0， 1：x为正， -1：x为负，相当于被废弃的函数cmp
[::-1]代表序列反转
2^31 和 -2^31 的比特数为32，其中正负号占用了一位
32位整数范围 [−2^31, 2^31 − 1] 中正数范围小一个是因为0的存在

8. String to Integer (atoi) 1行

class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 231 - 1), -231)

使用正则表达式 ^：匹配字符串开头，[\+\-]：代表一个+字符或-字符，?：前面一个字符可有可无，\d：一个数字，+：前面一个字符的一个或多个，\D：一个非数字字符
max(min(数字, 231 - 1), -231) 用来防止结果越界

9. Palindrome Number 1行

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return (k:=str(x)) == k[::-1]

不使用字符串的进阶解法：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        r = list(map(lambda i: int(10*-i  x % 10), range(int(math.log10(x)), -1, -1))) if x > 0 else [0, x]
        return r == r[::-1]

思路是一样的，这里把整数转成了列表而不是字符串
比如一个整数12321，我想取出百位数可以这么做：12321 * 10^{int(log_{10}12321)} % 10 = 123 % 10 = 3

11. Container With Most Water 3行

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res, l, r = 0, 0, len(height) - 1
        while l < r: res, l, r = (max(res,  height[l]  (r - l)), l + 1, r) if height[l] < height[r] else (max(res,  height[r]  (r - l)), l, r - 1)
        return res

双指针 O(N) 解法
res：结果，l：容器左壁索引，r：容器右壁索引
如果 height[l] < height[r] 那么 l += 1 否则 r -= 1，说明：如果 height[0] < height[3] 那么(0, 1), (0, 2)对应的容器体积一定小于(0, 3)的，因为此时计算体积的时候高为 height(0)，容器的宽减少而高不增加，面积必然缩小

13. Roman to Integer 2行

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
        return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))

构建一个字典记录所有罗马数字子串，注意长度为2的子串记录的值是（实际值-子串内左边罗马数字代表的数值）
这样一来，遍历整个s的时候判断当前位置和前一个位置的两个字符组成的字符串是否在字典内，如果在就记录值，不在就说明当前位置不存在小数字在前面的情况，直接记录当前位置字符对应值
举个例子，遍历经过IV的时候先记录I的对应值1再往前移动一步记录IV的值3，加起来正好是IV的真实值4。max函数在这里是为了防止遍历第一个字符的时候出现[-1:0]的情况

14. Longest Common Prefix 2行

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        r = [len(set(c)) == 1 for c in zip(*strs)] + [0]
        return strs[0][:r.index(0)] if strs else ''

利用好zip和set
os 模块有提供一样的函数

class Solution:
	    def longestCommonPrefix(self, strs: List[str]) -> str:
		return os.path.commonprefix(strs)

15. 3Sum 5行

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums, r = sorted(nums), set()
        for i in [i for i in range(len(nums)-2) if i < 1 or nums[i] > nums[i-1]]:
            d = {-nums[i]-n: j for j, n in enumerate(nums[i + 1:])}
            r.update([(nums[i], n, -nums[i]-n) for j, n in enumerate(nums[i+1:]) if n in d and d[n] > j])
        return list(map(list, r))

时间复杂度：O(N^2)
这里 sort 一是为了避免重复，这一点可以体现在我们输出的结果都是升序的，如果不这么做 set 无法排除一些相同结果，而是为了节省计算，防止超时
for 循环内部的代码思想同 第一题 Two Sum，用字典记录｛需要的值:当前索引｝，如果字典中存在相同的数字，那么将会记录比较大的那个索引，因此可以用d[n] > i来避免一个元素重复选择
(nums[i], n, -nums[i]-n)保证了列表升序

16. 3Sum Closest 7行

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums, r, end = sorted(nums), float('inf'), len(nums) - 1
        for c in range(len(nums) - 2):
            i, j = max(c + 1, bisect.bisect_left(nums, target - nums[end] - nums[c], c + 1, end) - 1), end
            while r != target and i < j:
                s = nums[c] + nums[i] + nums[j]
                r, i, j = min(r, s, key=lambda x: abs(x - target)), i + (s < target), j - (s > target)
        return r

float('inf') = 正无穷
排序，遍历，双指针，O(N^2) 时间复杂度，二分法初始化
排序是为了使用双指针，首先遍历得到索引 c，然后计算 c，左指针 i，右指针 j 对应数字之和，如果大于 target，j 向内移动，否则 i 向内移动
i 的初始值不是 c + 1，是为了减少计算量，用二分法得到一个合理的初始值

17. Letter Combinations of a Phone Number 3行

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        from itertools import product
        l = '- - abc def ghi jkl mno pqrs tuv wxyz'.split()
        return [''.join(c) for c in product(*[l[int(i)] for i in digits])] if digits else []

本题相当于求解笛卡尔积

18. 4Sum 5行

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        from itertools import combinations as com
        dic, l = collections.defaultdict(list), [*com(range(len(nums)), 2)]
        for a, b in l: dic[target - nums[a] - nums[b]].append((a, b))
        r = [(*ab, c, d) for c, d in l for ab in dic[nums[c] + nums[d]]]
        return [*set(tuple(sorted(nums[i] for i in t)) for t in r if len(set(t)) == 4)]

思想类似于 2SUM，先得到任意两个数字的和记入字典，然后再获得其余任意俩个数字，看看是否匹配。2个 2SUM 相当于 4SUM。时间复杂度为 O(N^2)
1.用 combination 获得 nums 中任意两个不同索引的组合
2.用字典记录任意两个数字的和，dic =｛除了这两个数字之外还差多少：这俩个数字在 nums 中的索引｝
3.用 r 记录所有满足条件的索引序列，注意此时可能含有重复的索引
4.利用 len + set 保证 a，b，c，d 各不相等，用 set 删除重复的结果

19. Remove Nth Node From End of List 5行

# Definition for singly-linked list.
class ListNode:
    def init(self, x):
        self.val = x
        self.next = None
class Solution:     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:         l = []         while head: l, head = l + [head], head.next         if n != len(l): l[-n-1].next = l[-n].next         del l[-n]         return l and l[0]

列表记录整个链表，换成队列记录最后几个可以把空间复杂度压到 O(1)

20. Valid Parentheses 2行

class Solution:
    def isValid(self, s: str) -> bool:
        while any(('()' in s, '[]' in s, '{}' in s)): s = s.replace('()', '').replace('[]', '').replace('{}', '')
        return not s
	
国际站上有一种写法是这样的，相比于上面，下面的写法更加优雅（好理解）一点
class Solution:
    def isValid(self, s: str) -> bool:
        while s:
            l = len(s)
            s = s.replace('()', '').replace('[]', '').replace('{}', '')
            if l == len(s):  break
        return not s

不断删除有效括号直到不能删除，思路简单效率低。另外，stack的方法也很简单，而且快多了。

class Solution:
	    def isValid(self, s: str) -> bool:
	        stack, d = [], {'{': '}', '[': ']', '(': ')'}
	        for p in s:
	            if p in d:
	                stack += [p];
	            elif not (stack and d[stack.pop()] == p):
	                return False
	        return not stack

23. Merge k Sorted Lists 4行

# Definition for singly-linked list. class ListNode:
     def init(self, x):
         self.val = x
         self.next = None

class Solution:     def mergeKLists(self, lists: List[ListNode]) -> ListNode:         r, n, p = [], lists and lists.pop(), None         while lists or n: r[len(r):], n = ([n], n.next or lists and lists.pop()) if n else ([], lists.pop())         for n in sorted(r, key=lambda x: x.val, reverse=True): n.next, p = p, n         return n if r else []

本题思路：

1. 把题目给的所有链表中的所有节点放进一个列表 r。 2. 对这个列表 r 中的所有节点进行从大到小的排序。O(NlogN) 3. 把每个节点的指针指向前一个节点。（第一个节点，也就是最大的那个，指向None。） 4. 返回最后一个节点，也就是整个新链表的开头。

如何把所有节点放进 r(result link)？

我们首先初始化 r 为空列表，初始化 n(node) 为题目所给的第一个链表的开头节点，并删除lists中的这个节点，接着进入while循环，如果 n 不为空，那么 r += [n]，这里使用了切片的技巧（r[len(r):]=[n]相当于r=r+[n]），n=n.next，如果n是第一个链表的最后一个节点的话n.next就是None，下一次while的时候如果lists不为空就说明还有别的链表，此时n为None，我们让 r 不变，n=lists.pop()，也就是从lists中再取下一个节点赋值给n，重复以上步骤直到 lists 为空，我们就把所有节点放进 r 了。

怎么对 r 排序？

用了sorted函数，其中key定义了排序时用来比较的是每个元素的val属性，同时设置reverse为True代表降序排序。

如何修改每个节点的指针？

我们初始化 p(previous node) 为None。遍历降序排好的列表 r，r中的第一个元素就是值最大的元素，也就是我们应该返回的链表的结尾，我们设置它指向None，然后让p=这个节点，继续for循环。之后每经过一个节点 n 就把这个节点的next属性设置为上一个节点 p，遍历完成之后的 n，也就是我们遍历经过的最后一个元素，拥有最小的值，自然就是整个新链表的起始节点，我们将其作为输出值，函数返回。

24. Swap Nodes in Pairs 3行

# Definition for singly-linked list.
class ListNode:
    def init(self, x):
        self.val = x
        self.next = None
class Solution:     def swapPairs(self, head: ListNode) -> ListNode:         if head and head.next:             head.next.next, head.next, head = head, self.swapPairs(head.next.next), head.next         return head

每次递归交换两个节点，并返回新头参与上次递归
多值交换参考这里

26. Remove Duplicates from Sorted Array 3行

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        for i in range(len(nums)-1, 0, -1):
            if nums[i] == nums[i-1]: nums.pop(i)
        return len(nums)

时间效率O(N^2), pop操作的平均时间复杂度为O(N), 空间效率O(1)，逆遍历可以防止删除某个元素后影响下一步索引的定位
每次删除数组元素会引发大量的数据迁移操作，使用以下算法解题效率更高

class Solution:
	    def removeDuplicates(self, nums: List[int]) -> int:
		i = 0
		for j in range(1, len(nums)):
		    if nums[j] != nums[i]:
			nums[i + 1] = nums[j]
			i += 1
		return i + 1 if nums else 0

- 此解法思路同官方题解 - 数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。当我们遇到 nums[j] != nums[i]时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i + 1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止

28. Implement strStr() 1行

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
		return haystack.find(needle)

不用内置函数也可以

class Solution:
		def strStr(self, haystack: 'str', needle: 'str') -> 'int':
		    for i in range(0, len(haystack) - len(needle) + 1):
		        if haystack[i:i+len(needle)] == needle:
		            return i
	    	return -1

29. Divide Two Integers 5行

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        a, b, r, t = abs(dividend), abs(divisor), 0, 1
        while a >= b or t > 1:
            if a >= b: r += t; a -= b; t += t; b += b
            else: t >>= 1; b >>= 1
        return min((-r, r)[dividend ^ divisor >= 0], (1 << 31) - 1)

让被除数不断减去除数，直到不够减。每次减完后除数翻倍，并记录当前为初始除数的几倍（用 t 表示倍数 time），若发现不够减且 t 不为 1 则让除数变为原来的一半， t 也减半
a 为被除数绝对值，b 为除数绝对值，r 表示 result，t 表示当前除数对于原始除数的倍数
a << b 相当于 a * 2b，a >> b 相当于 a // 2b
异或操作 ^ 可以判断俩数字是否异号

33. Search in Rotated Sorted Array 3行

class Solution:
    def search(self, nums, target):
        self.class.getitem = lambda self, m: not(target < nums[0] <= nums[m] or nums[0] <= nums[m] < target or nums[m] < target <= nums[-1])
        i = bisect.bisect_left(self, True, 0, len(nums))
        return i if target in nums[i:i+1] else -1

作出数列的函数图像，可以看作是一个含断点的局部递增函数，形如:zap:，前面一段总是比较高
python 中 bisect 模块针对的是 list, 如果直接构造 list，相当于遍历所有元素，时间复杂度为 O(N) 而不是 O(logN)，因此我们修改当前类的魔法方法伪造 list，然后用当前类代替list
用二分搜索时，m 代表 middle，low 代表 low，hi 代表 high，当满足任一条件｛① targe < middle 且 middle 在前一段上且 target < nums[0] ② target > middle 且 middle 在第一段上 ③ target > middle 且 middle 在第二段上且 target <= nums[-1]｝时，应该向右搜索，因此 getitem 返回 False。
另外还有一种简单的思路：二分法找到断点的位置恢复原始数组，然后正常二分法即可

class Solution:
	    def search(self, nums, target):
		lo, hi, k = 0, len(nums) - 1, -1
		while lo <= hi:
		    m = (lo + hi) // 2
		    if m == len(nums) - 1 or nums[m] > nums[m+1]:
			k = m + 1
			break
		    elif m == 0 or nums[m] < nums[m-1]:
			k = m
			break
		    if nums[m] > nums[0]:
			lo = m + 1
		    else:
			hi = m - 1
		i = (bisect.bisect_left(nums[k:] + nums[:k], target) + k) % max(len(nums), 1)
		return i if nums and nums[i] == target else -1

34. 在排序数组中查找元素的第一个和最后一个位置

用自带的bisect函数，一行

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # if not nums or target not in nums:  return [-1, -1]
        return [bisect.bisectleft(nums, target), bisect.bisectright(nums, target)-1] \
            if nums and target in nums else [-1, -1]

35. Search Insert Position 1行

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target, 0, len(nums))

36. Valid Sudoku 4行

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[x for x in y if x != '.'] for y in board]
        col = [[x for x in y if x != '.'] for y in zip(*board)]
        pal = [[board[i+m][j+n] for m in range(3) for n in range(3) if board[i+m][j+n] != '.'] for i in (0, 3, 6) for j in (0, 3, 6)]
        return all(len(set(x)) == len(x) for x in (row, col, *pal))

利用 set 检查每个区块中是否有重复数字
pal 取区块的遍历方式是利用 i，j 遍历每个宫格左上角位置，然后取 3*3 区块

38. Count and Say 1行

class Solution:
    def countAndSay(self, n: int) -> str:
        return '1'  (n is 1) or re.sub(r'(.)\1', lambda m: str(len(m.group())) + m.group(1), self.countAndSay(n - 1))

正则表达式 re.sub(正则，替换字符串或函数，被替换字符串，是否区分大小写)
. 可匹配任意一个除了\n的字符

(.) 匹配任意一个除了\n的字符并把这个匹配结果放进第一组 (.)\1 匹配一个任意字符的二次重复并把那个字符放入数组 (.)\1* 匹配一个任意字符的多次重复并把那个字符放入数组

group(default=0)可以取匹配文本 group(1)取第一个括号内的文本

43. Multiply Strings 5行

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        d = {}
        for i, n1 in enumerate(num1[::-1]):
            for j, n2 in enumerate(num2[::-1]): d[i + j] = d.get(i + j, 0) + int(n1) * int(n2)
        for k in [d]: d[k + 1], d[k] = d.get(k + 1, 0) + int(d[k]  0.1), d[k] % 10
        return re.sub('^0*', '', ''.join(map(str, d.values()))[::-1]) or '0'

本题的难点在于计算整数的时候不能超过32bits，因此使用竖式计算
我们遍历num1中的每个数字n1，然后带着这个数字遍历num2中的每个数字n2做乘法，所得乘积放进 d 中相应的位置然后逐位计算结果
i + j 正好对应俩个数字相乘后所在的位置，比如 0 + 0 就应该是个位， 0 + 1 就是十位， 1 + 1 百位。这里所说的位置可以参考这篇博客中的过程图
若完全不想使用int()可以参考：

class Solution:
	    def multiply(self, num1: str, num2: str) -> str:
		d = {}
		for i, n1 in enumerate(num1[::-1]):
		    for j, n2 in enumerate(num2[::-1]):
			d[i + j] = d.get(i + j, 0) + (ord(n1) - 48) * (ord(n2) - 48)
		for k in [*d]:
		    d[k + 1], d[k] = d.get(k + 1, 0) + math.floor(d[k] * 0.1), d[k] % 10
		return re.sub('^0*', '', ''.join(map(str, d.values()))[::-1]) or '0'

46. Permutations 1行

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return [[n] + sub for i, n in enumerate(nums) for sub in self.permute(nums[:i] + nums[i+1:])] or [nums]

每次固定第一个数字递归地排列数组剩余部分
python 有内置函数可以直接实现

class Solution:
	    def permute(self, nums: List[int]) -> List[List[int]]:
		from itertools import permutations
		return list(permutations(nums))

48. rotate-image 1行

先转置后镜像对称

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = [i[::-1] for i in zip(*matrix)]

加 [:] 才会修改原列表

49. Group Anagrams 1行

class Solution:
    def groupAnagrams(self, strs):
        return [[*x] for _, x in itertools.groupby(sorted(strs, key=sorted), sorted)]

使用 groupby 函数依据 sorted 结果分组

50. Pow(x, n) 2行

class Solution:
    def myPow(self, x, n, r=1) -> float:
        x, n = n < 0 and 1 / x or x, abs(n)
        return self.myPow(x  x, n // 2, r  (not n % 2 or x)) if n else r

尾递归 O(logN) 解法
x^4 正常计算过程：x x x * x，O(N)
优化后：(x2)2，O(logN)

53. Maximum Subarray 2行

class Solution:
    def maxSubArray(self, nums):
        from functools import reduce
        return reduce(lambda r, x: (max(r[0], r[1]+x), max(r[1]+x,x)), nums, (max(nums), 0))[0]

reduce 函数详解
r[0]代表以当前位置为结尾的局部最优解
r[1]代表全局最优解
直接DP的解法更好理解一些

class Solution:
	    def maxSubArray(self, nums: List[int]) -> int:
	        for i in range(1, len(nums)):
	            nums[i] = max(nums[i], nums[i] + nums[i-1])
	        return max(nums)

54. Spiral Matrix 1行

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        return matrix and [matrix.pop(0)] + self.spiralOrder([zip(*matrix)][::-1])

为什么是[*matrix.pop(0)]而不是matrix.pop(0)？因为对于后面的递归，传进来的列表中元素是tuple

58. Length of Last Word 1行

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.strip(' ').split(' ')[-1])

59. Spiral Matrix II 3行

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        r, n = [[n2]], n2
        while n > 1: n, r = n - len(r), [[range(n - len(r), n)]] + [zip(*r[::-1])]
        return r

流程图

||  =>  |9|  =>  |8|      |6 7|      |4 5|      |1 2 3|
		 |9|  =>  |9 8|  =>  |9 6|  =>  |8 9 4|
				     |8 7|      |7 6 5|

61. Rotate List 4行

# Definition for singly-linked list.
class ListNode:
    def init(self, x):
        self.val = x
        self.next = None
class Solution:     def rotateRight(self, head: ListNode, k: int) -> ListNode:         l = []         while head: l[len(l):], head = [head], head.next         if l: l[-1].next, l[-1 - k % len(l)].next = l[0], None         return l[- k % len(l)] if l else None

62. Unique Paths 1行

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))

题目可以转换为排列组合问题，解是C(min(m,n), m+n)，从m+n个中选出m个下移或n个右移。
用DP做也很快，以后自己算 C(a, b) 也可以用算这题的DP法代替
math.factorial 的速度不亚于DP，可能内部有优化
0的阶乘为1

66. Plus One 1行

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

67. Add Binary 1行

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

非内置函数解法：

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        r, p = '', 0
        d = len(b) - len(a)
        a = '0' * d + a
        b = '0' * -d + b
        for i, j in zip(a[::-1], b[::-1]):
            s = int(i) + int(j) + p
            r = str(s % 2) + r
            p = s // 2
        return '1' + r if p else r

69. Sqrt(x) 1行

class Solution:
    def mySqrt(self, x: int) -> int:
        return int(x ** 0.5)

出题者应该是希望看到下面的答案：

class Solution:
    def mySqrt(self, x: int) -> int:
        r = x
        while r*r > x:
            r = (r + x/r) // 2
        return int(r)

基本不等式(a+b)/2 >=√ab 推导自 (a-b)^2 >= 0，注意 a>0 且 b>0
r 代表 result

70. Climbing Stairs 2行

class Solution:
    def climbStairs(self, n: int) -> int:
        from functools import reduce
        return reduce(lambda r, _: (r[1], sum(r)), range(n), (1, 1))[0]

dp递归方程：到达当前楼梯的路径数 = 到达上个楼梯的路径数 + 到达上上个楼梯的路径数
这里用一个元组 r 来储存（当前楼梯路径数，下一层楼梯路径数）
利用 reduce 来代替for循环。reduce 函数详解

71. Simplify Path 4行

class Solution:
    def simplifyPath(self, path: str) -> str:
        r = []
        for s in path.split('/'):
            r = {'':r, '.':r, '..':r[:-1]}.get(s, r + [s])
        return '/' + '/'.join(r)

73. 矩阵置零 5行

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row = [[0] * len(i) if 0 in i else i for i in matrix]
        col = [[0]  len(j) if 0 in j else list(j) for j in zip(matrix)]
        col2row = list(map(list, zip(*col)))
        # 上面一行效果等同：
        # col2row = [list(i) for i in zip(*col)]
        for i in range(len(matrix)):
            matrix[i] = col2row[i] if row[i] != [0] * len(matrix[0]) else row[i]

获取每一行 / 列的值，假如有0 就整行 / 整列置为0
重新将列排序列表转换为行排序列表，即原来的matrix中有0的列全为0，行不变
zip(*col) 返回的是zip类型，需要转换成list，其中元素类型为元组
所以之后做了两步转换，先将zip()返回的各个元组转换为list，在将整个转换为list
替换matrix各行，如果一整行为0，则替换为0，否则为col2row对应的各行

74. 搜索二维矩阵 4行

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:  return False
        col = list(list(zip(*matrix))[0])  # set() -> list()
        index = bisect.bisect_left(col, target, 0, len(matrix)-1)  # 二分查找
        return target in (matrix[index] + matrix[index-1])

先获取首列，然后二分类找到这个数所在的行，然后进行判断

78. Subsets 2行

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        from itertools import combinations
        return sum([list(combinations(nums, i)) for i in range(len(nums) + 1)], [])

80. 删除排序数组中的重复项 II 4行

def removeDuplicates(nums: [int]) -> int:
    for i in range(len(nums)-3, -1, -1):
        if nums[i] == nums[i+1] and nums[i] == nums[i+2]:
            nums.pop(i)
    return len(nums)

从尾部开始考虑

81. 搜索旋转排序数组 II 1行

def search(nums: [int], target: int) -> bool:
    return target in nums

83. Remove Duplicates from Sorted List 3行

# Definition for singly-linked list.
class ListNode:
    def init(self, x):
        self.val = x
        self.next = None
class Solution:     def deleteDuplicates(self, head: ListNode) -> ListNode:         if head:             head.next = self.deleteDuplicates(head.next)             return head.next if head.next and head.val == head.next.val else head

如果当前节点和下一个节点的值相同，则返回第二个节点
在每个递归中将下一个递归结果连接到当前节点

88. Merge Sorted Array 1行

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        while n > 0: nums1[m+n-1], m, n = (nums1[m-1], m-1, n) if m and nums1[m-1] > nums2[n-1] else (nums2[n-1], m, n-1)

这种题倒着算更容易
上面那行代码其实就相当于：

class Solution:
	    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
	        """
	        Do not return anything, modify nums1 in-place instead.
	        """
	        while n > 0:
	            if m and nums1[m-1] > nums2[n-1]:
	                nums1[m+n-1], m, n = nums1[m-1], m-1, n
	            else:
	                nums1[m+n-1], m, n = nums2[n - 1], m, n-1

89. Gray Code 1行

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return (lambda r: r + [x | 1<<n-1 for x in r[::-1]])(self.grayCode(n-1)) if n else [0]

前4个结果：

[0]
	[0 1]
	[00 01 11 10]
	[000 001 011 010 110 111 101 100]

递归方程：这一步结果 = 上一步结果 + 上一步结果的镜像并在每个二进制数字前面加一位1
<< 左移符号，即在二进制表示后加一位 0 ，例子：3<<1 等于 6（011 → 110），相当于 3 * 2的1次方
x | 1<
循环可以避免一些不必要的操作，会比递归快一些：

class Solution:
	    def grayCode(self, n: int) -> List[int]:
		r = [0]
		for i in range(n):
		    r.extend([x | 1<<i for x in r[::-1]])
		return r

或者直接背格雷码的公式🥶吧：

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ i >> 1  for i in range(1 << n)]

91. Decode Ways 4行

class Solution:
    def numDecodings(self, s: str) -> int:
        pp, p = 1, int(s[0] != '0')
        for i in range(1, len(s)):
            pp, p = p, pp  (9 < int(s[i-1:i+1]) <= 26) + p  (int(s[i]) > 0)
        return p

输入 '12' 的结果为 2，如果我们在 '12' 后面增加一个数字 3，输入变成 '123'，结果是 '12'的结果 + '1'的结果 = 3
i 从索引 1 开始逐渐遍历 s，当前位置对应结果 = 上上次结果(如果 i 位置字符和 i-1 位置字符的组合满足条件) + 上次结果(如果 s[i] 不为 0)

94. Binary Tree Inorder Traversal 2行

# Definition for a binary tree node.
class TreeNode:
    def init(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:     def inorderTraversal(self, root: TreeNode) -> List[int]:         f = self.inorderTraversal         return f(root.left) + [root.val] + f(root.right) if root else []

递归

class Solution:     def inorderTraversal(self, root: TreeNode) -> List[int]:         r, stack = [], []         while True:             while root:                 stack.append(root)                 root = root.left             if not stack:                 return r             node = stack.pop()             r.append(node.val)             root = node.right         return r

迭代

98. Validate Binary Search Tree 3行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def isValidBST(self, root: TreeNode, first=True) -> bool:         if not root: return first or []         l = self.isValidBST(root.left, 0) + [root.val] + self.isValidBST(root.right, 0)         return all([a > b for a, b in zip(l[1:], l)]) if first else l

搜索二叉树的中序遍历结果呈升序

101. Symmetric Tree 5行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def isSymmetric(self, root: TreeNode) -> bool:         if not root or root.left is root.right: return True         l, r, i, o = root.left, root.right, TreeNode(0), TreeNode(0)         if (l and l.val) != (r and r.val): return False         i.left, i.right, o.left, o.right = l.left, r.right, l.right, r.left         return self.isSymmetric(i) and self.isSymmetric(o)

一棵树对称意味着：

- 左节点 == 右节点 - 左节点的左子树与右节点右子树对称 - 左节点的右子树与右节点左子树对称

前三行处理特殊情况：root为None或root无子节点直接返回True，root只有一个子节点或root两个子节点不相等直接返回False
第一个条件在前三行处理过了，对于第二和第三个条件，我们分别构造两个假树i(inner)和o(outer)，i代表内假树，对应条件二，o代表外假树，对应条件三。递归内外假树即可

104. Maximum Depth of Binary Tree 1行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def maxDepth(self, root: TreeNode) -> int:         return max(map(self.maxDepth,(root.left, root.right))) + 1 if root else 0

利用map函数递归左右节点获取最大值，map函数会将参数一所指向的函数应用于参数二里的所有对象并返回所有结果构成的迭代器

110. 平衡二叉树 3行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def isBalanced(self, root: TreeNode, first=True) -> bool:         if not root: return first or 0         l, r = map(lambda x: self.isBalanced(x, False), [root.left, root.right])         return max(l,r)+1 if min(l,r)>-1 and abs(l-r)<=1 else (-1, False)[first]

DFS递归每个节点
如果这个节点不平衡，那么这棵树肯定不平衡，它和它的所有父节点都返回 -1（根节点返回False）
如果节点平衡，则返回当前树的高度 + 1（根节点返回True）

112. Path Sum 3行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def hasPathSum(self, root: TreeNode, sum: int) -> bool:         if not root: return False         l, r, f = root.left, root.right, lambda x: self.hasPathSum(x, sum - root.val)         return l is r and sum == root.val or f(l) or f(r)

考虑初始状态：当树不存在时直接返回 False
考虑支路1：当前节点为叶节点时直接判断总和是否达到要求
考虑支路2：当前节点为非叶节点时将总和缩小并继续递归，判断左右节点是否存在满足条件的
当递归函数到达叶节点时，sum 已经被削减了多次，此时 sum - node.val 即为 原始的sum - 整条路径的总和

118. Pascal's Triangle 1行

class Solution:     def generate(self, numRows: int) -> List[List[int]]:         return [[math.factorial(i)//math.factorial(i-j)//math.factorial(j) for j in range(i+1)] for i in range(numRows)]

参考了杨辉三角的数学性质，维基百科
正常迭代方法：

class Solution: 	    def generate(self, numRows: int) -> List[List[int]]: 		r = [[1]] 		for i in range(1, numRows): 		    r.append([1] + [sum(r[-1][j:j+2]) for j in range(i)]) 		return numRows and r or []

121. Best Time to Buy and Sell Stock 2行

class Solution:     def maxProfit(self, prices: List[int]) -> int:         from functools import reduce         return reduce(lambda r, p: (max(r[0], p-r[1]), min(r[1], p)), prices, (0, float('inf')))[0]

r = (结果，之前遍历过的所有元素中的最小值)
reduce 函数详解

class Solution:     def maxProfit(self, prices: List[int]) -> int:         r, m = 0, float('inf')         for p in prices:             r, m = max(r, p - m), min(m, p)         return r

122. Best Time to Buy and Sell Stock II 2行

class Solution:     def maxProfit(self, prices: List[int]) -> int:         return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)

本题可以在同一天买入和卖出，因此只要当天票价比昨天的高就可以卖出

124. Binary Tree Maximum Path Sum 4行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def maxPathSum(self, root: TreeNode, ok=True) -> int:         if not root: return 0         l, r = self.maxPathSum(root.left, False), self.maxPathSum(root.right, False)         self.max = max(getattr(self, 'max', float('-inf')), l + root.val + r)         return self.max if ok else max(root.val + max(l, r), 0)

使用 self.max 记录全局最大值，getattr 返回自身 max 属性的值或预定义的负无穷
本题思路是：递归每一个节点，返回max(以当前节点为结尾的最大路径和,0)。并更新最大值全局最大路径和=max(全局最大路径和，当前节点值+左子树返回结果+右子树返回结果)
用ok判断是不是第一次递归，是就返回全局最大值，否则照常

133. Clone Graph

""" Definition for a Node.
 class Node:     def init(self, val, neighbors):         self.val = val         self.neighbors = neighbors """ class Solution:     def cloneGraph(self, node: 'Node') -> 'Node':         return copy.deepcopy(node)

dfs解法请参考 133克隆图

136. Single Number 2行

class Solution:     def singleNumber(self, nums: List[int]) -> int:         from functools import reduce         return reduce(xor, nums)

这里用到了异或（xor），相同的数字异或后为0，0异或任何数都等于那个数，用reduce在列表所有元素之间使用异或^，那么留下的就是那个单独的数字了

138. Copy List with Random Pointer 1行

""" Definition for a Node.
 class Node:     def init(self, val, next, random):         self.val = val         self.next = next         self.random = random """ class Solution:     def copyRandomList(self, head: 'Node') -> 'Node':         return copy.deepcopy(head)

内置函数

139. Word Break 8行

class Solution:     def wordBreak(self, s, wordDict):                  def f(s, d={}):             if not s in d:                 for i in range(1, 1 + len(s)):                     d[s[:i]] = s[:i] in wordDict and (i == len(s) or f(s[i:]))                     if d[s[:i]]: return True                 return False             return d[s]                  return f(s)

brute force + memory

141. Linked List Cycle 2行

# Definition for singly-linked list. class ListNode(object):
     def init(self, x):
         self.val = x
         self.next = None

class Solution(object):     def hasCycle(self, head):         """         :type head: ListNode         :rtype: bool         """         while head and head.val != None: head.val, head = None, head.next         return head != None

这题不支持python3，所以用pyhton2解法代替，下题记得调回来 :baby_chick:
破坏走过的所有节点，下次再遇到就知道了
不过以上方法会丢失原有信息，一般解法为快慢指针

# Definition for singly-linked list. class ListNode(object):
     def init(self, x):
         self.val = x
         self.next = None

class Solution(object):     def hasCycle(self, head):         slow = fast = head         while fast and fast.next:             fast = fast.next.next             slow = slow.next             if slow == fast:                 return True         return False

142. Linked List Cycle II 5行

# Definition for singly-linked list. class ListNode(object):
     def init(self, x):
         self.val = x
         self.next = None

class Solution(object):     def detectCycle(self, head):         """         :type head: ListNode         :rtype: ListNode         """         s = {None}         while head not in s:             s.add(head)             head = head.next         return head

把见过的节点丢集合里，下次再遇见就是环的开始
还有一个纯数学的快慢指针解法，设环的起始节点为 E，快慢指针从 head 出发，快指针速度为 2，设相交节点为 X，head 到 E 的距离为 H，E 到 X 的距离为 D，环的长度为 L，那么有：快指针走过的距离等于慢指针走过的距离加快指针多走的距离（多走了 n 圈的 L） 2(H + D) = H + D + nL，因此可以推出 H = nL - D，这意味着如果我们让俩个慢指针一个从 head 出发，一个从 X 出发的话，他们一定会在节点 E 相遇

_ 				 /     \ 		 head_E       \ 				\       / 				 X_/

class Solution(object): 	    def detectCycle(self, head): 		slow = fast = head 		while fast and fast.next: 		    fast = fast.next.next 		    slow = slow.next 		    if slow == fast: 			break 		else: 		    return None 		while head is not slow: 		    head = head.next 		    slow = slow.next 		return head

146. LRU Cache 7行

class LRUCache(object):
def init(self, capacity):         self.od, self.cap = collections.OrderedDict(), capacity
def get(self, key):         if key not in self.od: return -1         self.od.movetoend(key)         return self.od[key]
def put(self, key, value):         if key in self.od: del self.od[key]         elif len(self.od) == self.cap: self.od.popitem(False)         self.od[key] = value
Your LRUCache object will be instantiated and called as such:
obj = LRUCache(capacity)
param_1 = obj.get(key)
obj.put(key,value)

148. Sort List 10行

# Definition for singly-linked list.
class ListNode:
    def init(self, x):
        self.val = x
        self.next = None
class Solution:     def sortList(self, head: ListNode) -> ListNode:         if not (head and head.next): return head         pre, slow, fast = None, head, head         while fast and fast.next: pre, slow, fast = slow, slow.next, fast.next.next         pre.next = None         return self.mergeTwoLists(*map(self.sortList, (head, slow)))          def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:         if l1 and l2:             if l1.val > l2.val: l1, l2 = l2, l1             l1.next = self.mergeTwoLists(l1.next, l2)         return l1 or l2

使用快慢指针寻找链表中点，并分解链表
递归融合俩个有序链表，详解见 21 题
此处忽略了递归开栈导致的非常数级空间复杂度（想太多了吧:laughing:），如果一定要抬杠，推荐使用quicksort

class Solution(object): 	    def sortList(self, head): 		""" 		:type head: ListNode 		:rtype: ListNode 		""" 		def partition(start, end): 		    node = start.next.next 		    pivotPrev = start.next 		    pivotPrev.next = end 		    pivotPost = pivotPrev 		    while node != end: 			temp = node.next 			if node.val > pivotPrev.val: 			    node.next = pivotPost.next 			    pivotPost.next = node 			elif node.val < pivotPrev.val: 			    node.next = start.next 			    start.next = node 			else: 			    node.next = pivotPost.next 			    pivotPost.next = node 			    pivotPost = pivotPost.next 			node = temp 		    return [pivotPrev, pivotPost]
def quicksort(start, end): 		    if start.next != end: 			prev, post = partition(start, end) 			quicksort(start, prev) 			quicksort(post, end)
newHead = ListNode(0) 		newHead.next = head 		quicksort(newHead, None) 		return newHead.next

150. Evaluate Reverse Polish Notation 5行

class Solution:     def evalRPN(self, tokens: List[str]) -> int:         t, f = tokens.pop(), self.evalRPN         if t in '+-*/':             b, a = f(tokens), f(tokens)             t = eval('a' + t + 'b')         return int(t)

递归地返回左右表达式操作后结果
eval 函数将字符串看作代码得到输出值

155. Min Stack 每个1行

class MinStack:          def init(self):         self.data = [(None, float('inf'))]
def push(self, x: 'int') -> 'None':         self.data.append((x, min(x, self.data[-1][1])))
def pop(self) -> 'None':         if len(self.data) > 1: self.data.pop()
def top(self) -> 'int':         return self.data[-1][0]
def getMin(self) -> 'int':         return self.data[-1][1]
Your MinStack object will be instantiated and called as such:
obj = MinStack()
obj.push(x)
obj.pop()
param_3 = obj.top()
param_4 = obj.getMin()

160. Intersection of Two Linked Lists 3行

# Definition for singly-linked list.
class ListNode(object):
    def init(self, x):
        self.val = x
        self.next = None
class Solution(object):     def getIntersectionNode(self, headA, headB):         """         :type head1, head1: ListNode         :rtype: ListNode         """         a, b = (headA, headB) if headA and headB else (None, None)         while a != b: a, b = not a and headB or a.next, not b and headA or b.next         return a

这题不支持 Python3 所以只能用 Python2 做了
把第一条链表的尾部接到第二条链表的开头，第二条接到第一条的开头，就能消除俩条链表的长度差，并在某一时刻在第一个交叉点相遇，或在走完俩条链表长度的时候同时为 None

# 假设有两条链表1→2→3→4和①→②→③，模拟一下算法流程 ↓

1 → 2 ↘ ↗ → 4 1 → 2 ↘ ↗ → 4 → ① → → → 3(②) ❤ 相遇了 ① → → → 3(②) → ③ 把4接到①前面，把③接到1前面 ① → → → 3(②) → ③ → 1 → 2 ↗ 若非相交链表则同时走到None

162. Find Peak Element 2行

class Solution:     def findPeakElement(self, nums: List[int]) -> int:         self.class.getitem = lambda self, i: i and nums[i - 1] > nums[i]         return bisect.bisect_left(self, True, 0, len(nums)) - 1

二分查找套路
如果当前位置的左边是更大的数字，则当前位置置为True，继续向左搜索，最后应该插入的位置 = 我们寻找的位置 + 1，因此最后 - 1

165. Compare Version Numbers 4行

class Solution:     def compareVersion(self, version1: str, version2: str) -> int:         v1, v2 = [map(int, version1.split('.'))], [map(int, version2.split('.'))]         d = len(v2) - len(v1)         v1, v2 = v1 + [0]  d, v2 + [0]  -d         return (v1 > v2) - (v1 < v2)

利用 python 序列比较的性质

169. Majority Element 1行

class Solution:     def majorityElement(self, nums: List[int]) -> int:         return sorted(nums)[len(nums) // 2]

171. Excel Sheet Column Number 1行

class Solution:     def titleToNumber(self, s: str) -> int:         return sum((ord(c) - 64)  26*i for i, c in enumerate(s[::-1]))

173. Binary Search Tree Iterator 6行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class BSTIterator:
def init(self, root: TreeNode):         self.s = []         while root: self.s[len(self.s):], root = [root], root.left
def next(self) -> int:         """         @return the next smallest number         """         r, root = self.s[-1], self.s.pop().right         while root: self.s[len(self.s):], root = [root], root.left         return r.val
def hasNext(self) -> bool:         """         @return whether we have a next smallest number         """         return bool(self.s)
Your BSTIterator object will be instantiated and called as such:
obj = BSTIterator(root)
param_1 = obj.next()
param_2 = obj.hasNext()

模拟中序遍历的迭代过程，使用堆栈 self.s 进行深度优先搜索
空间复杂度为 O(树的高度)
平均时间复杂度 = 循环总次数（N） / 迭代器长度（N） = O(1)
迭代器解法：

from itertools import chain
class BSTIterator:
def init(self, root: TreeNode):         def gen(root): yield from chain(gen(root.left), [root.val], gen(root.right)) if root else ()         self.iter, self.len = gen(root), 0         for _ in gen(root): self.len += 1
def next(self) -> int:         """         @return the next smallest number         """         self.len -= 1         return next(self.iter)
def hasNext(self) -> bool:         """         @return whether we have a next smallest number         """         return bool(self.len)

平均时空复杂度： O(1)，O(1)

189. Rotate Array 1行

class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not return anything, modify nums in-place instead.         """         nums[:] = nums[len(nums) - k:] + nums[:len(nums) - k]

空间复杂度 = O(N)
进阶：

class Solution: 	    def rotate(self, nums: List[int], k: int) -> None: 		""" 		Do not return anything, modify nums in-place instead. 		""" 		for _ in range(k % len(nums)): nums[-1:], nums[:0] = [], nums[-1:]

- 时间复杂度 = O(k % len(nums))，空间复杂度 = O(1)

190. Reverse Bits 1行

class Solution:     # @param n, an integer     # @return an integer     def reverseBits(self, n):         return int(bin(n)[2:].zfill(32)[::-1], 2)

字符串操作
zfill用法

191. Number of 1 Bits 1行

class Solution(object):     def hammingWeight(self, n):         """         :type n: int         :rtype: int         """         return bin(n).count('1')

198. House Robber 2行

class Solution:     def rob(self, nums: List[int]) -> int:         from functools import reduce         return reduce(lambda r, n: (max(r[0], n + r[1]), r[0]), nums, (0, 0))[0]

DP递归方程：一直偷到这家的钱 = max（一直偷到上一家的钱，一直偷到上上家的钱 + 这家的钱）😃有点小绕
以上为下面代码的化简版，reduce 函数详解

class Solution:     def rob(self, nums: List[int]) -> int:         last, now = 0, 0         for i in nums:             last, now = now, max(last + i, now)         return now

DP不一定要数组，这里两个变量就够了，空间复杂度为O(1)

200. Number of Islands 7行

class Solution(object):     def numIslands(self, grid):         def sink(i, j):             if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and int(grid[i][j]):                 grid[i][j] = '0'                 for i, j in zip((i, i+1, i, i-1), (j+1, j, j-1, j)): sink(i, j)                 return 1             return 0         return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

根据题意，我们可以把每一个陆地点当作树根，用 DFS 搜索四周的陆地并沉没它，那么这一整块的陆地都被沉没了，下次我们再遇到陆地点的时候就说明发现新大陆了

202. Happy Number 1行

class Solution:     def isHappy(self, n: int) -> bool:         return self.isHappy(sum(int(i) ** 2 for i in str(n))) if n > 4 else n == 1

不是快乐数的数称为不快乐数(unhappy number)，所有不快乐数的数位平方和计算，最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中
这个规律比较难想到的，正常解法是判断n是否会进入循环：

class Solution:     def isHappy(self, n: int) -> bool:         seen = {1}         while n not in seen:             seen.add(n)             n = sum(int(i) ** 2 for i in str(n))         return n == 1

[203. Remove Linked List Elements 2行]()

# Definition for singly-linked list. class ListNode:
     def init(self, x):
         self.val = x
         self.next = None

class Solution:     def removeElements(self, head: ListNode, val: int) -> ListNode:         if head: head.next = self.removeElements(head.next, val)         return head.next if head and head.val == val else head

递归：每次都返回从当前位置算起第一个有效的节点或None

205. Isomorphic Strings 1行

class Solution:     def isIsomorphic(self, s: str, t: str) -> bool:         return [map(s.index, s)] == [map(t.index, t)]

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return all(s.index(i) == t.index(j) for i,j in zip(s,t))

同构代表两个字符串中每个位置上字符在自身第一次出现的索引相同

206. Reverse Linked List 2行

# Definition for singly-linked list.
class ListNode:
    def init(self, x):
        self.val = x
        self.next = None
class Solution:     def reverseList(self, head: ListNode, tail=None) -> ListNode:         if head: head.next, tail, head = tail, head, head.next         return self.reverseList(head, tail) if head else tail

递归解法
此解法为尾递归，即直接以递归返回值作为结果，一般编译器会做优化，避免多余的函数开栈操作，实现效果相当于迭代

# Definition for singly-linked list. class ListNode:
     def init(self, x):
         self.val = x
         self.next = None

class Solution:     def reverseList(self, head: ListNode) -> ListNode:         p = None         while head: head.next, p, head = p, head, head.next         return p

迭代解法

215. Kth Largest Element in an Array 1行

class Solution:     def findKthLargest(self, nums: List[int], k: int) -> int:         return sorted(nums)[-k]

O(NlogN)调库
面试官一般不会接受以上答案的，可以参考下面这个O(N)的quick-selection，思路借鉴的quick-sort

class Solution: 	    def findKthLargest(self, nums: List[int], k: int) -> int: 		l = [x for x in nums if x > nums[0]] 		m = [x for x in nums if x == nums[0]] 		r = [x for x in nums if x < nums[0]] 		f = self.findKthLargest
if k <= len(l): 		    return f(l, k) 		elif k <= len(l) + len(m): 		    return nums[0] 		return f(r, k - len(l) - len(m))

class Solution:     def findKthLargest(self, nums: List[int], k: int) -> int:         return nlargest(k,nums)[-1]

用了 heapq 的 nlargest 函数，返回一个 list , 然后取最后一个

217. Contains Duplicate 1行

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

219. Contains Duplicate II 4行

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        r, d = k + 1, {}
        for i, n in enumerate(nums):
            r, d[n] = min(r, i - d.get(n, -k - 1)), i
        return r <= k

本题题目有误，实际意思是找同数字最小间隔，若不超过 k 则满足条件
遍历列表，每次都比对最小间隔，并更新哈希表索引，当前位置往左的最小间隔一定是与上一次同数字出现的索引的距离

225. Implement Stack using Queues 6行

class MyStack:
def init(self):         self.q = collections.deque()
def push(self, x):         self.q.append(x)         for _ in range(len(self.q) - 1): self.q.append(self.q.popleft())              def pop(self):         return self.q.popleft()
def top(self):         return self.q[0]          def empty(self):         return not len(self.q)

push 的时候把 x 放入队尾，然后遍历一遍原始队列元素，每次弹出之后加入队尾

230. Kth Smallest Element in a BST 3行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def kthSmallest(self, root, k):         from itertools import chain, islice         def gen(x): yield from chain(gen(x.left), [x.val], gen(x.right)) if x else ()         return next(islice(gen(root), k - 1, k))

本题利用迭代器骚了一波:grinning:，不太了解的话看这里 yield 推荐阅读博客
chain 函数可以组合多个迭代器，islice 函数对迭代器做切片操作
此题常规解法中序遍历还是需要了解下的

# Definition for a binary tree node. 	# class TreeNode(object): 	#     def init(self, x): 	#         self.val = x 	#         self.left = None 	#         self.right = None
class Solution(object): 	    def kthSmallest(self, root, k): 		""" 		:type root: TreeNode 		:type k: int 		:rtype: int 		""" 		res = [] 		self.visitNode(root, res) 		return res[k - 1]
# 中序遍历 	    def visitNode(self, root, res): 		if root is None: 		    return 		self.visitNode(root.left, res) 		res.append(root.val) 		self.visitNode(root.right, res)

231. 2的幂 1行

class Solution:     def isPowerOfTwo(self, n: int) -> bool: 	""" 	:type n: int 	:rtype: bool 	"""         return n > 0 and n & n - 1 == 0

2 的幂的二进制形式最高位一定是1，其余为0
用常规思路也行

class Solution(object): 	    def isPowerOfTwo(self, n): 		return n > 0 and 2**int(math.log2(n)) == n

232. Implement Queue using Stacks 13行

class MyQueue:
def init(self):         """         Initialize your data structure here.         """         self.stack = []
def push(self, x: int) -> None:         """         Push element x to the back of queue.         """         self.stack.append(x)
def pop(self) -> int:         """         Removes the element from in front of queue and returns that element.         """         temp = []         while self.stack: temp.append(self.stack.pop())         r = temp.pop()         while temp: self.stack.append(temp.pop())         return r
def peek(self) -> int:         """         Get the front element.         """         temp = []         while self.stack: temp.append(self.stack.pop())         r = temp[-1]         while temp: self.stack.append(temp.pop())         return r
def empty(self) -> bool:         """         Returns whether the queue is empty.         """         return not self.stack
Your MyQueue object will be instantiated and called as such:
obj = MyQueue()
obj.push(x)
param_2 = obj.pop()
param_3 = obj.peek()
param_4 = obj.empty()

使用俩个栈来模拟队列，当需要取第一个元素的时候创建一个临时的栈temp，把栈里面的东西全部抽出来放进temp，完成操作后放回去

234. Palindrome Linked List 3行

# Definition for singly-linked list.
class ListNode:
    def init(self, x):
        self.val = x
        self.next = None
class Solution:     def isPalindrome(self, head: ListNode) -> bool:         def gen(n):             while n: yield n.val; n = n.next         return [gen(head)] == [gen(head)][::-1]

235. Lowest Common Ancestor of a Binary Search Tree 2行

# Definition for a binary tree node. class TreeNode:
     def init(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:     def lowestCommonAncestor(self, root, p, q):         while (root.val - p.val) * (root.val - q.val) > 0: root = (root.left, root.right)[p.val > root.val]         return root

最近公共祖先的值一定介于p、q值之间(闭区间)

236. Lowest Common Ancestor of a Binary Tree 2行

```python

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNod

README truncated. View on GitHub

🔗 More in this category

:snake: Shortest-LeetCode-Python-Solutions

前言

:trophy: 里程碑

推荐

题库解析

class ListNode:

def init(self, x):

self.val = x

self.next = None

class ListNode:

def init(self, x):

self.val = x

self.next = None

国际站上有一种写法是这样的，相比于上面，下面的写法更加优雅（好理解）一点

class ListNode:

def init(self, x):

self.val = x

self.next = None

class ListNode:

def init(self, x):

self.val = x

self.next = None

class ListNode:

def init(self, x):

self.val = x

self.next = None

class ListNode:

def init(self, x):

self.val = x

self.next = None

class ListNode:

def init(self, x):

self.val = x

self.next = None

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

Definition for a Node.

Definition for a Node.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

class ListNode(object):