近期论坛无法登录的解决方案


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 5694|回复: 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>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2. #include<vector>
  3. #include<limits.h>
  4. #include<string>. 1point 3acres 璁哄潧
  5. using namespace std;
  6. . Waral 鍗氬鏈夋洿澶氭枃绔,
  7. int solution(int X). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8. {
  9.     if(X == 0) return 0;
  10.     string str = to_string(X), strAns = string(str.size()-1, '9');
  11.     int len = str.size();
  12.     for(int i = 0; i < len-1; i++)
  13.     {
  14.         string tem = str.substr(0, i) + (str[i]>str[i+1]?str[i]:str[i+1]) + str.substr(i+2);
  15.         if(strAns > tem) strAns = tem;
  16.     }
  17.     return stoi(strAns);
  18. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  19. int main(). From 1point 3acres bbs
  20. {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.     cout << solution(233614) << endl;
  22.     return 0;
  23. }
复制代码
2.
  1. #include<iostream>. from: 1point3acres.com/bbs
  2. #include<stack>
  3. using namespace std;

  4. int Solution(string &word) {
  5.     word+= '\n';.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.     int len = word.size(), ans = 0, spaceCnt = 0, curPathLen =0, dotFlag = 0;
  7.     stack<pair<string, int> > st;. From 1point 3acres bbs
  8.     string curDir, extension;
  9.     for(int i = 0; i < len; i++). visit 1point3acres.com for more.
  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.         {
  21.             curPathLen -= st.top().first.size();. 1point3acres.com/bbs
  22.             st.pop();
  23.         }. 鍥磋鎴戜滑@1point 3 acres
  24.         if(dotFlag)
  25.         {
  26.             if(extension == "jpeg" || extension == "gif" || extension == "png"). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.                 ans = (ans + curPathLen + curDir.size() + 1) % 1000000007;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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, 祝我好运!

. 1point3acres.com/bbs

评分

2

查看全部评分

lvvvvv 发表于 2016-8-24 23:02:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
mren 发表于 2016-8-24 04:45.鏈枃鍘熷垱鑷1point3acres璁哄潧
那还能怎么做, 时间复杂度O(n^2)我觉得降不下来的

以前好像讨论过 , 找第一个 patten  a1>a2>a3,  去掉 a2,  没有的话就最后两个去掉小的. from: 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
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. visit 1point3acres.com for more.
以前好像讨论过 , 找第一个 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
有个疑问就是,需不需要考虑文件名以空格开头的情况,我看到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的时候
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-30 00:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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