一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 6457|回复: 10
收起左侧

google OA 参考答案

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

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

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

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

x
题目链接: http://www.1point3acres.com/bbs/thread-199304-1-1.html
我的答案:
1.
  1. #include<iostream>
  2. #include<vector>
  3. #include<limits.h>
  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();. 鍥磋鎴戜滑@1point 3 acres
  11.     for(int i = 0; i < len-1; i++). more info on 1point3acres.com
  12.     {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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;
  15.     }
  16.     return stoi(strAns);. 1point3acres.com/bbs
  17. }

  18. int main(). from: 1point3acres.com/bbs
  19. {
  20.     cout << solution(233614) << endl;
  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.     {
  11.         if(word[i]!='\n')
  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.         {. Waral 鍗氬鏈夋洿澶氭枃绔,
  21.             curPathLen -= st.top().first.size();.1point3acres缃
  22.             st.pop();
  23.         }
  24.         if(dotFlag)
  25.         {
  26.             if(extension == "jpeg" || extension == "gif" || extension == "png").1point3acres缃
  27.                 ans = (ans + curPathLen + curDir.size() + 1) % 1000000007;
  28.         }
  29.         else
  30.         {
  31.             st.push(make_pair("/"+ curDir, spaceCnt));
  32.             curPathLen += curDir.size() + 1;
  33.         }
  34.         extension = "", dotFlag = 0, spaceCnt = 0, curDir = "";
  35.     }
  36.     return ans;
  37. }

  38. int main()
  39. {
  40.     string str =
  41. string("dir1\n dir11\n dir12\n  picture.jpeg\n  dir121\n   file1.txt\n   dir122\ndir2\n file2.gif\n");
  42.     cout << Solution(str) << endl;
  43. }
复制代码
找工作不易, 大家互相帮忙吧, 还在准备面google, 祝我好运!
.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

2

查看全部评分

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

. more info on 1point3acres.com以前好像讨论过 , 找第一个 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)我觉得降不下来的

为什么是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,  没有的话就最后两个去掉小的

2 3 3 6 1 4 ...

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

使用道具 举报

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

使用道具 举报

brave2 发表于 2017-1-10 07:03:33 | 显示全部楼层
Stonre 发表于 2016-9-15 09:55. 1point3acres.com/bbs
有个疑问就是,需不需要考虑文件名以空格开头的情况,我看到leetcode上边有类似的题目考虑了这种情况,但是 ...

Assume that:
        N is an integer within the range[1..3,000,000];
        string S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9), spaces, dots (.) and end-of-line characters;
        string S is a correct listing of a file system contents.
回复 支持 反对

使用道具 举报

杜小渚 发表于 2017-1-29 06:03:21 | 显示全部楼层
请问我们是可以include java的库的吧,OA的时候
回复 支持 反对

使用道具 举报

chhua21815 发表于 2017-10-2 08:32:26 | 显示全部楼层
谢谢楼主了,多多练习了!!!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-17 10:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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