刷题记录

Problem: Compare two version numbers  version1  and  version2 . If  version1  >  version2  return  1;  if  version1  <  version2  return  -1; otherwise return  0 . You may assume that the version strings are non-empty and contain only digits and the  .  character. The  .  character does not represent a decimal point and is used to separate number sequences. For instance,  2.5  is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision. Example 1: Input: version1 = "0.1", version2 = "1.1" Output: -1 Example 2: Input: version1 = "1.0.1", version2 = "1" Output: 1 Example 3: Input: version1 = "7.5.2.4", version2 = "7.5.3" Output: -1 Analysis: 这道题实现的时候要注意在数组越界的时候把值赋为零。 Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int compareVersion ...

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; } * } */ c...

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

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

Problem: You have a list of  words  and a  pattern , and you want to know which words in  words  matches the pattern. A word matches the pattern if there exists a permutation of letters  p  so that after replacing every letter  x  in the pattern with  p(x) , we get the desired word. ( Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter. ) Return a list of the words in  words  that match the given pattern.  You may return the answer in any order. Example 1: Input: words = ["abc","deq","mee","aqq","dkd","ccc"] , pattern = "abb" Output: ["mee","aqq"] Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to t...

Probelm: Given an undirected  graph , return  true  if and only if it is bipartite. Recall that a graph is  bipartite  if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B. The graph is given in the following form:  graph[i]  is a list of indexes  j  for which the edge between nodes  i  and  j  exists.  Each node is an integer between  0  and  graph.length - 1 .  There are no self edges or parallel edges:  graph[i]  does not contain  i , and it doesn't contain any element twice. Example 1: Input: [[1,3], [0,2], [1,3], [0,2]] Output: true Explanation: The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0, 2} and {1, 3}. Example 2: Input: [[1,2,3], [0,2], [0,1,3], [0,2]] Output: false Explanation: The graph looks like this: 0...

Problem: Given the running logs of  n  functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions. Each function has a unique id, start from  0  to  n-1 . A function may be called recursively or by another function. A log is a string has this format :  function_id:start_or_end:timestamp . For example,  "0:start:0"  means function 0 starts from the very beginning of time 0.  "0:end:0"  means function 0 ends to the very end of time 0. Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id. Example 1: Input: n = 2 logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"] Output: [3, 4] Explanation: Function 0 starts at time 0, then it executes 2 units of...

Problem: We are given a binary tree (with root node  root ), a  target  node, and an integer value  K . Return a list of the values of all nodes that have a distance  K  from the  target  node.  The answer can be returned in any order. Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4] , target = 5 , K = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1. Note that the inputs "root" and "target" are actually TreeNodes. The descriptions of the inputs above are just serializations of these objects. Analysis: 这道题和之前那道 742. Closest Leaf in a Binary Tree  类似。都是先建图然后BFS。不同点在于，这道题如果按742的图的构建方式，test case [1] 通过不了， 因为node 1根本不会出现在图中。就会出现null pointer错误。 另外一个点就是，在while循环一开始判断k的值，循环底部k--。如果反过来而且k==0, 就得不到结果。 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 36 37 38 39 40 41 ...