925 Zenefits 电面

上周五面的，直接上题


arr = [1,2, 3, 1, 2]
Prefixes of the array: [1], [1, 2], [1,2, 3], [1,2,3,1

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

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

?

input: arr
output: int

感觉写的比较慢，估计还有一题来不及写，这周收到邮件已跪

ymne06 发表于 2015-10-14 19:09
楼主能否解释下这道题题意呢？我对题中的prefix [1,2, 3, 1] == {1, 2, 3} suffix [1, 2, 3, 1, 2] == {1,2 ...

[1,2,3,1]=={1,2,3} 指的是数组转换成集合

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

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

和POJ 2752类似

题意是给你一字符串，找你找到一个子串。使得子串即是原串的前辍，又是原串的后辍。

这和我们这道题就是一模一样了。

代码如下：

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <cstring>
   
4. #include <string>
   
5. #include <iostream>
   
6. #include <algorithm>
   
7. #include <vector>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define print(x) cout << x << endl
    
12. #define input(x) cin >> x
    
13. 
    
14. void get_next(const string& str, vector<int>& next) {
    
15.     int n = str.size();
    
16.     next = vector<int>(n + 1, -1);
    
17. 
    
18.     for (int pre = -1, suf = 0; pre < n && suf < n; /* pass */) {
    
19.         if (pre == -1 || str[pre] == str[suf]) {
    
20.             pre++;
    
21.             suf++;
    
22.             next[suf] = pre;
    
23.         } else {
    
24.             pre = next[pre];
    
25.         }
    
26.     }
    
27. }
    
28. 
    
29. int main() {
    
30.     string name;
    
31.     vector<int> next;
    
32. 
    
33.     while (input(name)) {
    
34.         get_next(name, next);
    
35.         int n = name.size();
    
36.         int u = next[n];
    
37.         vector<int> ans;
    
38.         ans.push_back(n);
    
39.         while (u) {
    
40.             ans.push_back(u);
    
41.             u = next[u];
    
42.         }
    
43.         reverse(ans.begin(), ans.end());
    
44.         for (int i = 0; i < ans.size(); i++) {
    
45.             if (i) {
    
46.                 printf(" ");
    
47.             }
    
48.             printf("%d", ans[i]);
    
49.         }
    
50.         puts("");
    
51.     }
    
52.     return 0;
    
53. }
    

复制代码

请问楼主用的什么方法解这道题呀～～

请问楼主是怎么做的呢，希望交流下~

我觉得这道题目可以这么做： 时间复杂度O(n) 空间复杂度 O(n)
左右同时扫描，比较prefix和suffix的集合是否相等，如果相等求出相等的数量res += m*n
比如 11211 左边集合为1的数量为2 右边也是2 那么这里肯定就有4种 然后包含2的时候 左边有三种 右边也是三种9种 答案就是4+9=13

不知道是不是这样

楼主能否解释下这道题题意呢？我对题中的prefix [1,2, 3, 1] == {1, 2, 3} suffix [1, 2, 3, 1, 2] == {1,2,3}  [1, 2, 3, 1] == [1, 2, 3, 1, 2]不太了解，下周电面zenefit，楼主好人帮帮忙

lcysjw 发表于 2015-10-14 15:16
请问楼主是怎么做的呢，希望交流下~

我觉得这道题目可以这么做： 时间复杂度O(n) 空间复杂度 O(n)

如何efficient的比较两个集合是否相等？

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

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

lengyu 发表于 2015-10-12 04:38
请问楼主用的什么方法解这道题呀～～

当时好像用的hashset，具体怎么样有点忘了，好像不是最优解，面试官说用hashmap

lcysjw 发表于 2015-10-14 15:16
请问楼主是怎么做的呢，希望交流下~

我觉得这道题目可以这么做： 时间复杂度O(n) 空间复杂度 O(n)

"左边集合为1的数量为2" 这里还是要用hashmap做记录吧?

darkwowgamer 发表于 2015-10-15 08:52
"左边集合为1的数量为2" 这里还是要用hashmap做记录吧?

不需要 直接就可以用一个集合来做