Leetcode 30 训练记录 (基本算法)

发表于 更新于 分类于

把30篇博文合并成一篇，记录 leetcode 的30天训练以及结果

第一天
两数之和

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if len(nums) < 2: return []
        dic = {}
        for i, e in enumerate(nums):
            if e in dic:
                return [dic[e], i]
            dic[target - e] = i

第二天
已排序列表去重

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        _ = len(nums)
        if _ < 2: return _
        i = 0
        for j xrange(1,_):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i+1

第三天
删除元素

1
2
3
4
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums: nums.remove(val)
        return len(nums)

第四天
三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        l = len(nums)
        if l < 3: return []
        nums.sort()
        res = []
        for pt in range(l - 2):
            if nums[pt] > 0: break
            if pt > 0 and nums[pt] == nums[pt - 1]: continue
            lf, rg = pt + 1, l - 1
            while lf < rg:
                _ = nums[lf] + nums[rg] + nums[pt]
                if _ < 0:
                    lf += 1
                elif _ > 0:
                    rg -= 1
                else:
                    res.append([nums[lf], nums[rg], nums[pt]])
                    while lf < rg and nums[lf] == nums[lf + 1]:
                        lf += 1
                    while lf < rg and nums[rg] == nums[rg - 1]:
                        rg -= 1
                    lf += 1
                    rg -= 1
        return(res)

第五天
最近三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def threeSumClosest(self, nums: [int], target: int) -> int:
        l = len(nums)
        if l < 3: return []
        nums.sort()
        res = []

        lastsum = nums[0] + nums[1] + nums[-1]
        _ = lastsum

        for pt in range(l - 2):
            lf, rg = pt + 1, l - 1
            if pt > 0 and nums[pt] == nums[pt - 1]: continue
            while lf < rg:
                _ = nums[lf] + nums[rg] + nums[pt]
                if _ == target:
                    return target
                if abs(lastsum - target) > abs(_ - target):
                    lastsum = _
                if _ < target:
                    lf += 1
                elif _ > target:
                    rg -= 1
        return lastsum

第六天
最佳买卖股票时机 III

1
2
3
4
5
6
7
8
9
10
11
12
from sys import maxsize
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0 
        s1 = s2 = 0
        b1 = b2 = -maxsize
        for e in prices:
            s2 = max(s2, b2 + e)
            b2 = max(b2, s1 - e)
            s1 = max(s1, b1 + e)
            b1 = max(b1, -e)
        return s2

第七天
合并列表

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    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

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if None in (l1, l2):
            return l1 or l2
        n0 = cur = ListNode(None)
        n0.next = l1
        while l1 and l2:
            if l1.val < l2.val:
                l1 = l1.next
            else:
                nxt = cur.next
                cur.next = l2
                tmp = l2.next
                l2.next = nxt
                l2 = tmp
            cur = cur.next
        cur.next = l1 or l2
        return n0.next

第八天
排序列表去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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:
        i, j = head, head.next if head else None
        while j:
            if i.val == j.val:
                j = j.next
                i.next = j
            else:
                i = j
                j = i.next
        return head

第九天
链表判环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next: return False
        i, j = head, head.next
        try:
            while i is not j:
                i = i.next
                j = j.next.next 
            return True
        except:
            return False

第十天
两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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) -> ListNode:
        l3 = ListNode(0)
        rv = l3
        i = j = 0
        while l1 or l2 or i:
            v1 = v2 = 0
            if l1:
                v1 = l1.val
                l1 = l1.next
            if l2:
                v2 = l2.val
                l2 = l2.next
            i, j = divmod(v1 + v2 + i, 10)
            l3.next = ListNode(j)
            l3 = l3.next
        return rv.next

第十一天
删除列表末端第N个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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:
        del_pt = ListNode(None)
        del_pt.next = head
        rv = del_pt
        j = 0
        while(head):
            if j >= n:
                del_pt = del_pt.next
            j += 1
            head = head.next
        _ = del_pt.next.next if del_pt.next.next else None
        del_pt.next = _ 
        return rv.next

第十二天
合并K个有序列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
import heapq
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        rv = ListNode(None)
        pt = rv
        h = []
        for n in lists:
            while n:
                heapq.heappush(h,n.val)
                n = n.next
        while h:
            val = heapq.heappop(h)
            pt.next = ListNode(val)
            pt = pt.next
        return rv.next

第十三天
罗马数字转十进数

解法1：正则表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import re
reg = re.compile(r'IV|IX|XL|XC|CD|CM')
class Solution:
    romanValL = {
        'I':1,
        'V':5,
        'X':10,
        'L':50,
        'C':100,
        'D':500,
        'M':1000,
    }
    romanValH = {
        'IV':4,
        'IX':9,
        'XL':40,
        'XC':90,
        'CD':400,
        'CM':900,
    }
    def romanToInt(self, s: str) -> int:
        val = 0
        for x in reg.finditer(s):
            val += self.romanValH[x[0]]
        if val: s = re.sub(r'IV|IX|XL|XC|CD|CM', '', s)
        for x in s:
            val += self.romanValL[x]
        return val

解法2：替换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    romanValL = {
        'I':1,
        'V':5,
        'X':10,
        'L':50,
        'C':100,
        'D':500,
        'M':1000,
    }
    romanValH = {
        'IV':4,
        'IX':9,
        'XL':40,
        'XC':90,
        'CD':400,
        'CM':900,
    }
    def romanToInt(self, s: str) -> int:
        val = 0
        for x,v in self.romanValH.items():
            while x in s:
                val += v
                s = s.replace(x,'',1)
        for x,v in self.romanValL.items():
            while x in s:
                val += v
                s = s.replace(x,'',1)
        return val

第十四天
最长相同前缀

1
2
3
4
5
6
7
8
9
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        s_max, s_min = max(strs), min(strs)
        
        for i, v in enumerate(s_min):
            if s_max[i] != v:
                return s_min[:i]
        return s_min

第十五天
括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2:
            return False
        v = []
        d = {
            '}': '{',
            ')': '(',
            ']': '[',
        }
        for e in s:
            if e in ['(','[','{']:
                v.append(e)
            elif not v or v.pop() != d[e]:
                return False
        return not v

第十六天
无重复的最长子字符串

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        l = {}
        st = m = 0
        for i, e in enumerate(s):
            if e in l: 
                st = max(st, l[e] + 1)
            m = max(m, i - st + 1)
            l[e] = i
        return m

第十七天
最长回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestPalindrome(self, s: str) -> str:
        l = len(s)
        if l <= 1: return s
        tl = 1
        j = 1
        rv = s[0]
        for i in range(l):
            if i-tl >= 1 and s[i - tl - 1: i + 1]==s[i - tl - 1: i + 1][::-1]:
                j = i - tl - 1
                tl += 2
                continue

            if i - tl >= 0 and s[i - tl: i + 1] == s[i - tl: i + 1][::-1]:
                j = i - tl
                tl += 1
        return s[j: j + tl]

第十八天
正则表达式匹配

1
2
3
4
5
6
7
import re
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if re.match('^'+p+'$',s):
            return True
        else:
            return False

第十九天
相同的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not any([p,q]):
            return True
        elif all([p,q]) and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

第二十天
对称树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSym(self, Left, Right):
        if not Left and not Right:
            return True
        return Left and Right and Left.val == Right.val and self.isSym(Left.left, Right.right) and self.isSym(Left.right, Right.left)
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.isSym(root, root)

第二十一天
二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
# 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 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) if root else 0

第二十二天
正序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        lev_val = []
        lev = 0

        lev_val.append([root.val])
        dq = collections.deque([(1, root.left, root.right)])
        while dq:
            lev, l, r = dq.popleft()
            if l or r and len(lev_val) <= lev:
                lev_val.append([])
            if l:
                lev_val[lev].append(l.val)
                dq.append((lev + 1, l.left, l.right))
            if r:
                lev_val[lev].append(r.val)
                dq.append((lev + 1, r.left, r.right))
        while [] in lev_val:
            lev_val.remove([])
        return lev_val

第二十三天
Unique Binary Search Trees II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if not n:
            return []
        return self.gen(1, n + 1)
    
    def gen(self, s, e):
        if s == e:
            return [None]
        res = []
        for i in range(s, e):
            for left in self.gen(s, i):
                for right in self.gen(i + 1, e):
                    node = TreeNode(i)
                    node.left, node.right = left, right
                    res.append(node)
        return res

第二十四天
恢复二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        current, previous, todel, stack = root, TreeNode(-float('inf')), [], []
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            node = stack.pop()
            if node.val < previous.val: todel.append((previous, node))
            previous, current = node, node.right
        todel[0][0].val, todel[-1][1].val = todel[-1][1].val, todel[0][0].val

第二十五天
买卖股票的最佳时机 II

1
2
3
4
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum([max(prices[day + 1] - prices[day], 0) \
                    for day in range(len(prices) - 1)])

第二十六天
是否存在子序列

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isSubsequence(self, t: str, s: str) -> bool:
        p_s = p_t = 0
        l_s, l_t = len(s), len(t)
        while p_s < l_s and p_t < l_t:
            v = t[p_t]
            if s[p_s] == v:
                p_t += 1
            p_s += 1
        return p_t == l_t

第二十七天
分饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        assigned = 0
        p_s = p_g = 0
        l_s, l_g = len(s), len(g)
        while p_s < l_s and p_g < l_g:
            if s[p_s] >= g[p_g]:
                assigned += 1
                p_g += 1
            p_s += 1
        return assigned

第二十八天
跳一跳

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        step = 0
        l = len(nums)
        for i, v in enumerate(nums):
            if i > step:
                return False
            step = max(step, i + v)
            if step >= l:
                return True
        return True

第二十九天
加气站分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost): return -1
        l = len(gas)
        pt = tank = i = 0
        while i < l:
            tank += gas[i] - cost[i] 
            i += 1
            if tank <= 0:
                pt = i
                tank = 0
        if pt >= l:
            pt = 0
        return pt

第三十天
通配符匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        length = len(s)
        if len(p) - p.count('*') > length:
            return False
        dp = [True] + [False]*length
        for i in p:
            if i != '*':
                for n in reversed(range(length)):
                    dp[n+1] = dp[n] and (i == s[n] or i == '?')
            else:
                for n in range(1, length+1):
                    dp[n] = dp[n-1] or dp[n]
            dp[0] = dp[0] and i == '*'
        return dp[-1]