Table of Contents
Array & Hashing
Two Pointers
Binary Search
Backtracking
1-D Dynamic Programming
Solutions
Array & Hashing
217. Contains Duplicate
力扣题目链接
思路
代码
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
record = set()
for i in nums:
if i in record:
return True
record.add(i)
return False
242. Valid Anagram
力扣题目链接
思路
代码
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
hashmap = collections.defaultdict(list)
count_s = [0]*26
count_t = [0]*26
for l in s:
count_s[ord(l)-ord("a")] += 1
for l in t:
count_t[ord(l)-ord("a")] += 1
return count_s == count_t
1. Two Sum
力扣题目链接
思路
代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
record = {}
for index, value in enumerate(nums):
diff = target - value
if diff in record:
return record[diff],index
record[value] = index
return [] # 如果无解，返回[]
49. Group Anagrams
力扣题目链接
思路
代码
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list)
for s in strs:
count = [0]*26
for c in s:
count[ord(c)-ord("a")] += 1
res[tuple(count)].append(s)
return res.values()
# Time Complexity: O(m * n), where m is length of the strs, n is the length of the s
# Space Complexity:
347. Top K Frequent Elements
力扣题目链接
思路
代码
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
freq = [[] for i in range(len(nums) + 1)]
# step1: fill your hashmap
for n in nums:
count[n] = 1 + count.get(n, 0)
for n, c in count.items():
freq[c].append(n)
# step2: output via the result array
res = []
for i in reversed(range(0, len(freq))): # go through index reversely
for n in freq[i]: # fill the result array
res.append(n)
if len(res) == k: # Top K
return res
# O(n)
Two Pointers
125. Valid Palindrome
力扣题目链接
思路
- initialize
l and r
while l < r, which is outer loop, controls the two pointers move, point to the next letter.- skip constantly until
l >= r, which means going through the end of string. Using while rather than if which only make a step forward, due to more than one punctuaction and space.
代码
class Solution:
def isPalindrome(self, s):
l, r = 0, len(s) - 1
while l < r:
while l < r and not self.alphanum(s[l]): # skip constantly from the left of string until l >= r
l += 1
while l < r and not self.alphanum(s[r]): # skip constantly from the right of string until l >= r
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return True
def alphanum(self, c): # when judgment condition statement is too long to type
return (
ord("A") <= ord(c) <= ord("Z")
or ord("a") <= ord(c) <= ord("z")
or ord("0") <= ord(c) <= ord("9")
)
Binary Search
704. Binary Search
力扣题目链接
思路
代码
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid
return -1
875. Koko Eating Bananas
力扣题目链接
思路
代码
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l = 1
r = max(piles)
while l <= r:
mid = l + (r - l) // 2
hour = 0
for p in piles:
hour += math.ceil(p / mid)
if hour > h:
l = mid + 1
else:
r = mid - 1
return l
153. Find Minimum in Rotated Sorted Array
力扣题目链接
思路
代码
class Solution:
def findMin(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] < nums[r]: # min has not passed the mid
r = mid
else: # min has passed the mid
l = mid + 1
return nums[r]
Backtracking
78. Subsets
力扣题目链接
思路
代码
class Solution:
def subsets(self, nums):
res = []
self.backtracking(sorted(nums), 0, [], res)
return res
def backtracking(self, nums, startindex, path, res):
res.append(path[:])
for i in range(startindex, len(nums)):
path.append(nums[i])
self.backtracking(nums, i + 1, path, res)
path.pop()
90. Subsets II
力扣题目链接
思路
代码
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
nums.sort()
self.backtracking(nums, 0, path, res)
return res
def backtracking(self, nums, startindex, path, res):
uset = set()
res.append(path[:])
if startindex >= len(nums):
return
for i in range(startindex, len(nums)):
if nums[i] in uset:
continue
uset.add(nums[i])
path.append(nums[i])
self.backtracking(nums, i + 1, path, res)
path.pop()
70. Climbing Stairs
力扣题目链接
思路
代码
class Solution:
def climbStairs(self, n: int) -> int:
one, two = 1, 1
for i in range(n - 1):
temp = one
one = one + two
two = temp
return one