记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
5/16 面试题 04.06. 后继者
中序遍历逆序 右根左 记录前一个节点pre
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def inorderSuccessor(root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
global pre,flag
pre=None
flag = True
def find(node):
global pre,flag
if not node:
return
find(node.right)
if node==p:
flag = False
return
if flag:
pre = node
find(node.left)
find(root)
return pre
5/17 953. 验证外星语词典
比较前后两个单词是否符合顺序
按位比较 如果相等继续比较 如果前一个单词大于后一个则返回错误
def isAlienSorted(words, order):
"""
:type words: List[str]
:type order: str
:rtype: bool
"""
index = {}
for i,c in enumerate(order):
index[c] = i
def check(a,b):
m,n = len(a),len(b)
if n<m:
if b==a[:n]:
return False
for i in range(n):
if index[a[i]]>index[b[i]]:
return False
elif index[a[i]]==index[b[i]]:
continue
else:
return True
return True
else:
for i in range(m):
if index[a[i]]>index[b[i]]:
return False
elif index[a[i]]==index[b[i]]:
continue
else:
return True
return True
for i in range(len(words)-1):
if not check(words[i],words[i+1]):
return False
return True
5/18 668. 乘法表中第k小的数
m,n<=310^4 无法得到所有的数值来排序
取数值x 计算不大于x的数个数
共m行n列 每行每列单调递增
start = x//n 必定有start行 所有数都不大于x 共有startn个
从start+1行继续判断
可以得到不大于x的个数cnt
cnt可以与k比较 如果cnt比k小 说明x需要更大一些 反之x需要变小
所以可以使用二分来寻找x的值
def findKthNumber(m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
def find(x):
cnt = 0
start = x//n
cnt += start*n
for i in range(start+1,m+1):
cnt += x//i
return cnt
l,r = 1,m*n
while l<=r:
mid = (l+r)//2
cnt = find(mid)
if cnt<k:
l = mid+1
else:
r = mid-1
return r+1
5/19 462. 最少移动次数使数组元素相等 II
从小到大排序
找中位数
…a,b,c,…
如果共有2n+1个数
假设b是中位数 左边n个移动次数为x 右边n个移动次数为y 总次数为x+y
如果选定比b小的a 那么左边移动次数为 x-(b-a)*n 右边移动次数为y+(b-a)*n 加上b移动 b-a
总次数为 x-bn+an+y+bn-an+(b-a) = x+y+(b-a) > x+y 次数比假设的多
同理如果选定比b大的c也是一样
…a,b…
如果共有2n+2个数
选择a 左边n个移动次数为x 右边n个移动次数为y b移动b-a => x+y+b-a
选择b 左边n个移动次数为x+(b-a)*n 右边n个移动次数为y-(b-a)*n a移动b-a
=> x+(b-a)*n+y-(b-a)*n+b-a=x+y+b-a
所以此时选a或者b结果一样
综上所述只要选中位数即可得到最少移动数
def minMoves2(nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
n = len(nums)
target = nums[n//2]
ans = 0
for num in nums:
ans += abs(num-target)
return ans
5/20 436. 寻找右区间
[start,end] 起始位置start不会重复
如果startj=endi 那么i的右区间必定是j
初始化m为所有start对应的位置 后续将所有判断过的end结果记录保存
数组li存放所有start 并从小到大排序
为了找到右侧区间 二分在li中 找到第一个大于end的值 即为右侧区间起始start
def findRightInterval(intervals):
"""
:type intervals: List[List[int]]
:rtype: List[int]
"""
li = []
m = {}
for loc,tmp in enumerate(intervals):
li.append(tmp[0])
m[tmp[0]] = loc
li.sort()
ans = []
for tmp in intervals:
target = tmp[1]
if target>li[-1]:
ans.append(-1)
continue
if target in m:
ans.append(m[target])
continue
l,r = 0,len(li)-1
while l<=r:
mid = (l+r)//2
if li[mid]<target:
l = mid+1
else:
r = mid-1
ans.append(m[li[l]])
m[target] = m[li[l]]
return ans
5/21 961. 在长度 2N 的数组中找出重复 N 次的元素
哈希表 记录出现过的数字
def repeatedNTimes(nums):
"""
:type nums: List[int]
:rtype: int
"""
m = {}
for num in nums:
if num in m:
return num
else:
m[num]=1
5/22 464. 我能赢吗
最多20个数 使用20位二进制数来记录几个数被使用
dfs(used,total) 判断当前使用了used 总和为total 先手是否能够获胜
mem记录已经判断过的情况
def canIWin(maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
if (1+maxChoosableInteger)*maxChoosableInteger//2<desiredTotal:
return False
mem = {}
def dfs(used,total):
if (used,total) in mem:
return mem[(used,total)]
for i in range(maxChoosableInteger):
if (used>>i)&1==0:
tmptotal = total+i+1
if tmptotal>=desiredTotal or (not dfs(used|(1<<i) , tmptotal)):
mem[(used,total)] = True
return True
mem[(used,total)] = False
return False
return dfs(0,0)
