10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 997|回复: 9
收起左侧

[算法题] 有趣的OA题....Indeed

[复制链接] |试试Instant~ |关注本帖
newgod2500 发表于 2017-7-14 11:32:33 | 显示全部楼层 |阅读模式

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

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

x

                               
登录/注册后可看大图

                               
登录/注册后可看大图


最后做出来有一些test case超时过不了,请问有更快的法子呢?
q4.JPG
捕获3.JPG
gegeyongfu 发表于 2017-7-14 11:55:21 | 显示全部楼层
楼主是fresh grad 吗?
回复 支持 反对

使用道具 举报

 楼主| newgod2500 发表于 2017-7-14 12:13:24 | 显示全部楼层
gegeyongfu 发表于 2017-7-14 11:55
楼主是fresh grad 吗?

不是。紫薯紫薯紫薯
回复 支持 反对

使用道具 举报

fateacher 发表于 2017-7-14 14:08:49 | 显示全部楼层
不知道楼主是什么法子
不过最快也是O(N)的时间复杂度了吧
回复 支持 反对

使用道具 举报

 楼主| newgod2500 发表于 2017-7-18 07:38:43 | 显示全部楼层
fateacher 发表于 2017-7-14 14:08
不知道楼主是什么法子
不过最快也是O(N)的时间复杂度了吧

想不出O(N)的思路,请问一下能大概说说思路吗?谢谢
回复 支持 反对

使用道具 举报

magicsets 发表于 2017-7-18 08:45:45 | 显示全部楼层
就是用一个数组记录每个字符到目前为止出现了多少次吧,其实是比较常见的一类题目,见过一次就不会忘记了。
贴个C++版本的供参考:

  1. #include <iostream>
  2. #include <string>
  3. #include <vector>

  4. std::string Transform(const std::string &s) {
  5.   std::vector<char> counts(26);
  6.   for (int i = 0; i < 26; ++i) {
  7.     counts[i] = i - 1;
  8.   }
  9.   std::string r;
  10.   for (char c : s) {
  11.     char &cnt = counts[c - 'a'];
  12.     cnt = (cnt + 1) % 26;
  13.     r.push_back(cnt + 'a');
  14.   }
  15.   return r;
  16. }

  17. int main(int argc, char *argv[]) {
  18.   std::cout << Transform("yzz") << "\n";
  19.   std::cout << Transform("apapap") << "\n";

  20.   return 0;
  21. }
复制代码
回复 支持 反对

使用道具 举报

vegito2002 发表于 2017-7-18 12:10:43 | 显示全部楼层
加速的核心点在于每个i的k的计算, 这个计算如果遍历0..i - 1肯定最后就是O(N^2)复杂度. 可以用类似DP的memoization来加速,  二维表格, 一个坐标是26个字母, 一个坐标是长度, 每个entry表示number of occrrence of this character up till this position/length.

因为这个表格在计算每一个entry的时候,其实你只需要上一行(上一个length)的结果, 所以最后实际上不需要维护整个26 * N的表格, 只需要维护一行, 也就是26个变量(作为一个数组)就行, 每一个i更新一次.

至于cyclic increment这个应该直接做就行了.
回复 支持 反对

使用道具 举报

头像被屏蔽
carlvane110 发表于 2017-8-2 03:34:56 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

maydaycn 发表于 2017-9-19 00:51:02 | 显示全部楼层
请问楼主 您这个是oa几呢?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-22 16:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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