亚洲国产另类在线观看,中国熟妇久久com,国产精999

這里是 HOT 100刷題筆記，篇幅較長，因此分成兩部分，按照題目序號排列。有幾題沒做后序會補上。

兩數(shù)之和

比較好的辦法就是利用map來存儲每一個元素以及其對應的索引，但是這里要考慮到map是無法存儲重復的key，因此我們在判斷是否存在滿足符合條件的，一個為原數(shù)組中的索引，另一個為Map中的索引這個一定要注意。

解法1：
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        Map = {}
        for i in range(len(nums)):
            Map[nums[i]] = i
        for i in range(len(nums)):
            j = Map.get(target - nums[i])
            if j and j != i:
                return[i, j]
        return []
        
解法2：（將兩個for循環(huán)合并一下，可以讓程序提前終止，讓Map存儲當前元素之前的信息）
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        Map = {}
        for i in range(len(nums)):
            j = Map.get(target - nums[i])
            if j != None :
                return[j, i]
            Map[nums[i]] = i #這一步的順序不能調(diào)換
        return []

兩數(shù)相加

這一題其實就是兩個鏈表相加，這一需要考慮到兩個鏈表的長度不一致和進位的情況，這一題還有一個小技巧，就是使用一個頭節(jié)點，這樣代碼寫起來更方便。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s = 0
        head = p = ListNode(0)
        while(l1 or l2 or s):
            s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
            p.next = ListNode(s%10)
            p = p.next
            s = s // 10
            if l1:
                l1 = l1.next
            else:
                l1 = None
            if l2:
                l2 = l2.next
            else:
                l2 = None
        return head.next

最長無重復子串

經(jīng)典的滑動窗口題目，模板題，詳情參考：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = {}
        left = 0
        right = 0
        length = len(s)
        res = 0
        while(right < length):
            c = s[right]
            if c not in window:
                window[c] = 1
            else:
                window[c] += 1
            right += 1
            while(window[c] > 1):
                d = s[left]
                left += 1
                window[d] -= 1
            res = max(res, right-left)
        return res

最長回文子串

這一題與647回文字串這一題一樣，具體的我就不多說了。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ''
        length = len(s)
        dp = [[0]*length for i in range(length)]
        for i in range(length):
            for j in range(length):
                if i == j:
                    dp[i][j] = 1
        maxlength = 1
        res = s[0]
        for i in range(length-1, -1, -1):
            for j in range(i+1, length):
                if s[j] == s[i]:
                    if j == i+1:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = 0
                if dp[i][j] == 1:
                    if j - i + 1 > maxlength:
                        maxlength = j - i + 1
                        res = s[i:j+1]
        return res

盛最多水的容器

簡單的DP:
$res = max{min(a[i], a[j])*(j - i)}$
采用雙指針進行搜索，將a[i]和a[j]中較小的坐標進行移動，因為將較大的往里進行移動，最終的結(jié)果一定會變小。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        res = -99999999
        while(i <= j):
            res = max(res, min(height[i], height[j])*(j - i))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return res

三數(shù)之和

參考：https://blog.csdn.net/sd4567855/article/details/86777399 先排序再利用雙指針來去重。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        length = len(nums)
        if length < 3 or nums[0] > 0 or nums[-1] < 0 :
            return res
        for i in range(length-2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i-1] == nums[i]:
                continue
            j = i + 1
            k = length - 1
            while(j < k):
                if nums[i] + nums[j] + nums[k] == 0:
                    res.append([nums[i], nums[j], nums[k]])
                    while(j < k and nums[j] == nums[j+1]):
                        j += 1
                    while(j < k and nums[k-1] == nums[k]):
                        k -= 1
                    j += 1
                    k -= 1
                elif nums[i] + nums[j] + nums[k] > 0:
                    k -= 1
                else:
                    j += 1
        return res

電話號碼的字母組合

簡單的DFS即可。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        Dict = {'2':{'a', 'b', 'c'}, 
        '3':{'d', 'e', 'f'}, '4':{'g', 'h', 'i'}, '5':{'j', 'k', 'l'}, 
        '6':{'m', 'n', 'o'}, '7':{'p', 'q', 'r', 's'}, '8':{'t', 'u', 'v'}, 
        '9':{'w', 'x', 'y', 'z'}}
        length = len(digits)
        res = []
        def dfs(route, count):
            if count == length:
                res.append(route)
                return
            for c in Dict[digits[count]]:
                dfs(route + c, count + 1)
        dfs('', 0)
        return res

刪除鏈表的倒數(shù)第N個節(jié)點

快慢指針，基本操作，需要注意的是有一種情況是直接刪除頭節(jié)點。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head:
            return None
        temp = head
        count = 0
        while(temp):
            count += 1
            if count == n:
                break
            temp = temp.next
        
        slow = head
        fast = temp

        pre = None
        while(fast.next):
            fast = fast.next
            pre = slow
            slow = slow.next
        if not pre:
            return head.next
        pre.next = slow.next
        return head

有效的括號

比較直接的方法就是利用python的正則表達式直接對這三種括號進行替換。

借助棧結(jié)構(gòu)來完成括號的匹配操作。

解法1：
class Solution:
    def isValid(self, s: str) -> bool:
        while('()' in s or '{}' in s or '[]' in s):
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
        return s == ''

解法2：
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c == '(' or c == '[' or c == '{':
                stack.append(c)
            else:
                if not stack:
                    return False
                if c == ')':
                    temp = stack.pop()
                    if temp != '(':
                        return False
                elif c == ']':
                    temp = stack.pop()
                    if temp != '[':
                        return False
                elif c == '}':
                    temp = stack.pop()
                    if temp != '{':
                        return False
        return stack == []

合并兩個有序鏈表

正常的鏈表遍歷操作，注意在合并鏈表的時候，除了要保存頭節(jié)點以外，還需要用一個指針來記錄鏈表當前節(jié)點的位置。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        head1 = l1
        head2 = l2
        head3 = None
        temp = None
        if head1.val <= head2.val:
            head3 = head1
            temp = head3
            head1 = head1.next
        else:
            head3 = head2
            temp = head3
            head2 = head2.next
        while(head1 and head2):
            if head1.val <= head2.val:
                temp.next = head1
                temp = head1
                head1 = head1.next
            else:
                temp.next = head2
                temp = head2
                head2 = head2.next
        while(head1):
            temp.next = head1
            temp = head1
            head1 = head1.next
        while(head2):
            temp.next = head2
            temp = head2
            head2 = head2.next
        return head3

括號生成

https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/
這一題使用遞歸比較符合正常的想法，同樣需要設計好遞歸函數(shù)的參數(shù)，這里使用route，left，right這三個參數(shù)，分別表示存儲的路徑，左括號還剩余的數(shù)量，右括號還剩余的數(shù)量，該遞歸函數(shù)沒有返回值，使用全局變量來存儲不同的路徑。
當左右剩余的括號數(shù)量為0的時候，表明找到了滿足題意的路徑。
當剩余的左括號數(shù)量大于剩余的右括號數(shù)量的時候，程序終止，因為這樣生成的路徑一點不滿足題意。
左右剩余的括號數(shù)量大于0的時候，才進行下一次擴展。

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

        def dfs(route, left, right):
            if left == 0 and right == 0:
                res.append(route)
                return
            if left > right:
                return
            if left > 0:
                dfs(route + '(', left - 1, right)
            if right > 0:
                dfs(route + ')', left, right - 1)

        dfs('', n, n)
        return res

合并K個排序鏈表

比較直觀的做法，直接利用分治的方法，接下來的重點就是如何設計好遞歸函數(shù)的參數(shù)了。
遞歸函數(shù)的參數(shù)還是借用二分的寫法，采用左右邊界來確定鏈表的個數(shù)。
也可以通過建立一個堆來合并這k個鏈表。

解法1：
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:

        def merge(l1, l2):
            p = ListNode()
            temp = p
            while(l1 and l2):
                if l1.val < l2.val:
                    temp.next = l1
                    l1 = l1.next
                else:
                    temp.next = l2
                    l2 = l2.next
                temp = temp.next
            if l1 :
                temp.next = l1
            else:
                temp.next = l2
            return p.next
    
        def recursion(l, r):
            if l == r:
                return lists[l]
            if l > r:
                return
            mid = (l + r) // 2
            left = recursion(l, mid)
            right = recursion(mid + 1, r)
            return merge(left, right)
        
        return recursion(0, len(lists) - 1)

解法2：
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
from heapq import heappush, heappop

class MyNode:
    def __init__(self, node):
        self.node = node
    
    def __lt__(self, other):
        if self.node.val <= other.node.val:
            return True
        else: return False
    
    def get(self):
        return self.node


class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        heap = []
        for l in lists:
            if l:
                heappush(heap, MyNode(l))
        
        p = head = ListNode(0)
        while heap:
            node = heappop(heap)
            p.next = node.get()
            p = p.next
            if node.get().next:
                heappush(heap, MyNode(node.get().next))
        return head.next

下一個排列

求下一個排列有著比較標準的算法，這個在組合數(shù)學上都有專門講過，C++中STL也專門封裝了這個方法。算法分為三步：

從后往前搜，找到第一個跳變：要求后一個大于前一個，如果沒有說明當前排列已經(jīng)是最大的了。

通過前面的跳變查找將數(shù)組分成了前后兩個部分，在后面部分的數(shù)組中找到第一個大于跳變的那個數(shù)，進行交換。

將后面部分的數(shù)組按照從小到達的順序進行交換。
語言表述可能不是很清楚，參考：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums) - 1
        i = length
        while(i >= 1 and nums[i-1] >= nums[i]):
            i -= 1
        if i == 0:
            nums.reverse()
            return nums
        j = length
        
        while(j >= 0 and nums[j] <= nums[i-1]):
            j -= 1
        temp = nums[j]
        nums[j] = nums[i-1]
        nums[i-1] = temp
        
        res = nums[i:]
        for i in range(len(res)):
            nums[length-i] = res[i]
        return nums

最長有效括號

直觀上來看需要用到棧這樣的結(jié)構(gòu)。需要記錄啥時候入棧，啥時候會出棧。當棧為空的時候，當前元素為'('或者當前棧頂元素為')'入棧，否則出棧，入棧的是字符的索引，這樣方便計算出括號的長度。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if s == "":
            return 0
        stack = []
        res = 0
        for index, c in enumerate(s):
            if not stack or c == '(' or s[stack[-1]] == ')': #注意細節(jié)
                stack.append(index)
            else:
                stack.pop()
                temp = stack[-1] if stack else -1 #注意細節(jié)
                res = max(res, index - temp )
        return  res

搜索旋轉(zhuǎn)排序數(shù)組

那這一題顯然是要用二分查找，但是這一題卻是局部有序，因此我們需要在原始的二分查找上面進行一些改動，一半來說二分查找的難點在于邊界條件。首先需要判斷元素是在左邊部分還是右邊部分，然后對于左邊部分和右邊部分需要各自判斷其的左右部分。

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

在排序數(shù)組中查找元素的第一個和最后一個位置

二分法查找左邊界和右邊界，二分法的細節(jié)太難寫了，開區(qū)間還是閉區(qū)間，等于還是不等于都需要注意。這里還有一種寫法來求左右邊界，如果有那么就一直向左移動或者是向右移動，沒有的話就返回-1。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def serachLeft(nums):
            if not nums:
                return -1
            left = 0
            right = len(nums) - 1
            while(left <= right):
                mid = (left + right) // 2
                if nums[mid] == target: #要求找最左邊，因此更新右邊界
                    right = mid - 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            if left <= len(nums) - 1 and nums[left] == target: #注意
                return left
            else:
                return -1
        def searchRight(nums):
            if not nums:
                return -1
            left = 0
            right = len(nums) - 1
            while(left <= right):
                mid = (left + right) // 2
                if nums[mid] == target: #要求找最右邊，因此更新左邊界
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            if right >= 0 and nums[right] == target: #注意
                return right
            else:
                return -1
        return [serachLeft(nums), searchRight(nums)]

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

最后一種寫法:
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def left_search(nums):
            l = 0 
            r = len(nums) - 1
            while(l <= r):
                mid = (l + r) // 2
                if nums[mid] ==  target:
                    r = mid - 1
                elif nums[mid] > target:
                    r = mid - 1
                else:
                    l = mid + 1
            if l == len(nums) or nums[l] != target:
                return -1
            return l
        
        def right_searh(nums):
            l = 0
            r = len(nums) - 1
            while(l <= r):
                mid = (l + r) // 2
                if nums[mid] == target:
                    l = mid + 1
                elif nums[mid] > target:
                    r = mid - 1
                else:
                    l = mid + 1
            if r < 0 or nums[r] != target:
                return -1
            return r
        l = left_search(nums)
        r = right_searh(nums)
        return [l, r]

組合總和

標準的DFS，需要設計好遞歸函數(shù)的參數(shù)?；镜谋闅v和剪枝都很簡單，關鍵是如何去重，這個跟以前的DFS有區(qū)別，不能用標記來記錄走過的路徑，因為這里的數(shù)字可以重復選取。解法里給了一個索引來記錄當前節(jié)點的順序，在下一次的遍歷中從這個節(jié)點開始，這樣就保證了數(shù)字可以重復選取，也避免了路徑的重復。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        res = []
        def dfs(i, sumNum, route):
            if sumNum == 0:
                res.append(route)
                return
            for index in range(i, len(candidates)):
                if sumNum >= candidates[index]:
                    dfs(index, sumNum - candidates[index], route + [candidates[index]])
        dfs(0, target, [])
        return res

接雨水

這一題本質(zhì)上是要求一個定值，第一眼看到這題我也沒啥好的思路，看了題解才知道要用單調(diào)遞減棧。需要使用棧是因為新的凹槽左邊界一定是最新遇到的，而要使用遞減棧是因為當?shù)偷挠龅礁叩牟艜鄳陌疾?。在具體實現(xiàn)上這一題有很多細節(jié)，首先我們?nèi)霔Ｊ窃氐南聵耍驗楹竺嫖覀冃枰褂孟聵藖砬髮挾?。當前棧不為空且當前元素大于棧頂則出棧。在計算凹槽能存儲的雨水時，需要當前元素，前一個元素，后面一個元素來共同計算，當沒有前一個元素的時候，直接跳出，計算凹槽的寬度沒啥難度，但是計算凹槽的高度的時候需要注意：前后兩個高度取較低的再減去中間這個最低的才能得到相對高度差。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        stack = []
        for i in range(len(height)):
            while(stack and height[stack[-1]] < height[i]):
                temp = stack.pop()#出棧
                if not stack:#沒有前一個元素直接跳出
                    break
                left = stack[-1]
                right = i
                width = right - left -1
                length = min(height[left], height[right]) - height[temp]
                ans += width*length
            stack.append(i)#下標入棧
        return ans

全排列

標準的排列做法。這里需要注意一下python中傳遞列表這一類數(shù)據(jù)的時候

解法1：（錯誤）
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        res = []
        route = [0]*length
        flags = [0]*length
        def dfs(count):
            if count == length:
                print(route)
                res.append(route)
                return
            for i in range(length):
                if flags[i] == 0:
                    flags[i] = 1
                    route[count] = nums[i]
                    dfs(count + 1)
                    flags[i] = 0

        dfs(0)
        return res

解法2：(對傳遞的列表進行復制)
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        res = []
        route = [0]*length
        flags = [0]*length
        def dfs(count):
            if count == length:
                print(route)
                res.append(route[:])
                return
            for i in range(length):
                if flags[i] == 0:
                    flags[i] = 1
                    route[count] = nums[i]
                    dfs(count + 1)
                    flags[i] = 0

        dfs(0)
        return res

解法3：（將存儲路徑的變量采用參數(shù)的形式來傳遞）
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        res = []
        flags = [0]*length
        def dfs(count, route):
            if count == length:
                res.append(route)
                return
            for i in range(length):
                if flags[i] == 0:
                    flags[i] = 1
                    dfs(count + 1, route + [nums[i]])
                    flags[i] = 0

        dfs(0, [])
        return res

旋轉(zhuǎn)圖像

先將矩陣進行轉(zhuǎn)置，再將每一行反轉(zhuǎn)即可。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        for i in range(len(matrix)):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(len(matrix)):
            matrix[i].reverse()

字母異位詞分組

比較好的辦法就是利用字典，但是我們需要區(qū)分好鍵值，這里使用排序函數(shù)來進行區(qū)分。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        Dict = {}
        for s in strs:
            key = ''.join(sorted(s))
            if key not in Dict:
                Dict[key] = []
            Dict[key].append(s)
        return list(Dict.values())

最大子序和

簡答的DP。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0]*len(nums)
        dp[0] = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            if dp[i-1] < 0:
                dp[i] = nums[i]
            else:
                dp[i] = dp[i-1] + nums[i]
            res = max(res, dp[i])
        return res

跳躍游戲

這一題需要用動態(tài)規(guī)劃，k表示到達第i步時，能夠走的最遠距離。如果k<i那么就返回False，每次對k進行更新 k = max(k, i+nums[i])

解法1：超時
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        flags = [0]*length
        flags[0] = 1
        for i in range(length-1):
            if flags[i] == 1:
                for j in range(i, min(i+nums[i]+1, length)):
                    flags[j] = 1
                    if flags[-1] == 1:
                        return True
        if flags[-1] == 1:
            return True
        else:
            return False

解法2：
k表示在在當前位置能夠走到的最遠距離。
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        k = 0
        for i in range(length):
            if i > k:
                return False
            k = max(k, i + nums[i])
        return True

合并區(qū)間

這個題目從暴力上是沒法解決的，暴力的復雜度是n!，只能通過排序的手段來降低時間復雜度。注意cmp_to_key這個關鍵字需要引入functools包。
按照貪心的策略來進行排序，優(yōu)先按照左端從小到大進行排序，如果左端相同則將右端較大的放在前面，如果前一個區(qū)間的右端點小于后一個區(qū)間的左端點，那么這兩個區(qū)間不會重合，否則兩個重復，新區(qū)間的右端點為這兩個區(qū)間有邊界的較大值。
改正，這個題目只需要對左邊界排序即可，其他的不用管。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        def compare(a, b):
            if a[0] > b[0] or (a[0] == b[0] and a[1] < b[1]):
                return 1
            elif a[0] == b[0] and a[1] == b[1]:
                return 0
            else:
                return -1
        intervals.sort(key = cmp_to_key(compare))
        res = [intervals[0]]
        for left, right in intervals[1:]:
            temp = res[-1]
            if left > temp[1]: #注意是嚴格大于
                res.append([left, right])
            else:
                res[-1][1] = max(right, temp[1])
        return res

不同路徑

第一眼看上去像是簡單的迷宮搜索問題，可以直接嘗試暴力搜索，結(jié)果超時，這里我給了兩種寫法，第一種使用了標記數(shù)組，后面發(fā)現(xiàn)是沒有必要的，因為根據(jù)題意是絕對不會往回走的?；剡^頭來仔細看一下，這個題其實就是組合數(shù)的定義，或者我們也可以使用標準的DP來解決：
$dp[i][j] = dp[i-1][j] + dp[i][j-1]$
需要注意初始化的問題，不然結(jié)果全為0。

解法1：超時
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        self.count = 0
        flags = [[0]*m for i in range(n)]
        def dfs(x, y):
            if x == n-1 and y == m-1:
                self.count += 1
            if x <0 or x >n-1 or y < 0 or y > m-1:
                return
            for (delta_x, delta_y) in [(0, 1), (1, 0)]:
                if x+delta_x < 0 or x+delta_x > n-1 or y+delta_y <0 or y+delta_y > m-1:
                    continue
                if flags[x+delta_x][y+delta_y] == 0:
                    flags[x+delta_x][y+delta_y] = 1
                    dfs(x+delta_x, y+delta_y)
                    flags[x+delta_x][y+delta_y] = 0
        flags[0][0] = 1
        dfs(0, 0)
        return self.count

解法2：超時
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        self.count = 0
        def dfs(x, y):
            if x == n-1 and y == m-1:
                self.count += 1
            if x <0 or x >n-1 or y < 0 or y > m-1:
                return
            dfs(x+1, y)
            dfs(x, y+1)
        dfs(0, 0)
        return self.count

解法3：DP
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0]*(m + 2) for i in range(n+2)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if i == 1 and j == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n][m]

最小路徑和

同樣這一題是非?；A的DP，按照我之前的寫法將數(shù)組外圍擴充一下，但是這種寫法不能填充0，應該填充一個很大的值。這個一定要注意。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        width = len(grid)
        length = len(grid[0])
        dp = [[0]*length for i in range(width)]
        for i in range(0, width):
            for j in range(0, length):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0 and j != 0:
                    dp[i][j] =  dp[i][j-1] + grid[i][j]
                elif i !=0 and j == 0:
                    dp[i][j] = dp[i-1][j] + grid[i][j]
                else: 
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

爬樓梯

斐波拉契數(shù)列，注意初始值。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0]*n
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n-1]

編輯距離

這一題也是經(jīng)典的DP，這一題與求兩個序列的最長公共子序列這一題類似，同樣是二階DP。
假設現(xiàn)在有兩個字符串a(chǎn)，b，dp[i][j]表示a[:i]和b[:j]這兩個字串的最短編輯距離，那么我們可以得到相應的狀態(tài)轉(zhuǎn)移方程：

$f(x)=\left\{ \begin{aligned} dp[i][j] = & dp[i-1][j-1] (a[i]=b[j]) \\ dp[i][j] = & 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) (a[i]!=b[j]) \end{aligned} \right.$

a[i]=b[j]的時候很好理解，當a[i]!=b[j]的時候，我們以a為例，我們可以將a[i]修改成和b[j]一樣的，這個時候就轉(zhuǎn)換成求dp[i-1][j-1]了，我們也可以直接將a[i]刪除，但是刪除a[i]之后，我們也無法去頂a[i-1]和b[j]是否相等，這個時候問題轉(zhuǎn)換成求dp[i-1][j]，我們也可以在a[i]后面增加一個和b[j]一樣的元素，這個時候a[i+1]和b[j]是一樣的，然后問題就轉(zhuǎn)換成dp[i][j-1]了。在具體實現(xiàn)的時候，我們需要添加一個空串，因為這樣容易初始化，因此代碼中會有相應的調(diào)整。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        length1 = len(word1) + 1
        length2 = len(word2) + 1
        #print(length1, length2)
        dp = [[0]*length1 for i in range(length2)]
        for i in range(length2):
            dp[i][0] = i
        for j in range(length1):
            dp[0][j] = j
        for i in range(1, length2):
            for j in range(1, length1):
                if word2[i-1] == word1[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    #print(i, j)
                    dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
        return dp[-1][-1]

顏色分類

三色國旗問題。官方題解寫的挺好的：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/ ，關于這個算法其實也比較好理解。p0表示左邊界，p2表示右邊界，cur表示遍歷的當前元素，因為最終我們需要讓整個數(shù)組變成遞增的形式，當nums[cur] = 2的時候，就需要和nums[p2]進行交換，并且將p2左移，當nums[cur] = 0的時候，就需要和nums[p1]進行交換，并且cur和p1都要右移，當nums[cur] = 1的時候，只需要cur右移即可。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        p0 = cur = 0
        p2 = len(nums) - 1
        while(cur <= p2):
            if nums[cur] == 2:
                nums[cur], nums[p2] = nums[p2], nums[cur]
                p2 -= 1
            elif nums[cur] == 0:
                nums[cur], nums[p0] = nums[p0], nums[cur]
                cur += 1
                p0 += 1
            else:
                cur += 1

最小覆蓋子串

同樣是經(jīng)典的滑動窗口題目。需要維護兩個字典，和兩個指針。但是這一題需要子串覆蓋，因此窗口收縮的條件更為嚴格，不能簡單的通過雙指針之間的距離大于等于目標串的長度就來進行窗口收縮操作，這樣會增加時間復雜度。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        window = {}
        need = {}
        left = 0
        right = 0
        valid = 0
        maxlength = inf
        temp = 0
        for c in t:
            if c not in need:
                need[c] = 1
            else:
                need[c] += 1
        while(right < len(s)):
            c = s[right]
            right += 1
            if c not in window:
                window[c] = 1
            else:
                window[c] += 1
            if c in need:
                if window[c] == need[c]:
                    valid += 1
            while(valid == len(need)): #這個收縮條件更為嚴格
                if right - left < maxlength:
                    maxlength = right - left
                    temp = left
                c = s[left]
                left += 1
                if c in need:
                    if need[c] == window[c]:
                        valid -= 1
                    window[c] -= 1
        if maxlength == inf:
            return ''
        else:
            return s[temp:temp+maxlength]

子集

類似于生成全排列，用一個深度優(yōu)先搜索最為直接。具體的實現(xiàn)的時候需要注意終止條件，這里不需要使用標記數(shù)組來防止重復遍歷。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        
        res = []
        def dfs(count, route):
            if count == length:
                res.append(route)
                return
            
            for i in range(2):
                if i == 1:
                    dfs(count + 1, route + [nums[count]])
                else:
                    dfs(count + 1, route)
                    
        dfs(0, [])
        return res

單詞搜索

同樣是DFS，但是這個DFS搜索稍微有點復雜。遞歸函數(shù)參數(shù)有3個，分別表示橫縱坐標和走過的步數(shù)，由于這個題需要從所有可能的路徑中找出一條滿足題意的路徑，因此這一題需要采用for循環(huán)的寫法：用flags標記數(shù)組來在防止同一條路徑上重復遍歷，并且還要保證不同的路徑之間互不影響。在進行下一步遞歸的時候需要保證不越界、未走過、且保證當前遍歷的元素與word中相同位置的元素相同這三個條件。最后需要注意的是，這一題需要剪枝，也就是當找到一條滿足題意的路徑的時候，需要立刻將程序終止，否則會超時。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        length = len(board)
        width = len(board[0])
        flags = [[0]*width for i in range(length)]
        self.res = 0
        def dfs(x, y, count):
            if count == len(word):
                self.res = 1
                return
            for delta_x, delta_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if self.res == 1:
                    return
                if x + delta_x >= 0 and x + delta_x <= length -1 and y + delta_y >= 0 and y + delta_y <= width - 1 and flags[x + delta_x][y + delta_y] == 0 and board[x+delta_x][y+delta_y] == word[count]:
                    flags[x + delta_x][y + delta_y] = 1
                    dfs(x + delta_x, y + delta_y, count + 1)
                    flags[x + delta_x][y + delta_y] = 0

        for i in range(length):
            for j in range(width):
                if board[i][j] == word[0]:
                    flags[i][j] = 1
                    dfs(i, j, 1)
                    flags[i][j] = 0
                    if self.res == 1:
                        return True
        return False

柱狀圖中最大的矩形

這一題與接雨水這一題神似，不同的是，接雨水那一題需要碰到更高的才會形成相應的凹槽，而這一題是遇到更低的柱形之后，后面會有凹槽這樣無法形成對應的矩形，只能計算前面的矩形了。因此這一題也需要使用到單調(diào)棧，單調(diào)不減的棧，這一同樣需要把元素索引入棧，因為需要計算對應的寬度，在計算寬度的時候還需要考慮前面是否有柱形，還有一個技巧就是在最后加上一個高度為0的柱形，計算寬度需要注意下，右邊界為當前元素的位置，左邊界為出棧后的棧頂，沒有的話就為空。參考：https://blog.csdn.net/Zolewit/article/details/88863970

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0) #注意這一步
        stack = []
        res = 0
        for i in range(len(heights)):
            while(stack and heights[i] < heights[stack[-1]]):
                mid = stack.pop()
                right = i #注意這一步
                if not stack:
                    width = right
                else:
                    left = stack[-1] #注意這一步
                    width = right - left - 1
                res = max(res, width*heights[mid])
            stack.append(i)
        return res

二叉樹的中序遍歷

題目要求使用非遞歸的方式來完成。這就需要定義一個棧來模擬系統(tǒng)棧的壓棧、彈棧過程。
在模擬中序遍歷的時候，同樣需要讓左子樹不斷入棧，直到最左邊即可。若當前節(jié)點為空，則出棧并獲取棧頂元素的值，并將當前元素更新到其右子樹的狀態(tài)。整個循環(huán)終止的條件為當前節(jié)點為空且棧也為空。

詳細情況請參考：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while(cur or stack):
            while(cur):
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res

不同的二叉搜索樹

簡單的DP，dp[i]表示i個節(jié)點的樹能夠構(gòu)成二叉搜索的種類:
$dp[n] = dp[0]*dp[n-1] + ... + dp[n-1]*dp[0]$
如果這一題是普通的二叉樹的話，就需要再乘以n!。

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0]*(n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(0, i):
                dp[i] += dp[j]*dp[i-1-j]
        return dp[n]

驗證二叉搜索樹

簡單的遞歸函數(shù)即可，同樣需要設計好參數(shù)和返回值，遞歸函數(shù)其實比較簡單，違反二叉樹的性質(zhì)就返回False，當樹遍歷到空節(jié)點的時候返回True，因為這個時候表示在遍歷過程中沒有出現(xiàn)任何違反二叉搜索樹性質(zhì)的情況，最后當所有的條件都滿足的時候，返回True即可。但是有一點需要注意，就是右子樹的每一個節(jié)點都要大于根節(jié)點，左子樹的每一個節(jié)點都要小于根節(jié)點，因此單獨地判斷每一個根節(jié)點和其左右子節(jié)點的大小關系是不夠的。這里第一種解法就是這種錯誤的解法。

解法1：錯誤的解法
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        if root.left:
            if root.left.val >= root.val:
                return False
        if root.right:
            if root.right.val <= root.val:
                return False
        left = self.isValidBST(root.left)
        right = self.isValidBST(root.right)
        if not left or  not right:
            return False
        else:
            return True

解法2：在遞歸函數(shù)的參數(shù)里設置上下界，lower和upper，注意是開區(qū)間：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        minNum = -9999999999
        maxNum = 9999999999
        def dfs(root, minNum, maxNum):
            if not root:
                return True
            if root.val <= minNum or root.val >= maxNum:
                return False
            left = dfs(root.left, minNum, root.val)
            right = dfs(root.right, root.val, maxNum)
            if not left or not right:
                return False
            else:
                return True
        return dfs(root, minNum, maxNum)

對稱二叉樹

有一種最笨的辦法就是直接將這棵樹進行交換然后再遍歷，如果遍歷的結(jié)果相同，那么說明這是一顆對稱樹，這里強調(diào)一下，應該使用先序遍歷，使用中序遍歷的話有些數(shù)據(jù)過不了。

建立一個合理的遞歸關系，直接對左右子樹進行判斷，不滿足相應的條件就返回False，滿足相應的條件就返回True，但是要注意的一點是根節(jié)點為空需要單獨判讀，不能放在遞歸函數(shù)里，遞歸函數(shù)里的參數(shù)為兩個表示左右子樹。

解法1：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def swap(root):
            if not root:
                return None
            newRoot = TreeNode()
            
            temp1 = root.left
            temp2 = root.right
            root.left = swap(temp2)
            root.right = swap(temp1)
            '''
            newRoot.val = root.val
            newRoot.left = swap(root.right)
            newRoot.right = swap(root.left)
            return newRoot
            '''
            return root

        def dfs(root):
            if not root:
                return ['null']
            else:
                left = dfs(root.left)
                right = dfs(root.right)
                return  [root.val] + left + right

        res1 = dfs(root)
        newNode = swap(root)
        res2 = dfs(newNode)

        if res1 == res2:
            return True
        else:
            return False

解法2：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def judge(left, right):
            if not left and not right:
                return True
            if not left:
                return False
            if not right:
                return False
            if left.val != right.val:
                return False
            return judge(left.left, right.right) and judge(left.right, right.left)
            
        if not root:
            return True
        if judge(root.left, root.right):
            return True
        else:
            return False

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

leetcode熱題 HOT 100刷題筆記（1）

leetcode熱題 HOT 100刷題筆記（1）

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

leetcode熱題 HOT 100刷題筆記（1）

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av