【第三轮】6.16-6.22 CareerCup 1.1

【解题思路】 用boolean[] 模拟Hashtable，但只能对ASCII有效，unicode可以使用Hashtable
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】普通版：https://gist.github.com/chouclee/5880c7fdf95bf593c395
Hashtable版 https://gist.github.com/chouclee/837102ddb0273f428cb5

【解题思路】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

【解题思路】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)

【解题思路】假设是ascii字符 共256个  用长度为256的Boolean数组表示某字符是否出现过
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】  https://gist.github.com/jyhjuzi/1f526165a8a54148bde4

【解题思路】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】

immortaliqi 发表于 2014-6-16 00:36
【解题思路】

用一个数组储存 每次储存新字符的时候检查数组 如果存在直接return

如果字符库只限 ...

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

【解题思路】设字符集为ascii（大小256），一个大小为256的 boolean 数组，出现一次后字符相应位置为 true，否则为 false
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/JoyceeLee/8118612ec2b571730f30
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
可以使用其他数据结构的话，采用Set，相同字符的话覆盖，最后比较总数
不可使用其他数据结构的话，采用一个大小为256的数组，统计每个字符的出现次数
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/MrCQ/6ec6ac7c5b7992eef6a5

【解题思路】
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

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

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