class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
ans = []
nums = sorted(nums)
self.dfs(nums, 0, [], ans)
return ans
def dfs(self, nums, index, path, ans):
ans.append(path)
for i in range(index, len(nums)):
if i != index and nums[i] == nums[i-1]:
continue
self.dfs(nums, i+1, path + [nums[i]], ans)
Time complexity is O(n* 2^n). Space complexity is 0(1).
Most all possible solution problem is about searching. Most searching questions can be solved by recursion.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
self.dfs(nums, 0, [], ans)
return ans
def dfs(self, nums, index, path, ans):
ans.append(path)
for i in range(index, len(nums)):
self.dfs(nums, i+1, path + [nums[i]], ans)
Time complexity is O(n * 2^n). Space complexity is 0(1).
class Solution:
"""
@param source:
@param target:
@return: return the index
"""
def strStr(self, source, target):
# Write your code here
if len(target) == 0:
return 0
if len(source) - len(target) < 0:
return -1
for i in range(len(source) - len(target) + 1):
if source[i:i+len(target)] == target:
return i
return -1
Solution 1
# 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:
if not l1: return l2
if not l2: return l1
carry = 0
dummy = ListNode(0)
p = dummy
while l1 and l2:
p.next = ListNode((l1.val + l2.val + carry) % 10)
carry = (l1.val + l2.val + carry) // 10
l1 = l1.next
l2 = l2.next
p = p.next
while l1:
p.next = ListNode((l1.val + carry) % 10)
carry = (l1.val + carry) // 10
l1 = l1.next
p = p.next
while l2:
p.next = ListNode((l2.val + carry) % 10)
carry = (l2.val + carry) // 10
l2 = l2.next
p = p.next
if carry != 0:
p.next = ListNode(carry)
return dummy.next
Time complexity is O(max(m,n)). Space complexity is O(max(m,n)).
Solution 1
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
perms = [[]]
for num in nums:
new_perms = []
for perm in perms:
for i in range(len(perm)+1):
new_perms.append(perm[:i] + [num] + perm[i:])
perms = new_perms
return perms
Time complexity is O(n!). Space complexity is O(1).
Solution 2
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums) <= 1:
return [nums]
perms = []
for i, num in enumerate(nums):
n = nums[:i] + nums[i+1:]
for y in self.permute(n):
perms.append([num] + y)
return perms
Time complexity is O(n!). Space complexity is O(1).
Solution 1
class Solution:
def fizzBuzz(self, n: int) -> List[str]:
result = []
fizz_buzz_dict = {3 : "Fizz", 5 : "Buzz"}
for i in range(1, n+1):
ans = ''
for key in fizz_buzz_dict.keys():
if i % key == 0:
ans += fizz_buzz_dict[key]
if not ans:
ans = str(i)
result.append(ans)
return result
Time complexity is O(n). Space complexity is O(1)
Solution 1
class Solution:
def firstUniqChar(self, s: str) -> int:
# build hash map : character and how often it appears
count = collections.Counter(s)
class Solution:
"""
@param s: a string
@return: it's index
"""
def firstUniqChar(self, s):
# write your code here
count = collections.Counter(s)
#alp = {}
# for c in s:
# if c not in alp:
# alp[c] = 1
# else:
# alp[c] += 1
# find the index
for i in range(len(s)):
if count[s[i]] == 1:
return i
return -1
Time complexity is O(n). Space complexity is O(n).
I am not sure if the time complexity is right.
Solution 1
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
if len(nums1) > len(nums2):
return self.intersect(nums2, nums1)
lookup = collections.defaultdict(int)
for num in nums1:
lookup[num] += 1
ans = []
for num in nums2:
if lookup[num] > 0:
ans.append(num)
lookup[num] -= 1
return ans
Time complexity is O(n^2). Space complexity is O(m+n).
Solution 1
class Solution:
def reverseString(self, s: List[str]) -> None:
“””
Do not return anything, modify s in-place instead.
“””
for i in range(len(s) // 2):
s[i], s[-i-1] = s[-i-1], s[i]
Time complexity is O(n). Space complexity is O(1).
Solution 1
class Solution:
def isPowerOfThree(self, n: int) -> bool:
maxint = 2 ** 31 - 1
return n > 0 and 3 ** int(math.log(maxint,3)) % n == 0
Time complexity is O(1). Space complexity is O(1).
步步发财