刷题记录

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

Problem: Design and implement a data structure for  Least Frequently Used (LFU)  cache. It should support the following operations:  get  and  put . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value)  - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least  recently  used key would be evicted. Follow up: Could you do both operations in  O(1)  time complexity? Example: LFUCache cache = new LFUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.get(3); // returns 3. cache.p...

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

Problem: Given a string  S  of digits, such as  S = "123456579" , we can split it into a  Fibonacci-like sequence   [123, 456, 579]. Formally, a Fibonacci-like sequence is a list  F  of non-negative integers such that: 0 <= F[i] <= 2^31 - 1 , (that is, each integer fits a 32-bit signed integer type); F.length >= 3 ; and  F[i] + F[i+1] = F[i+2]  for all  0 <= i < F.length - 2 . Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself. Return any Fibonacci-like sequence split from  S , or return  []  if it cannot be done. Example 1: Input: "123456579" Output: [123,456,579] Example 2: Input: "11235813" Output: [1,1,2,3,5,8,13] Example 3: Input: "112358130" Output: [] Explanation: The task is impossible. Example 4: Input: "0123" Output: [] Explanation: Leading zeroes are not allowed, so "01", "2...

Problem: You're given strings  J  representing the types of stones that are jewels, and  S  representing the stones you have.  Each character in  S is a type of stone you have.  You want to know how many of the stones you have are also jewels. The letters in  J  are guaranteed distinct, and all characters in  J  and  S  are letters. Letters are case sensitive, so  "a"  is considered a different type of stone from  "A" . Example 1: Input: J = "aA", S = "aAAbbbb" Output: 3 Example 2: Input: J = "z", S = "ZZ" Output: 0 Note: S  and  J  will consist of letters and have length at most 50. The characters in  J  are distinct. Analysis: skip Soluiton: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int numJewelsInStones(String J, String S) { Set<Character> set = new HashSet<>(); for ( char c: J.toCharArray()) { s...

Problem: Given a binary tree with  n  nodes, your task is to check if it's possible to partition the tree to two trees which have the equal sum of values after removing  exactly  one edge on the original tree. Example 1: Input: 5 / \ 10 10 / \ 2 3 Output: True Explanation: 5 / 10 Sum: 15 10 / \ 2 3 Sum: 15 Example 2: Input: 1 / \ 2 10 / \ 2 20 Output: False Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree. Note: The range of tree node value is in the range of [-100000, 100000]. 1 <= n <= 10000 Analysis: Get all sums, check whether the collections of sums contains totalSum/2. Do not include total sum to set of sums, if the total sum is 0, it will qualify.  Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public boolean checkEqualTree(TreeNode ro...