snowflake最新欧诶

很有用，谢谢

hzn942 发表于 2020-10-14 16:34
想了半天，第二题思路应该是用两个数组
array_d 和 array_t 分别记录以长度为i+1的时候D和T结尾组合个数， ...

谢谢分享

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

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

谢谢楼主

我觉得这3题都是动态规划，特别第二题，背包型动态规划

第二题，dpijk是对于前i个人已经连续了j个sde和k个sdt的方案总数

然后3重循环
dpijk+=sum（dpi-1 x y）xy就是还能加的人数，比如前面用了j个，后面就是3-j个的都可以

init就是dp000 等于1，其他dp0xy等于0

然后答案就是 dpnxy 对于所有xy求和

第三题也是dp，dpij=以坐标ij为右下角的最大正方形边长多少，然后答案就dpn-1n-1平方一下...

第二题代码

1. def theNumberofWays(self, d, t, queries):
   
2.         # dp[i][j][k] = to form a size of i employees, where last was j, and there are k consecutive of thems
   
3.         dp = [[[0] * (max(d, t) + 1) for _ in range(2)] for __ in range(2)]
   
4.         answer = [0] * len(queries)
   
5.         queryToIndex = {q : i for i, q in enumerate(queries)}
   
6.         queries.sort()
   
7.         index = 0
   
8.         dp[0][0][0] = 1
   
9.         dp[0][1][0] = 1
   
10.         for i in range(1, max(queries) + 1):
    
11.             dp[i % 2][0][0] = 0
    
12.             dp[i % 2][1][0] = 0
    
13.             dp[i % 2][0][1] = sum([dp[(i - 1) % 2][1][j] for j in range(t)])
    
14.             dp[i % 2][1][1] = sum([dp[(i - 1) % 2][0][j] for j in range(d)])
    
15.             for k in range(2, max(d, t) + 1):
    
16.                 dp[i % 2][0][k] = dp[(i - 1) % 2][0][k - 1] if k < d else 0
    
17.                 dp[i % 2][1][k] = dp[(i - 1) % 2][1][k - 1] if k < t else 0
    
18.             if queries[index] == i:
    
19.                 answer[queryToIndex[queries[index]]] = sum(dp[i % 2][0]) + sum(dp[i % 2][1])
    
20.                 index += 1
    
21.         return answer

复制代码

o彩蝶寻梦o 发表于 2021-2-1 13:26
第二题代码
[mw_shl_code=python,true]def theNumberofWays(self, d, t, queries):
        # dp[j][k] = ...

四个case没发过诶

笨笨李 发表于 2021-01-31 22:50:05
四个case没发过诶

因为TLE吗？求test cases，我瞅瞅，有链接吗？