刷题记录

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 by applying the above rules simultaneously to every cell in the c

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 ] . length == 0 )

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: 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 ; if (guess(mid) == 0 )

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: 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 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 binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a  full binary tree , but some nodes are null. The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the  null  nodes between the end-nodes are also counted into the length calculation. Example 1: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: 4 Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9). Example 2: Input: 1 / 3 / \ 5 3 Output: 2 Explanation: The maximum width existing in the third level with the length 2 (5,3). Example 3: Input: 1 / \ 3 2 / 5 Output: 2 Explanation: The maximum

Problem: You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map: 0  represents the  obstacle  can't be reached. 1  represents the  ground  can be walked through. The place with number bigger than 1  represents a  tree  can be walked through, and this positive number represents the tree's height. You are asked to cut off  all  the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1). You will start from the point (0, 0) and you should output the minimum steps  you need to walk  to cut off all the trees. If you can't cut off all the trees, output -1 in that situation. You are guaranteed that no two  trees  have the same height and there is at least one tree needs to be cut off. Example 1: Input: [ [1,2,3], [0,0,4], [7,6,5] ] Output: 6 Example 2: In