In python, hash_set is set; hash_table is dictionary
题目
find one missing from unsorted array
use a set, iterate over the input array Average O(n) Worst O(n^2)
for each number from 1 to n: find if it's in the set Average O(n) Worst O(n^2)
优化 use a boolean[]
因为连续，可以放进物理连续的boolean array里
Step 1: for each element in the input array (value=i), put it into the seen[i]=true O(n)
Step 2: for each element from 1...n: check if seen[i]==true O(n)
数学
等差数列求和，减去sum of input array，剩下的就是output Space O(1)
but it may overflow
bit operation XOR
交换律 a XOR b = b XOR a
结合律 a XOR (b XOR c) = (a XOR b) XOR c
0是单元 0 XOR a = a
a XOR a =0
find common numbers between 2 sorted arrays a[M], b[N]
需要确认 如果有重复元素怎么办
Assume没有重复 或者 有重复元素只输出一次
Hashset
比较大小，把小的放进hashset
Step 1: Insert all elements from smaller array a into the hash set
Step 2: For each element in array b, check if it's in the HashSet or not
Time = O(M+N) average, worst O(M^2+N*M)
Space = O(M)
谁小移谁
不相等就谁小移谁，相等就分别往前
Time = O(M+N)
Space = O(1)
如果M<<<N Binary Search
For each element in b[N], run binary search M times.
def most_common_words (freqs):
best = max(freqs.values())
words = [
key #代表元 expression
for key, val in freqs.items() #for循环
if val==best #判断条件
]
return (words, best)
new_mydic={
k.lower(): mydict.get(k.lower(), 0) + mydic.get(k.upper(),0)
for k in mydic.keys()
}
#output: {'a': 17, 'b': 34, 'z': 3}
class Solution(object):
def topKFrequent(self, combo, k):
"""
input: string[] combo, int k
return: string[]
"""
# write your solution here
mydict={}
for char in combo:
if char in mydict:
mydict[char]+=1
else:
mydict[char]=1
sorted_tuple=sorted(mydict.items(), key= lambda kv: -kv[1] )
return [x[0] for x in sorted_tuple][:k]
class Solution(object):
def topKFrequent(self, combo, k):
"""
input: string[] combo, int k
return: string[]
"""
# write your solution here
import collections
import heapq
counts = collections.Counter(combo)
items = list(counts.items())
items.sort(key=lambda item:(-item[1],item[0]))
return [item[0] for item in items[0:k]]
class Solution(object):
def topKFrequent(self, combo, k):
"""
input: string[] combo, int k
return: string[]
"""
# write your solution here
# max heap
mydict={}
for char in combo:
if char in mydict:
mydict[char]+=1
else:
mydict[char]=1
import heapq
freq=[]
for char in mydict.keys():
heapq.heappush(freq, (-mydict[char], char))
topk, i =[],0
while i < k and len(freq)>=1:
topk.append(heapq.heappop(freq)[1])
i+=1
return topk
class Solution(object):
def topKFrequent(self, combo, k):
"""
input: string[] combo, int k
return: string[]
"""
# write your solution here
# max heap
import collections
import heapq
count=collections.Counter(combo)
heap=[]
for key in count.keys():
heapq.heappush(heap, (count[key], key))
if len(heap)>k:
heapq.heappop(heap)
res=[]
while len(res)<=k and len(heap)>=1:
res.append(heapq.heappop(heap)[1])
return res[::-1]
def is_palindromic(word):
freq = {}
for i in range(len(word)):
if word[i] in freq:
freq[word[i]]+=1
else:
freq[word[i]]=1
odd_cnt = 0
for key in freq.key():
if freq[key]%2==1:
odd_cnt += 1
if odd_cnt > 1:
return False
return True
class Solution(object):
def numOfSubarraySumToK(self, nums, k):
"""
input: int[] nums, int k
return: int
"""
# write your solution here
sums, count = 0,0
mydict={}
for num in nums:
if sums not in mydict:
mydict[sums]=0
mydict[sums]+=1 #注意这句和下句的先后顺序
sums+=num
if sums-k in mydict:
count+=mydict[sums-k]
return count
def nearest_repeat (arr):
word_ind = {}
dist = float('inf')
for i in range(len(arr)):
if arr[i] in word_ind:
dist = min(dist, i -word_ind[arr[i]])
word_ind[arr[i]] = i
return dist
def 2sum(nums, target):
if len(nums)<=1:
return False
dict={}
for i in range (nums):
if nums[i] in dict:
return (dict[num[i]], i)
else:
dict[target-nums[i]]=i
return False
def longest_contained_range(arr):
unprocessed = set(arr)
maxlen = 0
while unprocessed:
elem = unprocessed.pop()
lower = elem - 1
while lower in unprocesssed:
unprocessed.remove(lower)
lower = lower-1
upper = elem + 1
while upper in unprocessed:
unprocessed.remove(upper)
upper = upper+1
maxlen = max(maxlen, upper-lower-1)
return maxlen
'John' in grades #return False
'Daniel' in grades #return True
grades['John'] = 'A'
grades['Ana'] = 'B+'
del grades['Ana'] #从字典里取这个key，然后删了
grades.pop('Ana') #随机pop出一个Ana（如果有两个Ana）
hash = hashfunc(key)
index = hash % array_size
x = {"a","b","c","d"}
x.add("e") #one element
x.update({"e", "f"}) #multiple elements
squared = {x**2 for x in [1,1,2]}
class Solution(object):
def missing(self, array):
"""
input: int[] array
return: int
"""
# write your solution here
n = len(array)+1
xor = 0
for i in range(1, n+1):
xor ^= i
for num in array:
xor ^= num
return xor
class Solution(object):
def common(self, A, B):
"""
input: int[] A, int[] B
return: Integer[]
"""
# write your solution here
i, j = 0, 0
result = []
while (i<len(A) and j<len(B)):
if (A[i]==B[j]):
result.append(A[i])
i+=1
j+=1
elif A[i]<B[j]:
i+=1
else:
j+=1
return result
def two_sum(list, target):
i,j = 0, len(list)-1
while i<j:
if list[i]+list[j] < target:
i += 1
elif list[i]+list[j] > target:
j -= 1
elif list[i]+list[j] == target:
return True
return False
# Time O(n)
# Space O(1)
def two_sum(list, target):
hashset = set()
for key in list:
if (target-key) in hashset:
return True
else:
hashset.add(key)
return False
# Time O(n)
# Space O(n)
def two_sum_duplicate(arr, sum):
dic = {}
count = 0
for key in arr:
if sum-key in dic:
count+=dic[sum-key]
if key in dic:
dic[key]+=1
else:
dic[key]=1
return count
# Time O(n)
# Space O(n)
def three_sum (array, target):
if array is None or len(array)==0:
return False
array.sort()
for i in range(len(array)-2):
start = i + 1
end = len(array)-1
while start<end:
tmp_sum = array[start] + array[end] + array[i]
if tmp_sum == target:
return True
elif tmp_sum < target:
start += 1
else:
end -= 1
return False
# Time O(n2)
# Space O(1)
for i in range(len(array)-3):
for j in range(i+1, len(array)-2):
#2sum
# Time O(n3)
# Space O(1)
def two_difference(array,target):
i,j = 0, 1
while j<len(array):
if array[j]-array[i] < target:
j += 1
elif array[j]-array[i] > target:
i += 1
elif:
return True
return False
# Time O(n)
# Space O(1)
def two_sum(list, target):
hashset = set()
for key in list:
if (key-target) in hashset or (target+key) in hashset:
return True
else:
hashset.add(key)
return False
# Time O(n)
# Space O(n)
def longest_sub_list(list):
hashset=set()
longest=0
slow=fast=0
while fast<len(list):
while list[fast] in hashset:
hashset.remove(list[slow])
slow+=1
hashset.add(list[fast])
longest = max(longest, fast-slow+1)
fast+=1
return longest
