拼图上门

   

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

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

请问为什么[3, 2, -1, 4] return 2呀，谢谢楼主，沾沾仙气～

[3, 2, -1, 4] 这里面有两个数可以用binary search找到， index 为1的“2”， 和index 为 2 的 “4”。  所以return 2 (可以找到两个)

alex_xiaofan 发表于 2018-10-29 11:28
[3, 2, -1, 4] 这里面有两个数可以用binary search找到， index 为1的“2”， 和index 为 2 的 “4”。  所 ...

想请教一下层主这个题除了暴力解法有什么别的好思路嘛？

可以想象成一个binaryTree, 最初的时候任何值都可以(MIN, MAX), 假设当前值为V，左边的边界变成(left, v), 右边的边界变成(v, right).

楼主第一题可以再解释一个deallocate是怎么工作的吗？没看懂描述。谢谢啦！

举个例子， 假设max是5 （池子是0，1，2，3，4）， 第一次调用allocate， 返回1 （池子里只剩下1，2，3，4），再次调用allocate,返回1（池子里剩下2，3，4），然后调用deallocate(0), 把0加入到池子（池子里现在是0，2，3，4）

第二题找binary 搜到的个数是这样的吧。

1. def count_found(arr):
   
2.     low, high = float('-inf'), float('inf')
   
3.     return count(arr, 0, len(arr) - 1, low, high)
   
4.    
   
5. def count(arr, start, end, low, high):
   
6.     if start > end:
   
7.         return 0
   
8.     mid = (start + end) // 2
   
9.     cur = 1 if low <= arr[mid] <= high else 0
   
10.     left_side = count(arr, start, mid - 1, low, arr[mid])
    
11.     right_side = count(arr, mid + 1, end, arr[mid], high)
    
12.    
    
13.     return left_side + right_side + cur
    
14.    
    
15. 
    
16. print(count_found([3, 2, -1, 4]))
    
17. print(count_found([3, 2, 1]))

复制代码