11/23 狗家 onsite

catinclay 发表于 2016-11-26 09:23
哈哈 我說的二維dp是palindrome那題
另一題確實是要三維dp

可以 帮忙解释下 第四轮 怎么用dp做嘛？？ 感激不尽！

xiangjn_alex 发表于 2016-11-27 12:12
可以 帮忙解释下 第四轮 怎么用dp做嘛？？ 感激不尽！

可以看一下我12樓的貼子 字數字數

第四题，可以把string拆成left和right两半，然后题目就转化为了shortestEditDistance(left,right)

第三题kruskal 第四题翻转后求最长公共子序列

楼主，我想请问下第一轮。 是不是有什么限制条件呀，比如数字都是小于10， 不然 a234, 可以理解成234个a?， 能否说明下具体的格式呢？谢谢楼主

1. #define MAXN 5000+5
   
2. short dp[MAXN][MAXN];
   
3. 
   
4. 
   
5. int intervalDP(string &s) {
   
6.         int n = s.length();
   
7.         for(int i=n-1;i >= 0; i--) {
   
8.                 for(int j=i+1;j<n;j++) {
   
9.                         if(s[i] == s[j]) {
   
10.                                 dp[i][j] = dp[i+1][j-1];
    
11.                         }else {
    
12.                                 dp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1;
    
13.                         }
    
14.                 }
    
15.         }
    
16.         return dp[0][n-1];
    
17. }
    
18. 
    
19. int lcs(string &s,string &t) {
    
20.         int n = s.length();
    
21.         for(int i=1;i<=n;i++) {
    
22.                 for(int j=1;j<=n;j++) {
    
23.                         if(s[i-1] == t[j-1]) {
    
24.                                 dp[i][j] = dp[i-1][j-1] + 1;
    
25.                         }else {
    
26.                                 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    
27.                         }
    
28.                 }
    
29.         }
    
30.         return dp[n][n];
    
31. }
    
32. 
    
33. int dfs(int l,int r,string &s) {
    
34.         if(l >= r) return 0;
    
35.         if(dp[l][r] != -1) return dp[l][r];
    
36.         if(s[l] == s[r]) {
    
37.                 dp[l][r] = dfs(l+1,r-1,s);
    
38.         }
    
39.         else {
    
40.                 dp[l][r] = min(dfs(l+1,r,s),dfs(l,r-1,s)) + 1;
    
41.         }
    
42.         return dp[l][r];
    
43. }
    
44. 
    
45. int main(){
    
46.         string s;
    
47.         while(cin>>s) {
    
48.                 int n = s.length();
    
49.                 // solution 1 区间dp
    
50.                 memset(dp,0,sizeof(dp));
    
51.                 cout<< intervalDP(s) <<endl;
    
52.                
    
53. 
    
54.                 // solution 2 lcs
    
55.                 memset(dp,0,sizeof(dp));
    
56.                 string t = s;
    
57.                 reverse(s.begin(),s.end());
    
58.                 int len = lcs(s,t);
    
59.                 cout<<n-len<<endl;
    
60.                
    
61. 
    
62.                 // solution 3 memory search
    
63.                 memset(dp,-1,sizeof(dp));
    
64.                 cout<<dfs(0,n-1,s)<<endl;
    
65. 
    
66.         }
    
67.         return 0;
    
68. }

复制代码

第四题三种方法：
1. 区间dp
2. 与翻转串求lcs, 答案：n-lcs
3. 记忆化搜索（比较好理解）

类与对象tju 发表于 2016-12-13 14:28
楼主，我想请问下第一轮。 是不是有什么限制条件呀，比如数字都是小于10， 不然 a234, 可以理解成234个a?， ...

没有限制，如果原字符串是11个a，会encode为a9a2，所以a234只可能理解成2个a和4个3

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

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

lz是hr collect完feedback以後叫去面application engineer 嗎？還是hc叫你去面的。。。

最后一题multi thread，是最后结尾count == 200 么，就算他们data race，最后还是各加100 -> 100 + 100 = 200? 求大神解答。。。