🦴狗新鲜面经

请问第一题followup怎么做？

spirit_room 发表于 2020/02/14 13:17:26
二分怎么做？

确定长度为m的字符串 存在或不存在 原字符串中 复杂度 O（n） , 从 1 到 n 二分查找 （如果m存在 那m+1肯定存在）

lyronly 发表于 2020-2-14 13:37
确定长度为m的字符串 存在或不存在 原字符串中 复杂度 O（n） , 从 1 到 n 二分查找 （如果m存在 那m+1肯 ...

为啥是二分呢？举个例子，“ABB”的返回结果应该是“BA”，二分能做什么呢？

论坛匿名账号 发表于 2020/02/14 14:42:31
为啥是二分呢？举个例子，“ABB”的返回结果应该是“BA”，二分能做什么呢？

二分找 最短字符串的长度

lyronly 发表于 2020-2-14 16:27
二分找 最短字符串的长度

题目要求是subsequence

第一题followup可以用递归或者DP做。实际也不难理解，但写代码也不容易，还是followup。

1. vector<vector<string>> dp;
   
2. string minNonSubsequence(string &s, int end, char last_c) {
   
3.     string ans;
   
4.     if (end == 0) {
   
5.         ans.push_back(last_c);
   
6.         return ans;
   
7.     }
   
8.    
   
9.     if (dp[end-1][last_c - 'A'].size()) {
   
10.         return dp[end-1][last_c - 'A'];
    
11.     }
    
12.    
    
13.     if (s[end-1] == last_c) {
    
14.         string tmp = minNonSubsequence(s, end - 1, 'A');
    
15.         string tmp1 = minNonSubsequence(s, end - 1, 'B');
    
16.         if (tmp.size() <= tmp1.size()) {
    
17.             ans = tmp;
    
18.         } else {
    
19.             ans = tmp1;
    
20.         }
    
21.         
    
22.         ans.push_back(last_c);
    
23.     } else {
    
24.         ans = minNonSubsequence(s, end - 1, last_c);
    
25.     }
    
26.    
    
27.     dp[end-1][last_c - 'A'] = ans;
    
28.     return ans;
    
29. }
    
30. 
    
31. int main() {
    
32.     string s = "AAABAA";
    
33.     dp = vector<vector<string>> (s.size(), vector<string>(2));
    
34.     string ans = minNonSubsequence(s, s.size(), 'A');
    
35.     cout << ans << endl;
    
36.     string ans1 = minNonSubsequence(s, s.size(), 'B');
    
37.     cout << ans1 << endl;
    
38.    
    
39.     return 0;
    
40. }

复制代码

spirit_room 发表于 2020/02/14 23:29:07
题目要求是subsequence

长度确定后找subsequence是O（n）

第一题follow up greedy O(n)

第一题followup

1. public String mnse(String s) {
   
2.     StringBuilder res = new StringBuilder();
   
3.     char last = '#';
   
4.     for (int i = -1; i < s.length(); i++) {
   
5.         char cur = i >= 0 ? s.charAt(i) : '#';
   
6.         char next = i < s.length() - 1 ? (s.charAt(i + 1) == 'A' ? 'B' : 'A') : 'A';
   
7.         if (cur == last) {
   
8.             res.append(next);
   
9.             last = next;
   
10.         }
    
11.     }
    
12. 
    
13.     return res.toString();
    
14. }

复制代码

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

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