每日一题(leetcode)

发表于 更新于

70. 爬楼梯 (2021.3.15)

1. 递归法/动态规划

1
2
3
4
5
6
class Solution:
    @lru_cache
    def climbStairs(self, n: int) -> int:

        if n <= 2: return n
        return self.climbStairs(n-2) + self.climbStairs(n-1)

2. 迭代法

1
2
3
4
5
6
class Solution:
    def climbStairs(self, n: int) -> int:
        a = b = 1
        for i in range(n):
            a, b = b, a + b
        return a

22. 括号生成 (2021.3.16)

1. 动态规划（打死我也想不出来的方法~）

1
2
3
4
5
6
7
8
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = [[] for _ in range(n+1)]
        res[0] = [""]
        for i in range(n+1):
            for j in range(i):
                res[i] += ["(" + x + ")" + y for x in res[j] for y in res[i-j-1]]
        return res[n]

2. 递归 + 剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def recursion(left, right, res, n, str_):
            if (left == n) and (right == n):
                res.append(str_)
                return None
            if left < n:
                recursion(left+1, right, res, n, str_ + '(')
            if left > right:
                recursion(left, right+1, res, n, str_ + ')')

        recursion(0, 0, res, n, '')
        return res

51. N 皇后 & 面试题 08.12. 八皇后

1. 回溯法 (2021.3.17)

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:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n < 1: return []
        self.res = []
        self.col = set()
        self.pie = set()
        self.na = set()
        self.dfs(0, n, [])
        return [[col*"." + "Q" + (n-col-1)*"." for col in sub_res] for sub_res in self.res]

    def dfs(self, row, n, cur):
        # 递归终止条件
        if row >= n:
            self.res.append(cur)
            return None

        for col in range(n):
            # 条件判断
            if (col in self.col) or (row + col in self.pie) or (row - col in self.na):
                continue
            self.col.add(col)
            self.pie.add(row + col)
            self.na.add(row - col)
            # 下探到下一层递归
            self.dfs(row+1, n, cur+[col])
            # 恢复当前层状态空间
            self.col.remove(col)
            self.pie.remove(row + col)
            self.na.remove(row - col)

2. 位运算 (2021.3.31)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n < 1: return []
        self.res = []
        self.dfs(n, 0, 0, 0, 0, [])
        return [['.'*sub_res + 'Q' + '.'*(n-sub_res-1) for sub_res in res] for res in self.res]


    def dfs(self, n, row, col, pie, na, cur):
        if row >= n:
            self.res.append(cur)
            return

        bits = (~(col | pie | na)) & ((1 << n) - 1)

        while bits:
            pos = bits & -bits
            pos_ = bin(pos -1).count('1')
            bits = bits & (bits - 1)
            self.dfs(n, row + 1, col | pos, (pie | pos) << 1, (na | pos) >> 1, cur+[pos_])

36. 有效的数独 (2021.3.18)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        row = [{} for _ in range(9)]
        col = [{} for _ in range(9)]
        sub = [{} for _ in range(9)]

        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    block = (i//3)*3 + j//3
                    num = int(board[i][j])
                    row[i][num] = row[i].get(num, 0) + 1
                    col[j][num] = col[j].get(num, 0) + 1
                    sub[block][num] = sub[block].get(num, 0) + 1

                    if row[i][num] > 1 or col[j][num] > 1 or sub[block][num] > 1:
                        return False
        return True

下面是国际区大佬的答案（我稍微改了一下，不然没法通过），😔望尘莫及~

1
2
3
4
5
6
7
8
9
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        seen = sum(([(c, i), (j, c), ((i//3)*3 + j//3, c, "#")]
            for i, row in enumerate(board)
            for j, c in enumerate(row)
            if c != '.'), [])

        return len(seen) == len(set(seen))

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        return 1 == max(list(collections.Counter(
        x
        for i, row in enumerate(board)
        for j, c in enumerate(row)
        if c != '.'
        for x in ((c, i), (j, c), ((i//3)*3 + j//3, c, "#"))
        ).values()) + [1])

37. 解数独 (2021.3.19)

1. DFS

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 Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        row = [set(range(1,10)) for _ in range(9)]
        col = [set(range(1,10)) for _ in range(9)]
        block = [set(range(1,10)) for _ in range(9)]

        emp = []
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    emp.append((i, j))
                else:
                    sub_block = (i//3)*3 + j//3
                    row[i].remove(int(board[i][j]))
                    col[j].remove(int(board[i][j]))
                    block[sub_block].remove(int(board[i][j]))

        def dfs(iter=0):
            if iter == len(emp):
                return True
            i, j = emp[iter]
            sub = (i//3)*3 + j//3
            for num in row[i] & col[j] & block[sub]:
                board[i][j] = str(num)
                row[i].remove(num)
                col[j].remove(num)
                block[sub].remove(num)
                if dfs(iter + 1):
                    return True
                row[i].add(num)
                col[j].add(num)
                block[sub].add(num)
            return False

        dfs()

127. 单词接龙 (2021.3.20)

1. BFS

这是超时的代码，今天没时间了，明天再解决超时问题吧😔

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
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        def change(str1, str2):
            count = 0
            for i, char in enumerate(str1):
                if char != str2[i]: count += 1
            if count == 1:
                return True
            else:
                return False

        res = [[beginWord]]
        res_len = []

        while res:
            cada = res.pop(0)
            for word in wordList:
                if word not in cada:
                    if change(word, cada[-1]):
                        cada.append(word)
                        if word == endWord:
                            res_len.append(len(cada))
                        res.append(cada[:])
                        cada.pop()
        if len(res_len) == 0:
            return 0
        else:
            return min(res_len)

今天发现循环列表的思路确实不太行，借鉴了大佬们的想法重新修改后，发现用列表实现队列的方式还是会超时~ (2021.3.21)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        wordList = list(set(wordList))
        if beginWord in wordList:
            wordList.remove(beginWord)
        if endWord not in wordList:
            return 0

        res = [[beginWord, 1]]

        while res:
            cada = res.pop(0)
            for i in range(len(cada[0])):
                for j in string.ascii_lowercase:
                    next_word = cada[0][:i] + j + cada[0][i+1:]
                    if next_word in wordList:
                        wordList.remove(next_word)
                        if next_word == endWord:
                            return cada[1]+1
                        res.append([next_word, cada[1]+1])
        return 0

这是BFS最后通过的代码，感觉自己真的太弱了😔
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        wordList = set(wordList)
        if beginWord in wordList:
            wordList.remove(beginWord)
        if endWord not in wordList:
            return 0

        res = collections.deque([[beginWord, 1]])

        while res:
            word, length = res.popleft()
            if word == endWord:
                return length
            for i in range(len(word)):
                for j in string.ascii_lowercase:
                    next_word = word[:i] + j + word[i+1:]
                    if next_word in wordList:
                        wordList.remove(next_word)
                        res.append([next_word, length+1])
        return 0

2. 双向BFS(Two-ended BFS) (2021.3.22)

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:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        if endWord not in wordList: return 0

        wordList = set(wordList)
        front = {beginWord}
        back = {endWord}
        dist = 1
        word_len = len(beginWord)

        while front:
            dist += 1
            next_set = set()
            for word in front:
                for i in range(word_len):
                    for c in string.ascii_lowercase:
                        if c != word[i]:
                            new_word = word[:i] + c + word[i+1:]
                            if new_word in back:
                                return dist
                            if new_word in wordList:
                                next_set.add(new_word)
                                wordList.remove(new_word)
            front = next_set
            if len(front) > len(back):
                front, back = back, front
        return 0

773. 滑动谜题 (2021.3.23)

1. BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:

        board = board[0] + board[1]
        mover = [(1,3), (0, 2, 4), (1, 5), (0, 4), (1, 3, 5), (2, 4)]
        q, visited = [(tuple(board), board.index(0), 0)], set()

        while q:
            state, loc, dis = q.pop(0)
            if state == (1,2,3,4,5,0):
                return dis
            for next_ in mover[loc]:
                _state = list(state)
                _state[next_], _state[loc] = _state[loc], _state[next_]
                _state = tuple(_state)
                if _state not in visited:
                    q.append((_state, _state.index(0), dis+1))
            visited.add(state)
        return -1

2. A*搜索————-待解决

1143. 最长公共子序列 (2021.3.25)

1. DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        if not text1 or not text2:
            return 0

        m = len(text1)
        n = len(text2)
        length = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    length[i][j] = length[i-1][j-1] + 1
                else:
                    length[i][j] = max(length[i-1][j], length[i][j-1])

        return length[m][n]

146. LRU 缓存机制 (2021.4.1)

1. 使用collections.OrderedDict数据结构

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 collections import OrderedDict
class LRUCache:

    def __init__(self, capacity: int):
        self.LRU = OrderedDict()
        self.remain = capacity


    def get(self, key: int) -> int:
        if key in self.LRU:
            v = self.LRU.pop(key)
            self.LRU[key] = v
            return v
        else:
            return -1


    def put(self, key: int, value: int) -> None:
        if key in self.LRU:
            self.LRU.pop(key)
            self.LRU[key] = value
        else:
            if self.remain > 0:
                self.remain -= 1
            else:
                self.LRU.popitem(last=False)
            self.LRU[key] = value

2. 哈希表 + 双向链表 (2021.4.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
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
58
59
60
61
62
63
class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.pre = None
        self.nex = None


class LRUCache:
    def __init__(self, capacity: int):
        self.LRUHash = dict()
        self.remain = capacity
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.nex = self.tail
        self.tail.pre = self.head


    def get(self, key: int) -> int:
        if key in self.LRUHash:
            node = self.LRUHash[key]
            self.removeToHead(node)
            return node.value
        else:
            return -1


    def put(self, key: int, value: int) -> None:
        if key in self.LRUHash:
            node = self.LRUHash[key]
            node.value = value
            self.removeToHead(node)
        else:
            if self.remain > 0:
                self.remain -= 1
            else:
                self.removeTail()
            node = DLinkedNode(key, value)
            self.LRUHash[key] = node
            self.addToHead(node)


    def addToHead(self, node):
        node.pre = self.head
        node.nex = self.head.nex
        self.head.nex.pre = node
        self.head.nex = node


    def removeToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)


    def removeNode(self, node):
        node.pre.nex = node.nex
        node.nex.pre = node.pre


    def removeTail(self):
        node = self.tail.pre
        self.removeNode(node)
        self.LRUHash.pop(node.key)

493. 翻转对 (2021.4.11)

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
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0

        def mergeSort(arr, left, right):
            if right <= left: return 0
            mid = (left + right) >> 1
            count = mergeSort(arr, left, mid) + mergeSort(arr, mid+1, right)
            temp = [0] * (right - left + 1)
            i, t, k = left, left, 0
            for j in range(mid+1, right+1):
                while (i<=mid) and (arr[i]<=2*arr[j]):
                    i += 1
                while (t<=mid) and (arr[t]<arr[j]):
                    temp[k] = arr[t]
                    k += 1; t += 1
                temp[k] = arr[j]; k += 1
                count += mid - i + 1
            while t<=mid:
                temp[k] = arr[t]
                k += 1; t += 1
            for p in range(k):
                arr[left+p] = temp[p]
            return count

        return mergeSort(nums, 0, len(nums)-1)

5. 最长回文子串 (2021.4.16)

1. DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_len = 1
        res = s[0]
        length = len(s)
        dp = [[False for _ in range(length)] for _ in range(length)]

        for j in range(0, length):
            for i in range(0, j+1):
                dp[i][j] = (s[i]==s[j]) and (j-i<2 or dp[i+1][j-1])

                if dp[i][j] and j-i+1 > max_len:
                    max_len = j-i+1
                    res = s[i:j+1]
        return res

2. 中心扩展算法 (2021.4.17)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s: str) -> str:

        self.length = len(s)
        self.max_len = 1
        self.start = 0

        def extend(s, left, right):
            while left >= 0 and right < self.length and s[left] == s[right]:
                if right-left+1 > self.max_len:
                    self.max_len = right-left+1
                    self.start = left
                left -= 1
                right += 1

        for i in range(self.length):
            extend(s, i, i)
            extend(s, i, i+1)
        return s[self.start:self.start+self.max_len]

10. 正则表达式匹配 (2021.4.19)

1. DP (暴力)

1
2
3
4
5
6
7
8
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s
        first_match = bool(s) and p[0] in [s[0], '.']
        if len(p) >= 2 and p[1] == '*':
            return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))
        else:
            return first_match and self.isMatch(s[1:], p[1:])

2. DP (带缓存)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        s_length, p_length = len(s), len(p)
        memo = {}
        def dp(i, j):
            if (i, j) in memo: return memo[(i, j)]
            if j == p_length:
                return i == s_length
            first_match = i < s_length and p[j] in [s[i], '.']
            if j <= p_length-2 and p[j+1] == '*':
                tmp = dp(i, j+2) or (first_match and dp(i+1, j))
            else:
                tmp = first_match and dp(i+1, j+1)
            memo[(i, j)] = tmp
            return tmp
        return dp(0, 0)

115. 不同的子序列 (2021.4.19)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        s_length, t_length = len(s), len(t)
        dp = [[1]*(s_length+1)] + [[0]*(s_length+1) for _ in range(t_length)]
        for i in range(1, t_length + 1):
            for j in range(1, s_length + 1):
                if t[i-1] == s[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]
        return dp[t_length][s_length]

283. 移动零 (2021.5.12)

使用 j 指针记录非零元素应该填入的位置

1
2
3
4
5
6
7
8
9
10
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1

11. 盛最多水的容器

双指针夹逼法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxArea(self, height: List[int]) -> int:
        # max_area = 0
        # for i in range(len(height)):
        #     for j in range(i, len(height)):
        #         area = (j-i) * min(height[i], height[j])
        #         max_area = max(max_area, area)
        # return max_area

        max_area = 0
        left, right = 0, len(height)-1
        while(left < right):
            area = (right - left) * min(height[left], height[right])
            max_area = max(max_area, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

70. 爬楼梯 (2021.5.13)

找最近重复子问题

1
2
3
4
5
6
7
8
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        f1, f2 = 1, 2
        for i in range(3, n + 1):
            f1, f2 = f2, f1+f2
        return f2

1. 两数之和

1. 暴力法 —-> 两重循环
2. 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # for i in range(len(nums)):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] + nums[j] == target:
        #             return [i, j]

        hash_dic = dict()
        for i, num in enumerate(nums):
            if target - num in hash_dic:
                return [i, hash_dic[target - num]]
            hash_dic[num] = i
        return []

15. 三数之和 (2021.5.14)

双指针夹逼法

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # result = []
        # for index, target in enumerate(nums):
        #     for i in range(index+1, len(nums)):
        #         for j in range(i+1, len(nums)):
        #             if nums[i] + nums[j] + target == 0:
        #                 result.append([nums[i], nums[j], target])
        # return result


        # result = set()
        # nums.sort()
        # for index, target in enumerate(nums):
        #     left = index + 1
        #     right = len(nums) - 1
        #     while(left < right):
        #         if target + nums[left] + nums[right] == 0:
        #             result.add((target, nums[left], nums[right]))
        #             left += 1
        #             right -= 1
        #         elif nums[left] + nums[right] > -target:
        #             right -= 1
        #         else:
        #             left += 1
        # return list(result)


        result = []
        nums.sort()
        for index, target in enumerate(nums):
            left = index + 1
            right = len(nums) - 1
            if index > 0 and nums[index] == nums[index - 1]: continue
            while(left < right):
                sum = target + nums[left] + nums[right]
                if sum > 0:
                    right -= 1
                elif sum < 0:
                    left += 1
                else:
                    result.append([target, nums[left], nums[right]])
                    while (left < right and nums[left] == nums[left + 1]):
                        left += 1
                    while (left < right and nums[right] == nums[right - 1]):
                        right -= 1
                    left += 1
                    right -= 1
        return result

206. 反转链表 (2021.5.15)

链表题只能是多练习，无技巧可言，熟能生巧

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:
    def reverseList(self, head: ListNode) -> ListNode:
        # pre, cur = None, head
        # while cur:
        #     temp = pre
        #     pre, cur = cur, cur.next
        #     pre.next = temp
        #     # temp = cur.next
        #     # cur.next = pre
        #     # pre = cur
        #     # cur = temp
        # return pre

        # if not head or not head.next:
        #     return head
        # newHead = self.reverseList(head.next)
        # head.next.next = head
        # head.next = None
        # return newHead

        def recur(head, pre=None):
            if not head:
                return pre
            next_ = head.next
            head.next = pre
            return recur(next_, head)

        return recur(head, None)

24. 两两交换链表中的节点 (2021.5.19)

递归有点难想呀，迭代方法要添加一个多余的节点来简化递归过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        # if head == None or head.next == None:
        #     return head
        # nextNode = head.next
        # head.next = self.swapPairs(nextNode.next)
        # nextNode.next = head
        # return nextNode

        dummyNode = ListNode(0)
        dummyNode.next = head
        temp = dummyNode
        while temp.next and temp.next.next:
            Node1 = temp.next
            Node2 = temp.next.next
            temp.next = Node2
            Node1.next = Node2.next
            Node2.next = Node1
            temp = Node1
        return dummyNode.next

141. 环形链表

1. 哈希表记录
2. 快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def hasCycle(self, head: ListNode) -> bool:

        # slow, quick = head, head
        # try:
        #     while slow and quick:
        #         quick = quick.next.next
        #         slow = slow.next
        #         if quick == slow:
        #             return True
        # except:
        #     return False

        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

142. 环形链表 II (2021.5.25)

1. 哈希表记录
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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:

        # visited = set()
        # while head:
        #     if head in visited:
        #         return head
        #     else:
        #         visited.add(head)
        #     head = head.next
        # return None

        fast, slow = head, head
        while True:
            if not (fast and fast.next):
                return None
            fast, slow = fast.next.next, slow.next
            if fast == slow:
                break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

292. Nim 游戏 (2021.9.18)

数学推理

1
2
3
4
5
6
class Solution:
    def canWinNim(self, n: int) -> bool:
        if n % 4 == 0:
            return False
        else:
            return True

36. 有效的数独 (2021.9.18)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [{} for _ in range(9)]
        col = [{} for _ in range(9)]
        block = [{} for _ in range(9)]

        for i in range(len(board)):
            for j in range(len(board[0])):
                num = board[i][j]
                if num != '.':
                    row[i][num] = row[i].get(num, 0) + 1
                    col[j][num] = col[j].get(num, 0) + 1
                    block[(i//3)*3+(j//3)][num] = block[(i//3)*3+(j//3)].get(num, 0) + 1

                    if row[i][num] > 1 or col[j][num] > 1 or block[(i//3)*3+(j//3)][num] > 1:
                        return False
        return True

剑指 Offer II 069. 山峰数组的顶部 (2021.10.14)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        # for i, num in enumerate(arr):
        #     if num > arr[i+1]:
        #         return i

        left, right, res = 0, len(arr)-1, -1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > arr[mid+1]:
                right = mid - 1
                res = mid
            else:
                left = mid + 1
        return res

412. Fizz Buzz (2021.10.14)

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
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        # res = []
        # for i in range(n):
        #     index = i + 1
        #     if index % 15 == 0:
        #         res.append('FizzBuzz')
        #     elif index % 5 == 0:
        #         res.append('Buzz')
        #     elif index % 3 == 0:
        #         res.append('Fizz')
        #     else:
        #         res.append(str(index))
        # return res

        ans = []
        for i in range(1, n + 1):
            s = ''
            if i % 3 == 0:
                s += 'Fizz'
            if i % 5 == 0:
                s += 'Buzz'
            if s == '':
                s = str(i)
            ans.append(s)
        return ans
-------------本文结束感谢您的阅读-------------