刷题记录

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

Problem: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. Analysis: 每当有极小数的时候，先把次小数push进stack,然后把极小数push进stack。当pop的数是当前min的时候，连续pop 2次，第二次的就是pop后的min. push -2     stack -2, max] min: -2 push 0     stack 0, -2, max] min: -2 push -3     stack -3, -2, 0, -2, max] min: -3 pop:     这里先pop-3出去，发现-3刚好是最小值，所以把 -2也pop出去，-2就是去除-3后的最小值。 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 class MinStack { ...

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: A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. Example 1: Input: "69" Output: true Example 2: Input: "88" Output: true Example 3: Input: "962" Output: false Analysis: 列举出可以rotate的数对，然后用同向双指针检查是否匹配。 Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public boolean isStrobogrammatic ( String num ) { Map < Character , Character > map = new HashMap < Character , Character >(); map . put ( '6' , '9' ); map . put ( '9' , '6' ); map . put ( '0' , '0' ); map . put ( '1' , '1' ); map . put ( '8' , '8' ); int l = 0 , r = num . length () - 1 ; while ( l <= r ) { ...

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 a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree  [1,2,2,3,4,4,3]  is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following  [1,2,2,null,3,null,3]  is not: 1 / \ 2 2 \ \ 3 3 Analysis: 如果当前对比的node1 和node 2相等，要符合symmetric tree我们需要比较node1.left == node2.right && node1.right == node2.left. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public boolean isSymmetric ( TreeNode root ) { return root == null || helper ( root . left , root . right ); } private boolean helper ( TreeNode left , TreeNode right ) { if ( left == null && right == null) return true; if (( left != null && right == null) || ( left == null && right != null) || left . val != right . val ) return false; r...

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