刷题记录

Problem: Given a string  S  of digits, such as  S = "123456579" , we can split it into a  Fibonacci-like sequence   [123, 456, 579]. Formally, a Fibonacci-like sequence is a list  F  of non-negative integers such that: 0 <= F[i] <= 2^31 - 1 , (that is, each integer fits a 32-bit signed integer type); F.length >= 3 ; and  F[i] + F[i+1] = F[i+2]  for all  0 <= i < F.length - 2 . Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself. Return any Fibonacci-like sequence split from  S , or return  []  if it cannot be done. Example 1: Input: "123456579" Output: [123,456,579] Example 2: Input: "11235813" Output: [1,1,2,3,5,8,13] Example 3: Input: "112358130" Output: [] Explanation: The task is impossible. Example 4: Input: "0123" Output: [] Explanation: Leading zeroes are not allowed, so "01", "2...

Problem: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note:  The input string may contain letters other than the parentheses  (  and  ) . Example 1: Input: "()())()" Output: ["()()()", "(())()"] Example 2: Input: "(a)())()" Output: ["(a)()()", "(a())()"] Example 3: Input: ")(" Output: [""] Analysis: 用到reverse那个递归方法暂时没看懂，而且也超出我的能力范围了。现在暂时用left and right count的方法做，容易理解和实现。 1. Count number of left and right invalid parentheses.     '()()))()': right is 2.  ')(': left is 1 and right is 1 2. Typical dfs, remove left first then remove right. '())', only remove the first invalid, even remove dup is the typical dfs way. Solution: The index pass by dfs is i not i + 1, because we removed char at i, then i becomes the prev i + 1. class Solution { public List< String > removeInvali...

Problem: The  n -queens puzzle is the problem of placing  n  queens on an  n × n  chessboard such that no two queens attack each other. Given an integer  n , return all distinct solutions to the  n -queens puzzle. Each solution contains a distinct board configuration of the  n -queens' placement, where  'Q'  and  '.'  both indicate a queen and an empty space respectively. Example: Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above. Analysis: Easy backtracking. 1. With 1d array to store the queens' positions, need to first initialize array to -1. queens[r] = c, c can be 0. 2. If two points are on the diagonal, then the abs of their rows and columns are equal. Solution: class Solution { List...

Problem: Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, add spaces in  s  to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = " catsanddog " wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [   "cats and dog",   "cat sand dog" ] Example 2: Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [   "pine apple pen apple",   "pineapple pen apple",   "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog...

Problem: Given a binary tree  where every node has a unique value , and a target key  k , find the value of the nearest leaf node to target  k  in the tree. Here,  nearest  to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a  leaf  if it has no children. In the following examples, the input tree is represented in flattened form row by row. The actual  root  tree given will be a TreeNode object. Example 1: Input: root = [1, 3, 2], k = 1 Diagram of binary tree: 1 / \ 3 2 Output: 2 (or 3) Explanation: Either 2 or 3 is the nearest leaf node to the target of 1. Example 2: Input: root = [1], k = 1 Output: 1 Explanation: The nearest leaf node is the root node itself. Example 3: Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2 Diagram of binary tree: 1 / \ 2 3 /...

Problem: Find all possible combinations of  k  numbers that add up to a number  n , given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Note: All numbers will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] Analysis: Combination sum 马甲题，顺便复习了一下DFS. Solution: class Solution { public List< List< Integer > > combinationSum3 ( int k, int n) { List< List< Integer > > res = new ArrayList<> (); dfs(res, new ArrayList<> (), 1 , n, k); return res; } private void dfs ( List< List< Integer > > res, List< Integer > list, int index, int target, int k) { if (target == 0 && list . size() == k) { res . add( new ArrayList...

Problem: Given two integers  n  and  k , return all possible combinations of  k  numbers out of 1 ...  n . Example: Input:  n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] Analysis: Very easy DFS. Solution: class Solution { public List< List< Integer > > combine ( int n, int k) { List< List< Integer > > res = new ArrayList<> (); if (k > n) return res; dfs(res, new ArrayList<> (), n, 1 , k); return res; } private void dfs ( List< List< Integer > > res, List< Integer > list, int n, int start, int k) { if (list . size() == k) { res . add( new ArrayList<> (list)); } else { for ( int i = start; i <= n; i ++ ) { list . add(i); dfs(res, list, n, i + 1 , k); list . remove(list . size() - 1 ); ...

Problem: Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example: Input: [4, 6, 7, 7] Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] Note: The length of the given array will not exceed 15. The range of integer in the given array is [-100,100]. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence. Analysis: It's dfs apparently. Since the array can not be sorted, we need to use set to remove duplicates.  Solution: class Solution { public List< List< Integer > > findSubsequences ( int [] nums) { List< List< Integer > > res = new ArrayList<> (); if (nums == null || nums . length == 0 ) return res; dfs(res, new ArrayList<> (), ...

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: 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: 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...