[第二轮] 2/18-2/24 CareerCup 1.3

mazl123321 发表于 2013-2-17 10:19
1. both str must have same length
2. for same char, both str have same count

感觉用HashMap的话就麻烦了，虽然也是O(n)

cqx83 发表于 2013-2-18 04:20
感觉用HashMap的话就麻烦了，虽然也是O(n)

Yes, you are right, thanks a lot

1. check if there is a duplicate in the visited zone. If yes, do nothing, ++p2. If no, copy *p2 to *tail and increment tail++. (tail is "not included")
Time: n^2 Space: 0

2. hashtable, easy. Time: n Space: 256

https://gist.github.com/JasonGitHub/4975307

https://github.com/JerrySun363/C ... k1/Permutation.java

1. 比较长度
2.用bitmap(开数组记录每个char出现的字数，string 1 用++， string 2 --)，然后check 是不是都是 0;
--------------
其实对permutation的定义不是很明白，我按照每个character 出现的次数一样来做的。
还有一个问题是Java的char取值范围是0-65535，但是我只取了0-255，如果出现中文或者别的文字的话就跪了。我想请教一下如果这个题目里的string不局限于 ASCII时应该怎么考虑？开一个65535的数组还是先排序再比较？

jerrysun 发表于 2013-2-19 00:42
https://github.com/JerrySun363/CareerCup/blob/master/Week1/Permutation.java

1. 比较长度

I see most of you guys solve it this way. Before you solve the problem during the interview, you can always ask questions, even ask for examples.
http://n1b-algo.blogspot.com/2009/01/string-permutations.html
This link may help you understand what is permutation.
The code seems good for me. :)

I check both length first, if the length equals: convert to charArray and sort. Then convert back to string and compare.
Don't know what's the complexity.. But I know it would be very large... Need some advices.

https://gist.github.com/lynntian/4981111

python无脑强A流，先比较长度，如果一样就sort再比较。。。我觉得用hash的话可以做到O(n)，但我不知道python是怎么比较两个list的，求教达人
https://gist.github.com/starcroce/4981843

overview:
method1: Test every char in str1, if it is in the str2,  then record its index in str2 using an int array. Whenever a char can't be found, return false.method2: Use a int array[256], plus 1 to the array[char in str1], minus 1 to the array[char in str2], if the result array is not all 0, return false.

C language:https://gist.github.com/hukun01/4982375

starcroce 发表于 2013-2-19 07:57
python无脑强A流，先比较长度，如果一样就sort再比较。。。我觉得用hash的话可以做到O(n)，但我不知道pytho ...

这这……我只能说 脚本语言就是不一样啊。
这个比较是内建的，查文档应该能知道，估计已经是最优化了。

https://gist.github.com/Toanso/4984905