刷题记录

Problem: Given a singly linked list, return a random node's value from the linked list. Each node must have the  same probability  of being chosen. Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space? Example: // Init a singly linked list [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head); // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning. solution.getRandom(); Analysis: 实在是看不懂reservoir sampling, 看了2个小时稍微有点儿眉目。。。意思就是随机取一个范围1到i的数，可以保证概率随机。。。。 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 26 27 28 29 30 31 32 33 34 35 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class

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 -