一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.16-6.22 CareerCup 1.1

  [复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-15 23:18:39 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 wrj5518 于 2014-6-15 23:18 编辑

1.1 Implement an algorithm to determine if a string has all unique characters. Whatif you cannot use additional data structures?

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。



monkerek 发表于 2014-6-16 00:20:43 | 显示全部楼层
【解题思路】
我理解的是题意是不能用hash和bitmap等其他数据结构?
直接对string排序, 逐次比较相邻的字符
【时间复杂度】
O(nlog(n)) -- 取决于排序算法
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/monkerek/f008f983280c2daf755d

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-17 07:16:59 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2014-6-15 23:54:30 | 显示全部楼层
【解题思路】
假设是aci把..256的大小.unicode什么的..太复杂了.
【时间复杂度】
N
【空间复杂度】
N
【gist link】

---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
"" 空String 是true把..也是unique..


https://gist.github.com/gaoyike/bedec0889b830a813902


评分

2

查看全部评分

回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-16 00:18:42 | 显示全部楼层
【解题思路】假设string里所有的字符都是ascii,以各个字符的ascii为索引查询一个大小为128的boolean数组就好。
【时间复杂度】O(n)
【空间复杂度】O(1)+O(n)
【gist link】https://gist.github.com/anonymous/071cbca01a61d0fb3e9a
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
null 返回false.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

immortaliqi 发表于 2014-6-16 00:36:25 | 显示全部楼层
本帖最后由 immortaliqi 于 2014-6-16 23:35 编辑

【解题思路】
  • 用一个数组储存 每次储存新字符的时候检查数组 如果存在直接return
  • 如果字符库只限于26个英文,那么用下标0-25代表a-z即可 存在为1 不存在为0 有1则return
  • 依旧是数组,如果空间无限制,可以将2扩展为所有asc编码(忘了asc编码总共有几个 255个还是多少?都还给c语言老师了)
  • 如果不使用数据结构,暂时想不出来,有个思路是继续利用asc码,然后维护一个int来加减或其他运算,最后通过动态加减的结果判断是否有重复的。
【时间复杂度】
  • 最坏 N^2(忘了怎么算了 明天一定学会)
  • N
  • N
  • 待解决
【空间复杂度】
  • N
  • 26
  • 255/?
  • 待解决
【gist link】
https://gist.github.com/immortaliqi/c50de4e2df35e7b27f69

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

habina 发表于 2014-6-16 04:24:19 | 显示全部楼层
【解题思路】
  Create a boolean array with all initial value True
  Read one character at a time, and set the corresponding array index of ASCII value to be False,
  Return True if the string has been fully iterated, otherwise return False
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/habina/aeb70fa03ad97d370c5a

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

atlas1017 发表于 2014-6-16 05:15:10 | 显示全部楼层
本帖最后由 atlas1017 于 2014-6-16 05:29 编辑

【解题思路】
如果不用其它data structure可以对其中所有的char 两两之间比较 前提是有至少两个char的话
【时间复杂度】
O(N^2)  
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/atlas1017/5d38b4919be4b3a96109

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

weilichen 发表于 2014-6-16 05:39:18 | 显示全部楼层
【解题思路】
参考了下大牛们的思路。把字符转换为ASCII。创建bool 数组检验选中字符是否已经在bool数组里存在。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/anonymous/efaa69ffe8d5af283ff1

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-6-16 09:40:20 | 显示全部楼层
本帖最后由 qianhuang 于 2014-6-16 10:04 编辑

【解题思路】
1. 如果字符是ASCII码,用256大小的bool数组或者bitset去存该字符是否出现过。
2. 如果空间复杂度限制在O(1),暴力搜索。
3. 如果string可以被毁坏的话,可以sort in place,然后对比相邻元素。
【时间复杂度】
1. O(n)
2. O(n^2)
3. O(nlogn)
【空间复杂度】
1. O(字符集大小)
2. O(1)
3. O(1)
【gist link】
https://gist.github.com/qianhuang/970914734385592bc39a

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-16 10:56:54 | 显示全部楼层
【解题思路】
Hash,假设字符集是ASCII的话就用一个int count[256]数出现的次数,如果某个字符出现次数大于1,就不unqiue。
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/anonymous/6b88e0640729b97e460b

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-16 12:12:32 | 显示全部楼层
【解题思路】 用boolean[] 模拟Hashtable,但只能对ASCII有效,unicode可以使用Hashtable
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】普通版:https://gist.github.com/chouclee/5880c7fdf95bf593c395
Hashtable版 https://gist.github.com/chouclee/837102ddb0273f428cb5

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jason51122 发表于 2014-6-16 12:34:50 | 显示全部楼层
本帖最后由 jason51122 于 2014-6-16 12:43 编辑

【解题思路】Assume the input is an ASCII string. Create a boolean array to keep record all states. Traverse the string and return false if any char has seen before. Return true after the traversal.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/cad80336bdbbe7ecd02d

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-16 13:37:34 | 显示全部楼层
本帖最后由 jing0328 于 2014-6-16 14:04 编辑

【解题思路】create a boolean array of length 256 and travese the string to set true/false in the correspoding spot (according to ASCII table), if some spot has already been set to true, then duplicate char exists.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/dfd6a05aa122d53afb05
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】my solution includes a user-interaction part where user can enter the input string and program outputs the result (true/false)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-16 14:31:03 | 显示全部楼层
【解题思路】假设是ascii字符 共256个  用长度为256的Boolean数组表示某字符是否出现过
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】  https://gist.github.com/jyhjuzi/1f526165a8a54148bde4

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-16 14:42:56 | 显示全部楼层
【解题思路】Assume the input is an ASCII string(256). Create a boolean array to keep record all states. Traverse the string and return false if any char has seen before. Return true after the traversal.楼上的和我想的差不多,这好像也是标准常用方法。初刷题。多观摩大家的方案吧
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/hilda8519/69fcc6db1db7efb8e107
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-16 15:53:08 | 显示全部楼层
immortaliqi 发表于 2014-6-16 00:36
【解题思路】
  • 用一个数组储存 每次储存新字符的时候检查数组 如果存在直接return
  • 如果字符库只限 ...

  • 木有代码,还真是拖延症啊。。。

    评分

    1

    查看全部评分

    回复 支持 反对

    使用道具 举报

    兰橘清檬 发表于 2014-6-16 16:17:57 | 显示全部楼层
    【解题思路】设字符集为ascii(大小256),一个大小为256的 boolean 数组,出现一次后字符相应位置为 true,否则为 false
    【时间复杂度】O(n)
    【空间复杂度】O(n)
    【gist link】https://gist.github.com/JoyceeLee/8118612ec2b571730f30
    ---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
    【test case】

    评分

    1

    查看全部评分

    回复 支持 反对

    使用道具 举报

    MrAcc 发表于 2014-6-16 16:25:59 | 显示全部楼层
    【解题思路】
    可以使用其他数据结构的话,采用Set,相同字符的话覆盖,最后比较总数
    不可使用其他数据结构的话,采用一个大小为256的数组,统计每个字符的出现次数
    【时间复杂度】
      O(n)
    【空间复杂度】
      O(1)
    【gist link】
    https://gist.github.com/MrCQ/6ec6ac7c5b7992eef6a5

    评分

    1

    查看全部评分

    回复 支持 反对

    使用道具 举报

    bitcpf 发表于 2014-6-16 23:11:12 | 显示全部楼层
    本帖最后由 bitcpf 于 2014-6-16 09:13 编辑

    【解题思路】
    Assume all characters are ASCII, then create a bool array with 256 member all false
    Traverse all characters in the String
    If the ASCII value is not true in the array, mark the ASCII array as ture
    Else return false
    【时间复杂度】
      O(n)
    【空间复杂度】  boolen array is a constant 256
      O(1)
    【gist link】
    https://gist.github.com/bitcpf/404d4d71e6c40a92fc2f

    评分

    1

    查看全部评分

    回复 支持 反对

    使用道具 举报

    aloncgo 发表于 2014-6-16 23:39:27 | 显示全部楼层
    本帖最后由 aloncgo 于 2014-6-17 07:39 编辑

    【解题思路】好像和前面好几个人都一样,开一个256的bool数组每个代表对应的ascii是否出现过,出现一样的就返回false,第一次写java,真是蠢哭了
    【时间复杂度】不会算啊,我现在学好吗
    【空间复杂度】。。。。
    【gist link】https://gist.github.com/weazord/9335e136f52a5850f1ef

    update
    【时间复杂度】O(n)
    【空间复杂度】O(1)
    应该没错吧。。。再看会书

    评分

    1

    查看全部评分

    回复 支持 反对

    使用道具 举报

    本版积分规则

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

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

    关闭

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

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

    custom counter

    GMT+8, 2016-12-3 04:25

    Powered by Discuz! X3

    © 2001-2013 Comsenz Inc. Design By HUXTeam

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