剑指 Offer 03. 数组中重复的数字

solution

flip num

题目中的所有数字都在 0 ~ n-1 的范围内，所以可以将数组中的所有数字都看作 index。遍历数组，对所有当前指向的数字置为相反数，如果出现 < 0 的数字，说明当前的 index 已经被置为相反数过了，当前的 index 就是一个重复数字。这其中有一个问题是 0，0 的相反数还是 0，所以如果是 0 在 index-0 但是之后又有重复的状况就会判别不出来，所以需要特别处理，比如说 [0, 1, 0]

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        countz = 0
        for i in range(len(nums)):
            if nums[abs(nums[i])] < 0:
                return abs(nums[i])
            elif nums[i] == 0 :
                countz += 1
                if countz > 1:
                    return 0
            nums[abs(nums[i])] *= -1

swap num

思路是做原地交换， 当前的值与 index 不相等的时候就进行当前值与指向值的交换，知道 nums[i] == nums[nums[i]] , 也就是说当前值和指向值是相等的，这有两种状况。第一种是 i == nums[i]，或者 nums[i] == nums[nums[i]] and i != nums[i]，第二种状况就是找到了重复值。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # Time(n) 90.67 %
    # Space(1) 41.00 %
    def findRepeatNumber(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if i != nums[i]:
                while nums[i] != nums[nums[i]]:
                    tmp = nums[i]
                    nums[i], nums[tmp] = nums[tmp] , nums[i]
            if i != nums[i] and nums[i] == nums[nums[i]]:
                return nums[i]

剑指 Offer 04. 二维数组中的查找

solution

搜索思路： [i,j] 左上的所有都是小于 当前数值的，[i,j] 右下的都是大于当前数值的。从右上角开始，如果比当前数值大，说明比本行及其下面的行都大，如果比当前数值小，说明本列及其右都小，所以可以按照如下规则。遇到比 target 小的，向下走一格，遇到比 target 大的，向左走一格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    # Time o(m+n) 99.08%
    # Space o(1) 20.58%
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        i = 0
        j = n - 1

        while 0<= i < m and  0<= j < n :
            #print(i,j)
            if target > matrix[i][j]:
                i += 1
            elif target < matrix[i][j]:
                j -= 1
            else:
                return True

        return False

剑指 Offer 05. 替换空格

solution

1
2
3
4
5
6
class Solution:
    # Time o(n) 54.61%
    # Space o(n) 5.31%
    def replaceSpace(self, s: str) -> str:
        return ''. join(['%20' if i == ' ' else i for i in list(s)])

剑指 Offer 06. 从尾到头打印链表

solution

1
2
3
4
5
6
7
8
9
10
class Solution:
    # Time o(n) 60%
    # Space o(1) 41%
    def reversePrint(self, head: ListNode) -> List[int]:
        stack = []
        cur = head
        while cur!= None:
            stack.append(cur.val)
            cur = cur.next
        return stack[::-1]

剑指 Offer 07. 重建二叉树

solution

两种解法的思路是一致的，以如下列表为例，在前序遍历中，第一个元素一定是当前构建的根节点，在中序遍历中，所有左子树元素一定在根节点的左边，所有右子树元素一定在根节点的右边。通过这两个特性，首先从前序树第一个元素取到根节点，再从中序树中找到根节点，根节点之前的部分就是左子树，根节点之后的部分就是右子树。而左子树的长度是固定的，所以在前序遍历数组中的第一个元素后取同样的长度，就得到了左子树的前序遍历数组。同理可以得到右子树的的相关所需结果。

[3, |9,2,8,| 20,15,7]
[2,9,8,| 3, | 15,20,7]

recursion + list para

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # Time o(n^2) 32.02%
        # Space o(n) 5.86%
        def build(prel, inl):
            #print(prel, inl)
            if len(prel) == 0:
                return None
            value = prel[0]
            root = TreeNode(value)
            idx_in_val = inl.index(value)
            root.left = build(prel[1: idx_in_val+1], inl[:idx_in_val])
            root.right = build(prel[idx_in_val+1:],  inl[idx_in_val+1:])
            return root 
        
        return build(preorder, inorder)

recursion + index para

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # Time o(n) 67.73%
    # Space o(1) 89.10%
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # Time o(n^2) 32.02%
        # Space o(n) 5.86%
        def build(prl, inl, inr):
            #print(prel, inl)
            if inl- inr == 0:
                return None
            value = preorder[prl]
            root = TreeNode(value)
            lenl = inorder[inl:inr].index(value)
                        
            root.left = build(prl+1,inl,inl+lenl )
            root.right = build(prl + lenl + 1,inl+lenl+ 1,inr)
            return root 
        
        return build(0, 0, len(inorder))

test cases

1
2
3
4
5
6
7
8
[3,9,20,15,7]
[9,3,15,20,7]
[2]
[2]
[]
[]
[3,9,2,8,20,15,7]
[2,9,8,3,15,20,7]

剑指 Offer 09. 用两个栈实现队列

两个 stak，一个用作 push，一个用作 pop。appendTail 将元素压入 stack 栈，deleteHead 时查看 pop 栈是否还有元素，如果空了就将 push 栈的元素倒入 pop 栈，否则 pop 栈顶的元素。

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class CQueue:
    # Time push o(1) delete o(1) on averaage 65.44%
    # Space o(n) 39.05%
    def __init__(self):
        self.push_ = []
        self.pop_ = []


    def appendTail(self, value: int) -> None:
        self.push_.append(value)


    def deleteHead(self) -> int:
        if self.push_ == [] and self.pop_ == []:
            return -1
        if self.pop_ != []:
            return self.pop_.pop()
        else:
            while self.push_ != []:
                self.pop_.append(self.push_.pop())
            return self.pop_.pop()

test Cases

1
2
3
4
5
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]

剑指 Offer 10- I. 斐波那契数列

solution

iteration

新 python3 可以处理长整数，为了节约时间，只需要在返回前进行 mod 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    # Time o(n) 80.47%
    # Space o(1) 43.41%
    def fib(self, n: int) -> int:
        MOD = 1000000007
        if n in (0,1):
            return n
        pre1 = 0
        pre2 = 1
        for i in range(n-1):
            tmp = (pre1 + pre2) 
            pre1 = pre2
            pre2 = tmp
        return pre2 % MOD

recursion

recursion 会溢出，使用 lru_cache 来避免这个问题。

1
2
3
4
5
6
7
8
9
10
11
from functools import lru_cache

class Solution:
    # Time o(n) 28.09%
    # Space o(1) 5.14%
    @lru_cache(None)
    def fib(self, n: int) -> int:
        MOD = 1000000007
        if n in (0,1):
            return n
        return (self.fib(n-1) + self.fib(n-2)) % 1000000007

test cases

1
2
3
4
5
0
1
2
100

剑指 Offer 10- II. 青蛙跳台阶问题

solution

与 10-i 同思路，只是停止条件不同

1
2
3
4
5
6
7
8
9
10
from functools import lru_cache
class Solution:
    # Time 28.41%
    # Space 5.09%
    @lru_cache(None)
    def numWays(self, n: int) -> int:
        MOD = 1000000007
        if n in (0,1):
            return 1
        return (self.numWays(n-1) + self.numWays(n-2)) % MOD

剑指 Offer 11. 旋转数组的最小数字

solution

遍历，如果出现了非递增元素，就会是最小的那个。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # Time o(n) 95.86%
    # Space o(1) 29.30%
    def minArray(self, numbers: List[int]) -> int:
        pre = numbers[0]
        for i in numbers[1:]:
            if i < pre:
                return i
            pre  =  i
        return numbers[0]

备注：因为允许重复数字出现，本题不能使用二分法

比如说 [3,3,3,3,3,3,1,3]，无法判断最小值到底是在左边还是在右边

test cases

1
2
3
4
5
6
7
8
9
10
[1,3,5]
[2,3,4,1]
[3,4,5,1,2]
[0]
[2,2,2,0,1]
[2,2,2]
# wrong answer
[1,3,3]
[3,1,3]
[3,3,3,3,3,3,3,3,1,3]

剑指 Offer 12. 矩阵中的路径

solution

使用 dfs 的思路求解，但需要注意的是两个细节。(a) 重复路径不是通过记录路径，而是通过标记路径，recursion之后再恢复来实现的，这样可以节省空间。(b) dfs 的深度是固定的 len(word)，已经遍历 matrix 来作为起始点了，所以遍历的深度不是遍历到无路可走而是没有按位符合 word 中的元素。

dfs + recover node

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
class Solution:
    # Time o(n*m*d) 92.83%
    # Space o(m*n) 48.64%
    def exist(self, board: List[List[str]], word: str) -> bool:
        if len(board) == 0 or len(word) == 0:
           return False
        m, n = len(board), len(board[0])
        
        def dfs(x, y, cur):
            if x< 0 or x >= m or y < 0 or y >= n or word[cur] != board[x][y]:
                return False
            ch = board[x][y]
            board[x][y] = ''
            
            cur += 1
            if cur == len(word):
                return True
    
            ans = dfs(x+1, y, cur) or dfs(x-1, y, cur) or dfs(x, y+1, cur) or dfs(x, y-1, cur)
            board[x][y] = ch
            return  ans 
        
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return  False

test cases

1
2
3
4
5
6
7
8
9
[["a","b"],["c","d"]]
"dbac"
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCCED"
 [["a","b"],["c","d"]]
"abcd"
[["a","b","c","e"],["s","f","c","s"],["a","d","e","e"]]
"bafb"

剑指 Offer 13. 机器人的运动范围

solution

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:
    # Time o(mn) 54.49%
    # Space o(mn) 66.66% 
    # Date 20210309
    def movingCount(self, m: int, n: int, k: int) -> int:
        
        def countBit(x, y):
            count = 0
            while x > 0:
                count += x % 10
                x = x // 10
            while y > 0:
                count += y % 10
                y = y // 10
            return count
        
        mx = [[0] * (n + 1) for _ in range(m+1)]
        ans = 0
        mx[0][1] = 1
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if countBit(i-1, j-1) > k:
                    continue
                if mx[i-1][j] == 0 and mx[i][j-1] == 0:
                    continue
                mx[i][j] = 1
                ans += 1
        return ans

test cases

1
2
3
4
5
6
7
8
9
10
11
12
1
2
1
3
1
0
37
28
15
1
1
1

剑指 Offer 14- II. 剪绳子 II

solution

思路和 14 - I 相同. Python 可以处理任意长度超大整数, 所以在返回前进行 MOD 即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # Time o(n) 39.41%
    # Space o(1) 87.76%
    # date: 20210309
    def cuttingRope(self, n: int) -> int:
        MOD = 1000000007
        ans = 1
        if n == 2 or n == 3:
            return n - 1
        while n not in (0, 2, 4):
            ans *= 3
            n -= 3
        if n > 0:
            ans *= n
        ans %= MOD
        return ans

test cases

剑指 Offer 14- I. 剪绳子

solution

trivial dp1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    # Time o(n^3) 7.26%
    # Space o(n) 43.99%
    # date: 20210309
    def cuttingRope(self, n: int) -> int:
        pre = [0] * (n + 1)
        for i in range(1, n):
            pre[i] = i
        cur = [0] * (n + 1)
        for j in range(n):
            for i in range(1, n+1):
                cur[i] = pre[i]
                for k in range(1, i):
                    cur[i] = max(cur[i], pre[k]*(i-k))
            pre, cur = cur, pre
        return max(pre)

dp 2

动态规划的思路, 在过程中加入可能的乘数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # Time o(n^2) 27.98%
    # Space o(n) 28.57%
    # date: 20210309
    def cuttingRope(self, n: int) -> int:
        pre = [0] * (n+1)

        for i in range(2,n+1):
            pre[i] = i-1

        for i in range(3,n+1):
            for j in range(2,i):
                pre[i] = max(pre[i], j *(i - j), j * pre[i-j])

        return max(pre)

math

拆出尽可能多的 3 直到只剩 2 或者 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # Time o(n^3) 27.98%
    # Space o(n) 28.57%
    # date: 20210309
    def cuttingRope(self, n: int) -> int:
        if n == 3 or n == 2:
            return n - 1
        ans = 1
        while n not in (0,2,4):
            n -= 3
            ans *= 3
        if n > 0:
            ans *= n
        return ans

背后的数学原理: https://leetcode.com/problems/integer-break/discuss/80721/Why-factor-2-or-3-The-math-behind-this-problem.

求导, 最佳是 e

test cases

1
2
3
4
5
6
7
8
2
4
16
27
10
32
28
58

wrong cases

1
4

剑指 Offer 15. 二进制中1的个数

solution

bit manipulation

1
2
3
4
5
6
7
8
9
10
class Solution:
    # Time o(n) 40.38%
    # Space o(1) 62.81%
    # date: 20210309
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n > 0:
            count += n & 1 # mod 2
            n >>= 1  # //2
        return count

built-in function

1
2
3
4
5
6
class Solution:
    # Time o(n) 8.11%
    # Space o(1) 57.56%
    # date: 20210309
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')

剑指 Offer 16. 数值的整数次方

solution

recursion

recursion 此消彼长, 没有重复计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from functools import lru_cache
@ lru_cache
class Solution:
    # Time o(logn) 95.45%
    # Space o(1) 73.93%
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            x = 1/x
            n = abs(n)
        if n == 1:
            return x
        ans = 1
        return self.myPow(x*x,n//2) if n & 1 != 1 else x * self.myPow(x*x, n//2)

test cases

1
2
0.00001
2147483647

剑指 Offer 17. 打印从1到最大的n位数

solution

..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def printNumbers(self, n: int) -> List[int]:
        # Time o(10^n) 5.57%
        # Space o(10^n) 5.01%
        # date: 20210309
        def bfs(s, ans):
            while len(s) > 0:
                cur = s.pop(0)
                ans.append(int(cur))
                if len(cur) == n:
                    continue
                for i in range(10):
                    s.append(cur + chr(ord('0') + i))
        s = [chr(ord('0') + i) for i in range(1,10)]
        ans = []
        bfs(s, ans)
        return ans

剑指 Offer 18. 删除链表的节点

solution

剑指 offer 的本意是希望以 o（1） 的时间删除链表内部节点的同时，考虑多种情况。（1）目标节点不在尾部且链表长度大于1，（2）目标节点在尾部（3） 链表长度为 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # Time o(n) 48.39%
    # Space o(n) 36.66%
    # Date 20210309
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        
        def findTarget(head, value):
            cur = head
            while cur:
                if cur.val == value:
                    return cur
                cur = cur.next
            return None

        def removeNode(head, target):
            # remove Node o(1)
            if target.next:
                target.val = target.next.val
                target.next = target.next.next
                return
            cur = head
            # remove tail Nonde o(n)
            while cur and cur.next:
                if not cur.next.next:
                    cur.next = None
                cur = cur.next
             
                
        target = findTarget(head, val)
        #print(target)
        if not target:
            return head
        # remove head None 
        if not head.next:
            return None
        removeNode(head,target)
        return head

剑指 Offer 19. 正则表达式匹配

solution

dp

1
2
3
4
5
6
7
8
9
10
11
dp[i][j]: s[:i+1] - p[:j+1] 的匹配情况
1. s[i] == p[j] or p[j] == '.' : dp[i][j] = dp[i-1][j-1]
2. p[j] == '*':
	1. if s[i] == p[j-1]  or p[j-1] == '.':
		dp[i][j] = s[i-1][j] // counts multiple a in a*
        or dp[i][j] = s[i][j-1] // counts a single a in a*
		or dp[i][j] = s[i][j-2] // counts empty a in a*
	2. not match 
		dp[i][j] = s[i][j-2] // a* counts as empty
	
		
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
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    # Time o(|s|*|p|) 72.68 %
    # Space o(|s|*|p|) 48.28%
    # Date: 20210309
    def isMatch(self, s: str, p: str) -> bool:
        ns = len(s)
        np = len(p)
        s = '#' + s
        p = '#' + p
        
        pre = [False]* (np+1)
        pre[0] = True

        # initiate with a* pattern for true
        # '' mathes '.*'
        for i in range(1,np+1):
            if p[i] == '*' and pre[i-2]:
                pre[i] = True

        for i in range(1, ns + 1):
            cur = [False]* (np+1)
            for j in range(1, np + 1):
                if s[i] == p[j] or p[j] == '.':
                    #print(i,j)
                    #print(s[i],p[j])
                    cur[j] = pre[j-1]
                elif p[j] == '*' and j > 1:
                    if s[i] == p[j-1] or p[j-1] == '.':
                        # multiple a
                        if i >= 1:
                            cur[j] = cur[j] or pre[j]
                        # counts no a
                        if j >= 2:
                            cur[j] = cur[j] or cur[j-2]
                        # counts one a
                        if j >= 1:
                            cur[j] = cur[j] or cur[j-1]
                    elif j>= 2:
                        cur[j] = cur[j] or cur[j-2]
            cur, pre = pre, cur
        #print(dp)
        return pre[-1]

recursion

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
30
31
32
class Solution:
    # Time o((|s| + |p|) * 2 ^ (|s| + |p|)) 12.56%
    # Space o(|s| + |p|) 13.44 %
    # Date: 20210309
    def isMatch(self, s: str, p: str) -> bool:
        ns = len(s)
        np = len(p)

        def ifMatch(sid, pid):
            if pid == np:
                return sid == ns
            # case without duplicate
            if pid + 1 == np or p[pid + 1] !='*':
                if sid == ns:
                    return False
                if s[sid] == p[pid] or p[pid] == '.':
                    return ifMatch(sid + 1, pid + 1)
                return False
            # case with *
            else:
                i = -1
                while i == -1 or s[sid+i] == p[pid] or p[pid] == '.':
                    if ifMatch(sid + i + 1, pid + 2):
                        return True
                    i += 1
                    if sid + i == ns:
                        break
                return False
            return False

        return ifMatch(0,0)

test cases

1
2
3
4
5
6
7
8
9
10
11
12
"ab"
".*ab"
"aa"
"a"
"aa"
"a*"
"ab"
".*"
"aab"
"c*a*b"
"mississippi"
"mis*is*p*."

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

solution

使用前后两个指针，维护p_od及之前都为奇数，p_ev及之后都为偶数。如果出现违反当前规则的状况，交换所指向的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    # Time o(n) 66.17%
    # Space o(1) 56.74%
    # Date 20210309
    def exchange(self, nums: List[int]) -> List[int]:
        p_od = 0
        p_ev = len(nums) -1

        while p_od < p_ev:
            if nums[p_od] & 1 == 1:
                p_od += 1
                continue
            else:
                while p_od < p_ev and nums[p_ev] & 1 == 0:
                    p_ev -= 1
                if p_od != p_ev:
                    nums[p_od], nums[p_ev] = nums[p_ev], nums[p_od]
        return nums

Test Cases

1
2
3
4
5
[1,2,3,4]
[1,3,3,5]
[2,3,1,4]
[2,2,2,1]
[]

剑指 Offer 22. 链表中倒数第k个节点

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    # Time o(n) 96.04%
    # Space o(1) 30.69%
    # Date o(20210309)
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        pre = head
        cur = head
        for i in range(k):
            if pre:
                pre = pre.next
            else:
                return None
        while pre:
            pre = pre.next
            cur = cur.next
        return cur

test cases

1
2
3
4
5
6
7
[1,2,3,4,5]
5
[1,2,3,4,5]
1
[1,2,3,4,5]
3

剑指 Offer 24. 反转链表

solution

从链表头开始遍历，将新的 Node 接在当前新链表之后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    # Time o(n) 98.47%
    # Space o(n) 24.01%
    # Date: 20210309
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        rehead = None
        while cur:
            node = ListNode(cur.val)
            node.next = rehead
            rehead = node
            cur = cur.next
        return rehead

剑指 Offer 25. 合并两个排序的链表

solution

iteration + 新空间

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
30
31
32
33
class Solution:
    # Time o(n) 24.44%
    # Space o(n) 20.67%
    # Date 20210310
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) and (not l2):
            return l1
        elif not l1:
            return l2
        elif not l2:
            return l1
        # l3
        # keep removing the smaller one from l1 and l2
        head = ListNode(None)
        cur = head
        while l1 and l2:
            curval = 0
            if l1.val <= l2.val:
                curval = l1.val
                l1 = l1.next
                
            else:
                curval = l2.val
                l2 = l2.next
            node = ListNode(curval)
            cur.next = node
            cur = cur.next
        if l1:
            cur.next = l1
        if l2:
            cur.next = l2

        return head.next

recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # Time o(n) 60.30%
    # Space o(n) 5.04%
    # Date 20210310
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) and (not l2):
            return l1
        elif not l1:
            return l2
        elif not l2:
            return l1
        # l3
        # keep removing the smaller one from l1 and l2
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

test cases

1
2
3
4
5
6
7
8
[1,2,4]
[1,3,4]
[]
[1]
[1]
[]
[1,2,3]
[5,6,7]

剑指 Offer 27. 二叉树的镜像

solution

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # Time o(logn)  59.51%
    # Space o(1) 82.99%
    # Date 20210310
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        root.left, root.right = root.right, root.left
        root.left = self.mirrorTree(root.left)
        root.right = self.mirrorTree(root.right)
        return root

test cases

1
[4,2,7,1,3,6,9]

剑指 Offer 28. 对称的二叉树

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # Time o(logn) 80.31%
    # Space o(1) 62.01%
    # Date: 20210310
    def isSymmetric(self, root: TreeNode) -> bool:

        def ifsym (A , B):
            if (not A) and (not B):
                return True
            if not(A and B):
                return False
            if not (A.val == B.val):
                return False
            return ifsym(A.left, B.right) and ifsym(A.right, B.left)
        if not root:
            return True
        return ifsym(root.left, root.right)

剑指 Offer 29. 顺时针打印矩阵

solution

题目不困难，但是需要想好 test cases，仔细考虑 edge cases

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
30
31
32
33
class Solution:
    # Time o(mn) 92.51 %
    # Space o(mn) 7.42 %
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])
        if n == 0:
            return []
        ans = []
        def printMatrix(sm, em, sn, en):
            nonlocal ans
            if sm >= em or sn >= en:
                return 
            #print(sm, em, sn, en)
            for i in matrix[sm][sn:en]:
                ans.append(i)
            if sm + 1 < em and en-1>= sn:
                for i in matrix[sm+1:em]:
                    ans.append(i[en-1])
            if em - 1 > sm and sn  < en-1:
                #print(matrix[em-1][sn: en-1][::-1])
                for i in matrix[em - 1][sn:en-1][::-1]:
                    ans.append(i)
            if sm+1 < em-1 and en-1 > sn:
                for i in matrix[sm+1: em-1][::-1]:
                    ans.append(i[sn])

            printMatrix(sm+1, em-1, sn+1, en-1)
        
        printMatrix(0, m, 0, n)
        return ans

test cases

1
2
3
4
5
[[1,2,3],[4,5,6],[7,8,9]]
[[1,2,3]]
[[1],[2],[3]]
[[1,2],[4,5],[7,8]]

剑指 Offer 30. 包含min函数的栈

solution

维持一个给 min value 的 stack，如果 push 的元素比栈顶元素小或者等于，就在 min_stack 里压栈。

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
30
31
32
33
34
35
36
37
38
39
class MinStack:
    # Time push, min, top, pop o(1) 76.07%
    # Space o(n) 23.05%
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack_val = []
        self.stack_min = []


    def push(self, x: int) -> None:
        self.stack_val.append(x)
        if len(self.stack_min) == 0:
            self.stack_min.append(x)
        else:
            if x <= self.stack_min[-1]:
                self.stack_min.append(x)

    def pop(self) -> None:
        ans = self.stack_val.pop()
        if ans == self.stack_min[-1]:
            self.stack_min.pop()

    def top(self) -> int:
        return self.stack_val[-1]


    def min(self) -> int:
        return self.stack_min[-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.min()

test cases

1
2
["MinStack","push","push","push","min","pop","top","min"]
[[],[-2],[0],[-3],[],[],[],[]]

剑指 Offer 31. 栈的压入、弹出序列

solution

弄一个新栈，模拟 stack 的操作状况

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    # Time o(n) 85.79%
    # Space o(n) 64.11%
    # Date 20210312
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        for i in popped:
            while (stack == [] or stack[-1] != i) and len(pushed) != 0:
                stack.append(pushed.pop(0))
            if stack[-1] != i:
                return False
            stack.pop()
        return True

test cases

1
2
3
4
[1,2,3,4,5]
[4,5,3,2,1]
[]
[]

剑指 Offer 32 - I. 从上到下打印二叉树

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # Time o(n) 47.24%
    # Space o(n) 40.60%
    # Date: 20210312
    def levelOrder(self, root: TreeNode) -> List[int]:
        ans = []
        if not root:
            return ans
        candi = [root]
        while candi != []:
            cur = candi.pop(0)
            ans.append(cur.val)
            if cur.left:
                candi.append(cur.left)
            if cur.right:
                candi.append(cur.right)
        return ans

test cases

1
2
3
[3,9,20,null,null,15,7]
[1,3,2,4,5,2,1,3]
[]

剑指 Offer 32 - II. 从上到下打印二叉树 II

solution

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    # Time o(n) 22.38%
    # Space o(n) 5.02%
    # Date: 20210312
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        def dfs(depth,root,ans):
            if not root:
                return 
            if depth == len(ans):
                ans.append([])
            ans[depth].append(root.val)
            dfs(depth + 1, root.left, ans)
            dfs(depth + 1, root.right, ans)
        dfs(0, root, ans)
        return ans

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    # Time o(n) 74.46%
    # Space o(n) 11.49%
    # Date: 20210312
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        candi = [(root,0)]
        while len(candi)!= 0:
            cur_node, depth = candi.pop(0)
            if depth == len(ans):
                ans.append([])
            ans[depth].append(cur_node.val)
            if cur_node.left:
                candi.append((cur_node.left, depth + 1))
            if cur_node.right:
                candi.append((cur_node.right, depth + 1))
        return ans

test cases

1
2
3
4
[3,9,20,null,null,15,7]
[1,2,3,4,6]
[2,3,null,1,2]
[]

剑指 Offer 32 - III. 从上到下打印二叉树 III

solution

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 在插入元素的时候判断层数，以此判断是从头插入还是从尾插入
class Solution:
    # Time o(n) 90.25%
    # Space o(n) 42.74%
    # Date 20210312
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        candi = [(root,0)]
        while len(candi)!= 0:
            cur_node, depth = candi.pop(0)
            if depth == len(ans):
                ans.append([])
            if depth & 1 == 1:
                ans[depth].insert(0, cur_node.val)
            else:
                ans[depth].append(cur_node.val)
            if cur_node.left:
                candi.append((cur_node.left, depth + 1))
            if cur_node.right:
                candi.append((cur_node.right, depth + 1))
        return ans

test cases

1
[3,9,20,null,null,15,7]

剑指 Offer 33. 二叉搜索树的后序遍历序列

solution

找到第一个大于 l[-1] 的值作为分割点，保持 left < root < right 的二叉树性质，否则返回 False

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
30
31
import sys
class Solution:
    # Time o(nlogn) 87.69%
    # Space o(nlogn) 5.19%
    # Date: 20210312
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if len(postorder) <= 1:
            return True
        if len(postorder) == 2 and postorder[0] != postorder[1]:
            return True
        root = postorder[-1]
        idx = 0
        while postorder[idx] < root:
            idx += 1
        # idx - 1 
        if idx == 0 :
            if min(postorder[:-1]) < root:
                return False
            return self.verifyPostorder(postorder[:-1])
        if idx == 0:
            left_max = -sys.maxsize
        else:
            left_max = max(postorder[:idx])
        if idx == len(postorder) - 1:
            right_min = sys.maxsize
        else:
            right_min = min(postorder[idx:-1])
        
        if left_max> root or right_min < root:
            return False
        return self.verifyPostorder(postorder[:idx]) and self.verifyPostorder(postorder[idx:-1])

test cases

1
2
3
4
[4, 6, 12, 8, 16, 14, 10]
[1,6,3,2,5]
[1,3,2,6,5]
[7,4,6,5]

剑指 Offer 35. 复杂链表的复制

solution

expand and split list

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
30
31
32
33
34
35
36
class Solution:
    # Time o(n) 30.38%
    # Space o(1) 78.08%
    # Date 20210312
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return head
        
        # expand linked list to double
        cur = head
        while cur:
            rear = cur.next
            copy = Node(cur.val)
            cur.next = copy
            copy.next = rear
            cur = cur.next.next

        # replicate random pointers
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        
        # split the list into two
        cur = head
        copyHead = cur.next
        copyCur = copyHead
        while copyCur.next:
            cur.next = cur.next.next 
            cur = cur.next

            copyCur.next = copyCur.next.next
            copyCur = copyCur.next
        cur.next = None
        return copyHead

HashTable + List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    # Time o(n) 55.88%
    # Space o(1) 78.08%
    # Date 20210312
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return head
        m = {}
        m[head] = Node(head.val)
        cur = head
        copy_head = copy_cur = m[head]
        while cur:
            if cur.random:
                if cur.random not in m:
                    m[cur.random] = Node(cur.random.val)
                copy_cur.random = m[cur.random]
            if cur.next:
                if cur.next not in m:
                    m[cur.next] = Node(cur.next.val)
                copy_cur.next = m[cur.next]
            cur = cur.next
            copy_cur = copy_cur.next
        return copy_head

test cases

1
2
3
4
[[7,null],[13,0],[11,4],[10,2],[1,0]]
[[1,1],[2,1]]
[[3,null],[3,0],[3,null]]
[]

剑指 Offer 36. 二叉搜索树与双向链表

solution

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
class Solution:
    # Time o(n) 88.80% 
    # Space o(1) 47.40 %
    # Date 20210317
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        head = None
        pre = None
        def dfs(root, head, pre):
            if not root:
                return head, pre
            head, pre = dfs(root.left, head, pre)
            if not head:
                head = root
                pre = root
            else:
                if pre.right != root : # some pointers of nodes may not change , large improvement with this condition
                    pre.right = root 
                if root.left != pre :
                    root.left = pre
                pre = root
            return dfs(root.right, head, pre)
        head, pre = dfs(root, head, pre)
        head.left = pre
        pre.right = head
        return head

test cases

剑指 Offer 37. 序列化二叉树

solution

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Codec:
    # Time o(n) 30.78%
    # Space o(n) 24.98%
    # Date 21210317
    # bfs serilization
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''
        ans = []
        stack = [root]
        while stack!= []:
            cur = stack.pop(0)
            if not cur:
                ans.append('null')
            else:
                ans.append(str(cur.val))
                stack.append(cur.left)
                stack.append(cur.right)
            
        return '['+ ','.join(ans) + ']'
            
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        if data == '':
            return None

        # print(data)
        tree = data.strip('[]').split(',')

        head = TreeNode(tree[0])
        stack = [head]
        i = 1
        while i < len(tree):
            cur = stack.pop(0)
            leftNode = TreeNode(int(tree[i])) if tree[i]!= 'null' else None
            if leftNode :
                stack.append(leftNode)
                cur.left = leftNode
            i += 1
            if i == len(tree):
                break
            rightNode = TreeNode(int(tree[i]) ) if tree[i]!= 'null' else None
            if rightNode :
                stack.append(rightNode)
                cur.right = rightNode
            i+= 1
        return head

test cases

1
2
3
4
5
[1,2,3,null,null,4,5]
[1,null,3,null,4,5]
[1, 2, 3]
[]
[1,2,null,3,null,4]

剑指 Offer 38. 字符串的排列

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    # Time o(2^n) 80.48%
    # Space o(n) 98.92%
    def permutation(self, s: str) -> List[str]:
        if s == '':
            return []
        ans = []
        def dfs(cur, candi, ans):
            if len(candi) == 0:
                ans.append(cur)
            for a in set(candi):
                candi.remove(a)
                dfs(cur + a, candi, ans)
                candi.append(a)
        dfs('', list(s), ans)
        return ans

test cases

1
2
"abc"
"aab"

剑指 Offer 39. 数组中出现次数超过一半的数字

solution

sort

1
2
3
4
5
6
7
class Solution:
    # Time o(nlogn) 33.07%
    # Space o(n) 10.78%
    # Date 20210420
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    # Time o(n) 33.07%
    # Space o(1) 10.78%
    # Date 20210420
    def majorityElement(self, nums: List[int]) -> int:
        count, major = 1, nums[0]
        n = len(nums)
        for n in nums[1:]:
            if count == 0:
                count, major = 1, n
            elif n == major:
                count += 1
            else:
                count -= 1
        return major

test cases

1
2
3
4
[1,2,3,2,2,2,5,4,2]
[1,2,2]
[1,2,3,3,2,3,3,3,3,3]
[5,4,3,2,1,1,1,1,1]

剑指 Offer 40. 最小的k个数

solution

heap

1
2
3
4
5
6
7
8
9
10
11
from heapq import *
class Solution:
    # Time o(nlogn) 80.49%
    # Space o(n)    71.37%
    # Date 20210420
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        heapify(arr)
        ans = []
        for i in range(k):
            ans.append(heappop(arr))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from heapq import *
class Solution:
    # Time o(nlogn) 80.49%
    # Space o(n)    20.46%
    # Date 20210420
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        heap = arr[:k]
        heap = [-n for n in heap]
        heapify(heap)
        for n in arr[k:]:
            if n <  -heap[0]:
                heapreplace(heap, -n)
        return [-n for n in heap]

divide + conquer

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
30
31
32
33
import random
class Solution:
    # Time avrg: o(n) worst: o(n^2) 54.82%
    # Space o(n) 44.56%
    # Date 20210420
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def partition( nums, l, r):
            pivot = nums[r]
            i = l - 1
            for j in range(l, r):
                if nums[j] <= pivot:
                    i += 1
                    nums[i], nums[j] = nums[j], nums[i]
            nums[i+1], nums[r] = nums[r], nums[i + 1]
            return i + 1

        def random_partition(nums, l, r):
            i = random.randint(l, r)
            nums[r], nums[i], nums[i], nums[r]
            return partition(nums, l , r)
        
        def random_select( arr, l, r, k):
            pos = random_partition(arr, l, r)
            num = pos - l + 1
            if k > num:
                random_select(arr, pos + 1, r, k - num)
            elif k < num:
                random_select(arr, l, pos-1, k)
        
        if k == 0:
            return []
        random_select(arr , 0, len(arr)-1, k)
        return arr[:k]

test cases

剑指 Offer 41. 数据流中的中位数

solution

heapq

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
30
31
32
33
34
35
36
37
38
39
40
from heapq import *
class MedianFinder:
    # Time o(logn) 85.84%
    # Space o(n) 21.96%
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.heap_left = [] # maxheap
        self.heap_right = [] # meanheap

    def addNum(self, num: int) -> None:
        if self.heap_left == []:
            heappush(self.heap_left, -num)
        elif len(self.heap_left) == len(self.heap_right):
            if num <=  self.heap_right[0]:
                heappush(self.heap_left, -num)
            else: 
                right_min = heappushpop(self.heap_right, num)
                heappush(self.heap_left, -right_min)
        else:
            if num >= - self.heap_left[0]:
                heappush(self.heap_right, num)
            else:
                left_max = - heappushpop(self.heap_left, -num)
                heappush(self.heap_right, left_max)

    def findMedian(self) -> float:
        #print(self.heap_left, self.heap_right)
        if len(self.heap_left) == len(self.heap_right):
            return (- self.heap_left[0] + self.heap_right[0])/2
        else:
            return -self.heap_left[0]



# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

test cases

1
2
3
4
5
6
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
["MedianFinder","addNum","findMedian"]
[[],[1],[]]
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[],[3],[8],[],[2],[]]

剑指 Offer 42. 连续子数组的最大和

solution

dp

1
2
3
dp[i] 以 index i 为结尾的连续子数组的最大和
if dp[i-1] + nums[i] < 0: dp[i] = 0
else: dp[i] = dp[i-1] + nums[i]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # Time o(n) 68.69%
    # Space o(n) 27.66%
    # Date 20210420
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(0, dp[i-1]) + nums[i]
        return max(dp)

test cases

1
2
3
4
[-2,1,-3,4,-1,2,1,-5,4]
[-1, 2, 3, 1, 3, -4, 3, -2, 3 ,2]
[2,3, 4, -1, 2, -3 ,2 , 4, -3, -2]
[1,2,-1,-2,2,1,-2,1,4,-5,4]

剑指 Offer 43. 1～n 整数中 1 出现的次数

solution

recursion

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:
    # Time o(n) 98.76%
    # Space o(n) 8.81%
    # Date 20210420
    def countDigitOne(self, n: int) -> int:
        def countOne(n):
            if n <= 1:
                return n
            return 10**(n-1) + 10*countOne(n-1)

        if n <= 1:
            return n
        nstr = str(n)
        l = len(nstr)
        if l == 1:
            return 1
        else:
            ans = 0
            ans += int(nstr[0]) * countOne(l-1)  + self.countDigitOne(int(nstr[1:]))
            if nstr[0] == '1':
                ans += int(nstr[1:]) + 1
            else:
                ans += 10**(l-1)
            return ans

test cases

1
2
3
4
5
12
89123
8989023
13
12304302

剑指 Offer 44. 数字序列中某一位的数字

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from functools import cmp_to_key
class Solution:
    # Time o(nlogn) 62.48%
    # Space o(n) 64.30%
    # Date 20210420
    def minNumber(self, nums: List[int]) -> str:
        # (1stBit, other, value)
        def compare(x, y):
            if str(x) + str(y) < str(y) + str(x):
                return -1
            elif x + y == y + x:
                return 0
            else:
                return 1
        
        nums.sort(key = cmp_to_key(compare))
        return ''.join(str(n) for n in nums)

test cases

1
2
3
[3,20,333,20,33,32,34,1]
[10,2]
[3,30,34,5,9]

剑指 Offer 46. 把数字翻译成字符串

solution

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    # Time o(n) 81.67%
    # Space o(1) 17.69%
    # Date 20210421
    def translateNum(self, num: int) -> int:
        strn = str(num)
        dp = [0] * len(strn)
        dp[0] = 1
        for i in range(1,len(strn)):
            dp[i] += dp[i-1]
            if '10' <= strn[i-1:i+1] <= '25':
                dp[i] += dp[i-2] if i >=2 else 1
        return dp[-1]

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # Time o(n)
    # Space o(1)
    # Date 20210420
    def translateNum(self, num: int) -> int:
        ans = 0
        def bfs(strn, i):
            nonlocal ans
            if i == len(strn):
                ans += 1
                return 
            bfs(strn, i + 1)
            if i + 2 <= len(strn) and 10 <= int(strn[i: i + 2]) <= 25:
                bfs(strn, i + 2)
        bfs(str(num), 0)
        return ans

test cases

1
2
3
4
5
80870304
2893
8923
121323442
12121223

剑指 Offer 47. 礼物的最大价值

solution

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # Time o(mn) 97.52%
    # Space o(n) 97.04%
    def maxValue(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [0]*n 
        for i in range(m):
            for j in range(n):
                dp[j] = max(dp[j], 0 if j == 0 else dp[j-1]) + grid[i][j]
        return dp[-1]

test cases

1
2
3
4
[[1,3,1],[1,5,1],[4,2,1]]
[[1,3,1],[1,5,1]]
[[2,3,1]]
[[2,3], [2,3], [2,1]]

剑指 Offer 48. 最长不含重复字符的子字符串

solution

Set + Sliding window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    # Time o(n) 97.02%
    # Space o(n) 7.02%
    # Date 20210421
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        l = 0
        n = len(s)
        if n <= 1:
            return n
        ans = 1
        curset = {s[0]}
        for r in range(1,n):
            if s[r] in curset:
                while l< r and s[l]!= s[r]:
                    curset.discard(s[l])
                    l +=1
                l += 1
            else:
                ans = max(ans, r-l + 1)
                curset.add(s[r])
            
        return ans

test cases

1
2
3
"abbccddsseessewwsawssdsddwefdosajf"
"abcabcbb"
"pwwkew"

剑指 Offer 49. 丑数

solution

dp1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # Time o(nk) 5.74%
    # Space o(n+k) 68.09%
    def nthUglyNumber(self, n: int) -> int:
        count = 1
        nums = [1]
        start = [0] * 3
        candi = [2, 3, 5]
        while len(nums) < n:
            adds = [candi[i] * nums[start[i]] for i in range(3)]
            min_add = min(adds)
            nums.append(min_add)
            start = [start[i] + (adds[i] == min_add) for i in range(3)]
        return nums[n-1]

dp2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    # Time o(n) 32.06%
    # Space o(n) 51.40%
    def nthUglyNumber(self, n: int) -> int:
        nums = [1]
        i1 = i2 = i3 = 0
        while len(nums) < n:
            if nums[-1] >= nums[i1] * 2 : 
                i1 +=1
            if nums[-1] >= nums[i2] * 3:
                i2 += 1
            if nums[-1] >= nums[i3] * 5:
                i3 += 1
            nums.append(min(nums[i1] * 2,nums[i2] *3, nums[i3] * 5))
        return nums[n-1]

brute force

1
2
3
4
5
6
7
class Solution:
    # Time o(nlogn) + o(abc) 5.01%
    # Space o(abc) 5.04%
    def nthUglyNumber(self, n: int) -> int:
        uglyNums = [2**a * 3**b * 5**c for a in range(32) for b in range(20) for c in range(15)]
        uglyNums.sort()
        return uglyNums[n-1]

test cases

剑指 Offer 50. 第一个只出现一次的字符

solution

OrderedDict

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import OrderedDict
class Solution:
    # Time o(n) 45%
    # Space o(n) 12%
    # Date 20210421
    def firstUniqChar(self, s: str) -> str:
        dic = OrderedDict()
        for c in s:
            if c in dic:
                dic[c] += 1
            else:
                dic[c] = 1
        ans = ' '
        while len(dic) > 0:
            c, time = dic.popitem(last = False)
            if time == 1:
                return c
        return ans

HashTable + list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import defaultdict
class Solution:
    # Time o(n) 37.24%
    # Space o() 11.79%
    # Date 20210421
    def firstUniqChar(self, s: str) -> str:
        dic = defaultdict(int)
        valId = {}
        for idx, c in enumerate(s):
            dic[c] += 1
            valId[c] = idx
        ans = ' '
        for c in dic:
            if dic[c] == 1:
                if ans == ' ' or  valId[c] < valId[ans]:
                    ans = c
        return ans

test cases

solution

merge sort

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
30
31
32
33
class Solution:
    # Time o(nlogn) 87.83% same as mergeSort
    # Space o(n) 82.20%
    # Date 20210421
    def reversePairs(self, nums: List[int]) -> int:
        # sort for nums[l: r+1]
        def mergeSort(nums, tmp, l, r):
            if l >= r:
                return 0
            
            mid = l + (r - l )//2
            inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid+1, r)
            i, j, pos = l, mid + 1, l
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    tmp[pos] = nums[i]
                    i += 1
                else:
                    inv_count += (mid+1) - i
                    tmp[pos] = nums[j]
                    j += 1
                pos += 1
            for k in range(i, mid + 1):
                tmp[pos] = nums[k]
                pos += 1
            for k in range(j, r+1):
                tmp[pos] = nums[k]
                pos += 1
            nums[l: r+1] = tmp[l: r+1]
            return inv_count
        
        ans = mergeSort(nums, [0]* len(nums), 0, len(nums)-1)
        return ans

test cases

1
2
3
4
5
6
[7,5,6,4]
[2,3,3,4,2,1,4,5]
[5,4,3,2,1]
[1,2,3,4,5]
[3,2,1,4,4,4,2,3]
[2,9,2,9,2,9,2,10,1,3,4,2,2]

剑指 Offer 52. 两个链表的第一个公共节点

solution

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
30
31
32
33
34
35
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # Time o(n) 35.63%
    # Space o(1) 68.50%
    # Date 20210421
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        curA, curB = headA, headB
        la, lb = 0, 0
        while curA:
            curA = curA.next
            la += 1
        while curB:
            curB = curB.next
            lb += 1
        if la > lb:
            headA, headB = headB, headA
            la,lb = lb,la
        curA, curB = headA, headB
        for i in range(lb - la):
            curB = curB.next
        while curA :
            # print(curA, '\n', curB)
            # print(id(curA), id(curB))
            # print(id(curA.val), id(curB.val))
            # print(id(curA.next), id(curB.next))
            # print(curA == curB)
            if curA is curB:
                return curA
            curA, curB = curA.next, curB.next
        return None

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
8
[4,1,8,4,5]
[5,0,1,8,4,5]
2
3
2
[0,9,1,2,4]
[3,2,4]
3
1
0
[2,6,4]
[1,5]
3
2

other

  1. object 相等的比较：需要实现 __ eq __ 类： https://stackoverflow.com/questions/14836228/is-there-a-standardized-method-to-swap-two-variables-in-python
  2. is vs == ： https://stackoverflow.com/questions/15008380/double-equals-vs-is-in-python

剑指 Offer 53 - I. 在排序数组中查找数字 I

solution

bisect

1
2
3
4
5
6
from bisect import *
class Solution:
    # Time (logn) 91%
    # Space o(1) extra 0%
    def search(self, nums: List[int], target: int) -> int:
        return bisect_right(nums, target) - bisect_left(nums, target)
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
from bisect import *
class Solution:
    # Time (logn) 91%
    # Space o(1) extra 0%
    def search(self, nums: List[int], target: int) -> int:
        def right(a, x):
            l, r = 0, len(a)
            while l < r:
                m = l + (r - l)//2
                if a[m] > x:
                    r = m
                else:
                    l = m + 1
            return l
        
        def left(a, x):
            l, r = 0, len(a)
            while l < r:
                m = l + (r-l)//2
                if a[m] < x:
                    l = m + 1
                else:
                    r = m
            return l
        r, l = right(nums, target) , left(nums, target)
        #print(r, l)
        return r - l

test cases

1
2
3
4
5
6
7
8
9
10
11
12
[5,7,7,8,8,10]
8
[5,7,7,8,8,10]
0
[5,7,7,8,8,10]
6
[5,7,7,8,8,10]
12
[5,7,7,7,8,10]
5
[5,7,7,7,8,10]
10

剑指 Offer 53 - II. 0～n-1中缺失的数字

solution

math

1
2
3
4
5
6
7
8
class Solution:
    # Time o(n) 64.13%
    # Space o(n) 49.20%
    # Date 20210421
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums) + 1
        total = (0 + n-1) * n//2
        return total - sum(nums)

binary search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # Time o(n) 94.21%
    # Space o(n) 7.29%
    # Date 20210421
    def missingNumber(self, nums: List[int]) -> int:
        l = 0
        r = len(nums)
        while l < r:
            m = l + (r - l)//2
            if nums[m] ==  m:
                l = m + 1
            else:
                r = m
        return l

test cases

1
2
3
4
5
[0,1,3]
[0,1,2,3,4,5,6,7,9]
[0]
[1]
[1,2]

剑指 Offer 54. 二叉搜索树的第k大节点

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # Time o(k) 93.56%
    # Space o(k) 97.30%
    # Date 20210421
    def kthLargest(self, root: TreeNode, k: int) -> int:
        count = 0
        nums = []
        def tras(root, nums):
            if not root or len(nums) == k:
                return
            tras(root.right, nums)
            if len(nums) == k:
                return 
            # print(root.val, nums)
            nums.append(root.val)
            tras(root.left, nums)
        tras(root, nums)
        #print(nums)
        return nums[-1]

test cases

1
2
3
4
5
6
[5,3,6,2,4,null,null,1]
3
[5,3,6,2,4,null,null,1]
5
[3,1,4,null,2]
1

剑指 Offer 55 - I. 二叉树的深度

solution

1
2
3
4
5
6
7
8
9
class Solution:
    # Time o(n) 76.52%
    # Space o(n) 7.47%
    def maxDepth(self, root: TreeNode) -> int:
        def dep(root):
            if not root:
                return 0
            return max(dep(root.left), dep(root.right)) + 1
        return dep(root)

test cases

1
2
3
[3,9,20,null,null,15,7]
[]
[1,2,3]

剑指 Offer 55 - II. 平衡二叉树

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    # Time o(n) 45.28%
    # Space o(1) extra 6.74
    def isBalanced(self, root: TreeNode) -> bool:
        def dep(root):
            if not root:
                return 0, True
            dl, fl = dep(root.left)
            dr, fr = dep(root.right)
            f = False if abs(dl - dr) > 1 else True
            f = f and fl and fr
            return max(dl, dr) + 1, f
        return dep(root)[1]

test case

1
2
3
[3,9,20,null,null,15,7]
[1,2,2,3,3,null,null,4,4]
[1,2,2,3,null,null,3,4,null,null,4]

剑指 Offer 56 - I. 数组中数字出现的次数

solution

bit manipulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # Time o(n) 84.10%
    # Space o(1) 98.83%
    # Date 20210422
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = nums[0]
        for n in nums[1:]:
            ret ^= n
        flg = 1
        while (flg & ret) == 0:
            flg <<= 1
        a = b = ret
        for n in nums:
            if flg & n == flg:
                a ^= n
            else:
                b ^= n
        return [a, b]

test cases

剑指 Offer 56 - II. 数组中数字出现的次数 II

solution

1
2
3
4
5
class Solution:
    # Time o(n) 99.16%
    # Space o(n) 75.39%
    def singleNumber(self, nums: List[int]) -> int:
        return (sum(set(nums)) * 3 - sum(nums))//2

test cases

1
2
[3,4,3,3]
[9,1,7,9,7,9,7]

剑指 Offer 57. 和为s的两个数字

solution

traverse

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # Time o(n^2) 18.01%
    # Space o(n) 57.81%
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for l in range(len(nums)):
            r = len(nums) - 1
            while nums[l] + nums[r] > target and r > l:
                r -= 1
            if nums[l] + nums[r] == target:
                return [nums[l], nums[r]]

two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    # Time o(n) 51.76%
    # Space o(n) 47.02%
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l, r = 0, len(nums) - 1
        while l < r-1 and nums[l] + nums[r] != target :
            if nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
        if nums[l] + nums[r] == target:
            return [nums[l], nums[r]]

test cases

1
2
[14,15,16,22,53,60]
76

剑指 Offer 57 - II. 和为s的连续正数序列

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # Time o(n) 78.33%
    # Space o(n^2) 97.74%
    # Date 20210422
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        ans = []
        cur = []
        count = 0
        for n in range(1, (target)//2 + 2):
            cur.append(n)
            count += n
            while count > target:
                count -= cur.pop(0)
            if count == target and len(cur) >= 2:
                ans.append(cur[:])
        return ans

test cases

1
2
3
4
5
6
1
5
9
15
28
1001

剑指 Offer 58 - I. 翻转单词顺序

solution

split

1
2
3
4
5
6
7
8
9
class Solution:
    # Time o(n) 89.90%
    # Space o(n) 66.50%
    # Date 20210422
    def reverseWords(self, s: str) -> str:
        dic = s.strip().split(' ')
        dic = [d.strip()  for d in dic if d!= '']
        # print(dic)
        return ' '.join(dic[::-1])

stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # Time o(n) 14.11%
    # Space o(n) 17.00%
    # Date 20210422
    def reverseWords(self, s: str) -> str:
        cur = ''
        ans = ''
        for c in s:
            # print(c, cur, ans)
            if c == ' ' and len(cur) > 0:
                ans = cur + ' ' + ans
                cur = ''
            elif c != ' ':
                cur += c
        ans = cur + ' ' + ans
        return ans.strip()

test cases

1
2
3
"the sky is blue"
"  hello world!  "
"a good   example"

剑指 Offer 58 - II. 左旋转字符串

solution

1
2
3
4
5
6
class Solution:
    # Time o(n) 68.97%
    # Space o(1) extra 61.17%
    # Date 20210422
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

test cases

1
2
3
4
"abcdefg"
2
"lrloseumgh"
6

剑指 Offer 59 - I. 滑动窗口的最大值

solution

deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque
class Solution:
    # Time o(n) 59.60 %
    # Space o(n) 5.28%
    # Date 20210422
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        cur = deque([])
        n = len(nums)
        ans = []
        for i in range(n):
            while len(cur)>0 and cur[0] <= i - k :
                cur.popleft()
            while len(cur)> 0 and nums[cur[-1]] < nums[i]:
                cur.pop()
            cur.append(i)
            ans.append(nums[cur[0]])
        return ans[k-1:]

test cases

1
2
3
4
[1,3,-1,-3,5,3,6,7]
3
[1,3,-1,-3,5,3,2,4,3,3,2,1,3,4,2,7]
3

剑指 Offer 59 - II. 队列的最大值

solution

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
30
31
32
33
34
35
36
37
38
class MaxQueue:
    # Time o(1) every op 76.14%
    # Space o(n) 32.02%
    # Date 20210422
    def __init__(self):
        self.que = []
        self.candi = []
        self.idx = 0


    def max_value(self) -> int:
        #print(self.que, self.candi, self.idx)
        if self.idx == len(self.que):
            return -1
        return self.que[self.candi[0]]

    def push_back(self, value: int) -> None:
        #print(value, self.que, self.candi, self.idx)
        self.que.append(value)
        while len(self.candi) > 0 and self.que[self.candi[-1]] < value:
            self.candi.pop()
        self.candi.append(len(self.que) - 1)

    def pop_front(self) -> int:
        #print(self.que, self.candi, self.idx)
        if self.idx == len(self.que):
            return -1
        if self.candi[0] == self.idx:
            self.candi.pop(0)
        self.idx += 1
        return self.que[self.idx-1]
    

# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()

test cases

1
2
3
4
5
6
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
["MaxQueue","push_back","push_back","max_value","pop_front","max_value","push_back","push_back","max_value","pop_front","max_value","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[],[3],[5],[],[],[],[2],[6],[],[],[]]
["MaxQueue","pop_front","max_value"]
[[],[],[]]

剑指 Offer 60. n个骰子的点数

solution

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    # Time o(n^2)
    # Space o(n)
    # Date 20210422
    def dicesProbability(self, n: int) -> List[float]:
        dp = [1/6] * 6
        for k in range(1,n):
            tmp = [0.0] *(5*(k+ 1)+1) 
            for i in range(len(dp)):
                for j in range(6):
                    tmp[i+j] += dp[i]/6
            dp = tmp
        return dp

剑指 Offer 61. 扑克牌中的顺子

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    # Time o(n) 83.20%
    # Space o(1) 86.67%
    # Date 20210422
    def isStraight(self, nums: List[int]) -> bool:
        nums.sort()
        candi = 0
        pre = -1
        for n in nums:
            if n == 0:
                candi  += 1
                continue
            if pre == n:
                return False
            if pre == -1:
                pre = n
            while n - pre > 1 and candi > 0:
                candi-= 1
                pre += 1
            if n - pre >1:
                return False
            pre = n
        return True

test cases

1
2
3
[1,2,1,4,3]
[2,3,4,1,5]
[0,1,2,3,0]

剑指 Offer 62. 圆圈中最后剩下的数字

solution

array

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # Time o(n) 16.97%
    # Space o(n) 21.18%
    def lastRemaining(self, n: int, m: int) -> int:
       	f = 0
        for i in range(1,n):
            f = (f + m)
        while len(nums) > 1:
            cur = (pre + m-1) % len(nums)
            nums.pop(cur)
            pre = cur
        return nums[-1]

dp

1
2
3
4
5
6
7
8
class Solution:
    # Time o(n) 79.28%
    # Space o(n) 47.77%
    def lastRemaining(self, n: int, m: int) -> int:
        ans = 0
        for i in range(2, n+1):
            ans = (ans + m) %i
        return ans

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
3
10
17
8
9
3
5
1
1
3
3
2
5

剑指 Offer 63. 股票的最大利润

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    # Time o(n) 91.68%
    # space o(1) extra 84.67%
    # Date 20210422
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        ans = 0
        left_min = prices[0]
        for p in prices[1:]:
            ans = max(ans, p - left_min)
            left_min = min(left_min, p)
        return ans

test cases

1
2
3
[7,1,5,3,6,4]
[7,6,4,3,1]
[2,3,4,3,2,3,3,2,1,4,5,8,3,2,9]

剑指 Offer 64. 求1+2+…+n

solution

and operator

利用了 python and，如果前半部分为 True，后半部分就不会再做比较的性质。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # Time o(n) 42.57%
    # Space o(n) 43.44%
    # Date 20210422 
    def __init__(self):
        self.ans = 0
    def sumNums(self, n: int) -> int:
        n > 1 and self.sumNums(n-1)
        self.ans += n 
        return  self.ans

ref : LCCN 评论区

test cases

1
3

剑指 Offer 65. 不用加减乘除做加法

solution

bit manipulation

1
2
3
4
5
6
7
class Solution:
    def add(self, a: int, b: int) -> int:
        x = 0xffffffff
        a, b = a & x, b & x
        while b != 0:
            a, b = (a ^ b), (a & b) << 1 & x
        return a if a <= 0x7fffffff else ~(a ^ x)

cr. KrahetsL6

test cases

1
2
1
1

剑指 Offer 66. 构建乘积数组

solution

recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # Time o(nlogn) 5.7%
    # Space o(n) 24.25%
    # Date 20210422
    def constructArr(self, a: List[int]) -> List[int]:
        def rec(a, l, r):
            if r - l == 1:
                return [1], a[l]
            m = (l + r)//2
            left, pdleft = rec(a, l ,m)
            right, pdright = rec(a, m, r)
            left = [i * pdright for i in left]
            right = [i * pdleft for i in right]
            return left + right, pdright* pdleft
        if len(a) == 0:
            return []
        return rec(a, 0, len(a))[0]

test cases

1
2
3
4
[1, 2, 3, 4, 5]
[]
[2,3,4,3,2,1,32]
[3,3,3,2,1,3,1,1]

剑指 Offer 67. 把字符串转换成整数

solution

array

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
30
31
32
33
class Solution:
    # Time o(n) 19.83%
    # Space o(n) 14.57%
    # Date 20210422
    def strToInt(self, str: str) -> int:
        MAX_INT = 2147483647
        s = str
        ans = 0
        sgn = 0
        s = s.strip()
        if len(s) == 0:
            return 0
        # print(s.strip())
        if s[0] == '-':
            sgn = -1
        elif s[0] == '+':
            sgn = 1
        elif s[0].isdecimal():
            sgn = 1
            ans = ord(s[0]) - ord('0')
        else:
            return ans
        for c in s[1:]:
            if c.isdecimal():
                ans = ans*10 + ord(c) - ord('0')
            else:
                break
        if sgn == -1 and ans > (MAX_INT +1):
            return -(MAX_INT + 1)
        elif sgn == 1 and ans > MAX_INT:
            return MAX_INT
        #print(sgn, ans, ans > (MAX_INT +1), MAX_INT)
        return sgn * ans

test cases

1
2
3
4
5
6
7
"42"
"--42000"
""
" "
"+42"
"words and 987"
"-91283472332"

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

solution

brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    # Time o(n) 26.61%
    # Space o(n) 16.53%
    # Date 20210422
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        candi = [0,0]
        ans  = None
        def tras(root):
            nonlocal ans
            if not root:
                return 0
            count = tras(root.left)
            count += tras(root.right)
            if root is p or root is q:
                count += 1
            if count == 2 and ans == None:
                ans = root
            return count
        tras(root)
        return ans

这道题讲真碰到好几次了，每次都忘记考虑搜索树这个问题！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # Time o(n) 82.32%
    # Space o(n) 11.92%
    # Date 20210422
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val > q.val:
            p, q = q, p
        while root:
            if root.val < p.val:
                root = root.right
            elif root.val > q.val:
                root = root.left
            else:
                break
        return root

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[6,2,8,0,4,7,9,null,null,3,5]
2
8
[6,2,8,0,4,7,9,null,null,3,5]
2
4
[6,2,8,0,4,7,9,null,null,3,5]
8
9
[6,2,8,0,4,7,9,null,null,3,5]
2
3
[6,2,8,0,4,7,9,null,null,3,5]
2
5
[6,2,8,0,4,7,9,null,null,3,5]
0
9
[6,2,8,0,4,7,9,null,null,3,5]
7
9

剑指 Offer 68 - II. 二叉树的最近公共祖先

solution

brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    # Time o(n) 52.92%
    # Space o(n) 10.06%
    # Date 20210422
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        candi = [0,0]
        ans  = None
        def tras(root):
            nonlocal ans
            if not root:
                return 0
            count = tras(root.left)
            count += tras(root.right)
            if root is p or root is q:
                count += 1
            if count == 2 and ans == None:
                ans = root
            return count
        tras(root)
        return ans

recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # Time o(n) 92.59%
    # Space o(n) 59.30%
    # Date 20210422
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root is p or root is q:
            return root
        left =  self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

test cases

1
2
3
4
5
6
[3,5,1,6,2,0,8,null,null,7,4]
5
1
[3,5,1,6,2,0,8,null,null,7,4]
5
4