一亩三分地论坛

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

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

google OA 参考答案

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

2016(7-9月) 码农类 硕士 全职@Google - 校园招聘会 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
题目链接: http://www.1point3acres.com/bbs/thread-199304-1-1.html
我的答案:
1.
  1. #include<iostream>. From 1point 3acres bbs
  2. #include<vector>
  3. #include<limits.h>. 1point3acres.com/bbs
  4. #include<string>
  5. using namespace std;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  6. int solution(int X)
  7. {
  8.     if(X == 0) return 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.     string str = to_string(X), strAns = string(str.size()-1, '9');
  10.     int len = str.size();
  11.     for(int i = 0; i < len-1; i++)
  12.     {
  13.         string tem = str.substr(0, i) + (str[i]>str[i+1]?str[i]:str[i+1]) + str.substr(i+2);
  14.         if(strAns > tem) strAns = tem; . more info on 1point3acres.com
  15.     }
  16.     return stoi(strAns);
  17. }. from: 1point3acres.com/bbs

  18. int main()
  19. {
  20.     cout << solution(233614) << endl;. 鍥磋鎴戜滑@1point 3 acres
  21.     return 0;
  22. }
复制代码
2.
  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;

  4. int Solution(string &word) {
  5.     word+= '\n';
  6.     int len = word.size(), ans = 0, spaceCnt = 0, curPathLen =0, dotFlag = 0;
  7.     stack<pair<string, int> > st;
  8.     string curDir, extension;
  9.     for(int i = 0; i < len; i++)
  10.     {. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.         if(word[i]!='\n'). 鍥磋鎴戜滑@1point 3 acres
  12.         {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.             if(word[i]!=' ') curDir += word[i];
  14.             if(dotFlag) extension += word[i];
  15.             if(word[i]==' ') spaceCnt++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.             if(word[i]=='.') dotFlag = 1;
  17.             continue;
  18.         }  
  19.         while(!st.empty() && spaceCnt <= st.top().second)
  20.         {
  21.             curPathLen -= st.top().first.size();
  22.             st.pop();
  23.         }
  24.         if(dotFlag).鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.         {
  26.             if(extension == "jpeg" || extension == "gif" || extension == "png")
  27.                 ans = (ans + curPathLen + curDir.size() + 1) % 1000000007;
  28.         }. more info on 1point3acres.com
  29.         else
  30.         {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  31.             st.push(make_pair("/"+ curDir, spaceCnt));
  32.             curPathLen += curDir.size() + 1;
  33.         }.1point3acres缃
  34.         extension = "", dotFlag = 0, spaceCnt = 0, curDir = "";
  35.     }
  36.     return ans;
  37. }. 1point3acres.com/bbs
  38. . visit 1point3acres.com for more.
  39. int main()
    . 鍥磋鎴戜滑@1point 3 acres
  40. {
  41.     string str =
  42. string("dir1\n dir11\n dir12\n  picture.jpeg\n  dir121\n   file1.txt\n   dir122\ndir2\n file2.gif\n");
  43.     cout << Solution(str) << endl;
  44. }
复制代码
找工作不易, 大家互相帮忙吧, 还在准备面google, 祝我好运!

鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

2

查看全部评分

lvvvvv 发表于 2016-8-24 23:02:01 | 显示全部楼层
mren 发表于 2016-8-24 04:45. Waral 鍗氬鏈夋洿澶氭枃绔,
那还能怎么做, 时间复杂度O(n^2)我觉得降不下来的

以前好像讨论过 , 找第一个 patten  a1>a2>a3,  去掉 a2,  没有的话就最后两个去掉小的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

2 3 3 6 1 4,   最后两个去掉 1
9 8 7 1 2 3, 去掉 8

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

lvvvvv 发表于 2016-8-24 04:09:46 | 显示全部楼层
第一题你就用暴力解 ?
回复 支持 反对

使用道具 举报

 楼主| mren 发表于 2016-8-24 04:45:01 | 显示全部楼层
lvvvvv 发表于 2016-8-24 04:09
第一题你就用暴力解 ?

那还能怎么做, 时间复杂度O(n^2)我觉得降不下来的
回复 支持 反对

使用道具 举报

xingrunzhi 发表于 2016-8-25 06:01:16 | 显示全部楼层
mren 发表于 2016-8-24 04:45
那还能怎么做, 时间复杂度O(n^2)我觉得降不下来的
. visit 1point3acres.com for more.
为什么是O(n^2), 这不是O(n)吗?一次遍历就出结果了啊
回复 支持 反对

使用道具 举报

tianyicai 发表于 2016-8-25 13:56:08 | 显示全部楼层
这道题竟然有小区别。。
回复 支持 反对

使用道具 举报

肥娇娇 发表于 2016-9-9 08:47:11 | 显示全部楼层
lvvvvv 发表于 2016-8-24 23:02
以前好像讨论过 , 找第一个 patten  a1>a2>a3,  去掉 a2,  没有的话就最后两个去掉小的
. Waral 鍗氬鏈夋洿澶氭枃绔,
2 3 3 6 1 4 ...

果然是这样。请问,是怎么想到的啊,
直接暴力解行不行呢?谢谢
回复 支持 反对

使用道具 举报

Stonre 发表于 2016-9-15 09:55:21 | 显示全部楼层
有个疑问就是,需不需要考虑文件名以空格开头的情况,我看到leetcode上边有类似的题目考虑了这种情况,但是不一样的是leetcode上是以\t而不是空格来缩进的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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