刷题记录

Problem: Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a  binary search tree . There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible. Analysis: This problem needs to encode as compact as possible so that "null" should be avoided. We use recursive preorder. While desalinizing, use lower bound and uppder bound to decide the legitimacy of current value. Converting data to queue, to reduce remove complexity to constant.  Similar problem 98. Validate Binary Search Tree W...

Problem: Given a Binary Search Tree (BST) with root node  root , and a target value  V , split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, while the other subtree has all nodes that are greater than the target value.  It's not necessarily the case that the tree contains a node with value  V . Additionally, most of the structure of the original tree should remain.  Formally, for any child C with parent P in the original tree, if they are both in the same subtree after the split, then node C should still have the parent P. You should output the root TreeNode of both subtrees after splitting, in any order. Example 1: Input: root = [4,2,6,1,3,5,7], V = 2 Output: [[2,1],[4,3,6,null,null,5,7]] Explanation: Note that root, output[0], and output[1] are TreeNode objects, not arrays. The given tree [4,2,6,1,3,5,7] is represented by the following diagram: 4 / \ ...

Problem: Given a positive integer  n  and you can do operations as follow: If  n  is even, replace  n  with  n /2 . If  n  is odd, you can replace  n  with either  n  + 1  or  n  - 1 . What is the minimum number of replacements needed for  n  to become 1? Example 1: Input: 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1 Example 2: Input: 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1 Analysis: User recursion.  Not fit for dp, because if n is odd, n can add 1. Solution: n + 1 might overflow, use long in recursion instead of int. class Solution { public int integerReplacement ( int n) { return ( int )longReplacement(n); } private int longReplacement ( long n) { if (n == 1 ) return 0 ; if (n % 2 == 0 ) return longReplacement(n / 2 ) + 1 ; else re...

Problem: According to the  Wikipedia's article : "The  Game of Life , also known simply as  Life , is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a  board  with  m  by  n  cells, each cell has an initial state  live  (1) or  dead  (0). Each cell interacts with its  eight neighbors  (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state.  The next state is created ...

Problem: Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example: Given num = 16, return true. Given num = 5, return false. Analysis: 类似于power of three。 Solution: class Solution { public boolean isPowerOfFour ( int num) { if (num <= 0 ) return false; while (num % 4 == 0 ) { num /= 4 ; } return num == 1 ; } }

Problem: Given an integer, write a function to determine if it is a power of three. Analysis: 判断一个数是否是3的次方。用数学公式那是不现实的。。。 如果一个数是3的次方，一直除以3最后结果是1. 不是3的次方，但是是3的倍数比如6，6/3=2. 2/3=0. 最后结果是0. Solution: class Solution { public boolean isPowerOfThree ( int n) { if (n <= 0 ) return false; while (n % 3 == 0 ) { n /= 3 ; } return n == 1 ; } }

Problem: Given two strings  A  and  B  of lowercase letters, return  true  if and only if we can swap two letters in  A  so that the result equals  B . Example 1: Input: A = "ab" , B = "ba" Output: true Example 2: Input: A = "ab" , B = "ab" Output: false Example 3: Input: A = "aa" , B = "aa" Output: true Example 4: Input: A = "aaaaaaabc" , B = "aaaaaaacb" Output: true Example 5: Input: A = "" , B = "aa" Output: false Analysis: Buddy string qualifies the following conditoin: 1. Length equal 2. If exact equal, A must have duplicate, since swap is required. 3. A and B only have 2 chars diff, and these 2 chars can swap. Solution: class Solution { public boolean buddyStrings ( String A , String B ) { // compare length if ( A . length() != B . length()) return false; // equals, find duplicates ...

Problem: You have a number of envelopes with widths and heights given as a pair of integers  (w, h) . One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you Russian doll? (put one inside other) Example: Given envelopes =  [[5,4],[6,4],[6,7],[2,3]] , the maximum number of envelopes you can Russian doll is  3  ([2,3] => [5,4] => [6,7]). Analysis: Two dimensional Longest increasing sub sequence. Convert this problem to 1D LIS. Sort the envelopes by width. So height becomes the 1D LIS. But if we have [3, 3], [3, 4], the former doll can not fit into the latter one. If there is a tie on width, sort height in desc order.  Time:  O(nlogn). Solution: class Solution { public int maxEnvelopes ( int [][] envelopes) { if (envelopes == null || envelopes . length == 0 || envelopes[ 0 ...

Problem: We are playing the Guess Game. The game is as follows: I pick a number from  1  to  n . You have to guess which number I picked. Every time you guess wrong, I'll tell you whether the number is higher or lower. You call a pre-defined API  guess(int num)  which returns 3 possible results ( -1 ,  1 , or  0 ): -1 : My number is lower 1 : My number is higher 0 : Congrats! You got it! Example: n = 10, I pick 6. Return 6. Analysis: The condition is very clear, so use double check template Solution: /* The guess API is defined in the parent class GuessGame. @param num, your guess @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); */ public class Solution extends GuessGame { public int guessNumber ( int n) { int left = 0 , right = n; while (left + 1 < right) { int mid = left + (right - left) / 2 ; ...

Problem: Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0 8/23/2018 update: 这道题不能取end的原因是，如果设end = mid - 1，那么end有可能为负。 ------------------ ------------------ ------------------ ------------------ ------------------ ------------------ -------------- Analysis: After trial for several times, the start = mid + 1 template wins and end should at nums.length Solution: class Solution { public int searchInsert ( int [] nums, int target) { int start = 0 , end = nums . length; while (start < end) { int mid = start + (end - start) / 2 ; if (nums[mid] == target) return mid; ...

Problem: Given an input string ( s ) and a pattern ( p ), implement regular expression matching with support for  '.'  and  '*' . '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the  entire  input string (not partial). Note: s  could be empty and contains only lowercase letters  a-z . p  could be empty and contains only lowercase letters  a-z , and characters like  .  or  * . Example 1: Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa" p = "a*" Output: true Explanation:  '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab" p = ".*" Output: true Explanation:  ".*" means "zero or more (*) ...

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 an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"] , Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. Analysis: What's in common of anagrams is they are the same if we sort them. So use a map, key is the sorted string, value is the anagram list.  Solution: class Solution { public List< List< String > > groupAnagrams ( String [] strs) { List< List< String > > res = new ArrayList<> (); if (strs == null || strs . length == 0 ) return res; Map< String , List< String > > map = new HashMap<> (); for ( int i = 0 ; i < strs . length; i ++ ) { char [] ch...

Problem: There are  N  rooms and you start in room  0 .  Each room has a distinct number in  0, 1, 2, ..., N-1 , and each room may have some keys to access the next room.  Formally, each room  i  has a list of keys  rooms[i] , and each key  rooms[i][j]  is an integer in  [0, 1, ..., N-1]  where  N = rooms.length .  A key  rooms[i][j] = v  opens the room with number  v . Initially, all the rooms start locked (except for room  0 ).  You can walk back and forth between rooms freely. Return  true  if and only if you can enter every room. Example 1: Input: [[1],[2],[3],[]] Output: true Explanation: We start in room 0, and pick up key 1. We then go to room 1, and pick up key 2. We then go to room 2, and pick up key 3. We then go to room 3. Since we were able to go to every room, we return true. Example 2: Input: [[1,3],[3,0,1],[2],[0]] Output: false Expla...