May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 5254|回复: 9
收起左侧

google OA 参考答案

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

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

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

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

x
题目链接: http://www.1point3acres.com/bbs/thread-199304-1-1.html
我的答案:
1.
  1. #include<iostream>. from: 1point3acres.com/bbs
  2. #include<vector>
  3. #include<limits.h>
  4. #include<string>-google 1point3acres
  5. using namespace std;

  6. int solution(int X)
  7. {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     if(X == 0) return 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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++). from: 1point3acres.com/bbs
  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;
  15.     }
  16.     return stoi(strAns);-google 1point3acres
  17. }

  18. int main()
  19. {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.     cout << solution(233614) << endl;
  21.     return 0;
  22. }
复制代码
2.
  1. #include<iostream>. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         }  . from: 1point3acres.com/bbs
  19.         while(!st.empty() && spaceCnt <= st.top().second)
  20.         {
  21.             curPathLen -= st.top().first.size();
  22.             st.pop();
  23.         }
  24.         if(dotFlag)
  25.         {
  26.             if(extension == "jpeg" || extension == "gif" || extension == "png"). Waral 鍗氬鏈夋洿澶氭枃绔,
  27.                 ans = (ans + curPathLen + curDir.size() + 1) % 1000000007;
  28.         }
  29.         else
  30.         {
  31.             st.push(make_pair("/"+ curDir, spaceCnt));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  32.             curPathLen += curDir.size() + 1;. more info on 1point3acres.com
  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, 祝我好运!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

2

查看全部评分

lvvvvv 发表于 2016-8-24 23:02:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
mren 发表于 2016-8-24 04:45
那还能怎么做, 时间复杂度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 | 显示全部楼层
关注一亩三分地微博:
Warald
第一题你就用暴力解 ?
回复 支持 反对

使用道具 举报

 楼主| 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 ...
. from: 1point3acres.com/bbs
果然是这样。请问,是怎么想到的啊,
.鐣欏璁哄潧-涓浜-涓夊垎鍦直接暴力解行不行呢?谢谢
回复 支持 反对

使用道具 举报

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

使用道具 举报

brave2 发表于 2017-1-10 07:03:33 | 显示全部楼层
Stonre 发表于 2016-9-15 09:55
有个疑问就是,需不需要考虑文件名以空格开头的情况,我看到leetcode上边有类似的题目考虑了这种情况,但是 ...
. From 1point 3acres bbs
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的时候
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-27 03:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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