Lucid OA 分享

大家好，新手來這邊求點大米，順便分享一下，希望有幫助
這次題目是這個

Gridland is a 2D world divided into cells. We describe each cell as an (x,y) coordinate with (0,0) in the top left corner. From some cell (x,y), an inhabitant can move either horizontally or vertically to an adjacent cell, i.e. (x+1, y) or (x, y+ 1). We describe each possible minimum path as a sequence of horizontal and vertical moves denoted by the characters H and V. For exa

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

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

"2 2 3", "5 8 1006", "6 6 36"], 每一組的都代表x, y, k.

當然可以用暴力解，先把所有組合列出來，再找，可是運算時間會過長，我的解法是用dp來解，backtracking. 這樣可以省去滿大的時間

1. 
   
2. class Solution:
   
3.     def getSafePaths(self, journeys):
   
4.     # Write your code here
   
5.     #create dp array
   
6. 
   
7.     #using dynammic programming, due to the limitation of x and y is 10, I gave the range from 0~11
   
8. 
   
9.         dp = [[1 for i in range(11)] for j in range(11)]
   
10. 
    
11.         #the number of ways on the dp[i][j] position is equal dp[i-1][j] + dp[i][j-1]
    
12.         for i in range(1, 11):
    
13.             for j in range(1,11):
    
14.                 dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
15.         res = []
    
16.         #use for loop to take a look each paramater and split it by space
    
17.         for journey in journeys:
    
18.             paramater = journey.split()
    
19.             x = int(paramater[0])
    
20.             y = int(paramater[1])
    
21.             k = int(paramater[2])+1
    
22.             result = ""
    
23. 
    
24.         #from the dp[x][y] backtracking the path we want.
    
25.         #if dp[x-1][y] >= k, it means the path is start from H, otherwise, from V.
    
26.         #we need to reduce the number of combination which starts from H.
    
27.             while( x > 0 and y > 0):
    
28.                 if dp[x-1][y] >= k:
    
29.                     result += "H"
    
30.                     x-=1
    
31.                 else:
    
32.                     result += "V"
    
33.                     k-=dp[x-1][y]
    
34.                     y-=1
    
35.             while y > 0:
    
36.                 result += "V"
    
37.                 y-=1
    
38.             while x > 0:
    
39.                 result += "H"
    
40.                 x-=1
    
41. 
    
42.             res.append(result)
    
43. 
    
44.         return res
    
45. if __name__ == "__main__":
    
46.     nums = ['2 2 2', '2 2 3']
    
47.     result = Solution().getSafePaths(nums)
    
48.     print(result)

复制代码

他給了我十天去解這題，如果看不懂的話可以底下留言，我會幫你解答

新手求點大米 好過日子 謝謝各位

请问楼主是在哪里申请的呢，可否发个链接？谢谢

xiaojdaha 发表于 2020-7-23 08:48
请问楼主是在哪里申请的呢，可否发个链接？谢谢

我在LinkedIn 上看到的，你搜一下應該會有

MarcoGWAF 发表于 2020-7-24 12:20
我在LinkedIn 上看到的，你搜一下應該會有

谢谢，我没有看到new grad，直接投SDE就好？

xiaojdaha 发表于 2020-7-24 10:52
谢谢，我没有看到new grad，直接投SDE就好？

對的

你好，请问一下如何解释 “k-=dp[x-1][y]” 这一步的理由？

Jerry563 发表于 2020-8-24 08:03
你好，请问一下如何解释 “k-=dp[x-1][y]” 这一步的理由？

因為你往vertical 方向移動，所以k個路徑裡把所有這個移動方向之前包含的數量 dp[x-1][y] 減掉

请问楼主这题过了test吗？怎么感觉不太对呢，比如从0,0到2,1,k=2，dp是
11
12
13
按照您的算法得到vhh，但答案应该是vvh吧，能讲解下您这题思路吗，多谢

1. def generate_path(x, y, k):
   
2.     val = '1'*(x+y)
   
3.     minv = int('0', 2)
   
4.     maxv = int(val, 2)
   
5.     init = -1
   
6. 
   
7.     for i in range(minv, maxv+1):
   
8.         res = str(bin(i)[2:])
   
9.         if res.count('1')==y:
   
10.             if len(res)<(x+y):
    
11.                 res = '0'*(x+y-len(res)) +res
    
12.             init+=1
    
13.             if init == k:
    
14.                 return ''.join(['V'  if i =='1' else 'H' for i in res])

复制代码

这个code就把path map到0和1上去，就变成纯数学问题，非常简洁。
generate_path(6, 6, 36) 得到‘HHHVHVHVVHVV’ 和楼上的code结果一样的

楼主去Lucid了吗