刷题记录

Problem: A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. Example: Input: n = 2 Output: ["11","69","88","96"] Analysis: 找规律： n = 0: "" n = 1: 0, 1, 8 n = 2: 88, 69, 11, 96 n = 3: 808, 609, 101, 906， 818, 619, 111, 916, 888, 689, 181, 986 可以发现n是在n-2的基础上开头和结尾都同时加上strobogrammatic对。如果n是要求的长 度那么还需要排除0. Solution: 这里第二个parameter的目的就是为了排除leading and tailing zeroes. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public List < String > findStrobogrammatic ( int n ) { return helper ( n , n ); } private List < String > helper ( int n , int m ) { if ( n == 0 ) return new ArrayList <>( Arrays . asList ( "" )); if ( n == 1 ) return new ArrayList <>( Arrays . asList ( "0&

Problem: Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let's take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element. The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list. Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first

Problem: Suppose you are at a party with  n  people (labeled from  0  to  n - 1 ) and among them, there may exist one celebrity. The definition of a celebrity is that all the other  n - 1  people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense). You are given a helper function  bool knows(a, b)  which tells you whether A knows B. Implement a function  int findCelebrity(n) , your function should minimize the number of calls to  knows . Note : There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return  -1 . Analysis: two pass,

Problem: right corner ( row 2,  col 2). The above rectangle (with the red border) is defined by (row1, col1) =  (2, 1)  and (row2, col2) =  (4, 3) , which contains sum =  8 . Example: Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12 Note: You may assume that the matrix does not change. There are many calls to  sumRegion  function. You may assume that  row 1 ≤  row 2 and  col 1 ≤  col 2. Analysis: 和mutable那道思路一样的。只是在算sum的时候用到了dp. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class NumMatrix { int [][] dp ; public NumMatrix ( int [][] matrix ) { if ( matrix . length == 0 || matrix [ 0 ]. length == 0 ) return; int m = matrix . length , n = matrix [ 0 ]. length ; dp = new int [ m + 1 ][ n + 1 ]; for ( int r

Problem: Given a non-empty string  s , you may delete  at most  one character. Judge whether you can make it a palindrome. Example 1: Input: "aba" Output: True Example 2: Input: "abca" Output: True Explanation: You could delete the character 'c'. Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000. Analysis: leetcode 面经真准。这道题是fb最近的电面原题。 Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public boolean validPalindrome ( String s ) { if ( s == null || s . length () == 0 ) return false; int l = 0 , r = s . length () - 1 ; while ( l < r ) { if ( s . charAt ( l ) == s . charAt ( r )) { l ++; r --; } else return isPalindrome ( s , l + 1 , r ) || isPalindrome ( s , l , r -

Problem: Given a  non-empty  string  s  and an abbreviation  abbr , return whether the string matches with the given abbreviation. A string such as  "word"  contains only the following valid abbreviations: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"] Notice that only the above abbreviations are valid abbreviations of the string  "word" . Any other string is not a valid abbreviation of  "word" . Note: Assume  s  contains only lowercase letters and  abbr  contains only lowercase letters and digits. Example 1: Given s = "internationalization", abbr = "i12iz4n": Return true. Example 2: Given s = "apple", abbr = "a2e": Return false. Analysis: 这道题的坑爹程度也只是稍微比isNumber Val