一亩三分地论坛

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

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

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

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

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

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

x
1.3 Given two strings, write a method to decide if one is a permutation of the other.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】

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

atlas1017 发表于 2014-6-16 06:17:51 | 显示全部楼层
答案里面那个碰到 less than 0 就直接 break return false的小trick 真是聪明= =!
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2014-6-16 00:21:03 | 显示全部楼层
本帖最后由 readman 于 2014-6-24 23:18 编辑

【解题思路】
first loop add char to int array
second minus char in int array
third test chars  
【时间复杂度】
n
【空间复杂度】
n
【gist link】
https://gist.github.com/gaoyike/2839135b288b36d984e8
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

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

【Some Question】
   1. Range of character. ASCII? 26 letters?
   2. can we destory the string?
   3. uppercase/lowercase. "dog" and "God" are anagram or not?
   4. blank space is ignored or not? "d" and "d    " are anagram or not?
【解题思路】
1. assign two arrays, each array store the numbers of every characters in the each string.
2. To optimize the method above, we can use just one array. Since we count the numbers of each characters in the first string, then we decrease them according the second string.
3. If the string can be destroyed, we can sort them first, then compare them.
【时间复杂度】
1. O(n)
2. O(n)
3. O(nlogn)
【空间复杂度】
1. O(1)
2. O(1)
3. O(1)
【gist link】
https://gist.github.com/qianhuang/1eeddb16121a0c0e0ed0
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-16 12:35:21 | 显示全部楼层
【解题思路】
  If the length of two strings are different, return False
  Put all characters from the first string into an array,
  Remove character which matches the character in the second string from the array
  If array is empty after the loop, return True
【时间复杂度】
  O(N)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/19a729085f14c9d2a3bc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
  Empty string
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-16 13:53:00 | 显示全部楼层
【解题思路】two int arrays are used to count each character for the given two strings, check if two counters for the same character mismatch
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/3f4d8a9409d230992a6b
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】user interaction is implemented in the code
回复 支持 反对

使用道具 举报

monkerek 发表于 2014-6-16 21:11:14 | 显示全部楼层
【解题思路】
use a dict(hashmap) to count the appearance of characters of the first string, then minus the number of that in the other string.
once the hash value is less than zero, return false
【时间复杂度】
O(n)
【空间复杂度】
O(1) for certain set of characters, say ascii
【gist link】
https://gist.github.com/monkerek/bd54cffd22ebde390a21
回复 支持 反对

使用道具 举报

心焰 发表于 2014-6-16 22:00:10 | 显示全部楼层
【解题思路】
1. compare the length of two strings, if not the same, return false; else go to 2
2. Use a hashmap to store the element & occurrences of chars in one string
3. Compare the other string with the hashmap, if cannot find a record of a char, break & return false; else minus the occurrence count, then go to 4
4. if all the occurrence counts are zero, return true, they are mutual permulations
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://github.com/FinalF/Carrer ... rmutationCheck.java
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-17 01:06:13 | 显示全部楼层
本帖最后由 wilbert 于 2014-6-17 23:29 编辑

【解题思路】
Hash,must meet the prerequisites that: 1. not null 2. two string should be in equal length.Count the number of occurrence of characters in the first string, and minus the occurrence of characters in the second string. If count[c] < 0, return false.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/21b1b1dd680f33d5ead7
回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-17 01:50:36 | 显示全部楼层
本帖最后由 小柯西 于 2014-6-19 16:06 编辑

【解题思路】
1. For 2 strings of same length, use a hashmap to store every character in s1, then check if those of s2 are contained in this hashmap.
2. Sort the 2 strings and compare their character in same index.
【时间复杂度】
1. O(n) for traversing char array. PS: containsKey() method has a time complexity of O(1).
2. O(nlg) for sorting.
【空间复杂度】
1. O(1) for hashmap.
2. O(1) if the strings are breakable.
【gist link】https://gist.github.com/6dfa93c2cc873f6f76e4.git
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
s1: "" s2: ""
s1: null, s2:"1111"
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-17 02:03:57 | 显示全部楼层
【解题思路】
若两个字符串长度不同,则返回 false
设字符集为 ascii(256个),利用一个大小为256的 int 数组;
第一遍对 s 中所有字符遍历,将每个字符出现的次数计入数组;
第二遍对 t 中所有字符遍历,在数组中减去字符出现的次数,若减去后小于 0,则返回 false;
返回 true
【时间复杂度】
n
【空间复杂度】
1
【gist link】
https://gist.github.com/JoyceeLee/826c8c3ea2bdedfe9622
回复 支持 反对

使用道具 举报

dreamhit 发表于 2014-6-17 06:06:35 | 显示全部楼层
Solution 1:
Sort the arrays, and compare the element one by one.
Time complexity O(nlogn)
Space complexity O(1)

Solution 2:
Time complexity: O(n), Space complexity: O(n)

Code link:
https://gist.github.com/Jocelyn9/d288fd5e38e7313ebb65
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-17 06:46:20 | 显示全部楼层
【解题思路】
1. 建立一个int数组,初始化为全0,长度为ASCII字符种类(256)。
2. 遍历第一个字符串,记录每一个字符出现的次数。
3. 遍历第二个字符串,每遇到一个字符,就在数组的相应元素中减去一。
4. 遍历数组,如果每一个元素都是0,则返回true;否则返回false。
【时间复杂度】
O(m+n),其中m和n分别是两个字符串的长度。
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_3-cc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-17 09:40:38 | 显示全部楼层
Assumptions : case sensitive     do not ignore white space
1.
【解题思路】
use a hashmap to count the frequency of  every chars in str1,   traverse str1, corresponding frequency - 1,  return false when the frequency is going to be negative
【时间复杂度】
O(n)
【空间复杂度】
O(1)
2.
【解题思路】
compare two  sorted char arrays   element by element  or  compare two strings generated from sorted char arrays
【时间复杂度】
O(nlogn)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/jyhjuzi/6a48769758a67ee2a7ae
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-17 15:29:13 | 显示全部楼层
本帖最后由 chouclee 于 2014-6-17 15:44 编辑

【解题思路】用两个HashMap分别统计字符串里字符出现的频率,然后比较两个HashMap,频数不一致的话return false。对大小写敏感,对空格敏感。如果想对大小写不敏感,在统计前可以先将字符串全部toLowerCase()或者toUpperCase(),对空格不敏感,可以在统计完成后,判断频数时跳过blank character
【时间复杂度】O(n)
【空间复杂度】O(1) (如果不可以破坏原string,调用toLowerCase()或toUpperCase()就是O(n))
【gist link】https://gist.github.com/chouclee/0fb6ccc84d604d50a14e
【test case】a = "我为人人"; b = "人人为我";

回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-17 17:57:11 | 显示全部楼层
【解题思路】先把两个字符串转换为java 数组,然后排序,然后转换为string,用java来比较
【时间复杂度】O(nlogn)
【空间复杂度】O(1)
【gist link】https://gist.github.com/qiangusc/d468e3ee938dd8f2a5e2
回复 支持 反对

使用道具 举报

asdw3276 发表于 2014-6-18 01:46:48 | 显示全部楼层
【解题思路】遍历第一个字符串,根据每一个字符的ascii码令int数组中相应的元素+1.遍历第二个字符串,根据每一个字符的ascii码令int数组中相应的元素-1. 最后遍历int数组是否全部为0即可
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/f9e259ebf504db026e7d

感谢所有给我code review的小伙伴
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-18 02:03:58 | 显示全部楼层
【解题思路】length s!=length t,false; s,t are empty, false; put s,t from array to string ,compare they are equal or not
【时间复杂度】O(nlogn)
【空间复杂度】O(1)
【gist link】https://gist.github.com/hilda8519/3fbd305943dab4addd62
回复 支持 反对

使用道具 举报

RealityPC 发表于 2014-6-18 08:33:57 | 显示全部楼层
【解题思路】loop over all chars in string1 and add one to the corresponding ascii array. do the same thing but minus one to string2. at the end, if all the ascii number have value 0, return true.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/pchong90/c2badf9e895b8fbf7ee4
回复 支持 反对

使用道具 举报

larry 发表于 2014-6-18 13:14:44 | 显示全部楼层
【解题思路】Use the thought we got in CC1.1
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/larry-liu/c3ec4c9f7f5586864963
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 23:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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