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

class Solution:
    def printListFromTailToHead(self, listNode):
        array = []
        def visitNode(node):
            if not node:
                return
            visitNode(node.next)
            nonlocal array
            array.append(node.val)
        
        visitNode(listNode)
        return array

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

class Solution:
    def FindKthToTail(self , pHead , k ):
        if not pHead:
            return None
        
        dummy = ListNode(0)
        dummy.next = pHead
        fast, slow = dummy, dummy
        
        for _ in range(k):
            fast = fast.next
            if not fast:
                return None
        while fast:
            fast = fast.next
            slow = slow.next
        
        return slow

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

class Solution:
    def ReverseList(self, pHead):
        dummy = ListNode(0)
        
        cur = pHead
        while cur:
            temp = cur.next
            cur.next = dummy.next
            dummy.next = cur
            
            cur = temp
        
        return dummy.next

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

class Solution:
    def Merge(self, pHead1, pHead2):
        dummy = ListNode(0)
        cur = dummy
        
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
                cur = cur.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
                cur = cur.next
                
        if pHead1:
            cur.next = pHead1
            pHead1 = pHead1.next
            cur = cur.next
        if pHead2:
            cur.next = pHead2
            pHead2 = pHead2.next
            cur = cur.next

        return dummy.next

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

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        node_1, node_2 = pHead1, pHead2
        while node_1 != node_2:
            if not node_1:
                node_1 = pHead2
            else:
                node_1 = node_1.next
            if not node_2:
                node_2 = pHead1
            else:
                node_2 = node_2.next
                
        return node_1

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

class Solution:
    def EntryNodeOfLoop(self, pHead):
        slow, fast = pHead, pHead
        while True:
            if not fast or not fast.next:
                return None
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        
        slow = pHead
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def EntryNodeOfLoop(self, pHead):
        visit_node = []
        while True:
            if not pHead:
                return None
            if pHead in visit_node:
                return pHead
            else:
                visit_node.append(pHead)
            pHead = pHead.next

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

class Solution:
    def deleteDuplication(self, pHead):
        
        if not pHead or not pHead.next:
            return pHead
        
        if pHead.val == pHead.next.val:
            cur = pHead.next
            while cur.next and cur.next.val == cur.val:
                cur = cur.next
            return self.deleteDuplication(cur.next)
        else:
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead

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

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, vin):
        # write code here
        if not pre:
            return None
        
        for i in range(len(vin)):
            if vin[i] == pre[0]:
                node = TreeNode(pre[0])
                node.left = self.reConstructBinaryTree(pre[1:(i+1)], vin[:i])
                node.right = self.reConstructBinaryTree(pre[(i+1):], vin[(i+1):])
        
        return node

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        if not pRoot2:
            return False
        
        def compareTwoTrees(node1, node2):
            if not node2:
                return True
            if node2 and not node1:
                return False
            if node1.val != node2.val:
                return False
            else:
                return compareTwoTrees(node1.left, node2.left) \
                        and compareTwoTrees(node1.right, node2.right)
        
        queue = [pRoot1]
        while queue:
            node = queue.pop(0)
            if compareTwoTrees(node, pRoot2):
                return True
            if node:
                queue.append(node.left)
                queue.append(node.right)
        
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def Mirror(self , pRoot ):
        if pRoot is None:
            return
        
        pRoot.left, pRoot.right = pRoot.right, pRoot.left
        
        self.Mirror(pRoot.left)
        self.Mirror(pRoot.right)
        return pRoot

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

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        
        queue = [root]
        result = []
        
        while queue:
            node = queue.pop(0)
            if not node:
                continue
            queue.append(node.left)
            queue.append(node.right)
            result.append(node.val)
        
        return result

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

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False
        
        def check(array):
            if len(array) <= 2:
                return True
            
            mid_value = array[-1]
            seperate = -1
            
            for index in range(len(array) - 1):
                if array[index] < mid_value and seperate == -1:
                    continue
                elif array[index] < mid_value and seperate != -1:
                    return False
                elif array[index] > mid_value and seperate == -1:
                    seperate = index
                elif array[index] > mid_value and seperate != -1:
                    continue
            
            return check(array[0:seperate]) and check(array[seperate:-1])
        
        return check(sequence)

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

class Solution:
    def Convert(self, pRootOfTree):
        head = None
        pre = None
        
        def inOrder(node):
            if not node:
                return None
            
            inOrder(node.left)
            
            nonlocal pre
            node.left = pre
            if pre:
                pre.right = node
            pre = node
            
            nonlocal head
            if not head:
                head = node
                
            inOrder(node.right)
        
        inOrder(pRootOfTree)
        return head

1
2
3
4
5
6

class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1

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

class Solution:
    def IsBalanced_Solution(self, pRoot):
        def visitNode(node):
            if not node:
                return True, 0
            result_l, depth_l = visitNode(node.left)
            result_r, depth_r = visitNode(node.right)
            if result_l and result_r and -1 <= depth_l - depth_r <= 1:
                return True, max(depth_l, depth_r) + 1
            else:
                return False, max(depth_l, depth_r) + 1
        result, _ = visitNode(pRoot)
        return result

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

class Solution:
    def GetNext(self, pNode):
        if pNode.right:
            cur = pNode.right
            while cur.left:
                cur = cur.left
            return cur
        else:
            parent, cur = pNode.next, pNode
            while True: 
                if not parent:
                    return None
                if parent.right == cur:
                    parent, cur = parent.next, parent
                else:
                    break
            return parent

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

class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        def compare(left, right):
            if left and not right:
                return False
            if right and not left:
                return False
            if not left and not right:
                return True
            if left.val != right.val:
                return False
            else:
                return compare(left.left, right.right) and \
                       compare(left.right, right.left)
        
        if not pRoot:
            return True
        return compare(pRoot.left, pRoot.right)

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

class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        
        node_lst = [pRoot]
        is_reverse = False
        result = []
        while node_lst:
            current_line = []
            for _ in range(len(node_lst)):
                node = node_lst.pop(0)
                current_line.append(node.val)
                if node.left:
                    node_lst.append(node.left)
                if node.right:
                    node_lst.append(node.right)
            if is_reverse:
                result.append(current_line[::-1])
            else:
                result.append(current_line)
            is_reverse = not is_reverse
        return result

 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 Print(self, pRoot):
        if not pRoot:
            return []
        
        cur_line = [pRoot]        
        result = []
        
        while cur_line:
            values_lst = []
            for _ in range(len(cur_line)):
                node = cur_line.pop(0)
                values_lst.append(node.val)
                if node.left:
                    cur_line.append(node.left)
                if node.right:
                    cur_line.append(node.right)
            
            result.append(values_lst)
            next_line = []
            
        return result

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

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        cur_num = 0
        node_found = None
        
        def visitNode(node, k):
            if not node:
                return
            
            visitNode(node.left, k)
            
            nonlocal cur_num
            nonlocal node_found
            cur_num += 1
            if cur_num == k:
                node_found = node
                
            visitNode(node.right, k)
        
        visitNode(pRoot, k)
        return node_found

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

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

 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 __init__(self):
        self.stack = []
        self.stack_min = []
        
    def push(self, node):
        self.stack.append(node)
        
        if not self.stack_min:
            self.stack_min.append(node)
        else:
            self.stack_min.append(node if node < self.stack_min[-1] else self.stack_min[-1])
        
    def pop(self):
        self.stack_min.pop()
        return self.stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def min(self):
        return self.stack_min[-1]

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

class Solution:
    def IsPopOrder(self, pushV, popV):
        stack = []
        for i in popV:
            while not stack or stack[-1] != i:
                if not pushV:
                    return False
                else:
                    stack.append(pushV.pop(0))
            stack.pop(-1)
                    
        return True

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

class Solution:
    # 返回对应char
    def __init__(self):
        self.letter_set = set()
        self.letter_hash_table = []
        
    def FirstAppearingOnce(self):
        return '#' if not self.letter_hash_table else self.letter_hash_table[0]
    
    def Insert(self, char):
        if char not in self.letter_set:
            self.letter_set.add(char)
            self.letter_hash_table.append(char)
        else:
            if char in self.letter_hash_table:
                self.letter_hash_table.remove(char)

1
2
3
4
5
6

class Solution:
    def maxInWindows(self, num, size):
        if size > len(num) or size == 0:
            return None

        return [max(num[i:i + size]) for i in range(0, len(num) - size + 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

class Solution:
    def __init__(self):
        self.first_half_heap = []
        self.second_half_heap = []
        self.N = 0
        
    def Insert(self, num):
        if self.N % 2 == 0:
            self.second_half_heap.append(num)
            self.second_half_heap = sorted(self.second_half_heap)
            self.first_half_heap.append(self.second_half_heap.pop(0))
            self.first_half_heap = sorted(self.first_half_heap)
        else:
            self.first_half_heap.append(num)
            self.first_half_heap= sorted(self.first_half_heap) 
            self.second_half_heap.append(self.first_half_heap.pop(-1))
            self.second_half_heap = sorted(self.second_half_heap)
        
        self.N += 1
        
    def GetMedian(self):
        if self.N % 2 == 0:
            return (self.first_half_heap[-1] + self.second_half_heap[0]) / 2
        else:
            return self.first_half_heap[-1]

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

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        max_m, max_n = len(array), len(array[0])
        i, j = 0, max_n - 1
        while i < max_m and j >= 0:
            if array[i][j] == target:
                return True
            elif array[i][j] > target:
                j -= 1
            else:
                i += 1
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def reOrderArray(self , array):
        odd_lst, even_lst = [], []
        for num in array:
            if num % 2 == 0:
                even_lst.append(num)
            else:
                odd_lst.append(num)
        odd_lst.extend(even_lst)
        return odd_lst

 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

class Solution:
    def printMatrix(self, matrix):
        left_top = (0, 0)
        right_top = (0, len(matrix[0]) - 1)
        left_bot = (len(matrix) - 1, 0)
        right_bot = (len(matrix) - 1, len(matrix[0]) - 1)
        
        result = []
        while left_top[0] <= left_bot[0] and left_top[1] <= right_top[1]:
            i = left_top[1]
            while i <= right_top[1]:
                result.append(matrix[left_top[0]][i])
                i += 1
                
            i = left_top[0] + 1
            while i <= right_bot[0]:
                result.append(matrix[i][right_top[1]])
                i += 1
            
            if left_top[0] != left_bot[0]:
                i = right_bot[1] - 1
                while i >= left_bot[1]:
                    result.append(matrix[right_bot[0]][i])
                    i -= 1
            
            if left_top[1] != right_top[1]:
                i = left_bot[0] - 1
                while i > left_top[0]:
                    result.append(matrix[i][left_top[1]])
                    i -= 1

            left_top = left_top[0] + 1, left_top[1] + 1
            right_top = right_top[0] + 1, right_top[1] - 1
            left_bot = left_bot[0] - 1, left_bot[1] + 1
            right_bot = right_bot[0] - 1, right_bot[1] - 1
        
        return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        result = None
        cur_sum = 0
        for num in array:
            if cur_sum <= 0:
                cur_sum = num
            else:
                cur_sum += num
            result = max(cur_sum, result) if result else cur_sum
        return result

 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 FindContinuousSequence(self, tsum):
        if tsum <= 2:
            return []
        
        slow, fast = 1, 2
        cur_sum = 3
        
        result = []
        while(fast < tsum):
            if cur_sum == tsum:
                result.append(range(slow, fast + 1))
                fast += 1
                cur_sum += fast
            elif cur_sum < tsum:
                fast += 1
                cur_sum += fast
            elif cur_sum > tsum:
                cur_sum -= slow
                slow += 1
       
        return result

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

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        left, right = 0, len(array) - 1
        while left < right:
            s = array[left] + array[right]
            if s == tsum:
                return [array[left], array[right]]
            elif s < tsum:
                left += 1
            elif s > tsum:
                right -=1
        
        return []

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

class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        def reverse(str_list):
            left, right = 0, len(str_list) - 1
            while left < right:
                str_list[left], str_list[right] = str_list[right], str_list[left]
                left += 1
                right -= 1
            return str_list
        
        str_list = list(s)
        str_list[0:n] = reverse(str_list[0:n])
        str_list[n:] = reverse(str_list[n:])
        
        return "".join(reverse(str_list))

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

class Solution:
    def IsContinuous(self, numbers):
        numbers.sort()
        zero_count = 0
        for num in numbers:
            if not num:
                zero_count += 1
        
        for index in range(zero_count, len(numbers)):
            if index == len(numbers) - 1:
                return True
            if numbers[index + 1] - numbers[index] == 0:
                return False
            if numbers[index + 1] - numbers[index] > 1:
                zero_count -= numbers[index + 1] - numbers[index] - 1
                if zero_count < 0:
                    return False
            index += 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def duplicate(self , numbers ):
        # write code here
        for i in range(len(numbers)):
            while i != numbers[i]:
                if numbers[numbers[i]] == numbers[i]:
                        return numbers[i]
                else:
                        numbers[numbers[i]], numbers[i] = numbers[i], numbers[numbers[i]]
        return -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

class Solution:
    def ReverseSentence(self, s):
        
        string = list(s)
        def reverse(left, right):
            while left < right:
                string[left], string[right] = string[right], string[left]
                left += 1
                right -= 1
        
        flag = False
        for i in range(len(string)):
            if not flag and string[i] != " ":
                flag = True
                l = i
            if string[i] == " ":
                reverse(l, i-1)
                flag = False
        else:
            if flag:
                reverse(l, i)
        
        reverse(0, len(string)-1)
        return "".join(string)

 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 StrToInt(self, s):
        s_reverse = s[::-1]
        dict_ = {
            '0': 0,
            '1': 1,
            '2': 2,
            '3': 3,
            '4': 4,
            '5': 5,
            '6': 6,
            '7': 7,
            '8': 8,
            '9': 9
        }
        result = 0
        digit = 1
        for letter in s_reverse:
            if letter in dict_:
                result += dict_[letter] * digit
            elif letter == s[0] and letter == '+':
                pass
            elif letter == s[0] and letter == '-':
                result = - result
            else:
                return 0
            digit *= 10
        return result

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

class Solution:
    def multiply(self, A):
        B = [0 for _ in range(len(A))]
        product = 1
        for i in range(len(A)):
            B[i] = product
            product *= A[i]
        
        product = 1
        for i in range(len(A))[::-1]:
            B[i] *= product
            product *= A[i]
            
        return B

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

class Solution:
    def FirstNotRepeatingChar(self, s):
        letter_lst = []
        dictionary = {}
        for index, letter in enumerate(s):
            if letter not in letter_lst:
                dictionary[letter] = index
                letter_lst.append(letter)
            else:
                letter_lst.remove(letter)
        if not letter_lst:
            return -1
        return dictionary[letter_lst[0]]

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

class Solution:
    def FindNumsAppearOnce(self , array ):
        set_1 = set()
        set_2 = set()
        for num in array:
            if num not in set_1:
                set_1.add(num)
            elif num not in set_2:
                set_2.add(num)
            else:
                continue
        
        return sorted(set_1 - set_2)

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

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        results = []
        def visitNode(node, num, state):
            if not node:
                return
            state.append(node.val)
            if not node.left and not node.right:
                if num == node.val:
                    nonlocal results
                    results.append(state)
                return
            visitNode(node.left, num - node.val, list(state))
            visitNode(node.right, num - node.val, list(state))
        
        if not root:
            return []
        visitNode(root, expectNumber, list())
        return results

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

class Solution:
    def Permutation(self, ss):
        # write code here
        results = []
        
        def check(cur_state, cur_choice):
            if not cur_choice:
                nonlocal results
                if cur_state not in results:
                    results.append(cur_state)
                return
            
            original_choice = tuple(cur_choice)
            for index in range(len(cur_choice)):
                next_choice = list(original_choice)
                next_choice.pop(index)
                check(cur_state + cur_choice[index], next_choice)
                
        check("", ss)
        return results

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

class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers:
            return ""

        results = []
        def backtrack(cur_state, choice):
            if not choice:
                nonlocal results
                results.append(int(cur_state))
                return
            for c in choice:
                next_choice = list(choice)
                next_choice.remove(c)
                backtrack(cur_state + str(c), next_choice)
                
        backtrack("", numbers)
        return min(results)

 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

class Solution:
    def hasPath(self , matrix , word):
        # write code here
        result = False
        def backtrack(state, matrix, word):
            if len(state) == len(word):
                nonlocal result 
                result = True
                return
            
            if len(state) == 0:
                for i in range(len(matrix)):
                    for j in range(len(matrix[0])):
                        if matrix[i][j] == word[0]:
                            next_state = list(state)
                            next_state.append((i, j))
                            backtrack(next_state, matrix, word)
            else:
                # up
                i, j = state[-1]
                if i - 1 >=0 and (i - 1, j) not in state:
                    if matrix[i - 1][j] == word[len(state)]:
                        next_state = list(state)
                        next_state.append((i - 1, j))
                        backtrack(next_state, matrix, word)
                # right
                if j + 1 < len(matrix[0]) and (i, j + 1) not in state:
                    if matrix[i][j + 1] == word[len(state)]:
                        next_state = list(state)
                        next_state.append((i, j + 1))
                        backtrack(next_state, matrix, word)
                # left
                if j - 1 >=0 and (i, j - 1) not in state:
                    if matrix[i][j - 1] == word[len(state)]:
                        next_state = list(state)
                        next_state.append((i, j - 1))
                        backtrack(next_state, matrix, word)
                # down
                if i + 1 < len(matrix) and (i + 1, j) not in state:
                    if matrix[i + 1][j] == word[len(state)]:
                        next_state = list(state)
                        next_state.append((i + 1, j))
                        backtrack(next_state, matrix, word)
        backtrack([], matrix, word)
        return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def Fibonacci(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        lst = [0, 1]
        while len(lst) <= n:
            lst.append(lst[-1] + lst[-2])
        return lst[-1]

1
2
3
4
5
6
7

class Solution:
    def jumpFloor(self, number):
        # write code here
        lst = [1, 2]
        while len(lst) < number:
            lst.append(lst[-1] + lst[-2])
        return lst[number - 1]

1
2
3
4
5
6

class Solution:
    def jumpFloorII(self, number):
        lst = [1]
        while len(lst) < number:
            lst.append(sum(lst) + 1)
        return lst[number - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def rectCover(self, number):
        lst = [0, 1, 2]
        if number <= 2:
            return lst[number]
        
        while len(lst) < number + 1:
            lst.append(lst[-1] + lst[-2])
        
        return lst[-1]

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

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        
        left, right = 0, len(rotateArray) - 1
        while left < right:
            mid = (left + right) // 2
            if rotateArray[mid] < rotateArray[right]:
                right = mid
            elif rotateArray[mid] == rotateArray[right]:
                right -= 1
            elif rotateArray[mid] > rotateArray[right]:
                left = mid + 1
                
        return rotateArray[left]

 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 GetNumberOfK(self, data, k):
        
        # get left point
        left, right = 0, len(data) - 1
        while left <= right:
            mid = round((left + right) / 2)
            if data[mid] == k:
                right = mid - 1
            elif data[mid] > k:
                right = mid - 1
            elif data[mid] < k:
                left = mid + 1
        if left >= len(data):
            return 0
        left_most = left
        
        # get the right point
        left, right = 0, len(data) - 1
        while left <= right:
            mid = round((left + right) / 2)
            if data[mid] == k:
                left = mid + 1
            elif data[mid] > k:
                right = mid - 1
            elif data[mid] < k:
                left = mid + 1
                
        if right < left_most:
            return 0
        return right - left_most + 1

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

class Solution:
    def cutRope(self, number):
        if number == 1:
            return 1
        dp = [None, 1]
        
        i = 2
        while i <= number:
            j = 1
            max_i = i
            while j < i:
                max_i = max(max_i, dp[i - j] * j)
                j += 1
            
            dp.append(max_i)
            i += 1 
            
        return dp[-1]

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

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # use fast sort
        def fast_sort(lst):
            if len(lst) <= 1:
                return lst
            mid_value = lst[-1]
            switch_index = 0
            for i in range(len(lst) - 1):
                if lst[i] <= mid_value:
                    lst[i], lst[switch_index] = lst[switch_index], lst[i]
                    switch_index += 1
                else:
                    continue
            lst[switch_index], lst[-1] = lst[-1], lst[switch_index]
            lst[:switch_index] = fast_sort(lst[:switch_index])
            lst[switch_index + 1:] = fast_sort(lst[switch_index + 1:])
            return lst
        
        tinput = fast_sort(tinput)
        return tinput[:k]

 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

class Solution:
    def InversePairs(self, data):
        result = 0
        
        def mergeSort(left, right):
            if left >= right:
                return   
            mid = (left + right) // 2
            mergeSort(left, mid)
            mergeSort(mid + 1, right)
            merge(left, mid, right)
        
        def merge(left, mid, right):
            nonlocal result
            nonlocal data
            
            merged_lst = []
            i, j = left, mid + 1
            while i <= mid or j <= right:
                if i > mid:
                    merged_lst.append(data[j])
                    j += 1
                elif j > right:
                    merged_lst.append(data[i])
                    i += 1
                elif data[i] <= data[j]:
                    merged_lst.append(data[i])
                    i += 1
                else:
                    merged_lst.append(data[j])
                    result += (mid - i + 1)
                    j += 1
            
            data[left:right + 1] = merged_lst
        
        mergeSort(0, len(data) - 1)
        return result % 1000000007

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

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        digit = 1
        ones = 0
        while digit <= n:
            a = n // digit
            b = n % digit
            ones += (a + 8) // 10 * digit + (a % 10 == 1) * (b + 1)
            
            # after each iter
            digit *= 10
        return ones

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n == 0:
            return -1
        children = [i for i in range(n)]
        away_index = 0
        while len(children) > 1:
            away_index = (m + away_index - 1) % len(children)
            children.pop(away_index)
        return children[0]

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

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        majority = numbers[0]
        count = 1
        for i in range(len(numbers)):
            if i == 1:
                continue
                
            if majority == numbers[i]:
                count += 1
            else:
                count -= 1
            
            if count == 0:
                majority = numbers[i]
                count = 1
         
        return majority

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

class Solution:
    def GetUglyNumber_Solution(self, index):
        if index == 0:
            return 0
        i2 = i3 = i5 = 0
        ugly_lst = [1]
        while len(ugly_lst) < index:
            next_2 = ugly_lst[i2] * 2
            next_3 = ugly_lst[i3] * 3
            next_5 = ugly_lst[i5] * 5
            ugly_lst.append(min(next_2, next_3, next_5))
            if next_2 == min(next_2, next_3, next_5):
                i2 += 1
            if next_3 == min(next_2, next_3, next_5):
                i3 += 1
            if next_5 == min(next_2, next_3, next_5):
                i5 += 1
        return ugly_lst[-1]

1
2
3

class Solution:
    def Sum_Solution(self, n):
        return n and (n + self.Sum_Solution(n - 1))