🐶🐶 昂塞特

以LC 363为基础写了个第二题

1. #第二个阿三小哥，先问了问有什么interesting research的话题可以分享，然后开始做题：
   
2. # 又是一个二维矩阵代表cost，然后有个地产商要买地，他有一个budget limit，
   
3. # 求 < budget能买到的面积最大的rectangle，讨论了15min怎么做怎么优化，
   
4. # 15min写code，然后花了10min回答我的问题
   
5. 
   
6. def max_area_within_budget(mat, budget):
   
7.     if not mat: return 0
   
8.     m, n = len(mat), len(mat[0])
   
9. 
   
10.     res = 0
    
11.     for up in range(m):
    
12.         sumarr = [0] * n
    
13.         for down in range(up, m):
    
14.             for j in range(n):
    
15.                 sumarr[j] += mat[down][j]
    
16.             height = down - up + 1
    
17.             width = find_max_width(sumarr, budget)
    
18.             res = max(res, width * height)
    
19.     return res
    
20.    
    
21. def find_max_width(arr, k):
    
22.     res = 0
    
23.     curr = start = end = 0
    
24.     while end < len(arr):
    
25.         curr += arr[end]
    
26.         end += 1
    
27.         while curr > k:
    
28.             curr -= arr[start]
    
29.             start += 1
    
30.         res =  max(res, end - start)
    
31.     return res
    
32. 
    
33. import unittest
    
34. 
    
35. class TestMaxAreaWithinBudget(unittest.TestCase):
    
36. 
    
37.     def test_1(self):
    
38.         mat = [[1, 1, 3, 6], [2, 4, 10, 3], [1, 1, 9, 6]]
    
39.         k = 10
    
40.         print(max_area_within_budget(mat, k))
    
41.         assert max_area_within_budget(mat, k) == 6
    
42.         k = 4
    
43.         print(max_area_within_budget(mat, k))
    
44.         assert max_area_within_budget(mat, k) == 3
    
45. 
    
46.     def test_2(self):
    
47.         mat = [
    
48.             [10, 10, 10, 10],
    
49.             [11, 1, 2, 3],
    
50.             [21, 2, 3, 4],
    
51.             [40, 1, 9, 9]
    
52.         ]
    
53.         k = 4
    
54.         print(max_area_within_budget(mat, k))
    
55.         assert max_area_within_budget(mat, k) == 3
    
56.         k = 8
    
57.         print(max_area_within_budget(mat, k))
    
58.         assert max_area_within_budget(mat, k) == 4
    
59.         k = 15
    
60.         print(max_area_within_budget(mat, k))
    
61.         assert max_area_within_budget(mat, k) == 6
    
62.         k = 34
    
63.         print(max_area_within_budget(mat, k))
    
64.         assert max_area_within_budget(mat, k) == 9
    
65.         k = 10000
    
66.         print(max_area_within_budget(mat, k))
    
67.         assert max_area_within_budget(mat, k) == 16
    
68. 
    
69. unittest.main()

复制代码

kaipeng21 发表于 2019/04/09 10:35:08
以LC 363为基础写了个第二题

[mw_shl_code=python,true]#第二个阿三小哥，先问了问有什么interesting research的话题可以分享，然后开始做题：
# ...

楼主好记性

第三题可不可以把"转弯"当做cost，存入PriorityQueue用bfs或者dfs的方法，最后如果能到end_point，一定是转弯最少的方式。

补充内容 (2019-4-10 13:29):
也有可能是刷题网武林无。 那题是一直走到底，遇到墙就拐，求最少距离。 麻烦楼主再次确认一下

umialpha 发表于 2019-4-10 13:26
第三题可不可以把"转弯"当做cost，存入PriorityQueue用bfs或者dfs的方法，最后如果能到end_point，一定是转 ...

貌似不是利口武陵武，就是要求转弯次数最少

ruy1su 发表于 2019-4-9 03:03
第三题是不是利口maze兔bfs找最短？

差不多这个意思，不过不是要路程短，要转弯少，不过思路差不多吧

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

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

Gary.W 发表于 2019-4-9 07:40
LC 363

厉害厉害，就是这个变体，把最大sum编程最大面积

zhangzx 发表于 2019-4-10 23:40
Q4就是把一个array of dict 转成 dict of array，然后要处理missing data这样，比较像DS面
Q1没有overfl ...

谢谢回复，大家加油！

谢谢楼主！请问面的是research职位吗，为什么还要讨论论文

warlord 发表于 2019-4-11 00:16
谢谢楼主！请问面的是research职位吗，为什么还要讨论论文

投的就是General SDE，貌似博士都会面一轮thesis