GOOGLE ONSITE一道最近高频DP

Sliding Window解法：

1.         public static List<String> lengthOfReward(String s) {
   
2.                 List<String> res = new ArrayList<>();
   
3.                 Set<String> set = new HashSet<>();
   
4.                 int right = 0;
   
5.                 int left = 0;
   
6.                
   
7.                 int countA = 0;
   
8.                 int countL = 0;
   
9.                
   
10.                 while (right < s.length() - 1) {
    
11.                         char c = s.charAt(right);
    
12.                         if (c == 'A') countA++;
    
13.                         else if (c == 'L') countL++;
    
14.                        
    
15.                         while (left < right && (countA > 1 || countL > 3)) {
    
16.                                 char toDelete = s.charAt(left++);
    
17.                                 if (toDelete == 'A') countA--;
    
18.                                 if (toDelete == 'L') countL--;
    
19.                         }
    
20.                        
    
21.                         String cand = s.substring(left, right + 1);
    
22.                        
    
23.                         if (!set.contains(cand)) {
    
24.                                 res.add(cand);
    
25.                                 set.add(cand);
    
26.                         }
    
27.                        
    
28.                         right++;
    
29.                 }
    
30.                
    
31.                 return res;
    
32.         }

复制代码

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

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

jedihy 发表于 2017-2-28 00:53
follow up的输入只有n的。

只有n是说　input 是data stream ? 不理解...

18844549105 发表于 2017-2-14 17:24
随手写的，不知道对不对.

楼主我超同意你。不过我更新的f[n][0][0]=f[n-1][0][0]+f[n-1][0][1]+f[n-1][0][2]，求指教！

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

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

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

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

1. int count(int n) {
   
2.         // igore "A" first, and consider "O" and "L" only
   
3.         // create a 2D array dp[i][j]
   
4.         // dp[i][0] the number of rewardable string with length of i and the last letter is "O"
   
5.         // dp[i][1] the number of rewardable string with length of i and the last letter is "L"
   
6.         vector<vector<int>> dp(n+1, vector<int>{1,0});
   
7.         dp[1] = {1,1};
   
8. 
   
9.         for (auto i = 2; i <= n; ++i) {
   
10.                 dp[i][0] = dp[i-1][0] + dp[i-1][1];  // the ith letter is O
    
11.                 dp[i][1] = dp[i-1][0] + dp[i-2][0];  // the ith letter is L
    
12.         }
    
13. 
    
14.         int res = dp[n][0] + dp[n][1];   // case when there is no "A"
    
15.         // consider all the cases with one A
    
16.         // there are i letters to the left of A and n-i-1 letter to the right of A
    
17.         for (int i = 0; i < n; ++i) {
    
18.                 res += (dp[i][0]+dp[i][1])*(dp[n-i-1][0] + dp[n-i-1][1]);
    
19.         }
    
20.        
    
21.         return res;
    
22. }

复制代码

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

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

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

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

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

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