[Uber]LC 34 Find First and Last Position of Element in Sorted Array
找一个target 在排序数组中出现多少次,最后问了一下复杂度和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 如果小于右端点,就可以划掉右半段。
[Uber]LC685
如果输入数组不是sorted该怎么解决,接下来问的是如果输入的数组已经排好序了,可以怎么用更小的时间复杂度解决这个问题。
要求优化到 two pointer!
如果不是sorted ,可不可以用一个size 为K 的max heap来保存一下tuple,compartor 比较的是每个数和target的绝对值。这样空间换时间?
LC 50 Pow(x,n)
Recursion很好写,interative的话,怎么理解每当遇到奇数的时候,就要把当前累计的pow放入ans?
power n变化过程:11--5--2--1
x的变化过程x--x2--x4--x^8
奇数对应的累乘就是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
网友评论