【LeetCode】1~99题



2020年09月19日    Author:Guofei

文章归类: 刷题    文章编号: 595

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


1. Two Sum

考点

  1. 限制加和等于n。不要每一步都判断x+y=n,而是判断n-x=y
  2. 两次遍历。考虑不写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

考点

  1. 对于链表,curr.next 指针向下走,这个不多说
  2. curr1=curr1.next if curr1 else curr1 这个操作,让遍历到尾部后,值保持curr1=None,好处是少些几行代码。作为配合,在其它行,可以用 if curr1 来判断是否到尾部
  3. 链表还有个好处,如本例,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

考点:

  1. 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

考点:

  1. 中位数的定义:中位数两边的数量相等。
  2. 因此,num1 的分割和num2的分割存在一个恒等关系,len(left1)+len(left2)=len(right1)+len(right2)
  3. 这也就意味着,给定num1的分割,就立即能计算出num2的分割
  4. 本质上还是把两次遍历变成一次
  5. 如果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

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

class Solution:

    def helper(self, left, right):
        while left >= 0 and right < len(self.s) and self.s[left] == self.s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        self.s = s
        left, right = 0, 0
        for i in range(len(s)):
            left1, right1 = self.helper(i, i)
            left2, right2 = self.helper(i, i + 1)
            if right1 - left1 > right - left:
                left, right = left1, right1
            if right2 - left2 > right - left:
                left, right = left2, right2

        return s[left:right + 1]

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

没有套路。
按位数颠倒一个整数。考虑负号和溢出。可以用字符串翻转作弊

int reverse(int x) {
    long res=0;
    while (x) {
        res = res * 10 + x % 10;
        x /= 10;
    }

    return res < INT32_MIN || res > INT32_MAX ? 0 : (int) res;
}

8. String to Integer (atoi)

实在无聊的题,就是各种边界条件。这题别做了,浪费时间。

# 3.13->3
# .1->0
# -+9->0
# -000123a123->-123


class Solution:
    def get_num(self, sub_str):
        res = []
        for i in sub_str:
            if i.isdigit():
                res.append(i)
            else:
                break
        if len(res) == 0:
            return 0
        return int(''.join(res))

    def myAtoi(self, s: str) -> int:

        s = s.lstrip()
        if len(s) == 0:
            return 0
        if s[0] == '+':
            res = self.get_num(s[1:])
        elif s[0] == '-':
            res = -self.get_num(s[1:])
        else:
            res = self.get_num(s)

        if res < -2 ** 31:
            return -2 ** 31
        if res > 2 ** 31 - 1:
            return 2 ** 31 - 1

        return res

9. Palindrome Number

数字反转基本就这套路了

  • 改进:跑一半就可以比较了
  • python: x_str == x_str[::-1]
pub fn is_palindrome(x: i32) -> bool {
    if x < 10 && x >= 0 {
        return true;
    }
    if x < 0 || x % 10 == 0 {
        return false;
    }
    let mut num = 0;
    let mut x = x;

    while x > num {
        num = num * 10 + x % 10;
        x = x / 10;
    }
    if x == num || num / 10 == x {
        return true;
    }
    false
}

10. Regular Expression Matching

好题!
套路:

  1. 递归(不是很容易想出)
  2. 递归的某些节点被反复调用。考虑存下来。(就是DP)

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

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        len_s, len_p = len(s), len(p)

        dp = [[None] * (len_p + 2) for _ in range(len_s + 2)]

        def isMatch(i, j):
            if j >= len_p:
                return i >= len_s

            if dp[i][j] is not None:
                return dp[i][j]

            first_match = (i < len_s) and p[j] in {s[i], '.'}
            if len_p - j >= 2 and p[j + 1] == '*':
                dp[i][j] = isMatch(i, j + 2) or (first_match and isMatch(i + 1, j))
                return dp[i][j]
            else:
                dp[i][j] = first_match and isMatch(i + 1, j + 1)
                return dp[i][j]

        return isMatch(0, 0)

c版本

bool isMatch1(char *s, char *p, int len_s, int len_p, char dp[len_s + 2][len_p + 2], int i, int j) {

    if (j >= len_p) {
        return i >= len_s;
    }

    if (dp[i][j] != 2) {
        return dp[i][j];
    }

    bool first_match = (i < len_s) && (p[j] == s[i] || p[j] == '.');
    if (len_p - j >= 2 && p[j + 1] == '*') {
        dp[i][j] = isMatch1(s, p, len_s, len_p, dp, i, j + 2) ||
                   (first_match && isMatch1(s, p, len_s, len_p, dp, i + 1, j));
        return dp[i][j];
    } else {
        dp[i][j] = first_match && isMatch1(s, p, len_s, len_p, dp, i + 1, j + 1);
        return dp[i][j];
    }

}

11. Container With Most Water

好题!

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

13

class Solution(object):
    def romanToInt(self, s):
        roman2num_dict={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        s_list=[roman2num_dict[i] for i in s[::-1]]
        y=0
        while len(s_list)>=2:
            if s_list[0]>s_list[1]:
                y+=s_list.pop(0)-s_list.pop(0)
            else:y+=s_list.pop(0)
        if len(s_list)==1:
            y+=s_list[0]
        return y

14

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res=''
        for idx_j in range(len(strs[0])):
            char=strs[0][idx_j]
            for idx_i in range(1,len(strs)):
                if idx_j>=len(strs[idx_i]):
                    return res
                if strs[idx_i][idx_j]!=char:
                    return res
            res+=char
        return res

15

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        nums.sort()


        def sum2(nums,n):
            his_dict=dict()
            res=list()
            for i,j in enumerate(nums):
                if n-j in his_dict:
                    res.append((-n,n-j,j))
                his_dict[j]=i
            return res

        res=[]
        for i in range(len(nums)-2):
            res.extend(sum2(nums[i+1:],-nums[i]))

        return list(set(res))

16. 3Sum Closest

n-Sum 两种思路:

  1. 复用2sum,加一层遍历。2sum复杂度是n,3sum复杂度是O(n^2)
  2. 2sum还有另一种解法,先排序,然后使用 Container With Most Water 的思路,找解复杂度是 O(n),但排序的复杂度是 O(nlgn),所以2sum复杂度是 O(nlgn),3sum复杂度 O(n^2+nlgn)=O(n^2)
  3. 所以2sum和3sum都可以用这个思路,复杂度一样
  4. 但3Sum Closest显然不能用1了,但可以用2
fn two_closest(nums: &[i32], target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;

    let mut closest = nums[left] + nums[right];
    let mut diff = (closest - target).abs();
    while left < right {
        let sum2 = nums[left] + nums[right];
        if sum2 == target { return target; }
        let abs_sum2 = (sum2 - target).abs();
        if abs_sum2 < diff {
            closest = sum2;
            diff = abs_sum2;
        }
        if sum2 > target {
            right -= 1;
        } else { left += 1; }
    }
    closest
}

impl Solution {
    pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
        let mut nums = nums;
        nums.sort();
        let mut res = nums[0] + nums[1] + nums[2];
        let mut diff = (target - res).abs();
        for idx in 0..nums.len() - 2 {
            let tmp = two_closest(&nums[idx + 1..], target - nums[idx]);
            let tmp_diff = (target - tmp - nums[idx]).abs();
            if tmp_diff < diff {
                diff = tmp_diff;
                res = tmp + nums[idx];
            }
        }
        res
    }
}

17. Letter Combinations of a Phone Number

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

  1. 利用 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)]
    
  2. 递归。这个递归方法要求返回所有遍历到叶节点的路径。而不是成功访问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)
    
  3. 递归(从前往后),另外,如果不考虑空的特殊情况,代码还可以再省一些
    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]
    
  4. 遇到笛卡尔积问题,优先使用这个套路。递归太容易写错,还是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
    
  5. 事实证明,太多骚操作,复用就不方便。简简单单的for循环。(22题复用此代码)
    all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz']
    res=['']
    for i in digits:
     res=[term+char for term in res for char in all_char[int(i)]]
    

18. 4Sum

用递归,nSUM都能做出来


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

考点:

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

基础题,

  1. 遇到链表,第一想到指针
  2. 处理链表,一律先转化成带空头节点的链表。可以减少一些边界条件的代码量,减少错误。
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

addition:其实熟练后可以不用全都加 dummy

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        dummy1=ListNode(None)
        dummy1.next=list1
        curr1,curr2=dummy1,list2
        while curr1.next and curr2:
            if curr1.next.val<=curr2.val:
                curr1=curr1.next
            else:
                tmp1,tmp2=curr1.next,curr2.next
                curr1.next=curr2
                curr2.next=tmp1
                curr1=curr1.next
                curr2=tmp2
        if curr1.next is None:
            curr1.next=curr2
        return dummy1.next

22. Generate Parentheses

f(n-1) 表示 f(n),马上得出思路

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n==1:
            return ['()']
        res=set()
        for term in self.generateParenthesis(n-1):
            tmp=[term[:i]+'()'+term[i:] for i in range(2*n)]
            res.update(tmp)

        return list(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

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

  1. 遇到链表,无脑转成带空头节点的链表
  2. curr.next and curr.next.next 来规避 curr.nextNone 的情况
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        dummy = ListNode(None)
        dummy.next = head
        curr = dummy
        while curr.next and curr.next.next:
            tmp1,tmp2=curr.next,curr.next.next
            tmp1.next=tmp2.next
            curr.next=tmp2
            tmp2.next=tmp1
            curr=tmp1

        return dummy.next

25. Reverse Nodes in k-Group

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

  1. 链表反转是一个基础考点。可以每次把最前面的节点放到后面。也可以每次把最后面的节点放到前面。
  2. 链表上的遍历,立即想到指针。
  3. 链表无脑转为带空头节点的链表。传入 reverse 函数的“子串”是前一级当成dummy来用,
  4. 代码逻辑不要混合,取k个与链表反转独立写。模块化适合考场。
class Solution:
    def reverse(self,dummy,tail):
        # first as dummy
        head=dummy.next
        curr=head
        while curr is not tail:
            tmp=curr.next
            curr.next=tail.next
            tail.next=curr
            curr=tmp
        dummy.next=tail
        return dummy,head

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy=ListNode(None)
        dummy.next=head
        curr=dummy

        i=k
        start=curr
        while curr.next:
            curr=curr.next
            i-=1
            if i==0:
                _,curr=self.reverse(start,curr)
                start=curr
                i=k

        return dummy.next

26. Remove Duplicates from Sorted Array

很简单,也没总结出啥套路,下一题一样。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        curr1,curr2=0,1
        while curr2<len(nums):
            if nums[curr1]<nums[curr2]:
                curr1+=1
                nums[curr1]=nums[curr2]
            curr2+=1
        return curr1+1

27. Remove Element

很简单,不用看了,跟上一个提一样

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        curr1,curr2=0,0
        while curr2<len(nums):
            if nums[curr2]!=val:
                nums[curr1]=nums[curr2]
                curr1+=1
            curr2+=1
        return curr1

28. Implement strStr()

自带的 haystack.find(needle)

KMP算法也可以

29. Divide Two Integers

不用再做了

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign=1
        if dividend<0:
            sign=-sign
            dividend=-dividend
        if divisor<0:
            sign=-sign
            divisor=-divisor

        res=sign*(dividend//divisor)
        if res>2**31-1:
            return 2**31-1
        if res<-2**31:
            return -2**31
        return res

30. Substring with Concatenation of All Words

这个题目有一些特殊情况,例如 ['ab','ba'] 这种可能相互重叠的,还有 ['ab','cd','ab'] 这种重复的。

似乎比较好写的解决方式是每次移动一格,做暴力搜索。

???还没找到更好的方案

import collections

class Solution:
    def is_good(self,text,words_dict,len_word,len_words):
        words_dict=words_dict.copy()
        for i in range(len_words):
            term=text[i*len_word:(i+1)*len_word]
            if term not in words_dict:
                return False
            elif words_dict[term]==0:
                return False

            words_dict[term]-=1
        return True




    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        res=[]
        len_word=len(words[0])
        len_words=len(words)
        curr=0
        words_dict=collections.Counter(words)
        while curr<len(s)-len_word*len_words+1:
            if self.is_good(s[curr:],words_dict,len_word,len_words):
                res.append(curr)
            curr+=1


        return res

31. Next Permutation

想到有个递推公式:

  1. 如果 num[i+1:] 有next,那么整体就有next,迭代为 f(num[i:]) = [num[i]] + f(num[i+1:])
  2. 如果 num[i+1:] 已经没有next,但是 num[i]num[i+1:] 中的某个小。就让两个数字互换,并且 num[i+1:] 重新排序。例如 2; 4, 3, 1 就先换位置,变成 3; 4, 2, 1,然后后者排序,变成 3; 1, 2, 4
  3. 如果以上条件都不满足,说明 num[i:] 是升序,就没有下一个了,按照题目要求,需要返回 nums.sort()

另外:

  • 题目中要求直接替换 nums,下面的代码用了额外空间配合for循环赋值实现。后续改改代码或许可以节省空间
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        def next_perm(nums):
            if len(nums)<=1:
                return False,None

            part1,part2=nums[0],nums[1:]
            has_next,next_nums = next_perm(part2)
            if has_next:
                return True,[part1] + next_nums
            else:
                if part1<max(part2):
                    next_idx=0
                    next_num=101
                    for idx,num in enumerate(part2):
                        if num>part1:
                            if num<next_num:
                                next_idx,next_num=idx,num
                    tmp=part2[next_idx]
                    part2[next_idx]=part1
                    part1=tmp
                    part2.sort()
                    return True,[part1]+part2
            return False,None

        has_next,next_nums=next_perm(nums)
        if has_next:
            for i in range(len(nums)):
                nums[i] = next_nums[i]
        else:
            nums.sort()

32. Longest Valid Parentheses

  • 两个计数器,left表示当前序列中,左括号数量。right表示当前序列中,右括号数量。
  • 如果left=right,更新一次最大值
  • 如果left<right,开始一个新的序列
  • (关键)以上忽略了 (() 这种情况,只需要把上面的算法从右向左再跑一次即可
class Solution:
    def helper(self,s,mode):
        left,right=0,0
        res=0
        for char in s:
            if char==mode:
                left+=1
            else:
                right+=1

            if right>left:
                left,right=0,0
            if right==left:
                res=max(res,left*2)
        return res    

    def longestValidParentheses(self, s: str) -> int:
        res1=self.helper(s,mode='(')
        res2=self.helper(s[::-1],mode=')')
        return max(res1,res2)

33. Search in Rotated Sorted Array

n种情况吧。(感觉下面的代码还可以优化,不过大体思路就是这样了)

class Solution:
    # def find_pivot(self,nums):
    #     left,right=0,len(nums)-1
    #     head,tail=nums[left],nums[right]
    #     mid_idx=(left+right)//2

        # return 0
    def search(self, nums: List[int], target: int) -> int:
        if nums[0]==target:
            return 0

        left,right=0,len(nums)-1

        if nums[0]<=target:
            while left<right:
                mid=(left+right)//2
                if nums[mid]<target:
                    if nums[mid]<nums[0]:
                        right=mid-1
                    else:
                        left=mid+1
                elif nums[mid]>target:
                    right=mid-1
                else:
                    return mid

        else:
            while left<right:
                mid=(left+right)//2

                if nums[mid]<target:
                    left=mid+1
                elif nums[mid]>target:
                    if nums[mid]>=nums[0]:
                        left=mid+1
                    else:
                        right=right-1
                else:
                    return mid



        mid=left
        if nums[mid]==target:
            return mid


        return -1

34. Find First and Last Position of Element in Sorted Array

先用二分法找左边,然后用二分法找右边。

  • 应该有合起来找的方法,但是写的慢
  • 下面的代码也有优化的空间
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res=[-1,-1]

        if len(nums)==0:
            return res


        # 寻找左边
        left,right=0,len(nums)-1
        while left<right:
            mid=(left+right)//2
            if nums[mid]>=target:
                right = mid-1
            else:
                left = mid+1

        if nums[left]<target:
            if left==len(nums)-1:
                return [-1,-1]
            if nums[left+1]==target:
                res[0]=left+1
            else:
                return [-1,-1]
        elif nums[left]==target:
            res[0]=left
        else:
            return [-1,-1]


        # 寻找右边
        left,right=res[0],len(nums)-1
        while left<right:
            mid=(left+right)//2
            if nums[mid]<=target:
                left=mid+1
            else:
                right=mid-1

        if nums[left]>target:
            res[1]=left-1
        else:
            res[1]=left


        return res

35. Search Insert Position

基本的二分法

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left,right=0,len(nums)-1
        while left<right:
            mid=(left+right)//2
            if nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid-1
            else:
                return mid

        if nums[left]<target:
            return left+1
        else:
            return left

36. Valid Sudoku

暴力解法

def is_good(lst):
    tmp=[i for i in lst if i!='.']
    return len(tmp)==len(set(tmp))

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for line in board:
            if not is_good(line):
                return False

        for i in range(9):
            col=[board[j][i] for j in range(9)]
            if not is_good(col):
                return False

        for i in range(3):
            for j in range(3):
                block=[board[3*i+i1][3*j+j1] for i1 in range(3) for j1 in range(3)]
                if not is_good(block):
                    return False
        return True

改进:可以用一个整数来表示列表,例如 [...,1,0,1,0] 表示2和4 存在,简写成 1010...

  • 一个新数 3 是否在已有呢?取决于 ...1010 & (1<<3) 是否为0
  • 如何更新呢? ...1010 | (1<<3)
  • 答案如下:
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row, col, box = [0] * 9, [0] * 9, [0] * 9
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    continue
                box_idx = (i // 3) * 3 + (j // 3)
                num = 1 << (ord(board[i][j]) + 48)
                if row[i] & num or col[j] & num or box[box_idx] & num:
                    return False
                row[i] |= num
                col[j] |= num
                box[box_idx] |= num

        return True

37. Sudoku Solver

练递归的好题!

用 set 来做,这个最易懂(跟我总结的公式有差别)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:

        nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
        row = [set() for _ in range(9)]
        col = [set() for _ in range(9)]
        block = [[set() for _ in range(3)] for _ in range(3)]  # 3*3
        blank = []

        # 初始化,按照行、列、宫 分别存入哈希表
        for i in range(9):
            for j in range(9):
                ch = board[i][j]
                if ch == ".":
                    blank.append((i, j))
                else:
                    row[i].add(ch)
                    col[j].add(ch)
                    block[i//3][j//3].add(ch)

        len_blank=len(blank)
        def dfs(n):
            if n == len_blank:
                return True
            i, j = blank[n]
            rst = nums - row[i] - col[j] - block[i//3][j//3]  # 可行解
            if not rst:
                return False
            for num in rst:
                board[i][j] = num
                row[i].add(num)
                col[j].add(num)
                block[i//3][j//3].add(num)
                if dfs(n+1):
                    return True
                row[i].remove(num)
                col[j].remove(num)
                block[i//3][j//3].remove(num)

        dfs(0)

用位运算优化加速

  • row[i], col[j], block[i//3][j//3] 都是int类型,第k位为1,表示 k+1 出现过
  • (~num) & 0x1ff,这个数的第 k 位为1,代表 k+1 没出现过,也就是k+1可以填入格子。(& 0x1ff 是因为高于9的位没有意义)
  • b & (−b) = b & (~b + 1) 可以保留最低的 1,其它全变为0
  • digit = bin(digitMask).count("0") - 1 ???用来计算最低位的1在第几位
  • b ^ (b & (-b)) = b & (b - 1) 可以消去最低位的1,可以以此来枚举下一个 1

官方答案

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def flip(i: int, j: int, digit: int):
            line[i] ^= (1 << digit)
            column[j] ^= (1 << digit)
            block[i // 3][j // 3] ^= (1 << digit)
          line = [0] * 9


        column = [0] * 9
        block = [[0] * 3 for _ in range(3)]
        valid = [False]
        spaces = list()

        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i, j))
                else:
                    digit = int(board[i][j]) - 1
                    flip(i, j, digit)

        def dfs(pos: int):
            if pos == len(spaces):
                valid[0] = True
                return

            i, j = spaces[pos]
            mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
            while mask:
                digitMask = mask & (-mask)
                digit = bin(digitMask).count("0") - 1
                flip(i, j, digit)
                board[i][j] = str(digit + 1)
                dfs(pos + 1)
                flip(i, j, digit)
                mask &= (mask - 1)
                if valid[0]:
                    return
        dfs(0)

38. Count and Say

简单,一遍过

class Solution:
    def countAndSay(self, n: int) -> str:
        if n==1:
            return '1'

        tmp=self.countAndSay(n-1)
        res=[]
        curr_idx=0
        curr_cnt=0

        curr=tmp[curr_idx]

        for idx,char in enumerate(tmp):
            if char!=curr:
                res.append(str(curr_cnt)+curr)
                curr_cnt=0
                curr=tmp[idx]

            curr_cnt+=1

        res.append(str(curr_cnt)+curr)

        return ''.join(res)

39. Combination Sum

这题也简单,不过需要注意 [2,2,3][2,3,2] 算是同一个解,因此多引入一个变量,以判断和防止重复计入。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        candidates.sort()
        res_all=[]
        def comb_sum(candidates,last_used,target,res):
            if target<0:
                return
            if target==0:
                res_all.append(res)
                return
            if target>0:
                for candidate in candidates:
                    if candidate<last_used:
                        continue
                    last_used=candidate
                    comb_sum(candidates,last_used,target-candidate,res+[candidate])

        comb_sum(candidates,0,target,list())

        return res_all

40. Combination Sum II

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        candidates.sort()
        res_all=[]
        def comb_sum(candidates,target,res):
            if target<0:
                return
            if target==0:
                res_all.append(res)
                return

            if not candidates:
                return

            # if target>0:
            for idx,candidate in enumerate(candidates):
                new_candidates=candidates[idx+1:] if idx<len(candidates)-1 else []
                comb_sum(new_candidates,target-candidate,res+[candidate])

        comb_sum(candidates,target,[])

        # 去重
        res_all=set([tuple(i) for i in res_all])
        res_all=list([list(i) for i in res_all])

        return res_all

上面的答案有重复搜索,改为这个

import collections

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        candidates = [[i,j] for i,j in collections.Counter(candidates).items()]
        candidates.sort()

        res_all=[]
        def comb_sum(candidates,target,res):
            if target<0:
                return
            if target==0:
                res_all.append(res)
                return

            if not candidates:
                return

            # if target>0:
            for idx,[candidate,candidate_cnt] in enumerate(candidates):
                if candidate_cnt==0:
                    continue

                new_candidate=candidates[idx:]
                candidates[idx][1]-=1
                comb_sum(new_candidate,target-candidate,res+[candidate])
                candidates[idx][1]+=1


        comb_sum(candidates,target,[])
        return res_all

41. First Missing Positive

算作弊了

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums=list(set(nums))
        nums.sort()
        res=1
        for i in nums:
            if i<=0:
                continue
            if i==res:
                res+=1
                continue
            else:
                return res
        return res

42. Trapping Rain Water

直接思路

  1. 左隔板为 left,寻找右边第一个大于 left 的隔板,记为 right
  2. 如果右边都小小于 left,就寻找右边最大的隔板,记为left
  3. 赋值 right = left,继续迭代。

想到之前有个隔板题,是从左到右遍历一次,然后从右往左遍历一次。因此想到,先把水填满,然后看看哪些流出去了。

(代码还可以优化)

class Solution:
    def trap(self, height: List[int]) -> int:
        max_height=max(height)
        total_water=max_height*len(height)-sum(height)
        left_min=-1
        for num in height:
            left_min=max(left_min,num)
            total_water-=(max_height-left_min)

        right_min=-1
        for num in height[::-1]:
            right_min=max(right_min,num)
            total_water-=(max_height-right_min)

        return total_water

43. Multiply Strings

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        return str(int(num1)*int(num2))

44. Wildcard Matching

各种超时

"babbbbaabababaabbababaababaabbaabababbaaababbababaaaaaabbabaaaabababbabbababbbaaaababbbabbbbbbbbbbaabbb"
"b**bb**a**bba*b**a*bbb**aba***babbb*aa****aabb*bbb***a"

超时的原因是有些地方被反复计算了,用 functools.lru_cache 做缓存(击败5%)

import functools


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @functools.lru_cache(maxsize=None, typed=False)
        def is_match(text,pattern):
            if pattern=='':
                return text==''

            if pattern=='*':
                return True

            if text=='':
                return False


            if pattern[0]=='?':
                return is_match(text[1:],pattern[1:])
            elif pattern[0]=='*':
                return is_match(text,pattern[1:]) or is_match(text[1:],pattern)
            else:
                return text[0]==pattern[0] and is_match(text[1:],pattern[1:])

        p_list=[]
        last_is_star=False
        for i in p:
            if i=='*':
                if last_is_star:
                    last_is_star=True
                    continue
                else:
                    p_list.append(i)
                    last_is_star=True
            else:
                p_list.append(i)
                last_is_star=False

        p=''.join(p_list)


        return is_match(s,p)

下面这个用了dp方法,不会超时

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for i in range(1, n + 1):
            if p[i - 1] == '*':
                dp[0][i] = True
            else:
                break

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
                elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m][n]

45. Jump Game II

动态规划基本题目,注意0

class Solution:
    def jump(self, nums: List[int]) -> int:
        len_nums=len(nums)
        dp=[0]*len_nums

        for i in range(len(nums)-2,-1,-1):
            # print(dp)
            if nums[i]==0:
                dp[i]=100000
            else:
                dp[i]=min(dp[i+1:i+nums[i]+1])+1

        return dp[0]

46. Permutations

用工具很方便

itertools.permutations(nums)

工具和递归的效率差不多,

  • 对nums做回溯(+递归),sep 左边代表已经填入的,右边代表待填入的
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        def permute_func(sep):
            if sep==len(nums):
                return res.append(nums.copy())

            for idx in range(sep,len(nums)):
                nums[idx],nums[sep]=nums[sep],nums[idx]
                permute_func(sep+1)
                nums[idx],nums[sep]=nums[sep],nums[idx]


        len_nums=len(nums)
        res=[]
        permute_func(0)
        return res

47. Permutations II

照抄上一题,在结果中去重:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res=set()
        len_nums=len(nums)
        def permute(sep):
            if sep==len_nums:
                res.add(tuple(nums))

            for idx in range(sep,len_nums):
                nums[idx],nums[sep]=nums[sep],nums[idx]
                permute(sep+1)
                nums[idx],nums[sep]=nums[sep],nums[idx]

        permute(0)
        return [list(i) for i in res ]

!!!还有性能更高的做法,待研究

48. Rotate Image

第一次不是很容易想到这个:

  • 旋转90度不容易,但是
  • 上下镜像、左右镜像、主对角线镜像是容易实现的
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n=len(matrix)


        for i in range(n):
            for j in range(i):
                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]

        for i in range(n):
            matrix[i]=matrix[i][::-1]

49. Group Anagrams

简单,sort即可

import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res=collections.defaultdict(list)
        for term in strs:
            res[''.join(sorted(term))].append(term)
        return list(res.values())

50. Pow(x, n)

x**n (开个玩笑)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def my_pow(x,n):
            if n==1:
                return x
            if n==0:
                return 1
            if n==-1:
                return 1/x

            tmp=my_pow(x,n//2)
            return tmp*tmp*my_pow(x,n%2)

        return my_pow(x,n)

递归调用会使用栈空间,因此,时间复杂度 $\log n$,空间复杂度 $\log n$

用位运算,可以把空间复杂度降低到 $\log n$,本质上是计算 $2^{k0} \times 2^{k1} \times 2^{k2} \times …$

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def my_pow(n):
            res=1
            val=x
            while n:
                n,k=divmod(n,2)
                if k:
                    res*=val
                val*=val
            return res
        return my_pow(n) if n>=0 else 1/my_pow(-n)

51. N-Queens

回溯法典型题目,!!! 多练习几遍

class Solution:
    def solveNQueens(self, n: int):
        col = [0] * n
        diagonal_1 = [0] * (2 * n - 1) # 副对角线
        diagonal_2 = [0] * (2 * n - 1) # 对角线
        solution = [[0] * n for i in range(n)]
        res = []
        chars = {0: '.', 1: 'Q'}

        def n_queens(col, diagonal_1, diagonal_2, solution, i):
            if i == n:
                res.append([''.join([chars[i] for i in line]) for line in solution])
                return

            for j in range(n):
                if col[j] or diagonal_1[i + j] or diagonal_2[i - j + n - 1]:
                    continue

                col[j] = diagonal_1[i + j] = diagonal_2[i - j + n - 1] = solution[i][j] = 1
                n_queens(col, diagonal_1, diagonal_2, solution, i + 1)
                col[j] = diagonal_1[i + j] = diagonal_2[i - j + n - 1] = solution[i][j] = 0

        n_queens(col, diagonal_1, diagonal_2, solution, 0)

        return res

52. N-Queens II

跟上面的题一样

class Solution:
    def totalNQueens(self, n: int) -> int:
        res=[0]

        cols=[0]*n
        diag_1=[0]*(2*n-1)
        diag_2=[0]*(2*n-1)

        def n_queens(cols,diag_1,diag_2,i):
            if i==n:
                res[0]+=1
                return

            for j in range(n):
                if cols[j] or diag_1[i+j] or diag_2[i-j+n-1]:
                    continue
                cols[j]=diag_1[i+j] =diag_2[i-j+n-1]=1
                n_queens(cols,diag_1,diag_2,i+1)
                cols[j]=diag_1[i+j] =diag_2[i-j+n-1]=0

        n_queens(cols,diag_1,diag_2,0)

        return res[0]

53. Maximum Subarray

好题!

不容易想出来:

  • f(i) 定义为:第 i 位结尾的最大序列,因此 f(i) = max(f(i-1)+nums[i], nums[i])
  • 然后求 max(f(i)) 即可
  • 下面的代码中,把 f(i) 写到 nums 中,以节省内存空间
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            if nums[i-1]>0:
                nums[i]=nums[i-1]+nums[i]

        return max(nums)

54. Spiral Matrix

  • 想到像削苹果一样,每次旋转90度,削头
  • list(zip(*matrix)) 是按照主对角线反转,配合 ::-1 可以达到逆时针旋转。(这一步参考48题)
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            # 削头(第一层)
            res += matrix.pop(0)
            # 将剩下的逆时针转九十度,等待下次被削
            matrix = list(zip(*matrix))[::-1]
        return res

!!!改进为 one line,非常惊艳!

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

如果pop结尾,会快很多。上下颠倒,每次削脚,然后顺时针旋转。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        matrix.reverse()
        res=[]
        while matrix:
            res.extend(matrix.pop())
            matrix.reverse()
            matrix=list(zip(*matrix))
        return res

55. Jump Game

普通的dp方法

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp=[False]*len(nums)
        dp[0]=True
        for idx,num in enumerate(nums):
            if dp[idx]:
                if idx+num+1>=len(nums):
                    return True
                for i in range(idx+1,idx+num+1):
                    dp[i]=True

        return dp[-1]

不知道能不能改进

56. Merge Intervals

简单,按照字面意思做

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        res=[intervals[0]]

        for i in range(1,len(intervals)):
            if res[-1][1]>=intervals[i][0]:
                if res[-1][1]<intervals[i][1]:
                    res[-1][1]=intervals[i][1]
            else:
                res.append(intervals[i])

        return res

##

直白的if-else

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            return [newInterval]
        res=[]

        has_insert_new=False
        for interval in intervals:
            if interval[1]<newInterval[0]:
                res.append(interval)
            elif interval[0]>newInterval[1]:
                if not has_insert_new:
                    res.append(newInterval)
                    has_insert_new=True
                res.append(interval)
            else:
                if not has_insert_new:
                    res.append(newInterval)
                    has_insert_new=True
                newInterval[0]=min(newInterval[0],interval[0])
                newInterval[1]=max(newInterval[1],interval[1])

        if not has_insert_new:
            res.append(newInterval)

        return res

O(n) 复杂度

感觉直接抄上一题也就 nlog(n) 复杂度

58. Length of Last Word

class Solution:
    def lengthOfLastWord(self, s: str) -> int:

        meet_word=False
        res=0
        for idx in range(len(s)-1,-1,-1):
            if s[idx]==' ':
                if meet_word:
                    return res
                else:
                    continue
            else:
                meet_word=True
                res+=1
        return res

60. Permutation Sequence

下面是抄的,太漂亮了

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factorial=[1]
        for i in range(1,n):
            factorial.append(factorial[-1]*i)

        res=[]
        k-=1
        nums=list(range(1,n+1))
        for mul in factorial[::-1]:
            div,k=divmod(k,mul)
            res.append(str(nums.pop(div)))

        return ''.join(res)

61. Rotate List

本来想直接写个耦合性高但性能好的解,发现还是解耦更好

class Solution:
    def get_len(self,head):
        length=0
        curr=head
        while curr:
            length+=1
            curr=curr.next
        return length

    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None:
            return None
        dummy=ListNode(val=None,next=head)
        curr1=curr2=dummy

        length=self.get_len(head)
        k=k%length
        for _ in range(k):
            curr2=curr2.next

        while curr2.next is not None:
            curr1=curr1.next
            curr2=curr2.next

        if curr1 is dummy:
            return dummy.next
        curr2.next=dummy.next
        dummy.next=curr1.next
        curr1.next=None
        return dummy.next

##

阶乘

class Solution:

    def uniquePaths(self, m: int, n: int) -> int:
        perm=[0]*(m+n-1)
        perm[0]=1
        for k in range(1,m+n-1):
            perm[k]=k*perm[k-1]

        return int(perm[m+n-2]/perm[m-1]/perm[n-1])

63. Unique Paths II

dfs,需要注意 要加cache (也就是 dp)

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        h,w=len(obstacleGrid),len(obstacleGrid[0])
        if obstacleGrid[0][0] or obstacleGrid[h-1][w-1]:
            return 0

        visited={(0,0):1}
        def cal_path(idx_i,idx_j):
            if obstacleGrid[idx_i][idx_j]:
                return 0

            if (idx_i,idx_j) in visited:
                return visited[(idx_i,idx_j)]

            if idx_i==0:
                part_up=0
            else:
                part_up=cal_path(idx_i-1,idx_j)

            if idx_j==0:
                part_left=0
            else:
                part_left=cal_path(idx_i,idx_j-1)

            visited[(idx_i,idx_j)]=part_up+part_left
            return visited[(idx_i,idx_j)]

        cal_path(h-1,w-1)
        return visited[(h-1,w-1)]

##

上一个题用了 dfs+dp,这题用 bfs

class Solution:
    def minPathSum(self, grid) -> int:
        h,w=len(grid),len(grid[0])
        queue={(0,0)}
        visited={(0,0):grid[0][0]}

        while queue:
            new_queue=set()
            for point in queue:
                for move in ((1,0),(0,1)):
                    next_point=point[0]+move[0],point[1]+move[1]
                    if next_point[0]<h and next_point[1]<w:
                        visited[next_point]=min(
                            visited.get(next_point,10**8),
                            visited[point]+grid[next_point[0]][next_point[1]]
                        )
                        new_queue.add(next_point)
            queue=new_queue

        return visited[(h-1,w-1)]

65~69

65-别做了

66-直白

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        cap=1
        for idx in range(len(digits)-1,-1,-1):
            digits[idx]+=cap
            cap,digits[idx]=divmod(digits[idx],10)
            if cap==0:
                break

        if cap==1:
            digits=[1]+digits


        return digits

67-作弊

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

68-别做了

69-作弊 int(sqrt(x))

其实可以用二分法

class Solution:
    def mySqrt(self, x: int) -> int:
        left,right=0,x
        while left<right:
            mid=(left+right)//2
            # print(left,right,mid)
            if mid*mid<x:
                left=mid+1
            elif mid*mid>x:
                right=mid-1
            else:
                return mid

        if (left-1)*(left-1)<x<left*left:
            return left-1
        else:
            return left

70

dfs+dp

class Solution:
    def climbStairs(self, n: int) -> int:

        visited={0:1,1:2}
        def dfs(i):
            if i in visited:
                return visited[i]
            cnt=dfs(i-1)+dfs(i-2)
            visited[i]=cnt
            return cnt

        return dfs(n-1)

71

别做

72

  • 这类题基本上都是递归+dp了,
  • 一开始思路卡在了增加一个字母怎样做dp,看答案发现第二个串删除一个字母相当于第一个串增加一个字母
  • 然后就变成简单题了
class Solution:

    def minDistance(self, word1: str, word2: str) -> int:
        len1, len2 = len(word1), len(word2)

        visited = dict()

        def min_dist(i, j):
            if (i, j) in visited:
                return visited[(i, j)]

            if i == len1:
                dist = len2 - j

            elif j == len2:
                dist = len1 - i

            elif word1[i] == word2[j]:
                dist = min_dist(i + 1, j + 1)
            else:
                dist = min(min_dist(i + 1, j) + 1, min_dist(i, j + 1) + 1, min_dist(i + 1, j + 1) + 1)

            visited[(i, j)] = dist
            return dist

        return min_dist(0, 0)

75. Sort Colors

作弊 nums.sort()

##

双指针+need,这类的题需要总结一下

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need_dict = dict()
        for char in t:
            if char in need_dict:
                need_dict[char] += 1
            else:
                need_dict[char] = 1

        curr1 = curr2 = 0
        res_len, res_s = len(s) + 1, ''
        if s[0] in need_dict:
            need_dict[s[0]] -= 1
        while curr1 < len(s) and curr2 < len(s):
            if all(i <= 0 for i in need_dict.values()):
                if curr2 - curr1 < res_len:
                    res_len = curr2 - curr1
                    res_s = s[curr1:curr2 + 1]

                if s[curr1] in need_dict:
                    need_dict[s[curr1]] += 1
                curr1 += 1

            else:
                curr2 += 1
                if curr2 == len(s):
                    break
                if s[curr2] in need_dict:
                    need_dict[s[curr2]] -= 1

        return res_s

77. Combinations

组合基础题,必背!

dfs+dp

class Solution:
    def combine(self, n: int, k: int):

        cache = dict()

        def dfs(n, k):
            if (n, k) in cache:
                return cache[(n, k)]

            if k > n or k == 0:
                res = [[]]
            elif k == n:
                res = [list(range(1,n+1))]
            else:
                res = [i + [n] for i in self.combine(n - 1, k - 1)] + self.combine(n - 1, k)
            cache[(n, k)] = res
            return res

        return dfs(n, k)

##

放回抽样基础题,必背!

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res=[[]]
        for i in nums:
            res=[item+next_choice for item in res for next_choice in ([],[i])]

        return res

找一个解即可,dfs

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        h,w=len(board),len(board[0])

        res=[False]

        def dfs(i,j,k):
            if res[0]:
                return

            if board[i][j]!=word[k]:
                return

            if k==len(word)-1:
                res[0]=True
                return

            for move_i,move_j in ((-1,0),(1,0),(0,1),(0,-1)):
                new_i,new_j=i+move_i,j+move_j
                if 0<=new_i<h and 0<=new_j<w:
                    char,board[i][j]=board[i][j],None

                    dfs(new_i,new_j,k+1)
                    board[i][j]=char

        for i in range(h):
            for j in range(w):
                dfs(i,j,0)
        return res[0]

80. Remove Duplicates from Sorted Array II

双指针,作为练习题

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        curr1=curr2=0

        tmp_dict=dict()

        while curr2<len(nums):
            if nums[curr2] not in tmp_dict:
                nums[curr1]=nums[curr2]
                tmp_dict[nums[curr1]]=1
                curr1+=1
                curr2+=1
            elif tmp_dict[nums[curr2]]==1:
                nums[curr1]=nums[curr2]
                tmp_dict[nums[curr1]]=2
                curr1+=1
                curr2+=1
            else:
                curr2+=1

        return curr1

82. Remove Duplicates from Sorted List II

遇到对节点有增、删的,先无脑加 dummy

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy=ListNode(val=None,next=head)
        curr1=dummy
        while curr1.next:
            if curr1.next.next:
                if curr1.next.val==curr1.next.next.val:
                    curr2=curr1.next
                    while curr2 and curr2.val==curr1.next.val:
                        curr2=curr2.next
                    curr1.next=curr2
                    continue
            curr1=curr1.next

        return dummy.next

83. Remove Duplicates from Sorted List

同上

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        dummy=ListNode(val=None,next=head)
        curr=dummy.next
        while curr.next:
            if curr.next.val==curr.val:
                curr.next=curr.next.next
            else:
                curr=curr.next
        return dummy.next

84. Largest Rectangle in Histogram

这题很难,看了很多答案才明白

想象锯木板,如果木板都是递增的那我很开心,如果突然遇到一块木板i矮了一截,那我就先找之前最戳出来的一块(其实就是第i-1块),计算一下这个木板单独的面积,然后把它锯成次高的,这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高,那我继续单独计算这个次高木板的面积(应该是第i-1和i-2块),再把它俩锯短。直到发觉不需要锯就比第i块矮了,那我继续开开心心往右找更高的。

当然为了避免到了最后一直都是递增的,所以可以在最后加一块高度为0的木板。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res=0
        heights.append(0)
        for i,height in enumerate(heights):
            for j in range(i-1,-1,-1):
                if heights[j] > height:
                    res = max(res,heights[j]*(i-j))
                    heights[j] = height
                else:
                    break

        return res

还有性能上进一步优化的空间:被锯掉的部分其实不用保存了,下次也不用遍历它。不过需要额外一个list来保存index信息。内存消耗多了,时间消耗少了。

86. Partition List

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        dummy = ListNode(next=head)
        dummy_bigger = ListNode()
        curr1 = dummy
        curr2 = dummy_bigger

        while curr1.next:
            if curr1.next.val < x:
                curr1 = curr1.next
            else:
                curr2.next = curr1.next
                curr2 = curr2.next
                curr1.next = curr1.next.next
                curr2.next=None
        curr1.next = dummy_bigger.next
        return dummy.next

87. Scramble String

这题很难想出来,但是想出来后很容易

class Solution:
    @lru_cache(None)
    def isScramble(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2) or s1 == '' or sorted(s1) != sorted(s2): return False
        if s1 == s2: return True
        for i in range(1, len(s1)):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]): return True
            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]): return True
        return False

88. Merge Sorted Array

作弊

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(n):
            nums1[i+m]=nums2[i]
        nums1.sort()

89. Gray Code

背下来

gray2real(这个还需要调整):

b = gray_code.cumsum(axis=1) % 2
mask = np.logspace(start=1, stop=len_gray_code, base=0.5, num=len_gray_code)
return (b * mask).sum(axis=1) / mask.sum()

real2gray:

gray[i] = i ^ (i>>1)

90. Subsets II

这个题

  1. 顺序交换算是同一个
  2. 要去重

思路就是基本的无放回抽样,一分钟写出来

import collections
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums = collections.Counter(nums)
        res = [[]]

        for num, cnt in nums.items():
            tmp = [[num] * i for i in range(cnt + 1)]
            res = [line + k for line in res for k in tmp]


        return res

91. Decode Ways

class Solution:
    def __init__(self):
        self.valid_nums1 = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
        self.valid_nums2 = {'22', '24', '16', '18', '10', '11', '12', '17', '23', '21', '19', '20', '14', '13', '25',
                            '15', '26'}

    def numDecodings(self, s: str) -> int:

        visited = dict()

        def dfs(s):
            if s in visited:
                return visited[s]
            res = 0
            if len(s) == 1:
                if s in self.valid_nums1:
                    res += 1
            elif len(s) == 2:
                res = 0
                if s in self.valid_nums2:
                    res += 1

                if s[0] in self.valid_nums1 and s[1] in self.valid_nums1:
                    res += 1
            else:

                if s[0] in self.valid_nums1:
                    res += dfs(s[1:])
                if s[:2] in self.valid_nums2:
                    res += dfs(s[2:])
                visited[s] = res
            return res

        return dfs(s)

93. Restore IP Addresses

dfs+dp,会背了

class Solution:
    num_1 = {'8', '1', '2', '3', '9', '4', '0', '5', '7', '6'}
    num_2 = {'62', '57', '34', '32', '47', '60', '65', '71', '75', '92', '52', '91', '68', '99', '28', '86', '94', '64',
             '85', '70', '87', '76', '30', '21', '79', '10', '33', '67', '56', '14', '31', '41', '88', '45', '54', '37',
             '12', '46', '20', '77', '27', '97', '49', '58', '51', '18', '50', '69', '96', '74', '36', '93', '59', '61',
             '29', '82', '22', '90', '84', '43', '42', '15', '24', '16', '26', '23', '73', '98', '38', '55', '66', '25',
             '48', '63', '72', '35', '13', '81', '95', '44', '53', '80', '39', '78', '89', '40', '17', '11', '19', '83'}

    num_3 = {'218', '237', '101', '118', '239', '186', '122', '126', '175', '184', '208', '156', '232', '245', '219',
             '211', '216', '169', '125', '133', '167', '197', '136', '152', '123', '174', '188', '231', '236', '114',
             '246', '148', '207', '234', '131', '150', '177', '144', '159', '113', '204', '129', '222', '130', '155',
             '171', '230', '242', '238', '124', '196', '128', '235', '138', '100', '137', '194', '140', '111', '105',
             '199', '201', '249', '170', '200', '193', '109', '223', '127', '203', '247', '165', '153', '185', '224',
             '221', '158', '139', '183', '252', '253', '190', '151', '157', '206', '143', '146', '213', '187', '147',
             '163', '226', '102', '110', '198', '145', '179', '182', '161', '180', '189', '116', '142', '244', '251',
             '115', '120', '243', '112', '132', '250', '104', '103', '176', '225', '214', '119', '154', '134', '233',
             '168', '255', '240', '121', '108', '229', '254', '141', '217', '202', '191', '135', '215', '181', '209',
             '212', '160', '210', '228', '172', '149', '162', '107', '117', '248', '220', '192', '178', '227', '241',
             '164', '205', '173', '106', '166', '195'}

    def restoreIpAddresses(self, s: str):

        cache = dict()

        def dfs(s, i):
            if (s, i) in cache:
                return cache[(s, i)]

            res = []
            if i == 1:
                if len(s) == 1 and s in self.num_1:
                    res = [s]
                elif len(s) == 2 and s in self.num_2:
                    res = [s]
                elif len(s) == 3 and s in self.num_3:
                    res = [s]
            elif len(s) == 0:
                res = []
            else:

                if s[0] in self.num_1:
                    res.extend([s[0] + '.' + item for item in dfs(s[1:], i - 1)])
                if s[:2] in self.num_2:
                    res.extend([s[:2] + '.' + item for item in dfs(s[2:], i - 1)])
                if s[:3] in self.num_3:
                    res.extend([s[:3] + '.' + item for item in dfs(s[3:], i - 1)])

            cache[(s, i)] = res
            return res

        return dfs(s, 4)

96. Unique Binary Search Trees

递归,结果为左子树的情况数乘以右子树的情况树 f(n)= f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(1)

class Solution:
    def numTrees(self, n: int) -> int:
        cache=[None]*(n+1)
        def func(n):
            if cache[n] is not None:
                return cache[n]
            if n==0:
                res=1
            else:    
                res=0       
                for i in range(n):
                    res+=func(i)*func(n-i-1)
            cache[n]=res
            return res

        return func(n)

95. Unique Binary Search Trees II

思路同上,dfs+cache

class Solution:
    def generateTrees(self, n: int):

        cache = dict()

        def myfunc(left, right):
            if (left, right) in cache:
                return cache[(left, right)]
            if right < left:
                res = [None]
            else:
                res = []
                for i in range(left, right + 1):
                    for left_node in myfunc(left, i - 1):
                        for right_node in myfunc(i + 1, right):
                            root = TreeNode(val=i)
                            root.left = left_node
                            root.right = right_node
                            res.append(root)


            cache[(left, right)] = res
            return res

        return myfunc(1, n)

97. Interleaving String

dfs+cache

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:

        res = [False]
        cache = set()

        def dfs(s1, s2, s3):
            if res[0]:
                return
            if (s1, s2, s3) in cache:
                return
            else:
                cache.add((s1, s2, s3))
            if len(s1) + len(s2) != len(s3):
                return

            if len(s1) == 0:
                if s2 == s3:
                    res[0] = True
                    return
            elif len(s2) == 0:
                if s1 == s3:
                    res[0] = True
                    return

            else:
                if s1[0] == s3[0]:
                    dfs(s1[1:], s2, s3[1:])
                if s2[0] == s3[0]:
                    dfs(s1, s2[1:], s3[1:])

        dfs(s1, s2, s3)
        return res[0]

98. Validate Binary Search Tree

  • 还是 dfs,
  • 因为是树,所以无须cache
  • 貌似是中序遍历???它们的内在关系之后研究一下
  • “左子树的所有节点都小于此节点”等价于“左子树的最大节点小于父节点”
class Solution:
    int_min = -2 ** 32
    int_max = 2 ** 32

    def isValidBST(self, root: TreeNode) -> bool:
        res = [True]

        def dfs(node, parent_min, parent_max):
            if res[0] is False:
                return

            if node is None:
                return

            if not parent_min < node.val < parent_max:
                res[0] = False
                return

            dfs(node.left, parent_min, node.val)
            dfs(node.right, node.val, parent_max)

        dfs(root, self.int_min, self.int_max)
        return res[0]

99. Recover Binary Search Tree

很直白的步骤:

  1. inorder 得到一个本应该递增的序列
  2. 在 inorder 结果上找到不对的节点
  3. 交换
class Solution:
    def inorder(self, root):
        return [] if (root is None) else self.inorder(root.left) + [root.val] + self.inorder(root.right)

    def recoverTree(self, root) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        nums = self.inorder(root)
        wrong_nodes = []
        nums_sorted = sorted(nums)
        for i in range(len(nums)):
            if nums[i] != nums_sorted[i]:
                wrong_nodes.append(i)

        val1, val2 = nums[wrong_nodes[0]], nums[wrong_nodes[1]]

        def dfs(node):
            if node is None:
                return node
            if node.val == val1:
                node.val = val2
            elif node.val == val2:
                node.val = val1

            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return root

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