刷题记录

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: You have a number of envelopes with widths and heights given as a pair of integers  (w, h) . One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you Russian doll? (put one inside other) Example: Given envelopes =  [[5,4],[6,4],[6,7],[2,3]] , the maximum number of envelopes you can Russian doll is  3  ([2,3] => [5,4] => [6,7]). Analysis: Two dimensional Longest increasing sub sequence. Convert this problem to 1D LIS. Sort the envelopes by width. So height becomes the 1D LIS. But if we have [3, 3], [3, 4], the former doll can not fit into the latter one. If there is a tie on width, sort height in desc order.  Time:  O(nlogn). Solution: class Solution { public int maxEnvelopes ( int [][] envelopes) { if (envelopes == null || envelopes . length == 0 || envelopes[ 0 ...

Problem: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note:  The input string may contain letters other than the parentheses  (  and  ) . Example 1: Input: "()())()" Output: ["()()()", "(())()"] Example 2: Input: "(a)())()" Output: ["(a)()()", "(a())()"] Example 3: Input: ")(" Output: [""] Analysis: 用到reverse那个递归方法暂时没看懂，而且也超出我的能力范围了。现在暂时用left and right count的方法做，容易理解和实现。 1. Count number of left and right invalid parentheses.     '()()))()': right is 2.  ')(': left is 1 and right is 1 2. Typical dfs, remove left first then remove right. '())', only remove the first invalid, even remove dup is the typical dfs way. Solution: The index pass by dfs is i not i + 1, because we removed char at i, then i becomes the prev i + 1. class Solution { public List< String > removeInvali...

Problem: The  n -queens puzzle is the problem of placing  n  queens on an  n × n  chessboard such that no two queens attack each other. Given an integer  n , return all distinct solutions to the  n -queens puzzle. Each solution contains a distinct board configuration of the  n -queens' placement, where  'Q'  and  '.'  both indicate a queen and an empty space respectively. Example: Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above. Analysis: Easy backtracking. 1. With 1d array to store the queens' positions, need to first initialize array to -1. queens[r] = c, c can be 0. 2. If two points are on the diagonal, then the abs of their rows and columns are equal. Solution: class Solution { List...

Problem: Given an input string ( s ) and a pattern ( p ), implement regular expression matching with support for  '.'  and  '*' . '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the  entire  input string (not partial). Note: s  could be empty and contains only lowercase letters  a-z . p  could be empty and contains only lowercase letters  a-z , and characters like  .  or  * . Example 1: Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa" p = "a*" Output: true Explanation:  '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab" p = ".*" Output: true Explanation:  ".*" means "zero or more (*) ...

Problem: You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map: 0  represents the  obstacle  can't be reached. 1  represents the  ground  can be walked through. The place with number bigger than 1  represents a  tree  can be walked through, and this positive number represents the tree's height. You are asked to cut off  all  the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1). You will start from the point (0, 0) and you should output the minimum steps  you need to walk  to cut off all the trees. If you can't cut off all the trees, output -1 in that situation. You are guaranteed that no two  trees  have the same height and there is at least one tree needs to be cut off. Example 1: Input: [ [...

Problem: Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, add spaces in  s  to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = " catsanddog " wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [   "cats and dog",   "cat sand dog" ] Example 2: Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [   "pine apple pen apple",   "pineapple pen apple",   "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog...

Problem: Given a string  s , you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. Example 1: Input: "aacecaaa" Output: "aaacecaaa" Example 2: Input: "abcd" Output: "dcbabcd" Analysis: 最佳答案是KMP算法，在面试中不可能做得出来。 "abcd" reverse it to dcab, check whether reversed string's substring at the index 0 of s. If yes, the shortest palindrome is r.substring(0, i) + s. i  = 0 sub:dcab i = 1 sub: cab i = 2 sub: ab (qualify res = dc + ab + cd) Solution: class Solution { public String shortestPalindrome ( String s) { if (s == null || s . length() == 0 ) return "" ; StringBuilder sb = new StringBuilder (s); String r = sb . reverse() . toString(); for ( int i = 0 ; i < r . length(); i ++ ) { if (s . startsWith(r . substr...

Problem: The demons had captured the princess ( P ) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight ( K ) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health ( negative  integers) upon entering these rooms; other rooms are either empty ( 0's ) or contain magic orbs that increase the knight's health ( positive  integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial h...

Problem: Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either   (3,6) or (6,9) has the maximum difference 3. Example 2: Input: [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0. Analysis: Sort all numbers into buckets. Compare the min value of the current bucket with max value of the previous bucket, we get the possible maximum gap. The size of bucket is calc from (max - min) / length + 1. The numberOfBuckets is calc from (max - min) / bucketSize + 1.  Then we can easily know which bucket a number belongs to by (number - min) / bucketSize.  Not all buckets are filled with numbers, we need to skip those empty buckets when comparing for the maximum gap. Solution: class Solution { ...