February 7, 2016
There are a several of stages to go through on Leetcode 318 problem solving today.
10 minutes to read question and think about solution, confused about requirement(以为包括子字符串) ->
20 minutes to read blogs to understand solutions ->
10 minutes to know the detail to implement (1) ->
20 minutes to implement without bugs (2) ->
10 minutes to implement with more clear code with bugs (3) ->
10 minutes debug to read code again, debugging to pinpoint bug ->
60 minutes to work on a better idea - optimal idea (5) ->
work on exceeded time issues (20 minutes, instead of 60+ minutes) (6)
Action items:
1. Always work on coding, using Visual Studio. Try to improve coding.
Leetcode 318: Maximum Product of Word Length
Given a string array
https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/
Solution 1:
Solution 2:
There are a several of stages to go through on Leetcode 318 problem solving today.
10 minutes to read question and think about solution, confused about requirement(以为包括子字符串) ->
20 minutes to read blogs to understand solutions ->
10 minutes to know the detail to implement (1) ->
20 minutes to implement without bugs (2) ->
10 minutes to implement with more clear code with bugs (3) ->
10 minutes debug to read code again, debugging to pinpoint bug ->
60 minutes to work on a better idea - optimal idea (5) ->
work on exceeded time issues (20 minutes, instead of 60+ minutes) (6)
Action items:
1. Always work on coding, using Visual Studio. Try to improve coding.
Leetcode 318: Maximum Product of Word Length
Given a string array
words
, find the maximum value of length(word[i]) * length(word[j])
where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/
Solution 1:
直接看看每个字符串都包括了哪个字符,然后一一枚举是否有交集:
- 有交集,则乘积为0
- 无交集,乘积为 words[i].length() * words[j].length()
Julia's practice:
其实因为全部都是小写的字母,用int 就可以存储每一位的信息。这就是位运算
- elements[i] |= 1 << (words[i][j] – ‘a’); //把words[i][j] 在26字母中的出现的次序变为1
- elements[i] & elements[j] // 判断是否有交集只需要两个数 按位 与 (AND)运算即可
http://www.cnblogs.com/onlyac/p/5155881.html
在一个字符串组成的数组words中,找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母,在这里字符串由小写字母a-z组成的。
对于这道题目我们统计下words[i]的小写字母a-z是否存在,然后枚举words[i]和words[j],找出max{Length(words[i]) * Length(words[j]) }。
小写字母a-z是26位,一般统计是否存在我们要申请一个bool flg[26]这样的数组,但是我们在这里用int代替,int是32位可以替代flg数组,用 与(&),或(1),以及向左移位(<<)就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111,“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000,这样两个进行与(&)得到0, 如果有相同的字母则不是0。
Here is julia's practice:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_B.cs
Read the webpage about precedence and order of evaluation:
https://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx
Solution 3:
Just for fun, write another version of bit manipulation implementation, but Julia created 3 bugs in the row before she writes a correct version.
Instead of using two words do not contain same char,
if ((s1 & s2) == 0) return true;
she tried to write a version to check any char from a to z, one by one check version:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_C.cs
Design takes practice. She thought about and then wrote, and then failed 3 times!
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_B.cs
Read the webpage about precedence and order of evaluation:
https://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx
Solution 3:
Just for fun, write another version of bit manipulation implementation, but Julia created 3 bugs in the row before she writes a correct version.
Instead of using two words do not contain same char,
if ((s1 & s2) == 0) return true;
she tried to write a version to check any char from a to z, one by one check version:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_C.cs
Design takes practice. She thought about and then wrote, and then failed 3 times!
No comments:
Post a Comment