LEETCODE

Problems Set

Sum Problems

Two Sum

Solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            left = nums[i]
            right = target - left
            for k in range(i + 1, len(nums)):
                if nums[k] == right:
                    return i, k

Optimized solution using enumerate(iterable, start=0)
- Iterable: any object that supports iteration
- Start: the index value from which the counter is to be started, by default it is 0
Enumerate() method adds a counter to an iterable and returns it in a form of an enumerating object. This enumerated object can then be used directly for loops or converted into a list of tuples using the list() function.
```
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for index, left in enumerate(nums):
            right = target - left
            if right in d: return [d[right], index]
            d[left] = index
```

Three Sum

https://leetcode.cn/problems/3sum/

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

        res = []
        size = len(nums)

        # 首先将nums排序
        nums.sort()

        # 判定特殊情况
        if not nums or size < 3:
            return []
        
        # 使用双指针的方法来解决这个问题
        # i: 遍历指针；left: 从 i+1 开始递增的指针；right: 从末尾开始递减的指针
        # 我们要找到的就是三个指针，使得其所在的元素之和为0
        # 这个算法的正确性在于，因为nums是已经排序的，那么对于每一个i，我们只需要在位于i后半段的元素中找到两个元素
        # 使其和为0就可以了
        # 循环条件是left < right:
            # 如果当前sum < 0，那么左指针右移让sum大一些
            # 如果当前指针 > 0，那么右指针左移让sum小一些
        
        # 开始遍历指针i
        for i in range(size):

            # 定义左指针和右指针
            left = i + 1
            right = size - 1

            # 因为排序了nums，所以后续不会有三数之和等于0，直接跳出循环
            if nums[i] > 0: break 

            # 因为会有相同的元素存在，如果当前元素和前一个相同，那么此轮得到的组合就是重复的，所以我们需要跳过当前元素
            if i >= 1 and nums[i] == nums[i - 1]: continue
            while left < right:
                sum_ = nums[i] + nums[left] + nums[right]
                if sum_ < 0:
                    left += 1
                elif sum_ > 0:
                    right -= 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    # 除了要对遍历元素i去重之外，两个指针也要分别去重
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    # 找到了一组指针之后，更新left和right，继续在当前i下寻找目标指针
                    left += 1
                    right -= 1

        return res

Four Sum

https://leetcode.cn/problems/4sum/

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

        size = len(nums)
        res = []
        nums.sort()

        if not nums or size < 4:
            return []
        
        for i in range(size):
            #if nums[i] > target: break
            if i > 0 and nums[i] == nums[i - 1]: continue
            for k in range(i + 1, size):
                if k > i + 1 and nums[k] == nums[k - 1]: continue
                left = k + 1
                right = size - 1
                while left < right:
                    sum_ = nums[i] + nums[k] + nums[left] + nums[right]
                    if sum_ > target:
                        right -= 1
                    elif sum_ < target:
                        left += 1
                    else:
                        res.append([nums[i], nums[k], 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 res

Longest Substring Without Repeating Character

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}

        left = 0
        right = 0
        counter = 0

        while left < len(s) and right < len(s):
            char = s[right]
            if char in d:
                left = max(left, d[char] + 1)
            d[char] = right
            counter = max(counter, right - left + 1)
            right += 1


        return counter

Sliding window techniques
- 更新left pointer的维度：把left pointer移动到当前存在于dict中的index的下一位。

Longest Palindrome

class Solution:
    def longestPalindrome(self, s: str) -> str:
        result = ""
        result_length = 0

        # 用取Palindrome的中间char向两边扩张的方法，分odd string和even string两种情况讨论
        for i in range (len(s)):

            # Initialize left 和 right 两个pointer，i 代表 middle index
            left, right = i, i

            # odd length
            while left >= 0 and right < len(s) and s[left] == s[right]:
                # 如果当前length更大则更新result_length
                if (right - left + 1) > result_length:
                    result_length = right - left + 1
                    # 切片 result string
                    result = s[left:right+1]
                left -= 1
                right += 1

            # even length 同理 odd length
            left, right = i, i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if (right - left + 1) > result_length:
                    result_length = right - left + 1
                    result = s[left:right+1]
                left -= 1
                right += 1

        return result

First Bad Version

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        start = 0
        end = n
        while start < end:
            middle = (start + end) // 2
            if isBadVersion(middle) == False:
                start = middle + 1
            else:
                end = middle

        return start

Pascal's Triangle

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:

        result = []
        for i in range(numRows):
            level = []
            for j in range(i + 1):
                if j == 0 or j == i:
                    level.append(1)
                else:
                    level.append(result[i-1][j-1]+result[i-1][j])
            result.append(level)
        
        return result

Permutation in String **

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        cntr, w = Counter(s1), len(s1)   

        for i in range(len(s2)):
            if s2[i] in cntr: 
                cntr[s2[i]] -= 1
            if i >= w and s2[i-w] in cntr: 
                cntr[s2[i-w]] += 1

            if all([cntr[i] == 0 for i in cntr]): 
                return True
        return False

Merge Two Trees

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:

        if root1 is None:
             return root2
        if root2 is None:
            return root1

        root1.val +=  root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1

链表系列问题

翻转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        if not head:
            return
        
        # 用两个pointer来构建新的linked ListNode
        prev = None # 初始prev为None
        curr = head # 从head开始

        while curr:
            temp = curr.next # 用temp先储存当前node后续的链表
            curr.next = prev # reverse链表，当前node指向prevNode
            prev = curr # 处理下一轮之前，更新prevNode为当前的Node
            curr = temp # Move current node to the next
        
        return prev

指定区间反转链表

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        # 需要两个指针来实现反转
        # 一个指向当前node，一个指向前一个node
        # 首先创建一个dummy head来确保起初的节点不反转
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        curr = head

        # 先找到第m个节点
        for _ in range(1,m):
            prev = curr
            curr = curr.next
        
        # 反转从m到n的节点
        for _ in range(m,n):
            # 用一个指针把开始反转节点后面的链表先存储下来
            # 不然改变方向后就没有指针指向后续要反转的链表了
            temp = curr.next
            # 每次一共需要修改三个位置的pointer
            # 从curr开始一步一步将其往后移，每一步移位
            curr.next = temp.next
            # 反转 pointer
            temp.next = prev.next
            # 修改prev的pointer
            prev.next = temp
        
        return dummy.next

分组翻转链表

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
        # write code here
        # 可以采取递归的方式，从后往前分组解决：即n个k组，若最后剩余的节点不足k个，则直接返回
        # 每一组的末尾元素是翻转后的新链表的链表首，也即最终要返回的的元素
        # 每一组起初的链表首变成了翻转后的链表尾，用于连接下一组翻转后的链表首

        # 递归的构建
        # 终止条件：剩余的节点不够遍历k次，将剩余的部分直接返回
        # 返回值：该组翻转后的链表首，其链接着该组翻转完成后的节点
        # 本级任务：对于每组先遍历k次，找到该组要翻转的结尾节点位置；然后从开头翻转至结尾。
        #       其中翻转后的尾作为下一份组的首。

        # 每次翻转后的尾部都是下一分组的头
        tail = head

        # 遍历k次找到该组的tail，若不足k次则直接返回
        for _ in range(k):
            if tail == None:
                return head
            tail = tail.next
        
        # 进行改组的翻转
        # 我们同样需要一个当前节点和一个前序节点
        prev, curr = None, head
        # 在curr节点到达该组的tail之前，将节点逐个翻转
        while curr != tail:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        # 翻转后的头现在变到了末尾，指向下一组需要翻转的链表
        head.next = self.reverseKGroup(tail, k)
        
        return prev

检测链表有无循环

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if fast == slow:
                return True
            
        return False

寻找链表中循环的入口节点

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here

        # 首先判断链表是否有循环，有的话确定slow pointer和fast pointer相遇的节点
        def hasCycle(self, head):
            if not head:
                return None
            
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next

                if fast == slow:
                    return slow
                
            return None

        # 获取slow节点
        slow = hasCycle(self, pHead)
        # 没有环的情况
        if not slow:
            return None
        # 获取到slow在cycle中的位置后，把fast移动到head
        # 然后开始同步遍历，则fast到达cycle需要的步数和slow再次到达cycle入口的步数相等
        # 即slow 和 fast 再次相遇的节点就是cycle的入口
        fast = pHead
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return slow

按照val顺序合并两个链表

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummyhead = ListNode()
        curr = dummyhead

        # 当list1和list2都有值时
        while list1 and list2:
            # 如果list1的当前value更小，更新curr.next为list1
            if list1.val < list2.val:
                curr.next = list1
                # update curr到下一个node
                curr = curr.next
                # update list1到下一个node
                list1 = list1.next
            else:
                curr.next = list2
                curr = curr.next
                list2 = list2.next
            
        if list1 or list2:
            curr.next = list1 if list1 else list2
        
        return dummyhead.next

根据给定value移除链表中的节点 (Two Pointer)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return
        
        dummyhead = ListNode(next=head)
        prev = dummyhead
        curr = head
        while curr:
            if curr.val == val:
                nextNode = curr.next
                prev.next = nextNode
                curr = nextNode
            else:
                prev = curr
                curr = curr.next
        
        return dummyhead.next

删除倒数第n个节点

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:
        # write code here
        # 先获取链表的长度
        length = i = 0
        l = dummy = head
        while l:
            length += 1
            l = l.next
        if length < 2:
            return None
        if n == length:
            return dummy.next
        while dummy:
            i += 1
            if i != length - n:
                dummy = dummy.next
            else:
                dummy.next = dummy.next.next
        return head

两个链表相加（结合反转链表）

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        # 先翻转两个链表
        def node_reverse(h):
            if not h:
                return h

            prev = None
            curr = h
            
            while curr:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp

            return prev
        
				# 如果其中一个链表为空则返回另一个
        if not head1:
            return head2
        if not head2:
            return head1
        
        head1 = node_reverse(head1)
        head2 = node_reverse(head2)

        #构建一个新的链表
        dummy = ListNode(-1)
        curr = dummy
        carry = 0

        while head1 or head2:
            val = carry
            # 如果head1有值则加上head1
            if head1:
                val += head1.val
                head1 = head1.next
            # 如果head1有值则加上head1
            if head2:
                val += head2.val
                head2 = head2.next
						#构建新的链表
            curr.next = ListNode(val%10)
            carry = val // 10
            curr = curr.next
        
        # 若最后进位还有剩余，则创建一个新的node来表示这个进位
        if carry != 0:
            curr.next = ListNode(carry)
        
        return node_reverse(dummy.next)

重排奇偶位置的链表

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def oddEvenList(self , head: ListNode) -> ListNode:
        # write code here
        if head == None:
            return head

        odd = head
        even = head.next
        evenHead = even
        

        while even and even.next:
            # 奇数位置节点的下一个是偶数为节点的下一个，e.g. 1.next = 2.next = 3 ->
            odd.next = even.next
            odd = odd.next # update 奇数位节点
            even.next = odd.next # even位的下一个跟在下一个odd后，即更新过后的odd的next
            even = even.next # update 偶数位节点
        # 整个even nodes跟在odd后
        odd.next = evenHead
        return head

删除重复节点

保留一个重复节点

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        if head == None:
            return head
        
        curr = head
        while curr and curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next
            else:
                curr = curr.next

        return head

不保留重复节点

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        if head == None:
            return head
        # 思想：比较每两个相邻的node，一旦出现重复，则先记下这个val，跳过后续所有相等的node
        # 构建一个dummy，好从head就开始比较是否有相等的node
        dummy = ListNode(-1)
        dummy.next = head
        curr = dummy

        while curr.next and curr.next.next:
            # 一旦发现相等val的nodes
            if curr.next.val == curr.next.next.val:
                # 记下当前val
                v = curr.next.val
                # 跳过后续所有该val的node
                while curr.next and curr.next.val == v:
                    curr.next = curr.next.next
            else:
                # 否则正常update curr
                curr = curr.next

        return dummy.next

构建链表

https://leetcode.cn/problems/design-linked-list/

class Node:
    def __init__(self, x=-1):
        self.val = x
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.head = Node()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        curr = self.head.next
        while index != 0:
            curr = curr.next
            index -= 1
        return curr.val

    def addAtHead(self, val: int) -> None:
        head_node = Node(x = val)
        head_node.next = self.head.next
        self.head.next = head_node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        tail_node = Node(x = val)
        prev = self.head
        while prev.next:
            prev = prev.next
        prev.next = tail_node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        
        if index < 0:
            self.addAtHead(val)
            return

        if index == self.size:
            self.addAtTail(val)
            return
        
        new_node = Node(x = val)
        prev = self.head
        while index != 0:
            prev = prev.next
            index -= 1
        temp = prev.next
        prev.next = new_node
        new_node.next = temp
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        prev = self.head
        while index != 0:
            prev = prev.next
            index -= 1
        prev.next = prev.next.next
        self.size -= 1


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

两两交换链表中的位置

https://leetcode.cn/problems/swap-nodes-in-pairs/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        while prev.next and prev.next.next:
            curr = prev.next
            temp = prev.next.next
            
            curr.next = temp.next
            temp.next = curr
            prev.next = temp

            prev = prev.next.next
        
        return dummy.next

BFS应用

01 Matrix

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        row = len(mat)
        col = len(mat[0])
        directions = [0, 1, 0, -1, 0]

        # Use BFS for this problem, specify a queue to track the entry
        # that are going to be processed
        q = collections.deque([])
        for i in range(row):
            for j in range(col):
                # 先处理初始值就为0的entry，因为他们到0的最短距离就是0
                if mat[i][j] == 0:
                    q.append((i, j))
                else:
                    mat[i][j] = -1 # 对于不是0-entry的点，先标记为unvisited
        
        while q: # 当待处理的queue不为空时
            r, c = q.popleft() # 提取当前要出的entry的row和col
            for d in range(4):
                # 获取当前entry上下左右四个位置的entry的坐标
                nr, nc = r + directions[d], c + directions[d+1]
                # 如果超出mat边界，或者已被访问过，则跳过当前循环
                if nr < 0 or nr >= row or nc < 0 or nc >= col or mat[nr][nc] != -1:
                    continue
                # 因为我们是从0开始的，所以与0相接的entry距离+1，以此类推
                mat[nr][nc] = mat[r][c] + 1
                # 最后将本轮获取的四个entry加入到待处理queue
                q.append((nr, nc))
        
        return mat

Rotting Oranges

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        directions = [0, -1, 0, 1, 0]

        if row == 0:  # check if grid is empty
            return -1

        # track the count of fresh oranges
        fresh_count = 0
        # track the minutes have been passed
        minutes = 0
        # denote a queue to track the rotten oranges, aka visited
        rotten = collections.deque()
        
        # 先用BFS遍历grid，先把已经腐烂的橘子加进queue(they are considered as visited)
        # 根据queue中的oranges，上下左右检查每个周边的橘子，并将其加入queue进行下一轮检索
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    fresh_count += 1 # 记录新鲜橘子
                elif grid[i][j] == 2:
                    rotten.append((i, j)) # append腐烂橘子
        
        # BFS
        while rotten and fresh_count > 0:
            minutes += 1 # it is safe to update the minutes by 1, since we visit oranges level by level
            for _ in range(len(rotten)):
                r, c = rotten.popleft() # 提取当前要处理的橘子
                for i in range(4): # 并找出上下左右四个entry的坐标
                    nr, nc = r + directions[i], c + directions[i+1]
                    if nr < 0 or nr >= row or nc < 0 or nc>= col or grid[nr][nc] == 2 or grid[nr][nc] == 0:
                        continue # 若上下左右entry的坐标超出boundary，不存在橘子，或者已经是腐烂的橘子(visited)，跳出当前循环
                    fresh_count -= 1 # 新鲜橘子减一
                    grid[nr][nc] = 2 # mark the entry as rotten(visited)
                    rotten.append((nr, nc)) # 把该entry坐标加入queue作为下一个检索其周边的current entry
        
        return minutes if fresh_count == 0 else -1

Binary Tree Level Order Traversal

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

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

        # 初始化一个queue来记录要处理的node
        queue = [root]
        output = []

        while queue:
            level = []
            nodes = len(queue)
            for i in range(nodes):
                curr = queue.pop(0)
                level.append(curr.val)
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            output.append(level)
        
        return output

Populating Next Right Pointers in Each Node

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return

        # 我们可以使用bfs从右向左给每一层的node添加pointer
        # 从第一层开始，最右侧的node就是root
        # 创建一个queue来追踪所有的levels
        q = deque([root])

        while q:
            # 初始化一个要添加的rightNode, 对于每一层最右侧的node来说，要添加的rightNode都是None
            rightNode = None
            # 处理每一层的Node
            for _ in range(len(q)):
                curr = q.popleft() # 从最右开始处理当前node
                curr.next = rightNode # 先给最右的Node添加pointer
                rightNode = curr # 再将要添加的rightNode更新为当前node
                # 如果当前node存在right，那么一定也存在一个left，按照right->left顺序添加进queue
                if curr.right:
                    q.extend([curr.right, curr.left])
        
        return root

DFS应用

Flood Fill

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:

        # Set the starting node
        source = image[sr][sc]

        row = len(image)
        col = len(image[0])

        # Define a DFS method to recursively find the pixels around the pixels
        def dfs(r, c, grid, color):
            # if the input of r and c is out of the bound of grid, return nothing
            if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
                return
            
            # if the current pixel is already filled with the expected color
            # or the current pixel is not equal to source
            if grid[r][c] != source or grid[r][c] == color:
                return
            
            # otherwise fill the current pixel to the expected color
            grid[r][c] = color

            # recursively check the pixels around the source
            dfs(r, c+1, grid, color) # right
            dfs(r, c-1, grid, color) # left
            dfs(r+1, c, grid, color) # up
            dfs(r-1, c, grid, color) # down

        dfs(sr, sc, image, color)
        return image

Max Area Island

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        max_area = 0

        # define a dfs function to recursively check the pixles around the current one
        def dfs(r, c):
            # if the current pixel is out of boundary or is visited (marked as 0), return 0
            if r < 0 or c < 0 or r >= row or c >= col or grid[r][c] == 0:
                return 0
            # mark the current pixel as visited
            grid[r][c] = 0
            return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)

        # for each pixel in the original grid, run dfs to search the max_area island
        for i in range(row):
            for j in range(col):
                # if the current pixel has not been visited yet
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i, j))
        
        return max_area

Validate Binary Search Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True
        
        #使用DFS思想，初始化一个stack来储存要处理的nodes
        stack = []
        #记录前一个node的value，初始值为负无穷大
        prevN = float("-inf")

        # 当stack不为空且root不为None时
        # 算法采用in order搜索顺序，即左子树->根->右子树
        while stack or root:
            while root: #先将所有左子树加入到stack中
                stack.append(root)
                root = root.left
            #到尽头时pop最后一个node，即最左node，应为最小value的node
            root = stack.pop()
            #若最小node比previous node value还小，则return false
            if root.val <= prevN:
                return False
            #若不是则更新previous node value
            prevN = root.val
            #将root移动到右子树，因为所有右子树value都大于root大于左子树，
            root = root.right
        return True

返回tree的深度 - 用递归解决

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        
        if not root:
            return 0
        
        return (1 + max(self.maxDepth(root.left), self.maxDepth(root.right)))

Tree

检测对称树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isMirror(r1, r2):
            if not r1 and not r2:
                return True
            elif not r1 or not r2:
                return False
        
            return r1.val == r2.val and isMirror(r1.left, r2.right) and isMirror(r1.right, r2.left)
        
        return isMirror(root, root)

反转树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

        def invertLevel(curr):
            if curr:
                curr.left, curr.right = curr.right, curr.left
                invertLevel(curr.left)
                invertLevel(curr.right)
            return
        
        invertLevel(root)
        return root

Array相关问题

Reshape the Matrix

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:

        row = len(mat)
        col = len(mat[0])

        if r * c != row * col:
            return mat
        
        # Create the output matrix with all entry initialized to zero
        output = [[0] * c for _ in range(r)]
        # Create index to keep track of the rows we already inserted
        index = 0
				
				#计算出来的row_insert, col_insert:
				# (0, 0), (0, 1), (1, 0), (1, 1)
        for i in range(r):
            for j in range(c):
                row_insert, col_insert = divmod(index, col)
                output[i][j] = mat[row_insert][col_insert]
                index += 1
        return output

Rotate Array

Intuitive solution但超时

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

切片

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        n = len(nums)
				# 只需要取余数，因为 rotate k 的整数倍时相当于回到了原array
        k = k % n
	     
        nums[:] = nums[n - k:] + nums[:n - k]

Merge Sorted Array

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
				# 创建两个pointer来记录nums1和nums2.
        pointer1 = m - 1
        pointer2 = n - 1

				# 一个单独的指针来记录 writing index
        writing_index = m + n - 1
				
				# 观察input，因为nums已经是非降序排列，所以可以倒叙insert。
				# 插入了哪一个nums list的值，就给对应nums list的pointer减一。
				while pointer2 >= 0:
            if pointer1 >= 0 and nums1[pointer1] >= nums2[pointer2]:
                nums1[writing_index] = nums1[pointer1]
                pointer1 -= 1
                
            else:
                nums1[writing_index] = nums2[pointer2]
                pointer2 -= 1

            writing_index -= 1

移除元素(双指针)

https://leetcode.cn/problems/remove-element/

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

双指针法解决有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/submissions/

滑动窗口方法找长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 用两个pointer来实现滑动窗口
        # 起始指针：若当前窗口的和大于target，则窗口要缩小，即start向前移动
        # 结束指针：即for循环中的遍历指针
        start = 0 # 窗口开始的指针
        curr_sum = 0
        res = float("inf")   # 定义一个无限大的数
        

        for end in range(len(nums)):
            curr_sum += nums[end]
            # 每次需要移动start，缩小窗口时，即会产生一个新的满足target的窗口
            while curr_sum >= target:
                # 那么我们首先需要更新窗口，在当前和新窗口间取更小的
                res = min(res, end - start + 1)
                # 其次更新curr_sum，因为窗口缩小，sum也会减少，当curr_sum重新满足小于target时跳出循环
                curr_sum -= nums[start]
                # start向前移动
                start += 1

        # 若最终res还是无穷大，则返回0
        return 0 if res == float("inf") else res

旋转生成矩阵

https://leetcode.cn/problems/spiral-matrix-ii/

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 先界定边界
        left = 0
        right = n - 1
        top = 0
        bottom = n - 1

        # 初始化矩阵
        matrix = [[0] * n for _ in range(n)]
        val = 1 # 从1开始填充，每填充一个，val + 1
        count = n * n # 要填充的value总数

        #然后从题目描述的四个方向分别填充矩阵
        while val <= count:
            for i in range(left, right + 1): # 从左至右填充
                matrix[top][i] = val
                val += 1
            top += 1 # 填充完一行后，top 下移一位
            for i in range(top, bottom + 1): # 从上至下填充
                matrix[i][right] = val
                val += 1
            right -= 1 # 最右列填充完成，right 左移一位
            for i in range(right, left - 1, -1): # 从左到右填充
                matrix[bottom][i] = val
                val += 1
            bottom -= 1 # 最底层填充完成，bottom 上移一位
            for i in range(bottom, top - 1, -1): # 从下到上填充
                matrix[i][left] = val
                val += 1
            left += 1  # 最左列填充完成，left 右移一位

        return matrix

Binary Search

Binary Search With Matrix

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        col = len(matrix[0])
        low = 0
        high = row * col - 1

        while low <= high:
            mid_position = (high + low) // 2
            mid_num = matrix[mid_position // col][mid_position % col]
            if target == mid_num:
                return True
            elif mid_num > target:
                high = mid_position - 1
            elif mid_num < target:
                low = mid_position + 1
        
        return False

非完全线性矩阵内寻找target

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param array int整型二维数组 
# @return bool布尔型
#
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        row = len(array)
        col = len(array[0])
        c = 0
        r = row - 1
        
        if row == 0 or col == 0:
            return False

        # 从最左下的元素开始，如果当前元素比target小，则向右移动
        # 如果比当前元素大，则向上移动
        while r >= 0 and c < col:
            if array[r][c] == target:
                return True
            elif array[r][c] < target:
                c += 1
            else:
                r -= 1

        return False

寻找旋转数组中的最小数字

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param rotateArray int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        left = 0
        right = len(rotateArray) - 1
        while left < right:
            m = (left + right) // 2
            mid = rotateArray[m]
            # 中间位比最右大，说明最小值在右半边序列
            if mid > rotateArray[right]:
                left = m + 1
            # 中间位比最右小，说明最小值在左半边序列
            elif mid < rotateArray[right]:
                right = m
            # 无法判断的情况下，一个一个减少right来判读mid在什么位置
            # 比如[6,6,6,6,1,3,6]
            else:
                right -= 1

        return rotateArray[left]

HashTable

找快乐数

https://leetcode.cn/problems/happy-number/

class Solution:
    def isHappy(self, n: int) -> bool:
        def getSum(num):
            sum_ = 0
            while num:
                sum_ += (num % 10) ** 2
                num = num // 10
            return sum_
        
        d_sum = set()
        while True:
            n = getSum(n)
            if n == 1:
                return True
            if n in d_sum:
                return False
            else:
                d_sum.add(n)

四数相加

https://leetcode.cn/problems/4sum-ii/

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:

        count = 0

        # 使用hashmap来解决这个问题
        # 先创建一个hashmap来储存list1和list2中每对数字的sum：作为key，以及该sum出现的次数：作为value
        hash_1 = dict()
        for num1 in nums1:
            for num2 in nums2:
                if num1 + num2 not in hash_1:
                    hash_1[num1 + num2] = 1
                else:
                    hash_1[num1 + num2] += 1
        
        # 再计算出list3 和 list4 中每对数字的sum及该sum出现次数
        # 用 0 - sum 得到 half，如果该half在hash_1中存在，则统计count
        # 最后返回count
        for num3 in nums3:
            for num4 in nums4:
                left = - num3 - num4
                if left in hash_1:
                    count += hash_1[left]
                

        return count

Two Pointer

反转字符串

https://leetcode.cn/problems/reverse-string-ii/

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        # 用two pointer解决这个问题
        # 第一个pointer指向每个2k片段的开头
        # 第二个pointer指向pointer_1 + k, 即需要反转的部分
        # 遍历str，反转前k个后，第一个pointer向后移动2k

        p_1 = 0

        while p_1 < len(s):
            p_2 = p_1 + k
            s = s[:p_1] + s[p_1:p_2][::-1] + s[p_2:]
            p_1 += 2 * k
        
        return s

Tips

Keep track of the current node when dealing with the linked list data type.
- 可以创建一个dummy head, let curr = dummyHead, then use curr to go through the linked list.
多运用two pointer来降低时间复杂度。
对于array的移位，旋转等问题多用切片。
对于linked list可以多用一个slow node 和一个 fast node 来track linked list。
对于Trees结构多用递归解决。

Notes

enumerate(iterable, start=0)
- enumerate(iterable, start=0)
  - Iterable: any object that supports iteration
  - Start: the index value from which the counter is to be started, by default it is 0
  Enumerate() method adds a counter to an iterable and returns it in a form of an enumerating object. This enumerated object can then be used directly for loops or converted into a list of tuples using the list() function.
zip()
- The zip() function returns a zip object, which is an iterator of tuples where the first item in each passed iterator is paired together, and then the second item in each passed iterator is paired together, etc.
- If the passed iterators have different lengths, the iterator with the least items decides the length of the new iterator.
- a = ("John", "Charles", "Mike") b = ("Jenny", "Christy", "Monica")
  x = zip(a, b)
  >>> (('John', 'Jenny'), ('Charles', 'Christy'), ('Mike', 'Monica'))
Slicing - 切片
1. array[ 起始索引(包含) : 终止索引(不包含) : 间隔 ]
2. 注意索引为负数时，倒数第一是-1，倒数第二个是-2…
3. array[ : ]：可以原样复制一个array
4. tuple也是一种list，唯一区别是tuple不可变。因此，tuple也可以用切片操作，只是操作的结果仍是tuple
```
>>> (0, 1, 2, 3, 4, 5)[:3]
(0, 1, 2)
```
5. 对于字符串同理
```
>>> 'ABCDEFG'[:3]
'ABC'
>>> 'ABCDEFG'[::2]
'ACEG'
```
6. in- place reverse一个list的时候注意先创建list副本
```
# 例如reverse a list s in place using slicing
s[:] = s[::-1]
```
divmod(被除数，除数) —> 返回一个tuple of (商，余数)
```
x = divmod(5, 2)
print(x)

>>> (2, 1)
```

*variables 可变参数

函数的参数

小白的Python新手教程，基于最新的Python 3！

https://www.liaoxuefeng.com/wiki/1016959663602400/1017261630425888

>>> matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
>>> print(*matrix)
[1, 3, 5, 7] [10, 11, 16, 20] [23, 30, 34, 60]

>>> l = [1,2,3,4,5]
>>> print(*l)
1 2 3 4 5

collections.deque()
Deque in Python - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
https://www.geeksforgeeks.org/deque-in-python/
counter
collections — Container datatypes
Source code: Lib/collections/__init__.py This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.,,...
https://docs.python.org/3/library/collections.html#collections.Counter
string.join(iterable): Takes all items in an iterable and joins them into one string.
A string must be specified as the separator.
Python String join() Method
W3Schools offers free online tutorials, references and exercises in all the major languages of the web. Covering popular subjects like HTML, CSS, JavaScript, Python, SQL, Java, and many, many more.
https://www.w3schools.com/python/ref_string_join.asp

Problems Set

Tips

Notes

函数的参数

Deque in Python - GeeksforGeeks

collections — Container datatypes

Python String join() Method