Postmates oa

可能当前对Postmates感兴趣的朋友不多，但是作为练手还是不错的。他们的oa一共4题，前3题很简单我就略过了，下面是第4题：
一个list a, 里面是每段绳子的长度，可以裁剪绳子，一个整数k, 表示最后需要的绳子根数，求返回每根绳子可能的最长长度。e.g. a = [7, 2, 3, 4, 9], k = 5, 返回3.

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

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

0 + 1 + 2，没办法得到5根.

如果觉得有用的话请打赏点大米，谢谢

sagefrog 发表于 2020-6-4 10:35
感觉是个二分法。求问楼主是猎头领英骚扰的么 谢谢

是的，二分法就可以了。我是在领英被联系的，他们的节奏很快，可能最近招人有点急哈哈

感觉是个二分法。求问楼主是猎头领英骚扰的么 谢谢

第四题 这个二分法 怎么个思路？蠡口上有相似的题吗？

willwillzhang 发表于 2020-6-19 09:25
第四题 这个二分法 怎么个思路？蠡口上有相似的题吗？

不太有印象是不是有类似题。但是大概思路就是通过题目能很快找到答案的最大和最小可能值，然后在这个区间里用二分法 - 每一个中间数可以验证是否符合要求

deyomizy 发表于 2020-6-19 10:01
不太有印象是不是有类似题。但是大概思路就是通过题目能很快找到答案的最大和最小可能值，然后在这个区间 ...

哦 明白了。 例如， a = [7, 2, 3, 4, 9], k = 5,   就是sort下， 看下中间值（3）是不是满足条件，满足则往右走，不满足则忙左走， 再取新区间的中间数。

willwillzhang 发表于 2020-6-19 10:56
哦 明白了。 例如， a = [7, 2, 3, 4, 9], k = 5,   就是sort下， 看下中间值（3）是不是满足条件，满足 ...

应该不是这样，min = 1, max = max(nums),代表绳子的最大长度，最小是1， 最大是array里面最长的，然后来二分，不需要sort

deyomizy 发表于 2020-6-19 10:01
不太有印象是不是有类似题。但是大概思路就是通过题目能很快找到答案的最大和最小可能值，然后在这个区间 ...

下面是这个的代码实现。

1. # -*- coding: utf-8 -*-# -*- coding: utf-8 -*-"""
   
2. 一个list a, 里面是每段绳子的长度，可以裁剪绳子，一个整数k, 表示最后需要的绳子根数，
   
3. 求返回每根绳子可能的最长长度。e.g. a = [7, 2, 3, 4, 9], k = 5, 返回3
   
4. """
   
5. 
   
6. 
   
7. def cut_rope(arr, k):
   
8.     if not arr:
   
9.         if k != 0:
   
10.             return -1
    
11.         else:
    
12.             return
    
13. 
    
14.     min_len = min(arr)
    
15.     max_len = max(arr)
    
16. 
    
17.     # binary search
    
18.     l = min_len
    
19.     r = max_len
    
20.     while l + 1 < r:
    
21.         m = (l + r) / 2
    
22.         if lte_count(arr, m) >= k:
    
23.             l = m
    
24.         else:
    
25.             r = m
    
26.     if lte_count(arr, r) >= k:
    
27.         return r
    
28.     if lte_count(arr, l) >= k:
    
29.         return l
    
30.     return -1
    
31. 
    
32. 
    
33. def lte_count(arr, limit):
    
34.     count = 0
    
35.     for it in arr:
    
36.         count += it // limit
    
37.     return count
    
38. 
    
39. 
    
40. import unittest
    
41. 
    
42. class Test(unittest.TestCase):
    
43.     def test_1(self):
    
44.         self.assertEqual(
    
45.             cut_rope([7, 2, 3, 4, 9], 5),
    
46.             3
    
47.         )
    
48. 
    
49.     def test_2(self):
    
50.         self.assertEqual(
    
51.             cut_rope([7, 2, 3, 4, 9], 2),
    
52.             7
    
53.         )
    
54. 
    
55.     def test_3(self):
    
56.         self.assertEqual(
    
57.             cut_rope([7, 2, 3, 4, 9], 6),
    
58.             3
    
59.         )
    
60. 
    
61.     def test_4(self):
    
62.         self.assertEqual(
    
63.             cut_rope([7, 2, 3, 4, 9], 1),
    
64.             9
    
65.         )
    
66. 
    
67.     def test_5(self):
    
68.         self.assertEqual(
    
69.             cut_rope([], 1),
    
70.             -1
    
71.         )
    
72. 
    
73. if __name__ == '__main__':
    
74.     unittest.main(verbosity=2)
    

复制代码

应该是求第K大的数吧。
最优算法是quickselect。

说错了，没考虑到一个绳子可以分两段。 例如 9 可以拆成两个4的绳子和1的废料

最后分的绳的长度一定是整数吗 还是可以小数？？