LeetCode刷题大全

2020年09月19日

Author: Guofei

文章归类: 8-数据结构与算法，文章编号: 590

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2020/09/19/lc.html

Edit

1. Two Sum

限制加和等于n。不要每一步都判断x+y=n，而是判断n-x=y
两次遍历。考虑不写2个for，而是1次遍历，把元素放到hashtable中

def twoSum(self, nums: List[int], target: int) -> List[int]:
    tmp_dict = dict()
    for i, j in enumerate(nums):
        if j in tmp_dict:
            return [tmp_dict[j], i]
        tmp_dict[target - j] = i

2. Add Two Numbers

对于链表，curr.next 指针向下走，这个不多说
curr1=curr1.next if curr1 else curr1 这个操作，让遍历到尾部后，值保持curr1=None，好处是少些几行代码。作为配合，在其它行，可以用 if curr1 来判断是否到尾部
链表还有个好处，如本例，l3 是含一个空的头的，返回 l3.next 即可

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    carry=0
    l3=ListNode(None)
    curr1,curr2,curr3=l1,l2,l3
    while curr1 or curr2 or carry:
        value=(curr1.val if curr1 else 0)+(curr2.val if curr2 else 0)+carry
        carry,val=divmod(value,10)
        curr3.next=ListNode(val)
        curr1=curr1.next if curr1 else curr1
        curr2=curr2.next if curr2 else curr2
        curr3=curr3.next
    return l3.next

3. Longest Substring Without Repeating Characters

2 sum 那道题里面写过，这种貌似需要两次遍历的题目。都可以想一下能不能用 hashTable 存下历史遍历，从而变成一次遍历。

def lengthOfLongestSubstring(self, s: str) -> int:
    used = dict()
    start = 0
    res = 0
    for i, c in enumerate(s):
        if c in used and start <= used[c]:
            start = used[c] + 1
        else:
            res = max(res, i - start + 1)
        used[c] = i
    return res

4. Median of Two Sorted Arrays

这个题目其实可以 cheat，俩列表加一起，然后用Python自代的sort，代码就不写了。

套路详解：https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation

中位数的定义：中位数两边的数量相等。
因此，num1 的分割和num2的分割存在一个恒等关系，len(left1)+len(left2)=len(right1)+len(right2)
这也就意味着，给定num1的分割，就立即能计算出num2的分割
本质上还是把两次遍历变成一次
如果if情况过多，考虑换一下两个变量，减少代码量。

(代码还是好难写，奇偶之类的)

def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect

            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

5. Longest Palindromic Substring

没有套路。中间往外拓，平方级复杂度。

6. ZigZag Conversion

没有套路。按照ZigZag的字面意思，在s上做遍历。
（其实还可以先算出每个值所在的位置，不过有点儿费草稿纸）

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows==1 or (len(s)<numRows):
            return s
        res_list = [''] * numRows
        location, direction = 0, -1 # 假想开头前面也迭代过程中，所以初始是负号
        for i in s:
            res_list[location] = res_list[location] + i
            if location == 0 or location == numRows - 1:
                direction = -direction
            location += direction
        return ''.join(res_list)

7. Reverse Integer

没有套路。
按位数颠倒一个整数。考虑负号和零。Python用字符串反转就行了。

class Solution:
    def reverse(self, x: int) -> int:
        sign = 1 if x >= 0 else -1
        y=sign*int(str(sign*x)[::-1])
        if y>2**31-1 or y<-2**31:
            return 0
        return y

简洁的写法

class Solution:
    def reverse(self, x: int) -> int:
        sign = (x > 0) - (x < 0)
        r = int(str(sign*x)[::-1])
        return sign*r * (r < 2**31)

8. String to Integer (atoi)

实在无聊的题，就是各种边界条件。不用看了

9. 10. Regular Expression Matching

好题！
套路：

递归（不是很容易想出）
递归的某些节点被反复调用。考虑存下来。（下面代码里面没有体现）

https://leetcode.com/problems/regular-expression-matching/solution/


def isMatch(text, pattern):
    if not pattern:
        return not text

    first_match= text and pattern[0] in {text[0],'.'}
    if len(pattern)>=2 and pattern[1]=='*':
        return isMatch(text,pattern[2:]) or first_match and isMatch(text[1:],pattern)
    else:
        return first_match and isMatch(text[1:],pattern[1:])

需要再过一遍：DP也能很好的解这个题。

11. Container With Most Water

像 2-sum 那个题目，看起来需要2次遍历，立即想到暂存历史计算，减少计算量。
先看看哪些情况是“不可能”的，把它们排除出去。左挡板从左向右遍历，如果后一个比前一个还短，那么这个不可能是 candidate，右挡板同样的道理。
（到上面这一步已经可以写代码了，最坏平方级复杂度）还可以继续优化（这个看答案才想出来）。我们上一步把不可能的情况删掉后得到了递增的左挡板，和递增（从右往左看）的右挡板。如果左挡板低于右挡板，那么右挡板向左移动就不可能是 candidate，于是又排除了很多情况，变成 O(n) 复杂度。

a=[1,8,6,2,5,4,8,3,7]
i,j=0,len(a)-1
weight=0
while i<j:
    weight=max(weight,(j-i)*min(a[i],a[j]))
    if a[i]<a[j]:
        i+=1
    else:
        j-=1

weight

12. Integer to Roman

all_symbols = [
    ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
    ,['', 'X', 'XX', 'XXX','XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
    , ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
    ,['', 'M', 'MM', 'MMM']
]

''.join([all_symbols[i][num//(10**i)%10] for i in range(3,-1,-1)])

13~15 无聊的题目

16. 3Sum Closest

n-Sum 两种思路：

复用2sum，加一层遍历。2sum复杂度是n，3sum复杂度是O(n^2)
2sum还有另一种解法，先排序，然后使用 Container With Most Water 的思路，找解复杂度是 O(n),但排序的复杂度是 O(nlgn)，所以2sum复杂度是 O(nlgn),3sum复杂度 O(n^2+nlgn)=O(n^2)
所以2sum和3sum都可以用这个思路，复杂度一样
但3Sum Closest显然不能用1了，但可以用2


nums=[0,-4,1,-5]
target=0

nums.sort()


def sum2_cloeset(nums,n):
    i,j=0,len(nums)-1
    res=nums[i]+nums[j]
    diff=abs(res-n)
    while i<j:
        sum2=nums[i]+nums[j]
        if sum2==n:
            return sum2
        diff_tmp=abs(sum2-n)
        if diff_tmp<diff:
            diff=diff_tmp
            res=sum2
        if sum2>n:
            j-=1
        else:
            i+=1
    return res


# nums=[1,2,3,4,5]
# sum2_cloeset(nums,5)


diff=abs(sum(nums[:3])-target)
res=sum(nums[:3])
for i in range(len(nums)-2):
    tmp=sum2_cloeset(nums[i+1:],target-nums[i])
    if abs(tmp+nums[i]-target)<diff:
        print(tmp,nums[i])
        res=tmp+nums[i]
        diff=abs(tmp+nums[i]-target)

res

17. Letter Combinations of a Phone Number

基础题，可以以此题为例子，把几种解法练熟了，甚至背下来。

利用 itertools

import itertools
def letterCombinations(self, digits: str) -> List[str]:
 if len(digits)==0:return []
 all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz']
 candidate=[list(all_char[int(button)]) for button in digits]
 return [''.join(i) for i in  itertools.product(*candidate)]

递归。这个递归方法要求返回所有遍历到叶节点的路径。而不是成功访问1个叶节点就返回。这两种递归都要非常熟悉。

all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz']
def letter_comb(digits):
 if len(digits)==0:
     return []
 if len(digits)==1:
     return list(all_char[int(digits[0])])
 prev=letter_comb(digits[:-1])
 lst=all_char[int(digits[-1])]
 return [s+l for s in prev for l in lst]
letter_comb(digits)

递归（从前往后），另外，如果不考虑空的特殊情况，代码还可以再省一些

all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz']
def letter_comb(digits):
 if len(digits)==0:
     return ['']
 prev=all_char[int(digits[0])]
 lst=letter_comb(digits[1:])
 return [p+l for p in prev for l in lst]

遇到笛卡尔积问题，优先使用这个套路。递归太容易写错，还是for循环好一些。

all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz']
def letter_comb(digits):
 digits=[int(i) for i in digits]
 res=['']
 for digit in digits:
     res=[i+j for i in res for j in all_char[digit]]
 return res

事实证明，太多骚操作，复用就不方便。简简单单的for循环。（22题复用此代码） ```python all_char=[’’,’’,’abc’,’edf’,’ghi’,’jkl’,’mno’,’pqrs’,’tuv’,’wxyz’]

digits=[int(i) for i in digits] def letter_comb(digits): res=[’’] for digit in digits: tmp=list() for i in res: for j in all_char[digit]: tmp.append(i+j) res=tmp return res




### 18. 4Sum

用递归，nSUM都能做出来
```python

def find_2sum(nums,target):
    i,j=0,len(nums)-1
    res=[]
    while i<j:
        sum2=nums[i]+nums[j]
        if sum2==target:
            res.append([nums[i],nums[j]])
            i+=1
        elif sum2>target:
            j-=1
        else:
            i+=1
    return res


def find_Nsum(nums,target,N):
    if N==2:
        return find_2sum(nums,target)
    res=[]
    for i in range(len(nums)-N+1):
        tmp=find_Nsum(nums[i+1:],target-nums[i],N-1)
        if len(tmp)>0:
            res.extend([[nums[i]]+t for t in tmp])
    return res


nums=[1,0,-1,0,-2,2]
target=0
nums.sort()
find_Nsum(nums,target,N=4)

19. Remove Nth Node From End of List

凡是链表上的遍历问题，一律先想想能否使用单指针/双指针/多指针
如果处理的链表是不含空的头节点那种，一律加上空的头节点。这样往往可以减少很多处理边界条件的代码量。

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    dummy=ListNode('')
    dummy.next=head
    curr1=dummy
    for i in range(n):
        curr1=curr1.next
    curr2=dummy
    while curr1.next:
        curr1=curr1.next
        curr2=curr2.next
    curr2.next=curr2.next.next
    return dummy.next

20. Valid Parentheses

好题目，用堆栈做，没什么难度

def isValid(self, s: str) -> bool:
    stack=list()
    pairs={'(':')','[':']','{':'}'}
    pairs2={')':'(',']':'[','}':'{'}
    for i in s:
        if i in pairs:
            stack.append(i)
        elif i in pairs2:
            if len(stack)==0:
                return False
            elif stack[-1]==pairs2[i]:
                stack.pop()
            else:
                return False
    return len(stack)==0

21. Merge Two Sorted Lists

遇到链表，第一想到指针
处理链表，一律先转化成带空头节点的链表。可以减少一些边界条件的代码量，减少错误。

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    if l1 is None :
        return l2
    if l2 is None:
        return l1
    dummy1,dummy2=ListNode(),ListNode()
    dummy1.next,dummy2.next=l1,l2
    curr1,curr2=dummy1,dummy2.next
    while curr2 and curr1.next:
        if curr1.next.val>curr2.val:
            tmp1,tmp2=curr1.next,curr2.next
            curr1.next=curr2
            curr2.next=tmp1
            curr2=tmp2
            curr1=curr1.next
        else:
            curr1=curr1.next
    while curr1.next:
        curr1=curr1.next
    curr1.next=curr2
    return dummy1.next

22. Generate Parentheses

先把左括号全写出来，然后插入右括号。想到套路:

抽屉插空问题
解决抽屉插空问题，需要罗列笛卡尔积。用17题的方法，最土的for循环。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        cases=[[[0],0]] # seq&cumsum
        for i in range(1,n):
            tmp=[]
            for case in cases:
                seq,cumsum=case
                for k in range(i-cumsum+1):
                    tmp.append([seq+[k],cumsum+k])
            cases=tmp

        res=[]
        for case in cases:
            seq,cumsum=case[0],case[1]
            one_case=''
            for i in seq:
                one_case+=')'*i
                one_case+='('
            one_case+=(')'*(n-cumsum))
            res.append(one_case)

        return set(res)

23. Merge k Sorted Lists

复用merge2

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists)==0:return None
        if len(lists)==1:return lists[0]
        def merge2(l1,l2):
            if l1 is None :
                return l2
            if l2 is None:
                return l1
            dummy1,dummy2=ListNode(),ListNode()
            dummy1.next,dummy2.next=l1,l2
            curr1,curr2=dummy1,dummy2.next
            while curr2 and curr1.next:
                if curr1.next.val>curr2.val:
                    tmp1,tmp2=curr1.next,curr2.next
                    curr1.next=curr2
                    curr2.next=tmp1
                    curr2=tmp2
                    curr1=curr1.next
                else:
                    curr1=curr1.next
            while curr1.next:
                curr1=curr1.next
            curr1.next=curr2
            return dummy1.next

        l1=lists[0]
        for i in range(1,len(lists)):
            l1=merge2(l1,lists[i])

        return l1

24. Swap Nodes in Pairs

考点都是在前面出现过的，必须都玩熟了：

遇到链表，无脑转成带空头节点的链表
用 curr.next and curr.next.next 来规避 curr.next 是 None 的情况

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        node=ListNode()
        node.next=head
        curr=node
        while curr.next and curr.next.next:
            tmp1,tmp2=curr.next,curr.next.next
            tmp1.next=tmp2.next
            tmp2.next=tmp1
            curr.next=tmp2
            curr=tmp1
        return node.next

25. Reverse Nodes in k-Group

这个题就是两个逻辑的合并：取接下来的n个node，链表反转。

链表反转是一个基础考点。可以每次把最前面的节点放到后面。也可以每次把最后面的节点放到前面。
链表上的遍历，立即想到指针。
链表无脑转为带空头节点的链表
实际上可以一边向下遍历，一边反转，但这种解法与“不玩儿骚操作”的理念不符。作为替代，把“遍历找到下面k个”和“链表反转”作为两个部分分开写（尽管运行速度会慢一些）

您的支持将鼓励我继续创作！

LeetCode刷题大全