求问amazon OA2 C++相关问题

1. 是不是最长回文子串那题给的是char* 而不是

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

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

有其他需要注意的地方吗，谢谢！

请问楼主：
int m = strlen(s);
bool dp[m][m];
那个编译器。。。这样定义数组可以吗？

yangmyfly 发表于 2016-10-8 12:13
想问下能把char* 转成string做 再转回去， 用c_str 或者 data()? 楼主是直接用c的那些函数做的，还是怎样？

1. char* findLP(char* s){
   
2.         int len = strlen(s);
   
3.         vector<int> axis(len,0);
   
4.         int rightMostPivot = 0;
   
5.         int curRightMost = 0;
   
6.         for(int i=0;i<len;i++){
   
7.             axis[i] = i<curRightMost ? std::min(curRightMost-i,axis[2*rightMostPivot-i]) : 0;
   
8.             while(i-axis[i]-1>=0 && i+axis[i]+1<len && s[i-axis[i]-1] == s[i+axis[i] + 1]){
   
9.                 axis[i]++;
   
10.             }
    
11.             if(i+axis[i]>curRightMost){
    
12.                 curRightMost = i+axis[i];
    
13.                 rightMostPivot = i;
    
14.             }
    
15.         }
    
16.         int maxPivot = 0;
    
17.         for(int i=0 ; i<len; i++) maxPivot = axis[i]>axis[maxPivot]?i:maxPivot;
    
18.         char* ret = new char[axis[maxPivot]+1];
    
19.         for(int i = maxPivot-axis[maxPivot]+1, j=0;i<maxPivot+axis[maxPivot];i+=2,j++){
    
20.             ret[j] = s[i];
    
21.         }
    
22.         ret[axis[maxPivot]] = '\0';
    
23.         return ret;
    
24.     }
    
25.    
    
26.     char* longestPalindrome(char* s) {
    
27.         int len = strlen(s);
    
28.         char* transformStr = new char[2*len+2];
    
29.         transformStr[0] = '#';
    
30.         transformStr[2*len+1] = '\0';
    
31.         for(int i=0; i<len; i++){
    
32.             transformStr[2*i+1] = s[i];
    
33.             transformStr[2*i+2] = '#';
    
34.         }
    
35.         return findLP(transformStr);
    
36.     }
    

复制代码

yangmyfly 发表于 2016-10-9 03:07
谢楼主， 楼主用O(n)的方法非常好啊。 目前有消息吗？ 还是想问下能不能使用string呢，相对更习惯用strin ...

这个问题我突然想到我可能理解错了 我以为你问我理论上能不能这么做 但你应该是问的amazon的平台给不给用string 这个我还真不确定了。。。
string应该是C++98的东西，但不知道amazon会不会用别的方法禁用掉。。。。

可以用 set和priority queue，昨天看帖子上说的，楼主什么时候做啊？ 我约的10.2做。

knight951753 发表于 2016-9-30 01:44
可以用 set和priority queue，昨天看帖子上说的，楼主什么时候做啊？ 我约的10.2做。

谢谢， 在你前面一天~~

unordered_map 不可以 但是map可以

楼主做了没有，遇到哪些题可以说一下不哇，跪谢跪谢！

knight951753 发表于 2016-10-2 03:05
楼主做了没有，遇到哪些题可以说一下不哇，跪谢跪谢！

刚做完，longest palindrome substring+k nearest point, copy random list

Thanks A lot!

knight951753 发表于 2016-10-2 13:03
Thanks A lot!

同学你有消息了吗...

没有呢，我抽到window sum, rectangle, 5 highest score, 估计最多也是个onsite , 你有么？

想问下能把char* 转成string做 再转回去， 用c_str 或者 data()? 楼主是直接用c的那些函数做的，还是怎样？