骨骼 电面

• binary search  

  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  

  ecutive number in tree(not binary tree)
  
  
  
  

第二题dp。
DP[a][b] = min( max(DP[a][x-1], DP[x+1][b]) + x  for x in range (a; b))

tm1234 发表于 2017-12-29 11:11
请问这个状态转移里 dp到底是一位还是二维呢

2维。抱歉少写了几个。完整应该是
dp[a] = min(max(dp[a][x-1], dp[x+1][b])+x for x in range(a, b))
这个是leetcode原题。

[b]补充内容 (2017-12-30 00:15):
晕。这破输入
dp[ a ][ b ] = min (max (dp[ a ][x-1], dp[x+1][ b ]) + x for x in range( a, b))

rippersean 发表于 2017-12-29 04:13
第二题dp。
DP[a] = min( max(DP[a][x-1], DP[x+1]) + x  for x in range (a; b))

请问这个状态转移里 dp到底是一位还是二维呢

第二题是像binarysearch差不多的做法，只是把中间的数换成左右和相等的那个数吗？

miamiae 发表于 2017-12-24 12:35
第二题是像binarysearch差不多的做法，只是把中间的数换成左右和相等的那个数吗？

每次猜的数字是cost cost和最小

楼主可以再解释一下第二题的意思和思路吗？还有第三题followup的思路？谢谢啊

同想问下第二题的思路，谢谢。

xiayank 发表于 2017-12-28 04:32
楼主可以再解释一下第二题的意思和思路吗？还有第三题followup的思路？谢谢啊

第三题dfs叭？第二题思路不清楚…

coloor 发表于 2017-12-28 23:12
第三题dfs叭？第二题思路不清楚…

哦哦，再问一下，第三题是不是里口128啊

xiayank 发表于 2017-12-29 02:08
哦哦，再问一下，第三题是不是里口128啊

不是，里口是binary tree，这个是普通树，可能多于2个孩子

能麻烦楼主给第二题举个例子么？不是很理解