新鲜亚麻OA

两题

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

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

shopping option是新题吧

Shopping Options里面的price是sort的吗？楼主我的想法是先sort,再递归搜索，如果小于等于budget就count++;楼主，这么解有问题吗？

风吹雨 发表于 2021-1-25 02:15
Shopping Options里面的price是sort的吗？楼主我的想法是先sort,再递归搜索，如果小于等于budget就count++; ...

不是sort，需要有memorization 有些case才不会超时

求楼主帮忙看下shopping options这样写可以吗

1. public int getNumberOfOptions(int[] priceOfJeans, int[] priceOfShoes,
   
2.                                   int[] priceOfSkirts, int[] priceOfTops, int dollars) {
   
3.         //dp[i][j] represents the # of options for buying items from 0 to i with j dollars
   
4.         //
   
5.        // induction rule: dp[i][j] += dp[i - 1][j - priceOfI] for each priceOfI if j - priceOfI >= 0
   
6.         //base case: dp[i][0] = 0, dp[0][j] depends on how many priceOfItem0 is <= j
   
7.         //time: O(4 * dollars * len of price array)
   
8. 
   
9.         int[][] dp = new int[4][dollars + 1];
   
10.         for (int i = 0; i < 4; i++) {
    
11.             for (int j = 0; j <= dollars; j++) {
    
12.                 if (j == 0) {
    
13.                     dp[i][j] = 0;
    
14.                 }
    
15.                 else if (i == 0) {
    
16.                     for (int price: priceOfJeans){
    
17.                         if (price <= j) {
    
18.                             dp[i][j]++;
    
19.                         }
    
20.                     }
    
21.                 }
    
22.                 else if (i == 1) {
    
23.                     induction(dp, priceOfShoes, i, j);
    
24.                 }
    
25.                 else if (i == 2) {
    
26.                     induction(dp, priceOfSkirts, i, j);
    
27.                 }
    
28.                 else if (i == 3) {
    
29.                     induction(dp, priceOfTops, i, j);
    
30.                 }
    
31.             }
    
32.         }
    
33.         return dp[3][dollars];
    
34. 
    
35. 
    
36.     }
    
37.     private void induction(int[][] dp, int[] prices, int i, int j) {
    
38.         for (int price: prices) {
    
39.             if (j - price >= 0) {
    
40.                 dp[i][j] += dp[i - 1][j - price];
    
41.             }
    
42.         }
    
43.     }

复制代码

dorothyzheng112 发表于 2021-1-30 11:51
求楼主帮忙看下shopping options这样写可以吗[mw_shl_code=java,true]public int getNumberOfOptions(int[] ...

亲测heap会爆掉
然后我优化了下只有两行，heap还是爆掉了。
大概是因为dollars 是 < 10^9。

最后没写出来testcase全过的解
现在想想可能得用Map来存之前的结果？有点类似用python写dfs，然后在dfs的function上加个@cache