刷题记录

Problem: Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, determine if  s  can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given s  =  "leetcode" , dict  =  ["leet", "code"] . Return true because  "leetcode"  can be segmented as  "leet code" . Analysis: State: dp[i] s前i个字符是否满足word break Transition: dp[i] == true, 满足 dp[j] == true && wordDict.contains(s.substring(i, j)) 举个例子: leet code        j = 4   i = 8 dp[j] 表示leet知否满足word break。 因为dp[]要比s多一位，dp[j] 对应的j指向的前一位。s.substring(4,8) == code. Solution: class Solution { public boolean wordBreak ( String s, List< String > wordDict) { int len = s . length(); boolean [] dp = new boolean [len + 1 ]; ...

Problem: Given a string that contains only digits  0-9  and a target value, return all possibilities to add  binary  operators (not unary)  + ,  - , or  * between the digits so they evaluate to the target value. Examples:  "123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> [] Analysis: The idea is plain DFS, the difficulty lies in how to deal with multiply. 2+3*2, the prev value is 5, we cant simply multiply 5 by 2. The correct formula is 5   -    3    +      3 *  2                                     val - prev  + prev * cur So we need to maintain prev value. When the previous operator is - or * =, the previous value is -cur or cur * pre respectively. Another point worth to mention ...

Problem: Write a function to generate the generalized abbreviations of a word. Example: Given word =  "word" , return the following list (order does not matter): ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"] Analysis: There are 2^n (n is the length of word) possible abbreviations. Use DFS to get all abbreviations. Solution: If we skip the current char, we can not append the count, because we dont know if the next char would be skipped or not. We can make sure the count is set is when current char remains or we reach the end. class Solution { public List< String > generateAbbreviations ( String word) { List< String > res = new ArrayList<> (); dfs(res, new StringBuilder (), word, 0 ); ...

Problem: Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full match, such that there is a bijection between a letter in  pattern  and a  non-empty  substring in  str . Examples: pattern =  "abab" , str =  "redblueredblue"  should return true. pattern =  "aaaa" , str =  "asdasdasdasd"  should return true. pattern =  "aabb" , str =  "xyzabcxzyabc"  should return false. Analysis: This problem is the recursive implementation of Word Pattern. Again, we can eliminate the index counter while doing dfs.  Solution:   class Solution { public boolean wordPatternMatch ( String pattern, String str) { return isMatch(pattern, str, new HashMap<> (), new HashSet<> ()); } private boolean isMatch ( String pat, String str, Map< Character , String > map, Set< String...

Problem: Given two strings  s  and  t , determine if they are isomorphic. Two strings are isomorphic if the characters in  s  can be replaced to get  t . All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself. For example, Given  "egg" ,  "add" , return true. Given  "foo" ,  "bar" , return false. Given  "paper" ,  "title" , return true. Analysis: Identical problem to word pattern.  Solution: class Solution { public boolean isIsomorphic ( String s, String t) { Map< Character , Character > map = new HashMap<> (); for ( int i = 0 ; i < strs . length; i ++ ) { char c1 = s . charAt(i); char c2 = t . charAt(i); String word = strs[i]; if (map . containsKey(c1) &...

Problem: Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full match, such that there is a bijection between a letter in  pattern  and a  non-empty  word in  str . Examples: pattern =  "abba" , str =  "dog cat cat dog"  should return true. pattern =  "abba" , str =  "dog cat cat fish"  should return false. pattern =  "aaaa" , str =  "dog cat cat dog"  should return false. pattern =  "abba" , str =  "dog dog dog dog"  should return false. Notes: You may assume  pattern  contains only lowercase letters, and  str  contains lowercase letters separated by a single space. Analysis: The difficulty of this problem lies in that how to decide new word in new pattern character not exist before. "abba" "dog cat cat dog". If there is a new pattern char, we need to make sure its paired...

Problem: Numbers can be regarded as product of its factors. For example, 8 = 2 x 2 x 2; = 2 x 4. Write a function that takes an integer  n  and return all possible combinations of its factors. Note:   You may assume that  n  is always positive. Factors should be greater than 1 and less than  n . Examples:  input:  1 output:  [] input:  37 output:  [] input:  12 output: [ [2, 6], [2, 2, 3], [3, 4] ] input:  32 output: [ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ] Analysis: Similar to combinations. The tricky part is i's upper bound should include remain, and check size of list to decide whether to add this list. Solution: class Solution { public List< List< Integer > > getFactors ( int n) { List< List< Integer > > res = new ArrayList<> (); dfs(res, new ArrayList<> (), n, 2 ); ...

Problem: Given an integer, write a function to determine if it is a power of two. Analysis: Base 2 representation of 2 is 10, 4 is 100, 8 is 1000.    100 &011 --------   000 If a number is power of 2, it qualifies the property that n & (n - 1) == 0 Solution:    class Solution { public boolean isPowerOfTwo ( int n) { return n > 0 && (n & (n - 1 )) == 0 ; } }

Problem: The set  [1,2,3,…, n ]  contains a total of  n ! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for  n  = 3): "123" "132" "213" "231" "312" "321" Given  n  and  k , return the  k th  permutation sequence. 7/24/2018 update: The purpose of removing the added element is that, each time we reduce k, we actually get the number from new order.1234 for instance, the index is always 0 everytime. ---------------------------- ---------------------------- ---------------------------- ---------------------------- ---------------------------- Analysis: 这种数学类的题在面试里面做出来的机会很渺茫啊。这道题想到于矩阵的扩展。如果n == 4,那么可以转换成找 6*4 matrix里面第k个数。 http://www.cnblogs.com/grandyang/p/4358678.html Solution: Note k has to subtract by 1, because index is zero based.  class Solution { public String getPermutation ( int n, int k) { List< Integ...

Problem: Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Analysis: 8 4 2 1 --------------- 5 | 0 1 0 1 6 | 0 1 1 0 7 | 0 1 1 1 m has the fewest 1 prefix, n has the most 1 prefix. Need to find the common 1 prefix. So clear n's last 1 one by one until n <= m; Solution: class Solution { public int rangeBitwiseAnd ( int m, int n) { while (n > m) { n = n & (n - 1 ); } return m & n; } }

Set bit: n |= 1 << i Clear bit: n &= ~(1<<i) Test bit: (n>>i) & 1 Clear last 1: n & (n - 1)

Problem: The  Hamming distance  between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers. Example: Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6. Note: Elements of the given array are in the range of  0  to  10^9 Length of the array will not exceed  10^4 Analysis: 4:     0 1 0 0 14:   1 1 1 0 2:     0 0 1 0 1:     0 0 0 1 Count bit by bit. Take look at the first bit. There is one 1. The hamming distance for first bit is 3. one 1 to three 0. Second bit has two 1, hamming distance is 4. one 1 to two 0 twice. We can conclude that the hamming di...

Problem: The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer  n  representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given  n  = 2, return  [0,1,3,2] . Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 Note: For a given  n , a gray code sequence is not uniquely defined. For example,  [0,2,3,1]  is also a valid gray code sequence according to the above definition. For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that. Analysis: We can conclude from the above image that, n can get from  n - 1. n == 1, code is 0, 1. Add 0 to front we have 00, 01. Then add 1 to front and reverse the code, we get 11, 10. Thus we have n == 2's code: 00, 01, 11, 10. Solution: class Solution { public List< Integer > grayCode ( i...

Problem: Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.  Return a list of all possible strings we could create. Examples: Input: S = "a1b2" Output: ["a1b2", "a1B2", "A1b2", "A1B2"] Input: S = "3z4" Output: ["3z4", "3Z4"] Input: S = "12345" Output: ["12345"] Analysis: See implementation Solution: class Solution { public List< String > letterCasePermutation ( String S ) { List< String > res = new ArrayList<> (); helper(res, 0 , new StringBuilder (), S ); return res; } private void helper ( List< String > res, int index, StringBuilder sb, String S ) { if (index == S . length()) { res . add(sb . toString()); return ; } char c = S . charAt(index); if ( Character ....

Problem: All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. For example, Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", Return: ["AAAAACCCCC", "CCCCCAAAAA"]. Analysis: 用bit manipulation 太难了，想不出来。 Use two sets, one stores distinct string, the other stores repeated. Solution: class Solution { public List< String > findRepeatedDnaSequences ( String s) { List< String > res = new ArrayList<> (); Set< String > seen = new HashSet<> (); Set< String > repeated = new HashSet<> (); if (s == null || s . length() == 0 ) return res; for ( int i = 0 ; i <= s . length() - 10 ; i ++ )...

Problem: Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the  Hamming weight ). For example, the 32-bit integer ’11' has binary representation  00000000000000000000000000001011 , so the function should return 3. Analysis: To determine ith bit in n is 1: 1 & (n >> i) Solution: public class Solution { // you need to treat n as an unsigned value public int hammingWeight ( int n) { int count = 0 ; for ( int i = 0 ; i < 32 ; i ++ ) { count += ( 1 & (n >> i)); } return count; } }

Problem: Given an array containing  n  distinct numbers taken from  0, 1, 2, ..., n , find the one that is missing from the array. Example 1 Input: [3,0,1] Output: 2 Example 2 Input: [9,6,4,2,3,5,7,0,1] Output: 8 Analysis: Similar to single number. If we have [0,1,3], then XOR with the complete set [0,1,2,3], we can get 2. Solution: class Solution { public int missingNumber ( int [] nums) { int res = nums . length; for ( int i = 0 ; i < nums . length; i ++ ) { res ^ = i ^ nums[i]; } return res; } }

The  Hamming distance  between two integers is the number of positions at which the corresponding bits are different. Given two integers  x  and  y , calculate the Hamming distance. Note: 0 ≤  x ,  y  < 2 31 . Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different. Analysis: XOR x and y, can set the diff digit to be 1. Then count 1s in xor. Solution: class Solution { public int hammingDistance ( int x, int y) { int count = 0 , xor = x ^ y; for ( int i = 0 ; i < 32 ; i ++ ) { count += ( 1 & (xor >> i) ); } return count; } }