Solution 1
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for i in range(0, len(nums)):
index = abs(nums[i]) - 1
nums[index] = -abs(nums[index])
return [i + 1 for i in range(len(nums)) if nums[i] > 0]
Time complexity is O(n). Space complexity is O(1).
Solution 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 pathSum(self, root: TreeNode, sum: int) -> int:
#go through reach node. count the paths when the start node is that node.
self.numOfPaths = 0
self.dfs(root, sum)
return self.numOfPaths
def dfs(self, node, sum):
if node is None:
return
self.count(node, sum)
self.dfs(node.left, sum)
self.dfs(node.right, sum)
def count(self, node, sum):
if node is None:
return
if node.val == sum:
self.numOfPaths += 1
self.count(node.left, sum-node.val)
self.count(node.right, sum-node.val)
Both time complexity and space complexity are O(n*n) to O(nlogn).
Solution 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 pathSum(self, root: TreeNode, sum: int) -> int:
self.result = 0
presum = {0:1}
currentsum = 0
self.dfs(root, sum, 0, presum)
return self.result
def dfs(self, root, sum, currentsum, presum):
if root is None:
return
currentsum += root.val
needpresum = currentsum - sum
self.result += presum.get(needpresum, 0)
presum[currentsum] = presum.get(currentsum, 0) + 1
self.dfs(root.left, sum, currentsum, presum)
self.dfs(root.right, sum, currentsum, presum)
# *********
presum[currentsum] -= 1
Both time complexity and space complexity are O(n).
Solution 1
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
zero = 0 #position of 0
for i in range(len(nums)):
#if the num is not 0, move the num to the position of last zero
if nums[i] != 0:
nums[zero] = nums[i]
zero += 1
for i in range(zero, len(nums)):
nums[i] = 0
Time complexity is O(n). Space complexity is O(1).
Solution 2
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort(key=bool, reverse=True)
Time complexity is O(n log n). Space complexity is O(n).
Solution 3
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
zero = 0
#swap current first 0 and next non-zero elements
for i in range(len(nums)):
if nums[i] != 0:
nums[i], nums[zero] = 0, nums[i]
zero += 1
Time complexity is O(n). Space complexity is O(1).
Solution 1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
#if head == None: return False
#if[], output should be true
#fist-find the middle node, second-reverse half of the list, third-compare
fast = slow = head
pre = None
while fast and fast.next: #make sure fast is the last one or None.
fast = fast.next.next
slow = slow.next
head.next = pre
pre = head
head = slow
#1-2-3-4, now slow is 3, fast is null, pre is 2
#1-2-3-4-5, slow is 3, fast is 5, pre is 2
if fast: slow = slow.next #slow is 4
#compare
while pre and slow:
if pre.val != slow.val:
return False
else:
pre = pre.next
slow = slow.next
return True
Time complexity is O(n). Space complexity is O(1).
Solution 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 invertTree(self, root: TreeNode) -> TreeNode:
#Recusive
if not root: return None
right = self.invertTree(root.left)
left = self.invertTree(root.right)
root.right = right
root.left = left
return root
Time complexity is O(n). Space complexity is O(n).
Solution 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 invertTree(self, root: TreeNode) -> TreeNode:
#Iterative
if not root: return None
current = root
stack = []
while stack or current:
if current:
stack.append(current)
current = current.left
else:
current = stack.pop()
current.right, current.left = current.left, current.right
current = current.left
return root
Time complexity is O(n). Space complexity is O(n).
Solution 1: Iterative
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#Iterative
dummy = ListNode(float('-inf'))
while head:
dummy.next, head.next, head = head, dummy.next, head.next
return dummy.next
Time complexity is O(n). Space complexity is O(1).
Solution 2: Recursive
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#Recursive
if not head or not head.next: return head
left = self.reverseList(head.next)
head.next.next = head
head.next = None
return left
Time complexity is O(n). Space complexity is O(n).
Solution 1
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.array = []
def push(self, x: int) -> None:
cur_min = self.getMin()
if cur_min == None or x < cur_min: cur_min = x #here we can not use if not cur_min. Because if cur_min is 0, it will be considered as not cur_min is true!
self.array.append((x, cur_min))
def pop(self) -> None:
self.array.pop()
def top(self) -> int:
if not self.array: return None
return self.array[-1][0]
def getMin(self) -> int:
if not self.array: return None
return self.array[-1][1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
Time complexity and space complexity are O(1).
Warning: Do not use ” if not x”, if “x” is a number!
Solution 1
class Solution:
def rob(self, nums: List[int]) -> int:
# for house 0, we have to choose: rob or not. If we rob, the max total amount we can get is the max amount at point house -2 + amount in house 0. If not, the max total amount we can get is the max amount at point house -1.Thus, the largest amount is max( amount at house -2 + house 0, amount at house -1)
dp_last, dp_now = 0, 0
for num in nums:
dp_last, dp_now = dp_now, max(dp_last + num, dp_now)
return dp_now
Time complexity is O(n). Space complexity is O(1).
Solution 1:
class Solution:
def majorityElement(self, nums: List[int]) -> int:
dic = {}
for num in nums:
if num in dic:
dic[num] += 1
else:
dic[num] = 1
for v,k in dic.items():
if k > len(nums)/2:
return v
Time complexity is O(n). Space complexity is O(n).
Solution 2
class Solution:
def majorityElement(self, nums: List[int]) -> int:
#The number of majority element is more than n/2. Set the first number as the majority number. Count this number and not this number. When equal, delete this part. Go on...
index, cnt = 0, 1
for i in range(1,len(nums)):
if nums[i] == nums[index]:
cnt += 1
else:
cnt -= 1
if cnt == -1:
index = i
cnt = 1
return nums[index]
Time complexity is O(n). Space complexity is O(1).
Solution 3
class Solution:
def majorityElement(self, nums):
nums.sort()
return nums[len(nums)//2]
Time complexity is O(nlgn). It is the time to sort array in Python. Space complexity is O(n). Timsort is used.
Solution 1
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
pointerA = headA
pointerB = headB
while pointerA != pointerB:
if not pointerA:
pointerA = headB
else:
pointerA = pointerA.next
if not pointerB:
pointerB = headA
else:
pointerB = pointerB.next
return pointerA
Time complexity is O(m+n). Space complexity is O(1).
步步发财