📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: newgod2500
跳转到指定楼层
上一主题 下一主题
收起左侧

有趣的OA题....Indeed

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x


最后做出来有一些test case超时过不了,请问有更快的法子呢?
更多图片 小图 大图
组图打开中,请稍候......

上一篇:Hard的题什么样级别的公司会要求啊?
下一篇:大佬们,我想问下用python刷leetcode会有什么结果。。。
🔗
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)的思路,请问一下能大概说说思路吗?谢谢
回复

使用道具 举报

🔗
marimo 2017-7-18 07:59:42 | 只看该作者
本楼:
全局:
同求思路
回复

使用道具 举报

🔗
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这个应该直接做就行了.
回复

使用道具 举报

🔗
maydaycn 2017-9-19 00:51:02 | 只看该作者
全局:
请问楼主 您这个是oa几呢?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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