371. Sum of Two Integers （Medium）
Given two integers a and b, return the sum of the two integers without using the operators + and -.
class Solution:
def getSum(self, a: int, b: int) -> int:
x, y = abs(a), abs(b)
# ensure that abs(a) >= abs(b)
if x < y:
return self.getSum(b, a)
# abs(a) >= abs(b) -->
# a determines the sign
sign = 1 if a > 0 else -1
if a * b >= 0:
# sum of two positive integers x + y
# where x > y
while y:
answer = x ^ y
carry = (x & y) << 1
x, y = answer, carry
else:
# difference of two integers x - y
# where x > y
while y:
answer = x ^ y
borrow = ((~x) & y) << 1
x, y = answer, borrow
return x * sign
#ANSWER
class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xFFFFFFFF
while b != 0:
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
max_int = 0x7FFFFFFF
return a if a < max_int else ~(a ^ mask)
bit manipulation 初见感觉是。 但不知道怎么处理。思路，borrow 是 x&y《《1， 没borrow的sum是x^y.
372. Super Pow (Medium)
Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
class Solution:
def superPow(self, a: int, b: List[int]) -> int:
base=1337
def f(a,b):
res=1
for i in range(b):
res*=(a%base)
res%=base
return res
if not b: return 1
last_digit=b.pop()
return f(self.superPow(a, b), 10) * f(a, last_digit) % base;
mod 有结合律交换律吗？。。不太清楚。。。 答案用了1） ab % k = (a%k)(b%k)%k
2）ab%k=(a%k)b%k
推到递推关系：
a^1234567 % k = (a^1234560 a^7)%k= ((a^1234560)%k ) ((a^7)%k ) %k
= ((a123456)10)%k ) ((a^7)%k ) %k
= ((((a123456)%k)10 )% k) ((a^7)%k ) %k
设 a^b%k=f(a,b)
f(a,1234567)= f(f(a,123456),10) f(a,7)%k
373. Find K Pairs with Smallest Sums （Medium）
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u, v) which consists of one element from the first array and one element from the second array.
Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.
class Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
res = []
if not nums1 or not nums2 or not k:
return res
heap = []
visited = set()
heapq.heappush(heap, (nums1[0] + nums2[0], 0, 0))
visited.add((0, 0))
while len(res) < k and heap:
_, i, j = heapq.heappop(heap)
res.append([nums1[i], nums2[j]])
if i+1 < len(nums1) and (i+1, j) not in visited:
heapq.heappush(heap, (nums1[i+1] + nums2[j], i+1, j))
visited.add((i+1, j))
if j+1 < len(nums2) and (i, j+1) not in visited:
heapq.heappush(heap, (nums1[i] + nums2[j+1], i, j+1))
visited.add((i, j+1))
return res
暴力解肯定TLE。。。也想到了是k-way merge sort 但怎么写出来？直接抄答案了，用到了heapq.heappush, heapq.heappop, visited. 先从（0，0）开始push，然后是（1，0）（0，1）， i.e. (i,j) then (i+1,j),(i,j+1)... 通过visited 去重。
TWO POINTER 思路是错的，因为 0 1 2 | 1 2 3 一旦pointer1 移动到+1位置，所有pointer1之后位置能匹配p2的都会lost。 所以用heapq去做。
374. Guess Number Higher or Lower （Easy）
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e. num > pick).
1: Your guess is lower than the number I picked (i.e. num < pick).
0: your guess is equal to the number I picked (i.e. num == pick).
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
l=1
r=n
while l<=r:
m=(l+r)//2
if guess(m)==0:
return m
elif guess(m)==1:
l=m+1
else:
r=m-1
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
l=1
r=n
while l<=r:
m1=l+(r-l)//3
m2=r-(r-l)//3
res1=guess(m1)
res2=guess(m2)
if res1==0:
return m1
if res2==0:
return m2
elif res1<0:
r=m1-1
elif res2>0:
l=m2+1
else:
l=m1+1
r=m2-1
二分法，三分法。。。
375. Guess Number Higher or Lower II （Medium）
We are playing the Guessing Game. The game will work as follows:
I pick a number between 1 and n.
You guess a number.
If you guess the right number, you win the game.
If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
class Solution:
def getMoneyAmount(self, n: int) -> int:
#dp[i][j] will save the min cost guessing from i to j
dp=[[0]*(n+1) for _ in range(n+1)]
def helper(start,end):
if start>=end: return 0
if dp[start][end]!=0: return dp[start][end]
res=float('inf')
for x in range(start,end+1):
#try select x,the cost will be
tmp=x+max(helper(start,x-1),helper(x+1,end))
res=min(res,tmp)
dp[start][end]=res
return res
return helper( 1, n)
没思路。。。看答案，用了DP 关键是DP【i】【j】定义为从i猜到j，花费的最小cost。 那么如果X在i，j之间，选定了X，则cost为 X+max（dp【start】【x-1】，dp【x+1】【end】）因为dp这时候还没值，所以用helper（start，x-1），helper（x+1，end）代替，用max是因为不确定是左面还是右面，只能按照最坏情况准备钱。扫描所有X，然后最小的作为dp【i】【j】cost结果。
376. Wiggle Subsequence （Medium）
A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.
For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.
A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
Given an integer array nums, return the length of the longest wiggle subsequence of nums.
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
#dp[i] the max length of wiggle including nums[i]
# 1 17 5 10 13 15 10 5 16 8
# 0 + - + + + - - + -
# 1 2 3 4 4 4 5 5 6 7
# 1 7 4 9 2 5
# 0 + - + - +
#sign[i] the sign of max length of nums[i-1] to nums[i] if increasing 1 decresasing -1
if len(nums)<2: return len(nums)
if len(nums)==2 and nums[0]!=nums[1]:return 2
if len(nums)==2 and nums[0]==nums[1]:return 1
count_plus=0
count_minus=0
presign=None
for i in range(1,len(nums)):
if nums[i]==nums[i-1]: continue
sign= nums[i]-nums[i-1]>0
if sign:
#positive
if presign is None:
count_minus=1
if presign!=sign:
count_plus=count_minus+1
else:
#negtive
if presign is None:
count_plus=1
if presign!=sign:
count_minus=count_plus+1
presign=sign
return max([1,count_plus,count_minus])
#ANSWER DP O（n*n）
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums)<2: return len(nums)
up=[1]*len(nums)
down=[1]*len(nums)
for i in range(1,len(nums)):
for j in range(i):
if nums[i]>nums[j]:
up[i]=max(up[i],down[j]+1)
elif nums[i]<nums[j]:
down[i]=max(down[i],up[j]+1)
return max(up[-1],down[-1])
#ANSWER DP O（n）
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums)<2: return len(nums)
up=[0]*len(nums)
down=[0]*len(nums)
up[0]=1
down[0]=1
for i in range(1,len(nums)):
if nums[i]>nums[i-1]:
up[i]=down[i-1]+1
down[i]=down[i-1]
elif nums[i]<nums[i-1]:
down[i]=up[i-1]+1
up[i]=up[i-1]
else:
down[i]=down[i-1]
up[i]=up[i-1]
return max(up[-1],down[-1])
#ANSWER DP O（n） space O（1）
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums)<2: return len(nums)
up=1
down=1
for i in range(1,len(nums)):
if nums[i]>nums[i-1]:
up =down +1
elif nums[i]<nums[i-1]:
down =up +1
return max(up ,down )
#Greedy
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums)<2: return len(nums)
maxLen=1
sign=0
for i in range(1,len(nums)):
if nums[i]<nums[i-1] and sign!=-1:
# find a peak nums[i-1] is peak, now it is a decreasing sequence sign=-1
sign=-1
maxLen+=1
elif nums[i]>nums[i-1] and sign!=1:
#valley
sign=1
maxLen+=1
return maxLen
本来想用DP做，但发现只用保持 count+ 和 count- 两个计数器就够了。 如果发现增加2元序列，count-加1. 如果发现减小2元序列，count+加1，最后返回count+,count-中最大的就可以了，注意corner case。答案用了多种方法，贴上来开阔思路。第三个方法和我的一样但是写的更简单
377. Combination Sum IV （Medium）
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The test cases are generated so that the answer can fit in a 32-bit integer.
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
@lru_cache(None)
def dp(remain):
if remain==0:
return 1
res=0
for n in nums:
if remain-n>=0:
res+=dp(remain-n)
return res
return dp(target)
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# minor optimization
# nums.sort()
dp = [0 for i in range(target+1)]
dp[0] = 1
for comb_sum in range(target+1):
for num in nums:
if comb_sum - num >= 0:
dp[comb_sum] += dp[comb_sum-num]
# minor optimization, early stopping.
# else:
# break
return dp[target]
知道是DP，而且知道DP【i】是能sum到i的组合个数，那么dp【i】=dp【i-n】+dp【n】为啥不对？？ n是添加的最后一个数。而且扫的是所有n in nums。 如果再拆分n，那么会有重复。
思路卡了， 应该是dp【i】+=dp【i-n】 要往组合里加n能到i，那么多出来的组合数就是dp【i-n】。应该求的是和。。。
378. Kth Smallest Element in a Sorted Matrix （Medium）
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
minheap = []
for r in range(min(k,n)):
minheap.append((matrix[r][0], r, 0 ))
heapq.heapify(minheap)
e = None
while k:
e, r,c = heapq.heappop(minheap)
if c<n-1:
heapq.heappush(minheap, (matrix[r][c+1], r, c+1))
k-=1
return e
#ANSWER II
class Solution:
def countLessEqual(self, matrix, mid, smaller, larger):
count, n = 0, len(matrix)
row, col = n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] > mid:
# As matrix[row][col] is bigger than the mid, let's keep track of the
# smallest number greater than the mid
larger = min(larger, matrix[row][col])
row -= 1
else:
# As matrix[row][col] is less than or equal to the mid, let's keep track of the
# biggest number less than or equal to the mid
smaller = max(smaller, matrix[row][col])
count += row + 1
col += 1
return count, smaller, larger
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
start, end = matrix[0][0], matrix[n - 1][n - 1]
while start < end:
mid = (end + start) // 2
smaller, larger = matrix[0][0], matrix[n - 1][n - 1]
count, smaller, larger = self.countLessEqual(matrix, mid, smaller, larger)
if count == k:
return smaller
if count < k:
start = larger # search higher
else:
end = smaller # search lower
return start
方法一，用minheap去merge n行rows。
方法二，左上和右下是min max，找到middle， 从左下角开始， 这时候计数多少数字小于middle，如果当前值小于middle，说明当前row以上的col元素都小于middle值，计数，并把当前元素指针向右移动， 并同时计算小于middle值的最大元素，同理， 如果当前元素大于mid， 当前元素指针向上移动，
起码minheap方法应该想出来。
379. Design Phone Directory （Medium）
Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.
Implement the PhoneDirectory class:
PhoneDirectory(int maxNumbers) Initializes the phone directory with the number of available slots maxNumbers.
int get() Provides a number that is not assigned to anyone. Returns -1 if no number is available.
bool check(int number) Returns true if the slot number is available and false otherwise.
void release(int number) Recycles or releases the slot number.
class PhoneDirectory:
def __init__(self, maxNumbers: int):
self.n=maxNumbers
self.avaliable=set([i for i in range(self.n)])
self.used=set()
self.current=-1
def get(self) -> int:
if not self.avaliable: return -1
while not self.check(self.current):
self.current= (self.current+1)%self.n
#current in self.avaliable
# remove from self.avaliable
self.avaliable.remove(self.current)
self.used.add(self.current)
res = self.current
self.current= (self.current+1)%self.n
return res
def check(self, number: int) -> bool:
return number in self.avaliable
def release(self, number: int) -> None:
self.avaliable.add(number)
if number in self.used:
self.used.remove(number)
# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)
def __init__(self, maxNumbers):
self.available = set(range(maxNumbers))
def get(self):
return self.available.pop() if self.available else -1
def check(self, number):
return number in self.available
def release(self, number):
self.available.add(number)
#MY ANSWER
class PhoneDirectory:
def __init__(self, maxNumbers: int):
self.n = maxNumbers
self.circular = list(range(maxNumbers))
self.head = 0
def get(self) -> int:
if self.circular[self.head%self.n]!=-1:
val = self.circular[self.head%self.n]
self.circular[self.head%self.n] = -1
self.head+=1
return val
else:
c=0
while self.circular[self.head %self.n]==-1:
c+=1
self.head+=1
if c>=self.n:
return -1
val = self.circular[self.head%self.n]
self.circular[self.head%self.n]=-1
return val
def check(self, number: int) -> bool:
return self.circular[number]!=-1
def release(self, number: int) -> None:
self.circular[number] = number
#ANSWER PERFECT
class PhoneDirectory:
def __init__(self, maxNumbers: int):
self.pos=0
self.next=[0]*maxNumbers
for i in range(maxNumbers):
self.next[i]=(i+1)%maxNumbers
def get(self) -> int:
if self.next[self.pos]==-1: return -1
res=self.pos
self.pos=self.next[self.pos]
self.next[res]=-1
return res
def check(self, number: int) -> bool:
return self.next[number]!=-1
def release(self, number: int) -> None:
if self.next[number]!=-1: return
self.next[number]=self.pos
self.pos=number
# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number) int[] next;
答案很完美的写法：Use a linked list to track available numbers, and a pointer to head. If head is still available, get() would return it and move to the next available number. Release would re-add a node to the beginning of the linked list and update head
380. Insert Delete GetRandom O(1) （Medium）
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.
from random import choice
class RandomizedSet():
def __init__(self):
"""
Initialize your data structure here.
"""
self.dict = {}
self.list = []
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.dict:
return False
self.dict[val] = len(self.list)
self.list.append(val)
return True
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.dict:
# move the last element to the place idx of the element to delete
last_element, idx = self.list[-1], self.dict[val]
self.list[idx], self.dict[last_element] = last_element, idx
# delete the last element
self.list.pop()
del self.dict[val]
return True
return False
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return choice(self.list)
#MY SOLUTION
class RandomizedSet:
def __init__(self):
self.dic = dict()
self.rev_dic = dict()
self.i = 0
self.i_store = set()
def insert(self, val: int) -> bool:
if val in self.dic:
return False
if not self.i_store:
self.dic[val] = self.i
self.rev_dic[self.i] = val
self.i+=1
else:
self.dic[val] = self.i_store.pop()
self.rev_dic[ self.dic[val] ] = val
return True
def remove(self, val: int) -> bool:
if val not in self.dic:
return False
i = self.dic[val]
self.i_store.add(i)
del self.dic[val]
del self.rev_dic[i]
return True
def getRandom(self) -> int:
idx = random.randint(0,self.i)
while idx not in self.rev_dic:
idx = random.randint(0,self.i)
return self.rev_dic[idx]
答案思路好，用dic保存插入元素位置方便找出index， 删除时候找出index，然后和list中最后一个元素交换位置，然后pop list del dict【val】
我的思路， 用dic和rev_dic作为存储val - pos的mapping， 当remove时候， 位置会多余出来，存在i_store中， 当插入时候优先用i_store的pos， 这样random找的时候大概率从0到i是连续存储的，这样random一个int就能找到val。
还是答案思路好。