一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1175|回复: 5
收起左侧

Coursera跪经 9/25

[复制链接] |试试Instant~ |关注本帖
royyjzhang 发表于 2016-9-26 00:54:33 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Coursera - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
第一题是magic binary string,题目可以在这里看到http://www.1point3acres.com/bbs/thread-202232-1-1.html
根据贪心把1的个数最多的放在靠前的位置,如果1的个数一样多就把长度更长的放在前面,莫名其妙有runtime error
  1. string maxMagicBS(string s) {
  2.         int n = s.length(), i, j, currentone, leftone, rightzero;
  3.         vector<Node> adjs;
  4.         Node now, temp;. From 1point 3acres bbs
  5.         string result;
  6.         if (n == 0) {. 鍥磋鎴戜滑@1point 3 acres
  7.                 return s; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.         }
    . From 1point 3acres bbs
  9.         i = 0;
  10.         currentone = 0;. 1point3acres.com/bbs
  11.         leftone = 0;
  12.         while (i < n) {
  13.                 if (s[i] == '0') {. 鍥磋鎴戜滑@1point 3 acres
  14.                         if (currentone != 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                                 j = i + 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  16.                                 while ((j < n) && (s[j] == '0') && (j - i + 1 <= currentone)) {
  17.                                         j++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.                                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.                                 if (adjs.size() == 0) {
  20.                                         leftone = currentone - j + i;
  21.                                 }
  22.                                 if (currentone != 0) {
  23.                                         now.right = j - 1;
  24.                                         now.left = i - (j - i);
  25.                                         now.numofone = i - now.left;
  26.                                         currentone = 0;. more info on 1point3acres.com
  27.                                         adjs.push_back(now);. From 1point 3acres bbs
  28.                                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.                                 i = j;. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.                         }
  31.                         else {
  32.                                 j = i + 1;
  33.                                 while ((j < n) && (s[j] == '0')) {
  34.                                         j++;. From 1point 3acres bbs
  35.                                 }
  36.                                 if (j == n) {
  37.                                         i = j;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  38.                                 }
  39.                                 else {
  40.                                         if (!adjs.empty()) {
  41.                                                 now = adjs[adjs.size() - 1];
  42.                                                 now.right = i;
  43.                                                 adjs.pop_back();
  44.                                                 while ((!adjs.empty()) && (now.numofone-(now.right-now.left+1) < 0)) {
  45.                                                         temp = adjs[adjs.size() - 1];
  46.                                                         adjs.pop_back();
  47.                                                         now.numofone += temp.numofone;
  48.                                                         now.left = temp.left;
  49.                                                 }
  50.                                                 if ((adjs.empty()) && (now.numofone - (now.right - now.left + 1) < 0)) {
  51.                                                         leftone--;
  52.                                                         now.left--;
  53.                                                         adjs.push_back(now);
  54.                                                 }
  55.                                         }
  56.                                         i++;
  57.                                 }
  58.                         }
  59.                 }
  60.                 else {
  61.                         i++;
  62.                         currentone++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  63.                 }
  64.         }
  65.         rightzero = n - 1 - now.right;
  66.         for (i = 0; i < adjs.size(); i++) {.1point3acres缃
  67.                 for (j = i + 1; j < adjs.size(); j++) {
  68.                         if (adjs[i].numofone < adjs[j].numofone) {
  69.                                 now = adjs[i];
  70.                                 adjs[i] = adjs[j];
  71.                                 adjs[j] = now;
  72.                         }
  73.                         else if ((adjs[i].numofone == adjs[j].numofone) && (adjs[i].left - adjs[i].right + 1 < adjs[j].left - adjs[j].right + 1)) {
  74.                                 now = adjs[i];
  75.                                 adjs[i] = adjs[j];
  76.                                 adjs[j] = now;
  77.                         }
  78.                 }. from: 1point3acres.com/bbs
  79.         }
  80.         if (leftone != 0) {
  81.                 result += '1'*leftone;
  82.         }
  83.         for (i = 0; i < adjs.size(); i++) {
  84.                 result += s.substr(adjs[i].left, adjs[i].right - adjs[i].left + 1);
  85.         }. visit 1point3acres.com for more.
  86.         if (rightzero != 0) {
  87.                 result += '0'*rightzero;
  88.         }
  89.         int check = 0;
  90.         for (i = 0; i<n; i++) {
  91.                 check = check + (result[i] - s[i])*i;
  92.         }
  93.         return result;
  94. }
复制代码
第二题是number of distinct sub-palindrome
用dp+计算在该位置回文字符串的半径,这样对于一个找到的回文字符串,算了左半边就不用算右半边了。
每个位置根据左半边的情况有以下四种情况的右半边
1. 左半边的位置不是回文字符串,那右半边对称位置也不是
2. 左半边的回文字符串被包含在整个回文字符串中,右半边同样被包含
3. 左半边的回文字符串半径大于在整个回文字符串半径,右半边应当将长度减小
4. 右半边字符串的半径可能更大,该情况会在之后计算中解决

然后用set检测是否有重复。

这个能过
  1. int para(string str) {
  2.         set<string> check;
  3.         int l = str.length(), result = 0;
  4.         if (l == 0) {
  5.                 return 0;
  6.         }
  7.         if (l == 1) {
  8.                 return 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.         vector<vector<int>> dp(2, vector<int>(l+1, 0));
  11.         str = "@" + str + "#";
  12.         for (int j = 0; j<=1; j++) {
  13.                 int r = 0;.1point3acres缃
  14.                 dp[j][0] = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.                 int i = 1;. visit 1point3acres.com for more.
  16.                 while (i <= l) {
  17.                         while (str[i - r - 1] == str[i + j + r]) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.                                 r++;
  19.                         dp[j][i] = r;
  20.                         int k = 1;
  21.                         while ((dp[j][i - k] != r - k) && (k<r)) {
  22.                                 dp[j][i + k] = min(dp[j][i - k], r - k);
  23.                                 k++;. visit 1point3acres.com for more.
  24.                         }
  25.                         r = max(r - k, 0);
  26.                         i += k;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  27.                 }
  28.         }
  29.         str = str.substr(1, l);
  30.         check.insert(string(1, str[0]));
  31.         result++;. visit 1point3acres.com for more.
  32.         for (int i = 1; i<l; i++) {
  33.                 for (int j = 0; j <= 1; j++) {. 1point3acres.com/bbs
  34.                         for (int r = dp[j][i]; r>0; r--) {
  35.                                 if (check.find(str.substr(i - r - 1, 2 * r + j)) == check.end()) {
  36.                                         check.insert(str.substr(i - r - 1, 2 * r + j));
  37.                                         result++;
  38.                                 }
  39.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  41.                 if (check.find(string(1, str[i])) == check.end()) {
  42.                         check.insert(string(1, str[i]));
  43.                         result++;
  44.                 }
  45.         }
  46.         return result;
  47. }
复制代码
跪求攒人品

评分

1

查看全部评分

窗外一棵树 发表于 2016-9-26 01:34:00 | 显示全部楼层
楼主这是 OA 还是电面? 现在已经换成面题了吗
回复 支持 反对

使用道具 举报

 楼主| royyjzhang 发表于 2016-9-26 05:48:43 | 显示全部楼层
窗外一棵树 发表于 2016-9-26 01:34
楼主这是 OA 还是电面? 现在已经换成面题了吗

这是60分钟的OA
回复 支持 反对

使用道具 举报

cococecil 发表于 2016-9-26 06:02:24 | 显示全部楼层
貌似第一题可以从后到前O(n)?. 鍥磋鎴戜滑@1point 3 acres
int cnt = 0;. 鍥磋鎴戜滑@1point 3 acres
output = str2number(str);
for(int i=str.length()-1;i>0;--i)
{
    if(str[i]=='1') cnt=std::max(cnt-1,0);
    else cnt+=1;. 1point3acres.com/bbs
    if(cnt==0)
    {
        int aMagicalNumber = str2num(str.substring(i)+str.substring(0,i));
        output = std::max(output,aMagicalNumber);
    }
}
回复 支持 反对

使用道具 举报

cococecil 发表于 2016-9-26 06:42:00 | 显示全部楼层
第二题geekforgeek上说是manacher+Set. visit 1point3acres.com for more.
http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-given-string/
不过从每个位置为中心扩展出去也是O(n^2)吧,没啥区别啊
回复 支持 反对

使用道具 举报

 楼主| royyjzhang 发表于 2016-9-26 07:15:07 | 显示全部楼层
cococecil 发表于 2016-9-26 06:02
貌似第一题可以从后到前O(n)?
int cnt = 0;
output = str2number(str);

这个从后向前的算法不行,可以试试看例子11011000,这是题目提供的标准样例,从你这个算法来看的话只有到str[0]才会发生交换,但这个和题目中只要相邻的magic string就能交换的原则是违背的。这个样例中10,1100两个是可以交换的magic string,输出是11100100
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 05:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表