一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2043|回复: 16
收起左侧

9月18日godaddyOA

[复制链接] |试试Instant~ |关注本帖
走一走看一看 发表于 2016-9-19 21:08:52 | 显示全部楼层 |阅读模式

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

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

x
昨天做的oa, 给我的链接说1个小时,我猜是两道题,结果打开是1个半小时,3道题。
1. Delete Node greater than X(LinkedList)
2. Subsequence, 可以参考subsets题,只不过由数字变为字符,而且不要空集,最后一个test 跑不过。。今天看到帖子说要删去重复。。但是我为什么觉得不会有重复呢。。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3. rearrangeWord: return next Alphabetically larger string obtained by rearrange the letters of the string, 要是没有输出“no answer”
   eg: pp no answer; hefg hegf


评分

2

查看全部评分

ericlee27 发表于 2016-10-2 01:45:00 | 显示全部楼层
freetalk 发表于 2016-9-25 01:47 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Rearrange word这题该怎么做呢。

Leetcode Next permutation, 双指针,如果头指针走到了-1 说明没有更大的了 返回no answer
回复 支持 1 反对 0

使用道具 举报

silence_shadow 发表于 2016-9-19 22:24:08 | 显示全部楼层
2是不是set不能有重复比如A,B和B,A;而sequence可以?
回复 支持 反对

使用道具 举报

JeremyLi 发表于 2016-9-20 10:11:13 | 显示全部楼层
请问楼主是海投的还是内推的?
回复 支持 反对

使用道具 举报

 楼主| 走一走看一看 发表于 2016-9-20 10:11:49 | 显示全部楼层
JeremyLi 发表于 2016-9-20 10:11
请问楼主是海投的还是内推的?

海投。。。。。。。。。
回复 支持 反对

使用道具 举报

 楼主| 走一走看一看 发表于 2016-9-20 10:12:49 | 显示全部楼层
silence_shadow 发表于 2016-9-19 22:24. From 1point 3acres bbs
2是不是set不能有重复比如A,B和B,A;而sequence可以?

有一贴子是说这道题要删去重复的值,在最后。我没明白的是input中每一个字母都是唯一的,怎么会有重复的值呢?
回复 支持 反对

使用道具 举报

freetalk 发表于 2016-9-25 01:47:12 | 显示全部楼层
Rearrange word这题该怎么做呢。
回复 支持 反对

使用道具 举报

 楼主| 走一走看一看 发表于 2016-9-26 09:24:50 | 显示全部楼层
freetalk 发表于 2016-9-25 01:47
Rearrange word这题该怎么做呢。
-google 1point3acres
我的思路是双指针,但是考虑的不够完全,虽然通过了testcase,我自己定义的case我的思路无法通过。
回复 支持 反对

使用道具 举报

 楼主| 走一走看一看 发表于 2016-9-26 09:36:54 | 显示全部楼层
freetalk 发表于 2016-9-25 01:47
Rearrange word这题该怎么做呢。

godaddy.png
回复 支持 反对

使用道具 举报

mayuki 发表于 2016-9-26 10:12:11 | 显示全部楼层
这个第三题应该是next permutation的变种吧,只是把数字换成字符
回复 支持 反对

使用道具 举报

oily 发表于 2016-9-26 11:05:17 | 显示全部楼层
楼主有电面了吗
回复 支持 反对

使用道具 举报

 楼主| 走一走看一看 发表于 2016-9-26 21:40:51 | 显示全部楼层
oily 发表于 2016-9-26 11:05
楼主有电面了吗
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
木有,估计默剧了。。。。。
回复 支持 反对

使用道具 举报

火火火bit 发表于 2016-10-1 06:52:58 | 显示全部楼层
第二题确实是去重就全过了。。
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-10-2 01:44:05 | 显示全部楼层
第二题重复可能这样的 给ABC 输出了(AB BA) AA, BB这样的 或者
回复 支持 反对

使用道具 举报

OO0OO 发表于 2016-10-2 08:30:07 | 显示全部楼层
freetalk 发表于 2016-9-25 01:47 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Rearrange word这题该怎么做呢。

正好刚做next permutation,参照wikipedia
https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order


算法类似这样,就用数字举例吧:

1,2,5,4,3,0

- 从末尾开始找到decreasing subsequence,这样数字被分成了两部分 (1,2) 和(5,4,3,0),因为(5,4,3,0)的decreasing的,不能通过变化它来找到下一个更大的. visit 1point3acres.com for more.
- 从末尾开始找到比2大的数字,也就是3,交换2,3 数字变成 1,3,5,4,2,0, 这一步因为下一个permutation肯定是(1,3,x,x,x,x)这个交换必定发生在两个部分之间,因为如果交换(2,1)会增加更多
- 把后半部分reverse,数字变成1,3,0,2,4,5,前半部分已经增加,后半部分变成可得到最小
就是增加的最少的,也就是next permutation.鏈枃鍘熷垱鑷1point3acres璁哄潧

用字母测试同样成立
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
get √
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs


回复 支持 反对

使用道具 举报

freetalk 发表于 2016-10-8 23:35:44 | 显示全部楼层
谢谢各位大大的解答!
回复 支持 反对

使用道具 举报

swufejun 发表于 2016-10-27 07:12:31 | 显示全部楼层
火火火bit 发表于 2016-10-1 06:52
第二题确实是去重就全过了。。

你说的是在结果里面删除重复的还是剪枝,因为这个string的char不能排序。。。去重就好蛋疼,subsets那个题是可以先排序的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-8 22:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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