[Uber]LC 34 Find First and Last Position of Element in Sorted Array
找一個(gè)target 在排序數(shù)組中出現(xiàn)多少次，最后問了一下復(fù)雜度和corner case托修。
LB: first element >=target
UB: first element >target
class Solution(object):
def searchRange(self, nums, target):
if not nums: return [-1,-1]
LB = self.find_LB(nums,target)
UB = self.find_UB(nums,target)
return [LB,UB]
def find_LB(self,nums,target):
l,r = 0,len(nums)
while l<r:
mid = l + (r-l)//2
if nums[mid]<target:
l = mid + 1
else:
r = mid
if l>=len(nums) or l<0: return -1
return l if nums[l]==target else -1
def find_UB(self,nums,target):
l,r = 0,len(nums)
while l<r:
mid = l + (r-l)//2
if nums[mid]>target:
r = mid
else:
l = mid+1
if r-1>=len(nums) or r-1<0: return -1
return r-1 if nums[r-1]==target else -1
[Uber] 154 Find Minimum in Rotated Sorted Array II
mid 如果小于右端點(diǎn)恒界，就可以劃掉右半段。
[Uber]LC685
如果輸入數(shù)組不是sorted該怎么解決涩拙，接下來問的是如果輸入的數(shù)組已經(jīng)排好序了耸采，可以怎么用更小的時(shí)間復(fù)雜度解決這個(gè)問題。
要求優(yōu)化到 two pointer!
如果不是sorted 洋幻，可不可以用一個(gè)size 為K 的max heap來保存一下tuple，compartor 比較的是每個(gè)數(shù)和target的絕對(duì)值文留。這樣空間換時(shí)間?
LC 50 Pow(x,n)
Recursion很好寫，interative的話骑篙，怎么理解每當(dāng)遇到奇數(shù)的時(shí)候森书，就要把當(dāng)前累計(jì)的pow放入ans?
power n變化過程:11--5--2--1
x的變化過程x--x2--x4--x^8
奇數(shù)對(duì)應(yīng)的累乘就是ans = xx^2x8=x11
def myPow(self, x, n):
if n==0: return 1
if x==0: return 0
if n<0:
n=-n
x = 1/x
return x*self.myPow(x*x,n//2) if n&1 else self.myPow(x*x,n//2)
def myPow(self, x, n):
if n==0: return 1
if x==0: return 0
if n<0:
n=-n
x = 1/x
ans = 1
while n:
if n&1: #odd
ans *=x
x*=x
n=n>>1
return ans
