eSJ5DeXV

1Leetcode Offline
2------------------------------
3Single Element in a Sorted Array
4------------------------------
5Given a sorted array consisting of only integers where every element
6appears twice except for one element which appears once. Find this
7single element that appears only once.
8Example 1:
9Input: [1,1,2,3,3,4,4,8,8]
10Output: 2
11Example 2:
12Input: [3,3,7,7,10,11,11]
13Output: 10
14Note:
15Your solution should run in O(log n) time and O(1) space.
16------------------------------
17------------------------------
18Coin Change 2
19------------------------------
20You are given coins of different denominations and a total amount of
21money. Write a function to compute the number of combinations that
22make up that amount. You may assume that you have infinite number of
23each kind of coin.
24Note:
25You can assume that
26 0 <= amount <= 5000
27 1 <= coin <= 5000
28 the number of coins is less than 500
29 the answer is guaranteed to fit into signed 32-bit integer
30Example 1:
31Input: amount = 5, coins = [1, 2, 5]
32Output: 4
33Explanation: there are four ways to make up the amount:
345=5
355=2+2+1
365=2+1+1+1
375=1+1+1+1+1
38Example 2:
39Input: amount = 3, coins = [2]
40Output: 0
41Explanation: the amount of 3 cannot be made up just with coins of 2.
42Example 3:
43Input: amount = 10, coins = [10]
44Output: 1
45------------------------------
46------------------------------
47Largest Palindrome Product
48------------------------------
49Find the largest palindrome made from the product of two n-digit
50numbers.
51 Since the result could be very large, you should return the largest
52palindrome mod 1337.
53Example:
54Input: 2
55Output: 987
56Explanation: 99 x 91 = 9009, 9009 % 1337 = 987
57Note:
58The range of n is [1,8].
59------------------------------
60------------------------------
61Find All Duplicates in an Array
62------------------------------
63Given an array of integers, 1 &le; a[i] &le; n (n = size of array),
64some elements appear twice and others appear once.
65Find all the elements that appear twice in this array.
66Could you do it without extra space and in O(n) runtime?
67Example:
68Input:
69[4,3,2,7,8,2,3,1]
70Output:
71[2,3]
72------------------------------
73------------------------------
74Two Sum
75------------------------------
76Given an array of integers, return indices of the two numbers such
77that they add up to a specific target.
78You may assume that each input would have exactly one solution, and
79you may not use the same element twice.
80Example:
81Given nums = [2, 7, 11, 15], target = 9,
82Because nums[0] + nums[1] = 2 + 7 = 9,
83return [0, 1].
84------------------------------
85------------------------------
86Add Two Numbers
87------------------------------
88You are given two non-empty linked lists representing two nonnegative integers. The digits are stored in reverse order and each
89of their nodes contain a single digit. Add the two numbers and
90return it as a linked list.
91You may assume the two numbers do not contain any leading zero,
92except the number 0 itself.
93Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
94Output: 7 -> 0 -> 8
95------------------------------
96------------------------------
97Longest Substring Without Repeating Characters
98------------------------------
99Given a string, find the length of the longest substring without
100repeating characters.
101Examples:
102Given "abcabcbb", the answer is "abc", which the length is 3.
103Given "bbbbb", the answer is "b", with the length of 1.
104Given "pwwkew", the answer is "wke", with the length of 3. Note that 
105the answer must be a substring, "pwke" is a subsequence and not a
106substring.
107------------------------------
108------------------------------
109Median of Two Sorted Arrays
110------------------------------
111There are two sorted arrays nums1 and nums2 of size m and n
112respectively.
113Find the median of the two sorted arrays. The overall run time
114complexity should be O(log (m+n)).
115Example 1:
116nums1 = [1, 3]
117nums2 = [2]
118The median is 2.0
119Example 2:
120nums1 = [1, 2]
121nums2 = [3, 4]
122The median is (2 + 3)/2 = 2.5
123------------------------------
124------------------------------
125Longest Palindromic Substring
126------------------------------
127Given a string s, find the longest palindromic substring in s. You
128may assume that the maximum length of s is 1000.
129Example:
130Input: "babad"
131Output: "bab"
132Note: "aba" is also a valid answer.
133Example:
134Input: "cbbd"
135Output: "bb"
136------------------------------
137------------------------------
138ZigZag Conversion
139------------------------------
140The string "PAYPALISHIRING" is written in a zigzag pattern on a
141given number of rows like this: (you may want to display this
142pattern in a fixed font for better legibility)
143P A H N
144A P L S I I G
145Y I R
146And then read line by line: "PAHNAPLSIIGYIR"
147Write the code that will take a string and make this conversion
148given a number of rows:
149string convert(string text, int nRows);
150convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
151------------------------------
152------------------------------
153Reverse Integer
154------------------------------
155Reverse digits of an integer.
156Example1: x = 123, return 321
157Example2: x = -123, return -321
158click to show spoilers.
159Have you thought about this?
160Here are some good questions to ask before coding. Bonus points for
161you if you have already thought through this!
162If the integer's last digit is 0, what should the output be? ie,
163cases such as 10, 100.
164Did you notice that the reversed integer might overflow? Assume the
165input is a 32-bit integer, then the reverse of 1000000003 overflows.
166How should you handle such cases?
167For the purpose of this problem, assume that your function returns 0
168when the reversed integer overflows.
169Note:
170The input is assumed to be a 32-bit signed integer. Your function
171should return 0 when the reversed integer overflows.
172------------------------------
173------------------------------
174String to Integer (atoi)
175------------------------------
176Implement atoi to convert a string to an integer.
177Hint: Carefully consider all possible input cases. If you want a
178challenge, please do not see below and ask yourself what are the
179possible input cases.
180Notes:
181It is intended for this problem to be specified vaguely (ie, no
182given input specs). You are responsible to gather all the input
183requirements up front.
184Update (2015-02-10):
185The signature of the C++ function had been updated. If you still see
186your function signature accepts a const char * argument, please
187click the reload button to reset your code definition.
188spoilers alert... click to show requirements for atoi.
189Requirements for atoi:
190The function first discards as many whitespace characters as
191necessary until the first non-whitespace character is found. Then,
192starting from this character, takes an optional initial plus or
193minus sign followed by as many numerical digits as possible, and
194interprets them as a numerical value.
195The string can contain additional characters after those that form
196the integral number, which are ignored and have no effect on the
197behavior of this function.
198If the first sequence of non-whitespace characters in str is not a
199valid integral number, or if no such sequence exists because either
200str is empty or it contains only whitespace characters, no
201conversion is performed.
202If no valid conversion could be performed, a zero value is returned.
203If the correct value is out of the range of representable values,
204INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
205------------------------------
206------------------------------
207Palindrome Number
208------------------------------
209Determine whether an integer is a palindrome. Do this without extra
210space.
211click to show spoilers.
212Some hints:
213Could negative integers be palindromes? (ie, -1)
214If you are thinking of converting the integer to string, note the
215restriction of using extra space.
216You could also try reversing an integer. However, if you have solved
217the problem "Reverse Integer", you know that the reversed integer
218might overflow. How would you handle such case?
219There is a more generic way of solving this problem.
220------------------------------
221------------------------------
222Regular Expression Matching
223------------------------------
224Implement regular expression matching with support for '.' and '*'.
225'.' Matches any single character.
226'*' Matches zero or more of the preceding element.
227The matching should cover the entire input string (not partial).
228The function prototype should be:
229bool isMatch(const char *s, const char *p)
230Some examples:
231isMatch("aa","a") → false
232isMatch("aa","aa") → true
233isMatch("aaa","aa") → false
234isMatch("aa", "a*") → true
235isMatch("aa", ".*") → true
236isMatch("ab", ".*") → true
237isMatch("aab", "c*a*b") → true
238------------------------------
239------------------------------
240Container With Most Water
241------------------------------
242Given n non-negative integers a1, a2, ..., an, where each represents
243a point at coordinate (i, ai). n vertical lines are drawn such that
244the two endpoints of line i is at (i, ai) and (i, 0). Find two
245lines, which together with x-axis forms a container, such that the
246container contains the most water.
247Note: You may not slant the container and n is at least 2.
248------------------------------
249------------------------------
250Integer to Roman
251------------------------------
252Given an integer, convert it to a roman numeral.
253Input is guaranteed to be within the range from 1 to 3999.
254------------------------------
255------------------------------
256Roman to Integer
257------------------------------
258Given a roman numeral, convert it to an integer.
259Input is guaranteed to be within the range from 1 to 3999.
260------------------------------
261------------------------------
262Longest Common Prefix
263------------------------------
264Write a function to find the longest common prefix string amongst an
265array of strings.
266------------------------------
267------------------------------
2683Sum
269------------------------------
270Given an array S of n integers, are there elements a, b, c in S such
271that a + b + c = 0? Find all unique triplets in the array which
272gives the sum of zero.
273Note: The solution set must not contain duplicate triplets.
274For example, given array S = [-1, 0, 1, 2, -1, -4],
275A solution set is:
276[
277 [-1, 0, 1],
278 [-1, -1, 2]
279]
280------------------------------
281------------------------------
2823Sum Closest
283------------------------------
284Given an array S of n integers, find three integers in S such that
285the sum is closest to a given number, target. Return the sum of the
286three integers. You may assume that each input would have exactly
287one solution.
288 For example, given array S = {-1 2 1 -4}, and target = 1.
289 The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
290------------------------------
291------------------------------
292Letter Combinations of a Phone Number
293------------------------------
294Given a digit string, return all possible letter combinations that
295the number could represent.
296A mapping of digit to letters (just like on the telephone buttons)
297is given below.
298Input:Digit string "23"
299Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
300Note:
301Although the above answer is in lexicographical order, your answer
302could be in any order you want.
303------------------------------
304------------------------------
3054Sum
306------------------------------
307Given an array S of n integers, are there elements a, b, c, and d in
308S such that a + b + c + d = target? Find all unique quadruplets in
309the array which gives the sum of target.
310Note: The solution set must not contain duplicate quadruplets.
311For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
312A solution set is:
313[
314 [-1, 0, 0, 1],
315 [-2, -1, 1, 2],
316 [-2, 0, 0, 2]
317]
318------------------------------
319------------------------------
320Remove Nth Node From End of List
321------------------------------
322Given a linked list, remove the nth node from the end of list and
323return its head.
324For example,
325 Given linked list: 1->2->3->4->5, and n = 2.
326 After removing the second node from the end, the linked list
327becomes 1->2->3->5.
328Note:
329Given n will always be valid.
330Try to do this in one pass.
331------------------------------
332------------------------------
333Valid Parentheses
334------------------------------
335Given a string containing just the characters '(', ')', '{', '}',
336'[' and ']', determine if the input string is valid.
337The brackets must close in the correct order, "()" and "()[]{}" are
338all valid but "(]" and "([)]" are not.
339------------------------------
340------------------------------
341Merge Two Sorted Lists
342------------------------------
343Merge two sorted linked lists and return it as a new list. The new
344list should be made by splicing together the nodes of the first two
345lists.
346------------------------------
347------------------------------
348Generate Parentheses
349------------------------------
350Given n pairs of parentheses, write a function to generate all
351combinations of well-formed parentheses.
352For example, given n = 3, a solution set is:
353[
354 "((()))",
355 "(()())",
356 "(())()",
357 "()(())",
358 "()()()"
359]
360------------------------------
361------------------------------
362Merge k Sorted Lists
363------------------------------
364Merge k sorted linked lists and return it as one sorted list.
365Analyze and describe its complexity.
366------------------------------
367------------------------------
368Swap Nodes in Pairs
369------------------------------
370Given a linked list, swap every two adjacent nodes and return its
371head.
372For example,
373Given 1->2->3->4, you should return the list as 2->1->4->3.
374Your algorithm should use only constant space. You may not modify
375the values in the list, only nodes itself can be changed.
376------------------------------
377------------------------------
378Reverse Nodes in k-Group
379------------------------------
380Given a linked list, reverse the nodes of a linked list k at a time
381and return its modified list.
382k is a positive integer and is less than or equal to the length of
383the linked list. If the number of nodes is not a multiple of k then
384left-out nodes in the end should remain as it is.
385You may not alter the values in the nodes, only nodes itself may be
386changed.
387Only constant memory is allowed.
388For example,
389Given this linked list: 1->2->3->4->5
390For k = 2, you should return: 2->1->4->3->5
391For k = 3, you should return: 3->2->1->4->5
392------------------------------
393------------------------------
394Remove Duplicates from Sorted Array
395------------------------------
396Given a sorted array, remove the duplicates in place such that each
397element appear only once and return the new length.
398Do not allocate extra space for another array, you must do this in
399place with constant memory.
400For example,
401Given input array nums = [1,1,2],
402Your function should return length = 2, with the first two elements
403of nums being 1 and 2 respectively. It doesn't matter what you leave
404beyond the new length.
405------------------------------
406------------------------------
407Remove Element
408------------------------------
409Given an array and a value, remove all instances of that value in
410place and return the new length.
411Do not allocate extra space for another array, you must do this in
412place with constant memory.
413The order of elements can be changed. It doesn't matter what you
414leave beyond the new length.
415Example:
416Given input array nums = [3,2,2,3], val = 3
417Your function should return length = 2, with the first two elements
418of nums being 2.
419 Try two pointers.
420 Did you use the property of "the order of elements can be
421changed"?
422 What happens when the elements to remove are rare?
423------------------------------
424------------------------------
425Implement strStr()
426------------------------------
427Implement strStr().
428Returns the index of the first occurrence of needle in haystack, or
429-1 if needle is not part of haystack.
430------------------------------
431------------------------------
432Divide Two Integers
433------------------------------
434Divide two integers without using multiplication, division and mod
435operator.
436If it is overflow, return MAX_INT.
437------------------------------
438------------------------------
439Substring with Concatenation of All Words
440------------------------------
441You are given a string, s, and a list of words, words, that are all
442of the same length. Find all starting indices of substring(s) in s
443that is a concatenation of each word in words exactly once and
444without any intervening characters.
445For example, given:
446s: "barfoothefoobarman"
447words: ["foo", "bar"]
448You should return the indices: [0,9].
449(order does not matter).
450------------------------------
451------------------------------
452Next Permutation
453------------------------------
454Implement next permutation, which rearranges numbers into the
455lexicographically next greater permutation of numbers.
456If such arrangement is not possible, it must rearrange it as the
457lowest possible order (ie, sorted in ascending order).
458The replacement must be in-place, do not allocate extra memory.
459Here are some examples. Inputs are in the left-hand column and its
460corresponding outputs are in the right-hand column.
4611,2,3 &#8594; 1,3,2
4623,2,1 &#8594; 1,2,3
4631,1,5 &#8594; 1,5,1
464------------------------------
465------------------------------
466Longest Valid Parentheses
467------------------------------
468Given a string containing just the characters '(' and ')', find the
469length of the longest valid (well-formed) parentheses substring.
470For "(()", the longest valid parentheses substring is "()", which
471has length = 2.
472Another example is ")()())", where the longest valid parentheses
473substring is "()()", which has length = 4.
474------------------------------
475------------------------------
476Search in Rotated Sorted Array
477------------------------------
478Suppose an array sorted in ascending order is rotated at some pivot
479unknown to you beforehand.
480(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
481You are given a target value to search. If found in the array return
482its index, otherwise return -1.
483You may assume no duplicate exists in the array.
484------------------------------
485------------------------------
486Search for a Range
487------------------------------
488Given an array of integers sorted in ascending order, find the
489starting and ending position of a given target value.
490Your algorithm's runtime complexity must be in the order of O(log
491n).
492If the target is not found in the array, return [-1, -1].
493For example,
494Given [5, 7, 7, 8, 8, 10] and target value 8,
495return [3, 4].
496------------------------------
497------------------------------
498Search Insert Position
499------------------------------
500Given a sorted array and a target value, return the index if the
501target is found. If not, return the index where it would be if it
502were inserted in order.
503You may assume no duplicates in the array.
504Here are few examples.
505[1,3,5,6], 5 &#8594; 2
506[1,3,5,6], 2 &#8594; 1
507[1,3,5,6], 7 &#8594; 4
508[1,3,5,6], 0 &#8594; 0
509------------------------------
510------------------------------
511Valid Sudoku
512------------------------------
513Determine if a Sudoku is valid, according to: Sudoku Puzzles - The
514Rules.
515The Sudoku board could be partially filled, where empty cells are
516filled with the character '.'.
517A partially filled sudoku which is valid.
518Note:
519A valid Sudoku board (partially filled) is not necessarily solvable.
520Only the filled cells need to be validated.
521------------------------------
522------------------------------
523Sudoku Solver
524------------------------------
525Write a program to solve a Sudoku puzzle by filling the empty cells.
526Empty cells are indicated by the character '.'.
527You may assume that there will be only one unique solution.
528A sudoku puzzle...
529...and its solution numbers marked in red.
530------------------------------
531------------------------------
532Count and Say
533------------------------------
534The count-and-say sequence is the sequence of integers beginning as
535follows:
5361, 11, 21, 1211, 111221, ...
5371 is read off as "one 1" or 11.
53811 is read off as "two 1s" or 21.
53921 is read off as "one 2, then one 1" or 1211.
540Given an integer n, generate the nth sequence.
541Note: The sequence of integers will be represented as a string.
542------------------------------
543------------------------------
544Combination Sum
545------------------------------
546Given a set of candidate numbers (C) (without duplicates) and a
547target number (T), find all unique combinations in C where the
548candidate numbers sums to T.
549The same repeated number may be chosen from C unlimited number of
550times.
551Note:
552All numbers (including target) will be positive integers.
553The solution set must not contain duplicate combinations.
554For example, given candidate set [2, 3, 6, 7] and target 7,
555A solution set is:
556[
557 [7],
558 [2, 2, 3]
559]
560------------------------------
561------------------------------
562Combination Sum II
563------------------------------
564Given a collection of candidate numbers (C) and a target number (T),
565find all unique combinations in C where the candidate numbers sums
566to T.
567Each number in C may only be used once in the combination.
568Note:
569All numbers (including target) will be positive integers.
570The solution set must not contain duplicate combinations.
571For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target
5728,
573A solution set is:
574[
575 [1, 7],
576 [1, 2, 5],
577 [2, 6],
578 [1, 1, 6]
579]
580------------------------------
581------------------------------
582First Missing Positive
583------------------------------
584Given an unsorted integer array, find the first missing positive
585integer.
586For example,
587Given [1,2,0] return 3,
588and [3,4,-1,1] return 2.
589Your algorithm should run in O(n) time and uses constant space.
590------------------------------
591------------------------------
592Trapping Rain Water
593------------------------------
594Given n non-negative integers representing an elevation map where
595the width of each bar is 1, compute how much water it is able to
596trap after raining.
597For example,
598Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
599The above elevation map is represented by array
600[0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue
601section) are being trapped. Thanks Marcos for contributing this
602image!
603------------------------------
604------------------------------
605Multiply Strings
606------------------------------
607Given two non-negative integers num1 and num2 represented as
608strings, return the product of num1 and num2.
609Note:
610The length of both num1 and num2 is < 110.
611Both num1 and num2 contains only digits 0-9.
612Both num1 and num2 does not contain any leading zero.
613You must not use any built-in BigInteger library or convert the
614inputs to integer directly.
615------------------------------
616------------------------------
617Wildcard Matching
618------------------------------
619Implement wildcard pattern matching with support for '?' and '*'.
620'?' Matches any single character.
621'*' Matches any sequence of characters (including the empty
622sequence).
623The matching should cover the entire input string (not partial).
624The function prototype should be:
625bool isMatch(const char *s, const char *p)
626Some examples:
627isMatch("aa","a") → false
628isMatch("aa","aa") → true
629isMatch("aaa","aa") → false
630isMatch("aa", "*") → true
631isMatch("aa", "a*") → true
632isMatch("ab", "?*") → true
633isMatch("aab", "c*a*b") → false
634------------------------------
635------------------------------
636Jump Game II
637------------------------------
638Given an array of non-negative integers, you are initially
639positioned at the first index of the array.
640Each element in the array represents your maximum jump length at
641that position.
642Your goal is to reach the last index in the minimum number of jumps.
643For example:
644Given array A = [2,3,1,1,4]
645The minimum number of jumps to reach the last index is 2. (Jump 1
646step from index 0 to 1, then 3 steps to the last index.)
647Note:
648You can assume that you can always reach the last index.
649------------------------------
650------------------------------
651Permutations
652------------------------------
653Given a collection of distinct numbers, return all possible
654permutations.
655For example,
656[1,2,3] have the following permutations:
657[
658 [1,2,3],
659 [1,3,2],
660 [2,1,3],
661 [2,3,1],
662 [3,1,2],
663 [3,2,1]
664]
665------------------------------
666------------------------------
667Permutations II
668------------------------------
669Given a collection of numbers that might contain duplicates, return
670all possible unique permutations.
671For example,
672[1,1,2] have the following unique permutations:
673[
674 [1,1,2],
675 [1,2,1],
676 [2,1,1]
677]
678------------------------------
679------------------------------
680Rotate Image
681------------------------------
682You are given an n x n 2D matrix representing an image.
683Rotate the image by 90 degrees (clockwise).
684Follow up:
685Could you do this in-place?
686------------------------------
687------------------------------
688Group Anagrams
689------------------------------
690Given an array of strings, group anagrams together.
691For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
692Return:
693[
694 ["ate", "eat","tea"],
695 ["nat","tan"],
696 ["bat"]
697]
698Note: All inputs will be in lower-case.
699------------------------------
700------------------------------
701Pow(x, n)
702------------------------------
703Implement pow(x, n).
704------------------------------
705------------------------------
706N-Queens
707------------------------------
708The n-queens puzzle is the problem of placing n queens on an n×n
709chessboard such that no two queens attack each other.
710Given an integer n, return all distinct solutions to the n-queens
711puzzle.
712Each solution contains a distinct board configuration of the nqueens' placement, where 'Q' and '.' both indicate a queen and an
713empty space respectively.
714For example,
715There exist two distinct solutions to the 4-queens puzzle:
716[
717 [".Q..", // Solution 1
718 "...Q",
719 "Q...",
720 "..Q."],
721 ["..Q.", // Solution 2
722 "Q...",
723 "...Q",
724 ".Q.."]
725]
726------------------------------
727------------------------------
728N-Queens II
729------------------------------
730Follow up for N-Queens problem.
731Now, instead outputting board configurations, return the total
732number of distinct solutions.
733------------------------------
734------------------------------
735Maximum Subarray
736------------------------------
737Find the contiguous subarray within an array (containing at least
738one number) which has the largest sum.
739For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
740the contiguous subarray [4,-1,2,1] has the largest sum = 6.
741click to show more practice.
742More practice:
743If you have figured out the O(n) solution, try coding another
744solution using the divide and conquer approach, which is more
745subtle.
746------------------------------
747------------------------------
748Spiral Matrix
749------------------------------
750Given a matrix of m x n elements (m rows, n columns), return all
751elements of the matrix in spiral order.
752For example,
753Given the following matrix:
754[
755 [ 1, 2, 3 ],
756 [ 4, 5, 6 ],
757 [ 7, 8, 9 ]
758]
759You should return [1,2,3,6,9,8,7,4,5].
760------------------------------
761------------------------------
762Jump Game
763------------------------------
764Given an array of non-negative integers, you are initially
765positioned at the first index of the array.
766Each element in the array represents your maximum jump length at
767that position.
768Determine if you are able to reach the last index.
769For example:
770A = [2,3,1,1,4], return true.
771A = [3,2,1,0,4], return false.
772------------------------------
773------------------------------
774Merge Intervals
775------------------------------
776Given a collection of intervals, merge all overlapping intervals.
777For example,
778Given [1,3],[2,6],[8,10],[15,18],
779return [1,6],[8,10],[15,18].
780------------------------------
781------------------------------
782Insert Interval
783------------------------------
784Given a set of non-overlapping intervals, insert a new interval into
785the intervals (merge if necessary).
786You may assume that the intervals were initially sorted according to
787their start times.
788Example 1:
789Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],
790[6,9].
791Example 2:
792Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as
793[1,2],[3,10],[12,16].
794This is because the new interval [4,9] overlaps with [3,5],[6,7],
795[8,10].
796------------------------------
797------------------------------
798Length of Last Word
799------------------------------
800Given a string s consists of upper/lower-case alphabets and empty
801space characters ' ', return the length of last word in the string.
802If the last word does not exist, return 0.
803Note: A word is defined as a character sequence consists of nonspace characters only.
804For example,
805Given s = "Hello World",
806return 5.
807------------------------------
808------------------------------
809Spiral Matrix II
810------------------------------
811Given an integer n, generate a square matrix filled with elements
812from 1 to n2 in spiral order.
813For example,
814Given n = 3,
815You should return the following matrix:
816[
817 [ 1, 2, 3 ],
818 [ 8, 9, 4 ],
819 [ 7, 6, 5 ]
820]
821------------------------------
822------------------------------
823Permutation Sequence
824------------------------------
825The set [1,2,3,&#8230;,n] contains a total of n! unique
826permutations.
827By listing and labeling all of the permutations in order,
828We get the following sequence (ie, for n = 3):
829"123"
830"132"
831"213"
832"231"
833"312"
834"321"
835Given n and k, return the kth permutation sequence.
836Note: Given n will be between 1 and 9 inclusive.
837------------------------------
838------------------------------
839Rotate List
840------------------------------
841Given a list, rotate the list to the right by k places, where k is
842non-negative.
843For example:
844Given 1->2->3->4->5->NULL and k = 2,
845return 4->5->1->2->3->NULL.
846------------------------------
847------------------------------
848Unique Paths
849------------------------------
850A robot is located at the top-left corner of a m x n grid (marked
851'Start' in the diagram below).
852The robot can only move either down or right at any point in time.
853The robot is trying to reach the bottom-right corner of the grid
854(marked 'Finish' in the diagram below).
855How many possible unique paths are there?
856Above is a 3 x 7 grid. How many possible unique paths are there?
857Note: m and n will be at most 100.
858------------------------------
859------------------------------
860Unique Paths II
861------------------------------
862Follow up for "Unique Paths":
863Now consider if some obstacles are added to the grids. How many
864unique paths would there be?
865An obstacle and empty space is marked as 1 and 0 respectively in the
866grid.
867For example,
868There is one obstacle in the middle of a 3x3 grid as illustrated
869below.
870[
871 [0,0,0],
872 [0,1,0],
873 [0,0,0]
874]
875The total number of unique paths is 2.
876Note: m and n will be at most 100.
877------------------------------
878------------------------------
879Minimum Path Sum
880------------------------------
881Given a m x n grid filled with non-negative numbers, find a path
882from top left to bottom right which minimizes the sum of all numbers
883along its path.
884Note: You can only move either down or right at any point in time.
885------------------------------
886------------------------------
887Valid Number
888------------------------------
889Validate if a given string is numeric.
890Some examples:
891"0" => true
892" 0.1 " => true
893"abc" => false
894"1 a" => false
895"2e10" => true
896Note: It is intended for the problem statement to be ambiguous. You
897should gather all requirements up front before implementing one.
898Update (2015-02-10):
899The signature of the C++ function had been updated. If you still see
900your function signature accepts a const char * argument, please
901click the reload button to reset your code definition.
902------------------------------
903------------------------------
904Plus One
905------------------------------
906Given a non-negative integer represented as a non-empty array of
907digits, plus one to the integer.
908You may assume the integer do not contain any leading zero, except
909the number 0 itself.
910The digits are stored such that the most significant digit is at the
911head of the list.
912------------------------------
913------------------------------
914Add Binary
915------------------------------
916Given two binary strings, return their sum (also a binary string).
917For example,
918a = "11"
919b = "1"
920Return "100".
921------------------------------
922------------------------------
923Text Justification
924------------------------------
925Given an array of words and a length L, format the text such that
926each line has exactly L characters and is fully (left and right)
927justified.
928You should pack your words in a greedy approach; that is, pack as
929many words as you can in each line. Pad extra spaces ' ' when
930necessary so that each line has exactly L characters.
931Extra spaces between words should be distributed as evenly as
932possible. If the number of spaces on a line do not divide evenly
933between words, the empty slots on the left will be assigned more
934spaces than the slots on the right.
935For the last line of text, it should be left justified and no extra
936space is inserted between words.
937For example,
938words: ["This", "is", "an", "example", "of", "text",
939"justification."]
940L: 16.
941Return the formatted lines as:
942[
943 "This is an",
944 "example of text",
945 "justification. "
946]
947Note: Each word is guaranteed not to exceed L in length.
948click to show corner cases.
949Corner Cases:
950A line other than the last line might contain only one word. What
951should you do in this case?
952In this case, that line should be left-justified.
953------------------------------
954------------------------------
955Sqrt(x)
956------------------------------
957Implement int sqrt(int x).
958Compute and return the square root of x.
959------------------------------
960------------------------------
961Climbing Stairs
962------------------------------
963You are climbing a stair case. It takes n steps to reach to the top.
964Each time you can either climb 1 or 2 steps. In how many distinct
965ways can you climb to the top?
966Note: Given n will be a positive integer.
967------------------------------
968------------------------------
969Simplify Path
970------------------------------
971Given an absolute path for a file (Unix-style), simplify it.
972For example,
973path = "/home/", => "/home"
974path = "/a/./b/../../c/", => "/c"
975click to show corner cases.
976Corner Cases:
977Did you consider the case where path = "/../"?
978In this case, you should return "/".
979Another corner case is the path might contain multiple slashes '/'
980together, such as "/home//foo/".
981In this case, you should ignore redundant slashes and return "/home/
982foo".
983------------------------------
984------------------------------
985Edit Distance
986------------------------------
987Given two words word1 and word2, find the minimum number of steps
988required to convert word1 to word2. (each operation is counted as 1
989step.)
990You have the following 3 operations permitted on a word:
991a) Insert a character
992b) Delete a character
993c) Replace a character
994------------------------------
995------------------------------
996Set Matrix Zeroes
997------------------------------
998Given a m x n matrix, if an element is 0, set its entire row and
999column to 0. Do it in place.
1000click to show follow up.
1001Follow up:
1002Did you use extra space?
1003A straight forward solution using O(mn) space is probably a bad
1004idea.
1005A simple improvement uses O(m + n) space, but still not the best
1006solution.
1007Could you devise a constant space solution?
1008------------------------------
1009------------------------------
1010Search a 2D Matrix
1011------------------------------
1012Write an efficient algorithm that searches for a value in an m x n
1013matrix. This matrix has the following properties:
1014Integers in each row are sorted from left to right.
1015The first integer of each row is greater than the last integer of
1016the previous row.
1017For example,
1018Consider the following matrix:
1019[
1020 [1, 3, 5, 7],
1021 [10, 11, 16, 20],
1022 [23, 30, 34, 50]
1023]
1024Given target = 3, return true.
1025------------------------------
1026------------------------------
1027Sort Colors
1028------------------------------
1029Given an array with n objects colored red, white or blue, sort them
1030so that objects of the same color are adjacent, with the colors in
1031the order red, white and blue.
1032Here, we will use the integers 0, 1, and 2 to represent the color
1033red, white, and blue respectively.
1034Note:
1035You are not suppose to use the library's sort function for this
1036problem.
1037click to show follow up.
1038Follow up:
1039A rather straight forward solution is a two-pass algorithm using
1040counting sort.
1041First, iterate the array counting number of 0's, 1's, and 2's, then
1042overwrite array with total number of 0's, then 1's and followed by
10432's.
1044Could you come up with an one-pass algorithm using only constant
1045space?
1046------------------------------
1047------------------------------
1048Minimum Window Substring
1049------------------------------
1050Given a string S and a string T, find the minimum window in S which
1051will contain all the characters in T in complexity O(n).
1052For example,
1053S = "ADOBECODEBANC"
1054T = "ABC"
1055Minimum window is "BANC".
1056Note:
1057If there is no such window in S that covers all characters in T,
1058return the empty string "".
1059If there are multiple such windows, you are guaranteed that there
1060will always be only one unique minimum window in S.
1061------------------------------
1062------------------------------
1063Combinations
1064------------------------------
1065Given two integers n and k, return all possible combinations of k
1066numbers out of 1 ... n.
1067For example,
1068If n = 4 and k = 2, a solution is:
1069[
1070 [2,4],
1071 [3,4],
1072 [2,3],
1073 [1,2],
1074 [1,3],
1075 [1,4],
1076]
1077------------------------------
1078------------------------------
1079Subsets
1080------------------------------
1081Given a set of distinct integers, nums, return all possible subsets.
1082Note: The solution set must not contain duplicate subsets.
1083For example,
1084If nums = [1,2,3], a solution is:
1085[
1086 [3],
1087 [1],
1088 [2],
1089 [1,2,3],
1090 [1,3],
1091 [2,3],
1092 [1,2],
1093 []
1094]
1095------------------------------
1096------------------------------
1097Word Search
1098------------------------------
1099Given a 2D board and a word, find if the word exists in the grid.
1100The word can be constructed from letters of sequentially adjacent
1101cell, where "adjacent" cells are those horizontally or vertically
1102neighboring. The same letter cell may not be used more than once.
1103For example,
1104Given board =
1105[
1106 ['A','B','C','E'],
1107 ['S','F','C','S'],
1108 ['A','D','E','E']
1109]
1110word = "ABCCED", -> returns true,
1111word = "SEE", -> returns true,
1112word = "ABCB", -> returns false.
1113------------------------------
1114------------------------------
1115Remove Duplicates from Sorted Array II
1116------------------------------
1117Follow up for "Remove Duplicates":
1118What if duplicates are allowed at most twice?
1119For example,
1120Given sorted array nums = [1,1,1,2,2,3],
1121Your function should return length = 5, with the first five elements
1122of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave
1123beyond the new length.
1124------------------------------
1125------------------------------
1126Search in Rotated Sorted Array II
1127------------------------------
1128Follow up for "Search in Rotated Sorted Array":
1129What if duplicates are allowed?
1130Would this affect the run-time complexity? How and why?
1131Suppose an array sorted in ascending order is rotated at some pivot
1132unknown to you beforehand.
1133(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
1134Write a function to determine if a given target is in the array.
1135The array may contain duplicates.
1136------------------------------
1137------------------------------
1138Remove Duplicates from Sorted List II
1139------------------------------
1140Given a sorted linked list, delete all nodes that have duplicate
1141numbers, leaving only distinct numbers from the original list.
1142For example,
1143Given 1->2->3->3->4->4->5, return 1->2->5.
1144Given 1->1->1->2->3, return 2->3.
1145------------------------------
1146------------------------------
1147Remove Duplicates from Sorted List
1148------------------------------
1149Given a sorted linked list, delete all duplicates such that each
1150element appear only once.
1151For example,
1152Given 1->1->2, return 1->2.
1153Given 1->1->2->3->3, return 1->2->3.
1154------------------------------
1155------------------------------
1156Largest Rectangle in Histogram
1157------------------------------
1158Given n non-negative integers representing the histogram's bar
1159height where the width of each bar is 1, find the area of largest
1160rectangle in the histogram.
1161Above is a histogram where width of each bar is 1, given height =
1162[2,1,5,6,2,3].
1163The largest rectangle is shown in the shaded area, which has area =
116410 unit.
1165For example,
1166Given heights = [2,1,5,6,2,3],
1167return 10.
1168------------------------------
1169------------------------------
1170Maximal Rectangle
1171------------------------------
1172Given a 2D binary matrix filled with 0's and 1's, find the largest
1173rectangle containing only 1's and return its area.
1174For example, given the following matrix:
11751 0 1 0 0
11761 0 1 1 1
11771 1 1 1 1
11781 0 0 1 0
1179Return 6.
1180------------------------------
1181------------------------------
1182Partition List
1183------------------------------
1184Given a linked list and a value x, partition it such that all nodes
1185less than x come before nodes greater than or equal to x.
1186You should preserve the original relative order of the nodes in each
1187of the two partitions.
1188For example,
1189Given 1->4->3->2->5->2 and x = 3,
1190return 1->2->2->4->3->5.
1191------------------------------
1192------------------------------
1193Scramble String
1194------------------------------
1195Given a string s1, we may represent it as a binary tree by
1196partitioning it to two non-empty substrings recursively.
1197Below is one possible representation of s1 = "great":
1198 great
1199 / \
1200 gr eat
1201 / \ / \
1202g r e at
1203 / \
1204 a t
1205To scramble the string, we may choose any non-leaf node and swap its
1206two children.
1207For example, if we choose the node "gr" and swap its two children,
1208it produces a scrambled string "rgeat".
1209 rgeat
1210 / \
1211 rg eat
1212 / \ / \
1213r g e at
1214 / \
1215 a t
1216We say that "rgeat" is a scrambled string of "great".
1217Similarly, if we continue to swap the children of nodes "eat" and
1218"at", it produces a scrambled string "rgtae".
1219 rgtae
1220 / \
1221 rg tae
1222 / \ / \
1223r g ta e
1224 / \
1225 t a
1226We say that "rgtae" is a scrambled string of "great".
1227Given two strings s1 and s2 of the same length, determine if s2 is a 
1228scrambled string of s1.
1229------------------------------
1230------------------------------
1231Merge Sorted Array
1232------------------------------
1233Given two sorted integer arrays nums1 and nums2, merge nums2 into
1234nums1 as one sorted array.
1235Note:
1236You may assume that nums1 has enough space (size that is greater or
1237equal to m + n) to hold additional elements from nums2. The number
1238of elements initialized in nums1 and nums2 are m and n respectively.
1239------------------------------
1240------------------------------
1241Gray Code
1242------------------------------
1243The gray code is a binary numeral system where two successive values
1244differ in only one bit.
1245Given a non-negative integer n representing the total number of bits
1246in the code, print the sequence of gray code. A gray code sequence
1247must begin with 0.
1248For example, given n = 2, return [0,1,3,2]. Its gray code sequence
1249is:
125000 - 0
125101 - 1
125211 - 3
125310 - 2
1254Note:
1255For a given n, a gray code sequence is not uniquely defined.
1256For example, [0,2,3,1] is also a valid gray code sequence according
1257to the above definition.
1258For now, the judge is able to judge based on one instance of gray
1259code sequence. Sorry about that.
1260------------------------------
1261------------------------------
1262Subsets II
1263------------------------------
1264Given a collection of integers that might contain duplicates, nums,
1265return all possible subsets.
1266Note: The solution set must not contain duplicate subsets.
1267For example,
1268If nums = [1,2,2], a solution is:
1269[
1270 [2],
1271 [1],
1272 [1,2,2],
1273 [2,2],
1274 [1,2],
1275 []
1276]
1277------------------------------
1278------------------------------
1279Decode Ways
1280------------------------------
1281A message containing letters from A-Z is being encoded to numbers
1282using the following mapping:
1283'A' -> 1
1284'B' -> 2
1285...
1286'Z' -> 26
1287Given an encoded message containing digits, determine the total
1288number of ways to decode it.
1289For example,
1290Given encoded message "12",
1291it could be decoded as "AB" (1 2) or "L" (12).
1292The number of ways decoding "12" is 2.
1293------------------------------
1294------------------------------
1295Reverse Linked List II
1296------------------------------
1297Reverse a linked list from position m to n. Do it in-place and in
1298one-pass.
1299For example:
1300Given 1->2->3->4->5->NULL, m = 2 and n = 4,
1301return 1->4->3->2->5->NULL.
1302Note:
1303Given m, n satisfy the following condition:
13041 ≤ m ≤ n ≤ length of list.
1305------------------------------
1306------------------------------
1307Restore IP Addresses
1308------------------------------
1309Given a string containing only digits, restore it by returning all
1310possible valid IP address combinations.
1311For example:
1312Given "25525511135",
1313return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
1314------------------------------
1315------------------------------
1316Binary Tree Inorder Traversal
1317------------------------------
1318Given a binary tree, return the inorder traversal of its nodes'
1319values.
1320For example:
1321Given binary tree [1,null,2,3],
1322 1
1323 \
1324 2
1325 /
1326 3
1327return [1,3,2].
1328Note: Recursive solution is trivial, could you do it iteratively?
1329------------------------------
1330------------------------------
1331Unique Binary Search Trees II
1332------------------------------
1333Given an integer n, generate all structurally unique BST's (binary
1334search trees) that store values 1...n.
1335For example,
1336Given n = 3, your program should return all 5 unique BST's shown
1337below.
1338 1 3 3 2 1
1339 \ / / / \ \
1340 3 2 1 1 3 2
1341 / / \ \
1342 2 1 2 3
1343------------------------------
1344------------------------------
1345Unique Binary Search Trees
1346------------------------------
1347Given n, how many structurally unique BST's (binary search trees)
1348that store values 1...n?
1349For example,
1350Given n = 3, there are a total of 5 unique BST's.
1351 1 3 3 2 1
1352 \ / / / \ \
1353 3 2 1 1 3 2
1354 / / \ \
1355 2 1 2 3
1356------------------------------
1357------------------------------
1358Interleaving String
1359------------------------------
1360Given s1, s2, s3, find whether s3 is formed by the interleaving of
1361s1 and s2.
1362For example,
1363Given:
1364s1 = "aabcc",
1365s2 = "dbbca",
1366When s3 = "aadbbcbcac", return true.
1367When s3 = "aadbbbaccc", return false.
1368------------------------------
1369------------------------------
1370Validate Binary Search Tree 
1371------------------------------
1372Given a binary tree, determine if it is a valid binary search tree
1373(BST).
1374Assume a BST is defined as follows:
1375The left subtree of a node contains only nodes with keys less than
1376the node's key.
1377The right subtree of a node contains only nodes with keys greater
1378than the node's key.
1379Both the left and right subtrees must also be binary search trees.
1380Example 1:
1381 2
1382 / \
1383 1 3
1384Binary tree [2,1,3], return true.
1385Example 2:
1386 1
1387 / \
1388 2 3
1389Binary tree [1,2,3], return false.
1390------------------------------
1391------------------------------
1392Recover Binary Search Tree
1393------------------------------
1394Two elements of a binary search tree (BST) are swapped by mistake.
1395Recover the tree without changing its structure.
1396Note:
1397A solution using O(n) space is pretty straight forward. Could you
1398devise a constant space solution?
1399------------------------------
1400------------------------------
1401Same Tree
1402------------------------------
1403Given two binary trees, write a function to check if they are equal 
1404or not.
1405Two binary trees are considered equal if they are structurally
1406identical and the nodes have the same value.
1407------------------------------
1408------------------------------
1409Symmetric Tree
1410------------------------------
1411Given a binary tree, check whether it is a mirror of itself (ie,
1412symmetric around its center).
1413For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1414 1
1415 / \
1416 2 2
1417 / \ / \
14183 4 4 3
1419But the following [1,2,2,null,3,null,3] is not:
1420 1
1421 / \
1422 2 2
1423 \ \
1424 3 3
1425Note:
1426Bonus points if you could solve it both recursively and iteratively.
1427------------------------------
1428------------------------------
1429Binary Tree Level Order Traversal
1430------------------------------
1431Given a binary tree, return the level order traversal of its nodes'
1432values. (ie, from left to right, level by level).
1433For example:
1434Given binary tree [3,9,20,null,null,15,7],
1435 3
1436 / \
1437 9 20
1438 / \
1439 15 7
1440return its level order traversal as:
1441[
1442 [3],
1443 [9,20],
1444 [15,7]
1445]
1446------------------------------
1447------------------------------
1448Binary Tree Zigzag Level Order Traversal
1449------------------------------
1450Given a binary tree, return the zigzag level order traversal of its
1451nodes' values. (ie, from left to right, then right to left for the
1452next level and alternate between).
1453For example:
1454Given binary tree [3,9,20,null,null,15,7],
1455 3
1456 / \
1457 9 20
1458 / \
1459 15 7
1460return its zigzag level order traversal as:
1461[
1462 [3],
1463 [20,9],
1464 [15,7]
1465]
1466------------------------------
1467------------------------------
1468Maximum Depth of Binary Tree
1469------------------------------
1470Given a binary tree, find its maximum depth.
1471The maximum depth is the number of nodes along the longest path from
1472the root node down to the farthest leaf node.
1473------------------------------
1474------------------------------
1475Construct Binary Tree from Preorder and Inorder Traversal
1476------------------------------
1477Given preorder and inorder traversal of a tree, construct the binary 
1478tree.
1479Note:
1480You may assume that duplicates do not exist in the tree.
1481------------------------------
1482------------------------------
1483Construct Binary Tree from Inorder and Postorder Traversal
1484------------------------------
1485Given inorder and postorder traversal of a tree, construct the
1486binary tree.
1487Note:
1488You may assume that duplicates do not exist in the tree.
1489------------------------------
1490------------------------------
1491Binary Tree Level Order Traversal II
1492------------------------------
1493Given a binary tree, return the bottom-up level order traversal of
1494its nodes' values. (ie, from left to right, level by level from leaf
1495to root).
1496For example:
1497Given binary tree [3,9,20,null,null,15,7],
1498 3
1499 / \
1500 9 20
1501 / \
1502 15 7
1503return its bottom-up level order traversal as:
1504[
1505 [15,7],
1506 [9,20],
1507 [3]
1508]
1509------------------------------
1510------------------------------
1511Convert Sorted Array to Binary Search Tree
1512------------------------------
1513Given an array where elements are sorted in ascending order, convert
1514it to a height balanced BST.
1515------------------------------
1516------------------------------
1517Convert Sorted List to Binary Search Tree
1518------------------------------
1519Given a singly linked list where elements are sorted in ascending
1520order, convert it to a height balanced BST.
1521------------------------------
1522------------------------------
1523Balanced Binary Tree
1524------------------------------
1525Given a binary tree, determine if it is height-balanced.
1526For this problem, a height-balanced binary tree is defined as a
1527binary tree in which the depth of the two subtrees of every node
1528never differ by more than 1.
1529------------------------------
1530------------------------------
1531Minimum Depth of Binary Tree
1532------------------------------
1533Given a binary tree, find its minimum depth.
1534The minimum depth is the number of nodes along the shortest path
1535from the root node down to the nearest leaf node.
1536------------------------------
1537------------------------------
1538Path Sum
1539------------------------------
1540Given a binary tree and a sum, determine if the tree has a root-toleaf path such that adding up all the values along the path equals
1541the given sum.
1542For example:
1543Given the below binary tree and sum = 22,
1544 5
1545 / \
1546 4 8
1547 / / \
1548 11 13 4
1549 / \ \
1550 7 2 1
1551return true, as there exist a root-to-leaf path 5->4->11->2 which
1552sum is 22.
1553------------------------------
1554------------------------------
1555Path Sum II
1556------------------------------
1557Given a binary tree and a sum, find all root-to-leaf paths where
1558each path's sum equals the given sum.
1559For example:
1560Given the below binary tree and sum = 22,
1561 5
1562 / \
1563 4 8
1564 / / \
1565 11 13 4
1566 / \ / \
1567 7 2 5 1
1568return
1569[
1570 [5,4,11,2],
1571 [5,8,4,5]
1572]
1573------------------------------
1574------------------------------
1575Flatten Binary Tree to Linked List
1576------------------------------
1577Given a binary tree, flatten it to a linked list in-place.
1578For example,
1579Given
1580 1
1581 / \
1582 2 5
1583 / \ \
1584 3 4 6
1585The flattened tree should look like:
1586 1
1587 \
1588 2
1589 \
1590 3
1591 \
1592 4
1593 \
1594 5
1595 \
1596 6
1597click to show hints.
1598Hints:
1599If you notice carefully in the flattened tree, each node's right
1600child points to the next node of a pre-order traversal.
1601------------------------------
1602------------------------------
1603Distinct Subsequences
1604------------------------------
1605Given a string S and a string T, count the number of distinct
1606subsequences of T in S.
1607A subsequence of a string is a new string which is formed from the
1608original string by deleting some (can be none) of the characters
1609without disturbing the relative positions of the remaining
1610characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is
1611not).
1612Here is an example:
1613S = "rabbbit", T = "rabbit"
1614Return 3.
1615------------------------------
1616------------------------------
1617Populating Next Right Pointers in Each Node
1618------------------------------
1619Given a binary tree
1620 struct TreeLinkNode {
1621 TreeLinkNode *left;
1622 TreeLinkNode *right;
1623 TreeLinkNode *next;
1624 }
1625Populate each next pointer to point to its next right node. If there
1626is no next right node, the next pointer should be set to NULL.
1627Initially, all next pointers are set to NULL.
1628Note:
1629You may only use constant extra space.
1630You may assume that it is a perfect binary tree (ie, all leaves are
1631at the same level, and every parent has two children).
1632For example,
1633Given the following perfect binary tree,
1634 1
1635 / \
1636 2 3
1637 / \ / \
1638 4 5 6 7
1639After calling your function, the tree should look like:
1640 1 -> NULL
1641 / \
1642 2 -> 3 -> NULL
1643 / \ / \
1644 4->5->6->7 -> NULL
1645------------------------------
1646------------------------------
1647Populating Next Right Pointers in Each Node II
1648------------------------------
1649Follow up for problem "Populating Next Right Pointers in Each Node".
1650What if the given tree could be any binary tree? Would your previous
1651solution still work?
1652Note:
1653You may only use constant extra space.
1654For example,
1655Given the following binary tree,
1656 1
1657 / \
1658 2 3
1659 / \ \
1660 4 5 7
1661After calling your function, the tree should look like:
1662 1 -> NULL
1663 / \
1664 2 -> 3 -> NULL
1665 / \ \
1666 4-> 5 -> 7 -> NULL
1667------------------------------
1668------------------------------
1669Pascal's Triangle
1670------------------------------
1671Given numRows, generate the first numRows of Pascal's triangle.
1672For example, given numRows = 5,
1673Return
1674[
1675 [1],
1676 [1,1],
1677 [1,2,1],
1678 [1,3,3,1],
1679 [1,4,6,4,1]
1680]
1681------------------------------
1682------------------------------
1683Pascal's Triangle II
1684------------------------------
1685Given an index k, return the kth row of the Pascal's triangle.
1686For example, given k = 3,
1687Return [1,3,3,1].
1688Note:
1689Could you optimize your algorithm to use only O(k) extra space?
1690------------------------------
1691------------------------------
1692Triangle
1693------------------------------
1694Given a triangle, find the minimum path sum from top to bottom. Each
1695step you may move to adjacent numbers on the row below.
1696For example, given the following triangle
1697[
1698 [2],
1699 [3,4],
1700 [6,5,7],
1701 [4,1,8,3]
1702]
1703The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 =
170411).
1705Note:
1706Bonus point if you are able to do this using only O(n) extra space,
1707where n is the total number of rows in the triangle.
1708------------------------------
1709------------------------------
1710Best Time to Buy and Sell Stock
1711------------------------------
1712Say you have an array for which the ith element is the price of a
1713given stock on day i.
1714If you were only permitted to complete at most one transaction (ie,
1715buy one and sell one share of the stock), design an algorithm to
1716find the maximum profit.
1717Example 1:
1718Input: [7, 1, 5, 3, 6, 4]
1719Output: 5
1720max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be
1721larger than buying price)
1722Example 2:
1723Input: [7, 6, 4, 3, 1]
1724Output: 0
1725In this case, no transaction is done, i.e. max profit = 0.
1726------------------------------
1727------------------------------
1728Best Time to Buy and Sell Stock II
1729------------------------------
1730Say you have an array for which the ith element is the price of a
1731given stock on day i.
1732Design an algorithm to find the maximum profit. You may complete as
1733many transactions as you like (ie, buy one and sell one share of the 
1734stock multiple times). However, you may not engage in multiple
1735transactions at the same time (ie, you must sell the stock before
1736you buy again).
1737------------------------------
1738------------------------------
1739Best Time to Buy and Sell Stock III
1740------------------------------
1741Say you have an array for which the ith element is the price of a
1742given stock on day i.
1743Design an algorithm to find the maximum profit. You may complete at
1744most two transactions.
1745Note:
1746You may not engage in multiple transactions at the same time (ie,
1747you must sell the stock before you buy again).
1748------------------------------
1749------------------------------
1750Binary Tree Maximum Path Sum
1751------------------------------
1752Given a binary tree, find the maximum path sum.
1753For this problem, a path is defined as any sequence of nodes from
1754some starting node to any node in the tree along the parent-child
1755connections. The path must contain at least one node and does not
1756need to go through the root.
1757For example:
1758Given the below binary tree,
1759 1
1760 / \
1761 2 3
1762Return 6.
1763------------------------------
1764------------------------------
1765Valid Palindrome
1766------------------------------
1767Given a string, determine if it is a palindrome, considering only
1768alphanumeric characters and ignoring cases.
1769For example,
1770"A man, a plan, a canal: Panama" is a palindrome.
1771"race a car" is not a palindrome.
1772Note:
1773Have you consider that the string might be empty? This is a good
1774question to ask during an interview.
1775For the purpose of this problem, we define empty string as valid
1776palindrome.
1777------------------------------
1778------------------------------
1779Word Ladder II
1780------------------------------
1781Given two words (beginWord and endWord), and a dictionary's word
1782list, find all shortest transformation sequence(s) from beginWord to
1783endWord, such that:
1784Only one letter can be changed at a time
1785Each transformed word must exist in the word list. Note that
1786beginWord is not a transformed word.
1787For example,
1788Given:
1789beginWord = "hit"
1790endWord = "cog"
1791wordList = ["hot","dot","dog","lot","log","cog"]
1792Return
1793 [
1794 ["hit","hot","dot","dog","cog"],
1795 ["hit","hot","lot","log","cog"]
1796 ]
1797Note:
1798Return an empty list if there is no such transformation sequence.
1799All words have the same length.
1800All words contain only lowercase alphabetic characters.
1801You may assume no duplicates in the word list.
1802You may assume beginWord and endWord are non-empty and are not the
1803same.
1804UPDATE (2017/1/20):
1805The wordList parameter had been changed to a list of strings
1806(instead of a set of strings). Please reload the code definition to
1807get the latest changes.
1808------------------------------
1809------------------------------
1810Word Ladder
1811------------------------------
1812Given two words (beginWord and endWord), and a dictionary's word
1813list, find the length of shortest transformation sequence from
1814beginWord to endWord, such that:
1815Only one letter can be changed at a time.
1816Each transformed word must exist in the word list. Note that
1817beginWord is not a transformed word.
1818For example,
1819Given:
1820beginWord = "hit"
1821endWord = "cog"
1822wordList = ["hot","dot","dog","lot","log","cog"]
1823As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -
1824> "cog",
1825return its length 5.
1826Note:
1827Return 0 if there is no such transformation sequence.
1828All words have the same length.
1829All words contain only lowercase alphabetic characters.
1830You may assume no duplicates in the word list.
1831You may assume beginWord and endWord are non-empty and are not the
1832same.
1833UPDATE (2017/1/20):
1834The wordList parameter had been changed to a list of strings
1835(instead of a set of strings). Please reload the code definition to 
1836get the latest changes.
1837------------------------------
1838------------------------------
1839Longest Consecutive Sequence
1840------------------------------
1841Given an unsorted array of integers, find the length of the longest
1842consecutive elements sequence.
1843For example,
1844Given [100, 4, 200, 1, 3, 2],
1845The longest consecutive elements sequence is [1, 2, 3, 4]. Return
1846its length: 4.
1847Your algorithm should run in O(n) complexity.
1848------------------------------
1849------------------------------
1850Sum Root to Leaf Numbers
1851------------------------------
1852Given a binary tree containing digits from 0-9 only, each root-toleaf path could represent a number.
1853An example is the root-to-leaf path 1->2->3 which represents the
1854number 123.
1855Find the total sum of all root-to-leaf numbers.
1856For example,
1857 1
1858 / \
1859 2 3
1860The root-to-leaf path 1->2 represents the number 12.
1861The root-to-leaf path 1->3 represents the number 13.
1862Return the sum = 12 + 13 = 25.
1863------------------------------
1864------------------------------
1865Surrounded Regions
1866------------------------------
1867Given a 2D board containing 'X' and 'O' (the letter O), capture all
1868regions surrounded by 'X'.
1869A region is captured by flipping all 'O's into 'X's in that
1870surrounded region.
1871For example,
1872X X X X
1873X O O X
1874X X O X
1875X O X X
1876After running your function, the board should be:
1877X X X X
1878X X X X
1879X X X X
1880X O X X
1881------------------------------
1882------------------------------
1883Palindrome Partitioning
1884------------------------------
1885Given a string s, partition s such that every substring of the
1886partition is a palindrome.
1887Return all possible palindrome partitioning of s.
1888For example, given s = "aab",
1889Return
1890[
1891 ["aa","b"],
1892 ["a","a","b"]
1893]
1894------------------------------
1895------------------------------
1896Palindrome Partitioning II
1897------------------------------
1898Given a string s, partition s such that every substring of the
1899partition is a palindrome.
1900Return the minimum cuts needed for a palindrome partitioning of s.
1901For example, given s = "aab",
1902Return 1 since the palindrome partitioning ["aa","b"] could be
1903produced using 1 cut.
1904------------------------------
1905------------------------------
1906Clone Graph
1907------------------------------
1908Clone an undirected graph. Each node in the graph contains a label
1909and a list of its neighbors.
1910OJ's undirected graph serialization:
1911Nodes are labeled uniquely.
1912We use # as a separator for each node, and , as a separator for node
1913label and each neighbor of the node.
1914As an example, consider the serialized graph {0,1,2#1,2#2,2}.
1915The graph has a total of three nodes, and therefore contains three
1916parts as separated by #.
1917First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
1918Second node is labeled as 1. Connect node 1 to node 2.
1919Third node is labeled as 2. Connect node 2 to node 2 (itself), thus
1920forming a self-cycle.
1921Visually, the graph looks like the following:
1922 1
1923 / \
1924 / \
1925 0 --- 2
1926 / \
1927 \_/
1928------------------------------
1929------------------------------
1930Gas Station
1931------------------------------
1932There are N gas stations along a circular route, where the amount of
1933gas at station i is gas[i].
1934You have a car with an unlimited gas tank and it costs cost[i] of
1935gas to travel from station i to its next station (i+1). You begin
1936the journey with an empty tank at one of the gas stations.
1937Return the starting gas station's index if you can travel around the
1938circuit once, otherwise return -1.
1939Note:
1940The solution is guaranteed to be unique.
1941------------------------------
1942------------------------------
1943Candy
1944------------------------------
1945There are N children standing in a line. Each child is assigned a
1946rating value.
1947You are giving candies to these children subjected to the following
1948requirements:
1949Each child must have at least one candy.
1950Children with a higher rating get more candies than their neighbors.
1951What is the minimum candies you must give?
1952------------------------------
1953------------------------------
1954Single Number
1955------------------------------
1956Given an array of integers, every element appears twice except for
1957one. Find that single one.
1958Note:
1959Your algorithm should have a linear runtime complexity. Could you 
1960implement it without using extra memory?
1961------------------------------
1962------------------------------
1963Single Number II
1964------------------------------
1965Given an array of integers, every element appears three times except
1966for one, which appears exactly once. Find that single one.
1967Note:
1968Your algorithm should have a linear runtime complexity. Could you
1969implement it without using extra memory?
1970------------------------------
1971------------------------------
1972Copy List with Random Pointer
1973------------------------------
1974A linked list is given such that each node contains an additional
1975random pointer which could point to any node in the list or null.
1976Return a deep copy of the list.
1977------------------------------
1978------------------------------
1979Word Break
1980------------------------------
1981Given a non-empty string s and a dictionary wordDict containing a
1982list of non-empty words, determine if s can be segmented into a
1983space-separated sequence of one or more dictionary words. You may
1984assume the dictionary does not contain duplicate words.
1985For example, given
1986s = "leetcode",
1987dict = ["leet", "code"].
1988Return true because "leetcode" can be segmented as "leet code".
1989UPDATE (2017/1/4):
1990The wordDict parameter had been changed to a list of strings
1991(instead of a set of strings). Please reload the code definition to
1992get the latest changes.
1993------------------------------
1994------------------------------
1995Word Break II
1996------------------------------
1997Given a non-empty string s and a dictionary wordDict containing a
1998list of non-empty words, add spaces in s to construct a sentence
1999where each word is a valid dictionary word. You may assume the
2000dictionary does not contain duplicate words.
2001Return all such possible sentences.
2002For example, given
2003s = "catsanddog",
2004dict = ["cat", "cats", "and", "sand", "dog"].
2005A solution is ["cats and dog", "cat sand dog"].
2006UPDATE (2017/1/4):
2007The wordDict parameter had been changed to a list of strings
2008(instead of a set of strings). Please reload the code definition to
2009get the latest changes.
2010------------------------------
2011------------------------------
2012Linked List Cycle
2013------------------------------
2014Given a linked list, determine if it has a cycle in it.
2015Follow up:
2016Can you solve it without using extra space?
2017------------------------------
2018------------------------------
2019Linked List Cycle II
2020------------------------------
2021Given a linked list, return the node where the cycle begins. If
2022there is no cycle, return null.
2023Note: Do not modify the linked list.
2024Follow up:
2025Can you solve it without using extra space?
2026------------------------------
2027------------------------------
2028Reorder List
2029------------------------------
2030Given a singly linked list L: L0→L1→…→Ln-1→Ln,
2031reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
2032You must do this in-place without altering the nodes' values.
2033For example,
2034Given {1,2,3,4}, reorder it to {1,4,2,3}.
2035------------------------------
2036------------------------------
2037Binary Tree Preorder Traversal
2038------------------------------
2039Given a binary tree, return the preorder traversal of its nodes'
2040values.
2041For example:
2042Given binary tree {1,#,2,3},
2043 1
2044 \
2045 2
2046 /
2047 3
2048return [1,2,3].
2049Note: Recursive solution is trivial, could you do it iteratively?
2050------------------------------
2051------------------------------
2052Binary Tree Postorder Traversal
2053------------------------------
2054Given a binary tree, return the postorder traversal of its nodes'
2055values.
2056For example:
2057Given binary tree {1,#,2,3},
2058 1
2059 \
2060 2
2061 /
2062 3
2063return [3,2,1].
2064Note: Recursive solution is trivial, could you do it iteratively?
2065------------------------------
2066------------------------------
2067LRU Cache
2068------------------------------
2069Design and implement a data structure for Least Recently Used (LRU)
2070cache. It should support the following operations: get and put.
2071get(key) - Get the value (will always be positive) of the key if the
2072key exists in the cache, otherwise return -1.
2073put(key, value) - Set or insert the value if the key is not already
2074present. When the cache reached its capacity, it should invalidate
2075the least recently used item before inserting a new item.
2076Follow up:
2077Could you do both operations in O(1) time complexity?
2078Example:
2079LRUCache cache = new LRUCache( 2 /* capacity */ );
2080cache.put(1, 1);
2081cache.put(2, 2);
2082cache.get(1); // returns 1
2083cache.put(3, 3); // evicts key 2
2084cache.get(2); // returns -1 (not found)
2085cache.put(4, 4); // evicts key 1
2086cache.get(1); // returns -1 (not found)
2087cache.get(3); // returns 3
2088cache.get(4); // returns 4
2089------------------------------
2090------------------------------
2091Insertion Sort List
2092------------------------------
2093Sort a linked list using insertion sort.
2094------------------------------
2095------------------------------
2096Sort List
2097------------------------------
2098Sort a linked list in O(n log n) time using constant space
2099complexity.
2100------------------------------
2101------------------------------
2102Max Points on a Line
2103------------------------------
2104Given n points on a 2D plane, find the maximum number of points that
2105lie on the same straight line.
2106------------------------------
2107------------------------------
2108Evaluate Reverse Polish Notation
2109------------------------------
2110Evaluate the value of an arithmetic expression in Reverse Polish
2111Notation.
2112Valid operators are +, -, *, /. Each operand may be an integer or
2113another expression.
2114Some examples:
2115 ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
2116 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
2117------------------------------
2118------------------------------
2119Reverse Words in a String
2120------------------------------
2121Given an input string, reverse the string word by word.
2122For example,
2123Given s = "the sky is blue",
2124return "blue is sky the".
2125Update (2015-02-12):
2126For C programmers: Try to solve it in-place in O(1) space.
2127click to show clarification.
2128Clarification:
2129What constitutes a word?
2130A sequence of non-space characters constitutes a word.
2131Could the input string contain leading or trailing spaces?
2132Yes. However, your reversed string should not contain leading or
2133trailing spaces.
2134How about multiple spaces between two words?
2135Reduce them to a single space in the reversed string.
2136------------------------------
2137------------------------------
2138Maximum Product Subarray
2139------------------------------
2140Find the contiguous subarray within an array (containing at least
2141one number) which has the largest product.
2142For example, given the array [2,3,-2,4],
2143the contiguous subarray [2,3] has the largest product = 6.
2144------------------------------
2145------------------------------
2146Find Minimum in Rotated Sorted Array
2147------------------------------
2148Suppose an array sorted in ascending order is rotated at some pivot
2149unknown to you beforehand.
2150(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
2151Find the minimum element.
2152You may assume no duplicate exists in the array.
2153------------------------------
2154------------------------------
2155Find Minimum in Rotated Sorted Array II
2156------------------------------
2157Follow up for "Find Minimum in Rotated Sorted Array":
2158What if duplicates are allowed?
2159Would this affect the run-time complexity? How and why?
2160Suppose an array sorted in ascending order is rotated at some pivot
2161unknown to you beforehand.
2162(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
2163Find the minimum element.
2164The array may contain duplicates.
2165------------------------------
2166------------------------------
2167Min Stack
2168------------------------------
2169Design a stack that supports push, pop, top, and retrieving the
2170minimum element in constant time.
2171push(x) -- Push element x onto stack.
2172pop() -- Removes the element on top of the stack.
2173top() -- Get the top element.
2174getMin() -- Retrieve the minimum element in the stack.
2175Example:
2176MinStack minStack = new MinStack();
2177minStack.push(-2);
2178minStack.push(0);
2179minStack.push(-3);
2180minStack.getMin(); --> Returns -3.
2181minStack.pop();
2182minStack.top(); --> Returns 0.
2183minStack.getMin(); --> Returns -2.
2184------------------------------
2185------------------------------
2186------------------------------
2187------------------------------
2188------------------------------
2189------------------------------
2190Intersection of Two Linked Lists
2191------------------------------
2192Write a program to find the node at which the intersection of two
2193singly linked lists begins.
2194For example, the following two linked lists:
2195A: a1 → a2
2196 ↘
2197 c1 → c2 → c3
2198 ↗ 
2199B: b1 → b2 → b3
2200begin to intersect at node c1.
2201Notes:
2202If the two linked lists have no intersection at all, return null.
2203The linked lists must retain their original structure after the
2204function returns.
2205You may assume there are no cycles anywhere in the entire linked
2206structure.
2207Your code should preferably run in O(n) time and use only O(1)
2208memory.
2209Credits:Special thanks to @stellari for adding this problem and
2210creating all test cases.
2211------------------------------
2212------------------------------
2213------------------------------
2214Find Peak Element
2215------------------------------
2216A peak element is an element that is greater than its neighbors.
2217Given an input array where num[i] ≠ num[i+1], find a peak element
2218and return its index.
2219The array may contain multiple peaks, in that case return the index
2220to any one of the peaks is fine.
2221You may imagine that num[-1] = num[n] = -∞.
2222For example, in array [1, 2, 3, 1], 3 is a peak element and your
2223function should return the index number 2.
2224click to show spoilers.
2225Note:
2226Your solution should be in logarithmic complexity.
2227Credits:Special thanks to @ts for adding this problem and creating
2228all test cases.
2229------------------------------
2230------------------------------
2231------------------------------
2232Maximum Gap
2233------------------------------
2234Given an unsorted array, find the maximum difference between the
2235successive elements in its sorted form.
2236Try to solve it in linear time/space.
2237Return 0 if the array contains less than 2 elements.
2238You may assume all elements in the array are non-negative integers
2239and fit in the 32-bit signed integer range.
2240Credits:Special thanks to @porker2008 for adding this problem and
2241creating all test cases.
2242------------------------------
2243------------------------------
2244Compare Version Numbers
2245------------------------------
2246Compare two version numbers version1 and version2.
2247If version1 &gt; version2 return 1, if version1 &lt; version2 return
2248-1, otherwise return 0.
2249You may assume that the version strings are non-empty and contain
2250only digits and the . character.
2251The . character does not represent a decimal point and is used to
2252separate number sequences.
2253For instance, 2.5 is not "two and a half" or "half way to version
2254three", it is the fifth second-level revision of the second firstlevel revision.
2255Here is an example of version numbers ordering:
22560.1 &lt; 1.1 &lt; 1.2 &lt; 13.37
2257Credits:Special thanks to @ts for adding this problem and creating
2258all test cases.
2259------------------------------
2260------------------------------
2261Fraction to Recurring Decimal
2262------------------------------
2263Given two integers representing the numerator and denominator of a
2264fraction, return the fraction in string format.
2265If the fractional part is repeating, enclose the repeating part in
2266parentheses.
2267For example,
2268Given numerator = 1, denominator = 2, return "0.5".
2269Given numerator = 2, denominator = 1, return "2".
2270Given numerator = 2, denominator = 3, return "0.(6)".
2271 No scary math, just apply elementary math knowledge. Still
2272remember how to perform a long division?
2273 Try a long division on 4/9, the repeating part is obvious. Now try
22744/333. Do you see a pattern?
2275 Be wary of edge cases! List out as many test cases as you can
2276think of and test your code thoroughly.
2277Credits:Special thanks to @Shangrila for adding this problem and
2278creating all test cases.
2279------------------------------
2280------------------------------
2281Two Sum II - Input array is sorted
2282------------------------------
2283Given an array of integers that is already sorted in ascending
2284order, find two numbers such that they add up to a specific target
2285number.
2286The function twoSum should return indices of the two numbers such
2287that they add up to the target, where index1 must be less than
2288index2. Please note that your returned answers (both index1 and
2289index2) are not zero-based.
2290You may assume that each input would have exactly one solution and
2291you may not use the same element twice.
2292Input: numbers={2, 7, 11, 15}, target=9
2293Output: index1=1, index2=2
2294------------------------------
2295------------------------------
2296Excel Sheet Column Title
2297------------------------------
2298Given a positive integer, return its corresponding column title as
2299appear in an Excel sheet.
2300For example:
2301 1 -> A
2302 2 -> B
2303 3 -> C
2304 ...
2305 26 -> Z
2306 27 -> AA
2307 28 -> AB
2308Credits:Special thanks to @ifanchu for adding this problem and
2309creating all test cases.
2310------------------------------
2311------------------------------
2312Majority Element
2313------------------------------
2314Given an array of size n, find the majority element. The majority
2315element is the element that appears more than &lfloor; n/2 &rfloor;
2316times.
2317You may assume that the array is non-empty and the majority element
2318always exist in the array.
2319Credits:Special thanks to @ts for adding this problem and creating 
2320all test cases.
2321------------------------------
2322------------------------------
2323------------------------------
2324Excel Sheet Column Number
2325------------------------------
2326Related to question Excel Sheet Column Title
2327Given a column title as appear in an Excel sheet, return its
2328corresponding column number.
2329For example:
2330 A -&gt; 1
2331 B -&gt; 2
2332 C -&gt; 3
2333 ...
2334 Z -&gt; 26
2335 AA -&gt; 27
2336 AB -&gt; 28
2337Credits:Special thanks to @ts for adding this problem and creating
2338all test cases.
2339------------------------------
2340------------------------------
2341Factorial Trailing Zeroes
2342------------------------------
2343Given an integer n, return the number of trailing zeroes in n!.
2344Note: Your solution should be in logarithmic time complexity.
2345Credits:Special thanks to @ts for adding this problem and creating
2346all test cases.
2347------------------------------
2348------------------------------
2349Binary Search Tree Iterator
2350------------------------------
2351Implement an iterator over a binary search tree (BST). Your iterator
2352will be initialized with the root node of a BST.
2353Calling next() will return the next smallest number in the BST.
2354Note: next() and hasNext() should run in average O(1) time and uses
2355O(h) memory, where h is the height of the tree.
2356Credits:Special thanks to @ts for adding this problem and creating
2357all test cases.
2358------------------------------
2359------------------------------
2360Dungeon Game
2361------------------------------
2362table.dungeon, .dungeon th, .dungeon td {
2363 border:3px solid black;
2364}
2365 .dungeon th, .dungeon td {
2366 text-align: center;
2367 height: 70px;
2368 width: 70px;
2369}
2370The demons had captured the princess (P) and imprisoned her in the
2371bottom-right corner of a dungeon. The dungeon consists of M x N
2372rooms laid out in a 2D grid. Our valiant knight (K) was initially
2373positioned in the top-left room and must fight his way through the
2374dungeon to rescue the princess.
2375The knight has an initial health point represented by a positive
2376integer. If at any point his health point drops to 0 or below, he
2377dies immediately.
2378Some of the rooms are guarded by demons, so the knight loses health
2379(negative integers) upon entering these rooms;
2380other rooms are either empty (0's) or contain magic orbs that
2381increase the knight's health (positive integers).
2382In order to reach the princess as quickly as possible, the knight
2383decides to move only rightward or downward in each step.
2384Write a function to determine the knight's minimum initial health so
2385that he is able to rescue the princess.
2386For example, given the dungeon below, the initial health of the
2387knight must be at least 7 if he follows the optimal path RIGHT->
2388RIGHT -> DOWN -> DOWN.
2389-2 (K)
2390-3
23913
2392-5
2393-10
23941
239510
239630
2397-5 (P)
2398Notes:
2399The knight's health has no upper bound.
2400Any room can contain threats or power-ups, even the first room the
2401knight enters and the bottom-right room where the princess is 
2402imprisoned.
2403Credits:Special thanks to @stellari for adding this problem and
2404creating all test cases.
2405------------------------------
2406------------------------------
2407Largest Number
2408------------------------------
2409Given a list of non negative integers, arrange them such that they
2410form the largest number.
2411For example, given [3, 30, 34, 5, 9], the largest formed number is
24129534330.
2413Note: The result may be very large, so you need to return a string
2414instead of an integer.
2415Credits:Special thanks to @ts for adding this problem and creating
2416all test cases.
2417------------------------------
2418------------------------------
2419------------------------------
2420Repeated DNA Sequences
2421------------------------------
2422All DNA is composed of a series of nucleotides abbreviated as A, C,
2423G, and T, for example: "ACGAATTCCG". When studying DNA, it is
2424sometimes useful to identify repeated sequences within the DNA.
2425Write a function to find all the 10-letter-long sequences
2426(substrings) that occur more than once in a DNA molecule.
2427For example,
2428Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
2429Return:
2430["AAAAACCCCC", "CCCCCAAAAA"].
2431------------------------------
2432------------------------------
2433Best Time to Buy and Sell Stock IV
2434------------------------------
2435Say you have an array for which the ith element is the price of a
2436given stock on day i.
2437Design an algorithm to find the maximum profit. You may complete at
2438most k transactions.
2439Note:
2440You may not engage in multiple transactions at the same time (ie, 
2441you must sell the stock before you buy again).
2442Credits:Special thanks to @Freezen for adding this problem and
2443creating all test cases.
2444------------------------------
2445------------------------------
2446Rotate Array
2447------------------------------
2448Rotate an array of n elements to the right by k steps.
2449For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is
2450rotated to [5,6,7,1,2,3,4].
2451Note:
2452Try to come up as many solutions as you can, there are at least 3
2453different ways to solve this problem.
2454[show hint]
2455Hint:
2456Could you do it in-place with O(1) extra space?
2457Related problem: Reverse Words in a String II
2458Credits:Special thanks to @Freezen for adding this problem and
2459creating all test cases.
2460------------------------------
2461------------------------------
2462Reverse Bits
2463------------------------------
2464Reverse bits of a given 32 bits unsigned integer.
2465For example, given input 43261596 (represented in binary as
246600000010100101000001111010011100), return 964176192 (represented in
2467binary as 00111001011110000010100101000000).
2468Follow up:
2469If this function is called many times, how would you optimize it?
2470Related problem: Reverse Integer
2471Credits:Special thanks to @ts for adding this problem and creating
2472all test cases.
2473------------------------------
2474------------------------------
2475Number of 1 Bits
2476------------------------------
2477Write a function that takes an unsigned integer and returns the
2478number of ’1' bits it has (also known as the Hamming weight).
2479For example, the 32-bit integer ’11' has binary representation
248000000000000000000000000000001011, so the function should return 3.
2481Credits:Special thanks to @ts for adding this problem and creating
2482all test cases.
2483------------------------------
2484------------------------------
2485House Robber
2486------------------------------
2487You are a professional robber planning to rob houses along a street.
2488Each house has a certain amount of money stashed, the only
2489constraint stopping you from robbing each of them is that adjacent
2490houses have security system connected and it will automatically
2491contact the police if two adjacent houses were broken into on the
2492same night.
2493Given a list of non-negative integers representing the amount of
2494money of each house, determine the maximum amount of money you can
2495rob tonight without alerting the police.
2496Credits:Special thanks to @ifanchu for adding this problem and
2497creating all test cases. Also thanks to @ts for adding additional
2498test cases.
2499------------------------------
2500------------------------------
2501Binary Tree Right Side View
2502------------------------------
2503Given a binary tree, imagine yourself standing on the right side of
2504it, return the values of the nodes you can see ordered from top to
2505bottom.
2506For example:
2507Given the following binary tree,
2508 1 <---
2509 / \
25102 3 <---
2511 \ \
2512 5 4 <---
2513You should return [1, 3, 4].
2514Credits:Special thanks to @amrsaqr for adding this problem and
2515creating all test cases.
2516------------------------------
2517------------------------------
2518Number of Islands
2519------------------------------
2520Given a 2d grid map of '1's (land) and '0's (water), count the
2521number of islands. An island is surrounded by water and is formed by
2522connecting adjacent lands horizontally or vertically. You may assume
2523all four edges of the grid are all surrounded by water.
2524Example 1:
252511110110101100000000
2526Answer: 1
2527Example 2:
252811000110000010000011
2529Answer: 3
2530Credits:Special thanks to @mithmatt for adding this problem and
2531creating all test cases.
2532------------------------------
2533------------------------------
2534Bitwise AND of Numbers Range
2535------------------------------
2536Given a range [m, n] where 0 <= m <= n <= 2147483647, return the
2537bitwise AND of all numbers in this range, inclusive.
2538For example, given the range [5, 7], you should return 4.
2539Credits:Special thanks to @amrsaqr for adding this problem and
2540creating all test cases.
2541------------------------------
2542------------------------------
2543Happy Number
2544------------------------------
2545Write an algorithm to determine if a number is "happy".
2546A happy number is a number defined by the following process:
2547Starting with any positive integer, replace the number by the sum of
2548the squares of its digits, and repeat the process until the number
2549equals 1 (where it will stay), or it loops endlessly in a cycle
2550which does not include 1. Those numbers for which this process ends
2551in 1 are happy numbers.
2552Example:&nbsp;19 is a happy number
255312 + 92 = 82
255482 + 22 = 68
255562 + 82 = 100
255612 + 02 + 02 = 1
2557Credits:Special thanks to @mithmatt and @ts for adding this problem
2558and creating all test cases.
2559------------------------------
2560------------------------------
2561Remove Linked List Elements
2562------------------------------
2563Remove all elements from a linked list of integers that have value
2564val.
2565Example
2566Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
2567Return: 1 --> 2 --> 3 --> 4 --> 5
2568Credits:Special thanks to @mithmatt for adding this problem and
2569creating all test cases.
2570------------------------------
2571------------------------------
2572Count Primes
2573------------------------------
2574Description:
2575Count the number of prime numbers less than a non-negative number,
2576n.
2577Credits:Special thanks to @mithmatt for adding this problem and
2578creating all test cases.
2579 Let's start with a isPrime function. To determine if a number is
2580prime, we need to check if it is not divisible by any number less
2581than n. The runtime complexity of isPrime function would be O(n) and
2582hence counting the total prime numbers up to n would be O(n2). Could
2583we do better?
2584
2585 As we know the number must not be divisible by any number > n / 2,
2586we can immediately cut the total iterations half by dividing only up
2587to n / 2. Could we still do better?
2588
2589 Let's write down all of 12's factors:
25902 × 6 = 12
25913 × 4 = 12
25924 × 3 = 12
25936 × 2 = 12
2594As you can see, calculations of 4 × 3 and 6 × 2 are not necessary.
2595Therefore, we only need to consider factors up to &radic;n because,
2596if n is divisible by some number p, then n = p × q and since p &le;
2597q, we could derive that p &le; &radic;n.
2598Our total runtime has now improved to O(n1.5), which is slightly
2599better. Is there a faster approach?
2600public int countPrimes(int n) {
2601 int count = 0;
2602 for (int i = 1; i < n; i++) {
2603 if (isPrime(i)) count++;
2604 }
2605 return count;
2606}
2607private boolean isPrime(int num) {
2608 if (num <= 1) return false;
2609 // Loop's ending condition is i * i <= num instead of i <=
2610sqrt(num)
2611 // to avoid repeatedly calling an expensive function sqrt().
2612 for (int i = 2; i * i <= num; i++) {
2613 if (num % i == 0) return false;
2614 }
2615 return true;
2616}
2617
2618 The Sieve of Eratosthenes is one of the most efficient ways to
2619find all prime numbers up to n. But don't let that name scare you, I
2620promise that the concept is surprisingly simple.
2621Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve
2622of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.
2623We start off with a table of n numbers. Let's look at the first
2624number, 2. We know all multiples of 2 must not be primes, so we mark
2625them off as non-primes. Then we look at the next number, 3.
2626Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must
2627not be primes, so we mark them off as well. Now we look at the next
2628number, 4, which was already marked off. What does this tell you?
2629Should you mark off all multiples of 4 as well?
2630
2631 4 is not a prime because it is divisible by 2, which means all
2632multiples of 4 must also be divisible by 2 and were already marked
2633off. So we can skip 4 immediately and go to the next number, 5. Now,
2634all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5
2635= 25, ... can be marked off. There is a slight optimization here, we
2636do not need to start from 5 × 2 = 10. Where should we start marking
2637off?
2638
2639 In fact, we can mark off multiples of 5 starting at 5 × 5 = 25,
2640because 5 × 2 = 10 was already marked off by multiple of 2,
2641similarly 5 × 3 = 15 was already marked off by multiple of 3.
2642Therefore, if the current number is p, we can always mark off
2643multiples of p starting at p2, then in increments of p: p2 + p, p2 +
26442p, ... Now what should be the terminating loop condition?
2645
2646 It is easy to say that the terminating loop condition is p < n,
2647which is certainly correct but not efficient. Do you still remember
2648Hint #3?
2649
2650 Yes, the terminating loop condition can be p < &radic;n, as all
2651non-primes &ge; &radic;n must have already been marked off. When the
2652loop terminates, all the numbers in the table that are non-marked
2653are prime.
2654The Sieve of Eratosthenes uses an extra O(n) memory and its runtime
2655complexity is O(n log log n). For the more mathematically inclined
2656readers, you can read more about its algorithm complexity on
2657Wikipedia.
2658public int countPrimes(int n) {
2659 boolean[] isPrime = new boolean[n];
2660 for (int i = 2; i < n; i++) {
2661 isPrime[i] = true;
2662 }
2663 // Loop's ending condition is i * i < n instead of i < sqrt(n)
2664 // to avoid repeatedly calling an expensive function sqrt().
2665 for (int i = 2; i * i < n; i++) {
2666 if (!isPrime[i]) continue;
2667 for (int j = i * i; j < n; j += i) {
2668 isPrime[j] = false;
2669 }
2670 }
2671 int count = 0;
2672 for (int i = 2; i < n; i++) {
2673 if (isPrime[i]) count++;
2674 }
2675 return count;
2676}
2677
2678------------------------------
2679------------------------------
2680Isomorphic Strings
2681------------------------------
2682Given two strings s and t, determine if they are isomorphic.
2683Two strings are isomorphic if the characters in s can be replaced to
2684get t.
2685All occurrences of a character must be replaced with another
2686character while preserving the order of characters. No two
2687characters may map to the same character but a character may map to
2688itself.
2689For example,
2690Given "egg", "add", return true.
2691Given "foo", "bar", return false.
2692Given "paper", "title", return true.
2693Note:
2694You may assume both s and t have the same length.
2695------------------------------
2696------------------------------
2697Reverse Linked List 
2698------------------------------
2699Reverse a singly linked list.
2700click to show more hints.
2701Hint:
2702A linked list can be reversed either iteratively or recursively.
2703Could you implement both?
2704------------------------------
2705------------------------------
2706Course Schedule
2707------------------------------
2708There are a total of n courses you have to take, labeled from 0 to n
2709- 1.
2710Some courses may have prerequisites, for example to take course 0
2711you have to first take course 1, which is expressed as a pair: [0,1]
2712Given the total number of courses and a list of prerequisite pairs,
2713is it possible for you to finish all courses?
2714For example:
27152, [[1,0]]
2716There are a total of 2 courses to take. To take course 1 you should
2717have finished course 0. So it is possible.
27182, [[1,0],[0,1]]
2719There are a total of 2 courses to take. To take course 1 you should
2720have finished course 0, and to take course 0 you should also have
2721finished course 1. So it is impossible.
2722Note:
2723The input prerequisites is a graph represented by a list of edges,
2724not adjacency matrices. Read more about how a graph is represented.
2725You may assume that there are no duplicate edges in the input
2726prerequisites.
2727click to show more hints.
2728Hints:
2729This problem is equivalent to finding if a cycle exists in a
2730directed graph. If a cycle exists, no topological ordering exists
2731and therefore it will be impossible to take all courses.
2732Topological Sort via DFS - A great video tutorial (21 minutes) on
2733Coursera explaining the basic concepts of Topological Sort.
2734Topological sort could also be done via BFS.
2735------------------------------
2736------------------------------
2737Implement Trie (Prefix Tree)
2738------------------------------
2739Implement a trie with insert, search, and startsWith methods.
2740Note:
2741You may assume that all inputs are consist of lowercase letters a-z.
2742------------------------------
2743------------------------------
2744Minimum Size Subarray Sum
2745------------------------------
2746Given an array of n positive integers and a positive integer s, find
2747the minimal length of a contiguous subarray of which the sum ≥ s. If
2748there isn't one, return 0 instead.
2749For example, given the array [2,3,1,2,4,3] and s = 7,
2750the subarray [4,3] has the minimal length under the problem
2751constraint.
2752click to show more practice.
2753More practice:
2754If you have figured out the O(n) solution, try coding another
2755solution of which the time complexity is O(n log n).
2756Credits:Special thanks to @Freezen for adding this problem and
2757creating all test cases.
2758------------------------------
2759------------------------------
2760Course Schedule II
2761------------------------------
2762There are a total of n courses you have to take, labeled from 0 to n
2763- 1.
2764Some courses may have prerequisites, for example to take course 0
2765you have to first take course 1, which is expressed as a pair: [0,1]
2766Given the total number of courses and a list of prerequisite pairs,
2767return the ordering of courses you should take to finish all
2768courses.
2769There may be multiple correct orders, you just need to return one of
2770them. If it is impossible to finish all courses, return an empty
2771array.
2772For example:
27732, [[1,0]]
2774There are a total of 2 courses to take. To take course 1 you should
2775have finished course 0. So the correct course order is [0,1]
27764, [[1,0],[2,0],[3,1],[3,2]]
2777There are a total of 4 courses to take. To take course 3 you should
2778have finished both courses 1 and 2. Both courses 1 and 2 should be
2779taken after you finished course 0. So one correct course order is
2780[0,1,2,3]. Another correct ordering is[0,2,1,3].
2781Note:
2782The input prerequisites is a graph represented by a list of edges,
2783not adjacency matrices. Read more about how a graph is represented.
2784You may assume that there are no duplicate edges in the input
2785prerequisites.
2786click to show more hints.
2787Hints:
2788This problem is equivalent to finding the topological order in a
2789directed graph. If a cycle exists, no topological ordering exists
2790and therefore it will be impossible to take all courses.
2791Topological Sort via DFS - A great video tutorial (21 minutes) on
2792Coursera explaining the basic concepts of Topological Sort.
2793Topological sort could also be done via BFS.
2794------------------------------
2795------------------------------
2796Add and Search Word - Data structure design
2797------------------------------
2798Design a data structure that supports the following two operations:
2799void addWord(word)
2800bool search(word)
2801search(word) can search a literal word or a regular expression
2802string containing only letters a-z or .. A . means it can represent
2803any one letter.
2804For example:
2805addWord("bad")
2806addWord("dad")
2807addWord("mad")
2808search("pad") -> false
2809search("bad") -> true
2810search(".ad") -> true
2811search("b..") -> true
2812Note:
2813You may assume that all words are consist of lowercase letters a-z.
2814click to show hint.
2815You should be familiar with how a Trie works. If not, please work on
2816this problem: Implement Trie (Prefix Tree) first.
2817------------------------------
2818------------------------------
2819Word Search II
2820------------------------------
2821Given a 2D board and a list of words from the dictionary, find all
2822words in the board.
2823Each word must be constructed from letters of sequentially adjacent
2824cell, where "adjacent" cells are those horizontally or vertically
2825neighboring. The same letter cell may not be used more than once in
2826a word.
2827For example,
2828Given words = ["oath","pea","eat","rain"] and board =
2829[
2830 ['o','a','a','n'],
2831 ['e','t','a','e'],
2832 ['i','h','k','r'],
2833 ['i','f','l','v']
2834]
2835Return ["eat","oath"].
2836Note:
2837You may assume that all inputs are consist of lowercase letters a-z.
2838click to show hint.
2839You would need to optimize your backtracking to pass the larger
2840test. Could you stop backtracking earlier?
2841If the current candidate does not exist in all words' prefix, you
2842could stop backtracking immediately. What kind of data structure
2843could answer such query efficiently? Does a hash table work? Why or
2844why not? How about a Trie? If you would like to learn how to
2845implement a basic trie, please work on this problem: Implement Trie
2846(Prefix Tree) first.
2847------------------------------
2848------------------------------
2849House Robber II
2850------------------------------
2851Note: This is an extension of House Robber.
2852After robbing those houses on that street, the thief has found
2853himself a new place for his thievery so that he will not get too
2854much attention. This time, all houses at this place are arranged in
2855a circle. That means the first house is the neighbor of the last
2856one. Meanwhile, the security system for these houses remain the same
2857as for those in the previous street.
2858Given a list of non-negative integers representing the amount of
2859money of each house, determine the maximum amount of money you can
2860rob tonight without alerting the police.
2861Credits:Special thanks to @Freezen for adding this problem and
2862creating all test cases.
2863------------------------------
2864------------------------------
2865Shortest Palindrome
2866------------------------------
2867Given a string S, you are allowed to convert it to a palindrome by
2868adding characters in front of it. Find and return the shortest
2869palindrome you can find by performing this transformation.
2870For example:
2871Given "aacecaaa", return "aaacecaaa".
2872Given "abcd", return "dcbabcd".
2873Credits:Special thanks to @ifanchu for adding this problem and
2874creating all test cases. Thanks to @Freezen for additional test
2875cases.
2876------------------------------
2877------------------------------
2878Kth Largest Element in an Array
2879------------------------------
2880Find the kth largest element in an unsorted array. Note that it is
2881the kth largest element in the sorted order, not the kth distinct
2882element.
2883For example,
2884Given [3,2,1,5,6,4] and k = 2, return 5.
2885Note:
2886You may assume k is always valid, 1 ≤ k ≤ array's length.
2887Credits:Special thanks to @mithmatt for adding this problem and
2888creating all test cases.
2889------------------------------
2890------------------------------
2891Combination Sum III
2892------------------------------
2893Find all possible combinations of k numbers that add up to a number
2894n, given that only numbers from 1 to 9 can be used and each
2895combination should be a unique set of numbers.
2896 Example 1:
2897Input: k = 3, n = 7
2898Output:
2899[[1,2,4]]
2900 Example 2:
2901Input: k = 3, n = 9
2902Output:
2903[[1,2,6], [1,3,5], [2,3,4]]
2904Credits:Special thanks to @mithmatt for adding this problem and
2905creating all test cases.
2906------------------------------
2907------------------------------
2908Contains Duplicate
2909------------------------------
2910Given an array of integers, find if the array contains any
2911duplicates. Your function should return true if any value appears at
2912least twice in the array, and it should return false if every
2913element is distinct.
2914------------------------------
2915------------------------------
2916The Skyline Problem
2917------------------------------
2918A city's skyline is the outer contour of the silhouette formed by
2919all the buildings in that city when viewed from a distance. Now
2920suppose you are given the locations and height of all the buildings
2921as shown on a cityscape photo (Figure A), write a program to output
2922the skyline formed by these buildings collectively (Figure B).
2923
2924
2925The geometric information of each building is represented by a
2926triplet of integers [Li, Ri, Hi], where Li and Ri are the x
2927coordinates of the left and right edge of the ith building,
2928respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri
2929≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all
2930buildings are perfect rectangles grounded on an absolutely flat
2931surface at height 0.
2932For instance, the dimensions of all buildings in Figure A are
2933recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24
29348] ] .
2935The output is a list of "key points" (red dots in Figure B) in the
2936format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines
2937a skyline. A key point is the left endpoint of a horizontal line
2938segment. Note that the last key point, where the rightmost building
2939ends, is merely used to mark the termination of the skyline, and
2940always has zero height. Also, the ground in between any two adjacent
2941buildings should be considered part of the skyline contour.
2942For instance, the skyline in Figure B should be represented as:[ [2
294310], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
2944Notes:
2945 The number of buildings in any input list is guaranteed to be in
2946the range [0, 10000].
2947 The input list is already sorted in ascending order by the left x
2948position Li.
2949 The output list must be sorted by the x position.
2950 There must be no consecutive horizontal lines of equal height in
2951the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], 
2952[12 7]...] is not acceptable; the three lines of height 5 should be
2953merged into one in the final output as such: [...[2 3], [4 5], [12
29547], ...]
2955Credits:Special thanks to @stellari for adding this problem,
2956creating these two awesome images and all test cases.
2957------------------------------
2958------------------------------
2959Contains Duplicate II
2960------------------------------
2961Given an array of integers and an integer k, find out whether there
2962are two distinct indices i and j in the array such that nums[i] =
2963nums[j] and the absolute difference between i and j is at most k.
2964------------------------------
2965------------------------------
2966Contains Duplicate III
2967------------------------------
2968Given an array of integers, find out whether there are two distinct
2969indices i and j in the array such that the absolute difference
2970between nums[i] and nums[j] is at most t and the absolute difference
2971between i and j is at most k.
2972------------------------------
2973------------------------------
2974Maximal Square
2975------------------------------
2976Given a 2D binary matrix filled with 0's and 1's, find the largest
2977square containing only 1's and return its area.
2978For example, given the following matrix:
29791 0 1 0 0
29801 0 1 1 1
29811 1 1 1 1
29821 0 0 1 0
2983Return 4.
2984Credits:Special thanks to @Freezen for adding this problem and
2985creating all test cases.
2986------------------------------
2987------------------------------
2988Count Complete Tree Nodes
2989------------------------------
2990Given a complete binary tree, count the number of nodes.
2991Definition of a complete binary tree from Wikipedia:
2992In a complete binary tree every level, except possibly the last, is
2993completely filled, and all nodes in the last level are as far left
2994as possible. It can have between 1 and 2h nodes inclusive at the
2995last level h.
2996------------------------------
2997------------------------------
2998Rectangle Area
2999------------------------------
3000Find the total area covered by two rectilinear rectangles in a 2D
3001plane.
3002Each rectangle is defined by its bottom left corner and top right
3003corner as shown in the figure.
3004Assume that the total area is never beyond the maximum possible
3005value of int.
3006Credits:Special thanks to @mithmatt for adding this problem,
3007creating the above image and all test cases.
3008------------------------------
3009------------------------------
3010Basic Calculator
3011------------------------------
3012Implement a basic calculator to evaluate a simple expression string.
3013The expression string may contain open ( and closing parentheses ),
3014the plus + or minus sign -, non-negative integers and empty
3015spaces .
3016You may assume that the given expression is always valid.
3017Some examples:
3018"1 + 1" = 2
3019" 2-1 + 2 " = 3
3020"(1+(4+5+2)-3)+(6+8)" = 23
3021Note: Do not use the eval built-in library function.
3022------------------------------
3023------------------------------
3024Implement Stack using Queues
3025------------------------------
3026Implement the following operations of a stack using queues.
3027push(x) -- Push element x onto stack.
3028pop() -- Removes the element on top of the stack.
3029top() -- Get the top element.
3030empty() -- Return whether the stack is empty.
3031Notes:
3032You must use only standard operations of a queue -- which means only
3033push to back, peek/pop from front, size, and is empty operations are
3034valid.
3035Depending on your language, queue may not be supported natively. You
3036may simulate a queue by using a list or deque (double-ended queue),
3037as long as you use only standard operations of a queue.
3038You may assume that all operations are valid (for example, no pop or
3039top operations will be called on an empty stack).
3040Credits:Special thanks to @jianchao.li.fighter for adding this
3041problem and all test cases.
3042------------------------------
3043------------------------------
3044Invert Binary Tree
3045------------------------------
3046Invert a binary tree.
3047 4
3048 / \
3049 2 7
3050 / \ / \
30511 3 6 9
3052to
3053 4
3054 / \
3055 7 2
3056 / \ / \
30579 6 3 1
3058Trivia:
3059This problem was inspired by this original tweet by Max Howell:
3060Google: 90% of our engineers use the software you wrote (Homebrew),
3061but you can’t invert a binary tree on a whiteboard so fuck off.
3062------------------------------
3063------------------------------
3064Basic Calculator II
3065------------------------------
3066Implement a basic calculator to evaluate a simple expression string.
3067The expression string contains only non-negative integers, +, -,
3068*, / operators and empty spaces . The integer division should
3069truncate toward zero.
3070You may assume that the given expression is always valid.
3071Some examples:
3072"3+2*2" = 7
3073" 3/2 " = 1
3074" 3+5 / 2 " = 5
3075Note: Do not use the eval built-in library function.
3076Credits:Special thanks to @ts for adding this problem and creating
3077all test cases.
3078------------------------------
3079------------------------------
3080Summary Ranges
3081------------------------------
3082Given a sorted integer array without duplicates, return the summary
3083of its ranges.
3084For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
3085Credits:Special thanks to @jianchao.li.fighter for adding this
3086problem and creating all test cases.
3087------------------------------
3088------------------------------
3089Majority Element II
3090------------------------------
3091Given an integer array of size n, find all elements that appear more
3092than &lfloor; n/3 &rfloor; times. The algorithm should run in linear
3093time and in O(1) space.
3094 How many majority elements could it possibly have?
3095 Do you have a better hint? Suggest it!
3096------------------------------
3097------------------------------
3098Kth Smallest Element in a BST
3099------------------------------
3100Given a binary search tree, write a function kthSmallest to find the
3101kth smallest element in it.
3102Note:
3103You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
3104Follow up:
3105What if the BST is modified (insert/delete operations) often and you
3106need to find the kth smallest frequently? How would you optimize the
3107kthSmallest routine?
3108 Try to utilize the property of a BST.
3109 What if you could modify the BST node's structure?
3110 The optimal runtime complexity is O(height of BST).
3111Credits:Special thanks to @ts for adding this problem and creating
3112all test cases.
3113------------------------------
3114------------------------------
3115Power of Two
3116------------------------------
3117Given an integer, write a function to determine if it is a power of
3118two.
3119Credits:Special thanks to @jianchao.li.fighter for adding this
3120problem and creating all test cases.
3121------------------------------
3122------------------------------
3123Implement Queue using Stacks
3124------------------------------
3125Implement the following operations of a queue using stacks.
3126push(x) -- Push element x to the back of queue.
3127pop() -- Removes the element from in front of queue.
3128peek() -- Get the front element.
3129empty() -- Return whether the queue is empty.
3130Notes:
3131You must use only standard operations of a stack -- which means only
3132push to top, peek/pop from top, size, and is empty operations are
3133valid.
3134Depending on your language, stack may not be supported natively. You
3135may simulate a stack by using a list or deque (double-ended queue), 
3136as long as you use only standard operations of a stack.
3137You may assume that all operations are valid (for example, no pop or
3138peek operations will be called on an empty queue).
3139------------------------------
3140------------------------------
3141Number of Digit One
3142------------------------------
3143Given an integer n, count the total number of digit 1 appearing in
3144all non-negative integers less than or equal to n.
3145For example:
3146Given n = 13,
3147Return 6, because digit 1 occurred in the following numbers: 1, 10,
314811, 12, 13.
3149 Beware of overflow.
3150------------------------------
3151------------------------------
3152Palindrome Linked List
3153------------------------------
3154Given a singly linked list, determine if it is a palindrome.
3155Follow up:
3156Could you do it in O(n) time and O(1) space?
3157------------------------------
3158------------------------------
3159Lowest Common Ancestor of a Binary Search Tree
3160------------------------------
3161Given a binary search tree (BST), find the lowest common ancestor
3162(LCA) of two given nodes in the BST.
3163According to the definition of LCA on Wikipedia: “The lowest common
3164ancestor is defined between two nodes v and w as the lowest node in
3165T that has both v and w as descendants (where we allow a node to be
3166a descendant of itself).”
3167 _______6______
3168 / \
3169 ___2__ ___8__
3170 / \ / \
3171 0 _4 7 9
3172 / \
3173 3 5
3174For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6.
3175Another example is LCA of nodes 2 and 4 is 2, since a node can be a
3176descendant of itself according to the LCA definition.
3177------------------------------
3178------------------------------
3179Lowest Common Ancestor of a Binary Tree
3180------------------------------
3181Given a binary tree, find the lowest common ancestor (LCA) of two
3182given nodes in the tree.
3183According to the definition of LCA on Wikipedia: “The lowest common
3184ancestor is defined between two nodes v and w as the lowest node in
3185T that has both v and w as descendants (where we allow a node to be
3186a descendant of itself).”
3187 _______3______
3188 / \
3189 ___5__ ___1__
3190 / \ / \
3191 6 _2 0 8
3192 / \
3193 7 4
3194For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3.
3195Another example is LCA of nodes 5 and 4 is 5, since a node can be a
3196descendant of itself according to the LCA definition.
3197------------------------------
3198------------------------------
3199Delete Node in a Linked List
3200------------------------------
3201Write a function to delete a node (except the tail) in a singly
3202linked list, given only access to that node.
3203Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the
3204third node with value 3, the linked list should become 1 -> 2 -> 4
3205after calling your function.
3206------------------------------
3207------------------------------
3208Product of Array Except Self
3209------------------------------
3210Given an array of n integers where n > 1, nums, return an array
3211output such that output[i] is equal to the product of all the
3212elements of nums except nums[i].
3213Solve it without division and in O(n).
3214For example, given [1,2,3,4], return [24,12,8,6].
3215Follow up:
3216Could you solve it with constant space complexity? (Note: The output
3217array does not count as extra space for the purpose of space
3218complexity analysis.)
3219------------------------------
3220------------------------------
3221Sliding Window Maximum
3222------------------------------
3223Given an array nums, there is a sliding window of size k which is
3224moving from the very left of the array to the very right. You can
3225only see the k numbers in the window. Each time the sliding window
3226moves right by one position.
3227For example,
3228Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
3229Window position Max
3230--------------- -----
3231[1 3 -1] -3 5 3 6 7 3
3232 1 [3 -1 -3] 5 3 6 7 3
3233 1 3 [-1 -3 5] 3 6 7 5
3234 1 3 -1 [-3 5 3] 6 7 5
3235 1 3 -1 -3 [5 3 6] 7 6
3236 1 3 -1 -3 5 [3 6 7] 7
3237Therefore, return the max sliding window as [3,3,5,5,6,7].
3238Note:
3239You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for
3240non-empty array.
3241Follow up:
3242Could you solve it in linear time?
3243 How about using a data structure such as deque (double-ended
3244queue)?
3245 The queue size need not be the same as the window’s size.
3246 Remove redundant elements and the queue should store only elements
3247that need to be considered.
3248------------------------------
3249------------------------------
3250Search a 2D Matrix II
3251------------------------------
3252Write an efficient algorithm that searches for a value in an m x n
3253matrix. This matrix has the following properties:
3254Integers in each row are sorted in ascending from left to right.
3255Integers in each column are sorted in ascending from top to bottom.
3256For example,
3257Consider the following matrix:
3258[
3259 [1, 4, 7, 11, 15],
3260 [2, 5, 8, 12, 19],
3261 [3, 6, 9, 16, 22],
3262 [10, 13, 14, 17, 24],
3263 [18, 21, 23, 26, 30]
3264]
3265Given target = 5, return true.
3266Given target = 20, return false.
3267------------------------------
3268------------------------------
3269Different Ways to Add Parentheses
3270------------------------------
3271Given a string of numbers and operators, return all possible results
3272from computing all the different possible ways to group numbers and
3273operators. The valid operators are +, - and *.
3274Example 1
3275Input: "2-1-1".
3276((2-1)-1) = 0
3277(2-(1-1)) = 2
3278Output: [0, 2]
3279Example 2
3280Input: "2*3-4*5"
3281(2*(3-(4*5))) = -34
3282((2*3)-(4*5)) = -14
3283((2*(3-4))*5) = -10
3284(2*((3-4)*5)) = -10
3285(((2*3)-4)*5) = 10
3286Output: [-34, -14, -10, -10, 10]
3287Credits:Special thanks to @mithmatt for adding this problem and
3288creating all test cases.
3289------------------------------
3290------------------------------
3291Valid Anagram
3292------------------------------
3293Given two strings s and t, write a function to determine if t is an
3294anagram of s.
3295For example,
3296s = "anagram", t = "nagaram", return true.
3297s = "rat", t = "car", return false.
3298Note:
3299You may assume the string contains only lowercase alphabets.
3300Follow up:
3301What if the inputs contain unicode characters? How would you adapt
3302your solution to such case?
3303------------------------------
3304------------------------------
3305------------------------------
3306------------------------------
3307------------------------------
3308------------------------------
3309------------------------------
3310------------------------------
3311------------------------------
3312------------------------------
3313------------------------------
3314------------------------------
3315------------------------------
3316------------------------------
3317------------------------------
3318------------------------------
3319Binary Tree Paths
3320------------------------------
3321Given a binary tree, return all root-to-leaf paths.
3322For example, given the following binary tree:
3323 1
3324 / \
33252 3
3326 \
3327 5
3328All root-to-leaf paths are:
3329["1->2->5", "1->3"]
3330Credits:Special thanks to @jianchao.li.fighter for adding this
3331problem and creating all test cases.
3332------------------------------
3333------------------------------
3334Add Digits
3335------------------------------
3336Given a non-negative integer num, repeatedly add all its digits
3337until the result has only one digit.
3338For example:
3339Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2
3340has only one digit, return it.
3341Follow up:
3342Could you do it without any loop/recursion in O(1) runtime?
3343 A naive implementation of the above process is trivial. Could you
3344come up with other methods?
3345 What are all the possible results?
3346 How do they occur, periodically or randomly?
3347 You may find this Wikipedia article useful.
3348Credits:Special thanks to @jianchao.li.fighter for adding this
3349problem and creating all test cases.
3350------------------------------
3351------------------------------
3352------------------------------
3353Single Number III
3354------------------------------
3355Given an array of numbers nums, in which exactly two elements appear
3356only once and all the other elements appear exactly twice. Find the
3357two elements that appear only once.
3358For example:
3359Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
3360Note:
3361The order of the result is not important. So in the above example,
3362[5, 3] is also correct.
3363Your algorithm should run in linear runtime complexity. Could you
3364implement it using only constant space complexity?
3365Credits:Special thanks to @jianchao.li.fighter for adding this
3366problem and creating all test cases.
3367------------------------------
3368------------------------------
3369------------------------------
3370Ugly Number
3371------------------------------
3372Write a program to check whether a given number is an ugly number.
3373Ugly numbers are positive numbers whose prime factors only include
33742, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it
3375includes another prime factor 7.
3376Note that 1 is typically treated as an ugly number.
3377Credits:Special thanks to @jianchao.li.fighter for adding this
3378problem and creating all test cases.
3379------------------------------
3380------------------------------
3381Ugly Number II
3382------------------------------
3383Write a program to find the n-th ugly number.
3384Ugly numbers are positive numbers whose prime factors only include
33852, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence
3386of the first 10 ugly numbers.
3387Note that 1 is typically treated as an ugly number, and n does not
3388exceed 1690.
3389 The naive approach is to call isUgly for every number until you
3390reach the nth one. Most numbers are not ugly. Try to focus your
3391effort on generating only the ugly ones.
3392 An ugly number must be multiplied by either 2, 3, or 5 from a 
3393smaller ugly number.
3394 The key is how to maintain the order of the ugly numbers. Try a
3395similar approach of merging from three sorted lists: L1, L2, and L3.
3396 Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1
3397* 2, L2 * 3, L3 * 5).
3398Credits:Special thanks to @jianchao.li.fighter for adding this
3399problem and creating all test cases.
3400------------------------------
3401------------------------------
3402------------------------------
3403------------------------------
3404------------------------------
3405Missing Number
3406------------------------------
3407Given an array containing n distinct numbers taken from 0, 1,
34082, ..., n, find the one that is missing from the array.
3409For example,
3410Given nums = [0, 1, 3] return 2.
3411Note:
3412Your algorithm should run in linear runtime complexity. Could you
3413implement it using only constant extra space complexity?
3414Credits:Special thanks to @jianchao.li.fighter for adding this
3415problem and creating all test cases.
3416------------------------------
3417------------------------------
3418------------------------------
3419------------------------------
3420------------------------------
3421Integer to English Words
3422------------------------------
3423Convert a non-negative integer to its english words representation.
3424Given input is guaranteed to be less than 231 - 1.
3425For example,
3426123 -> "One Hundred Twenty Three"
342712345 -> "Twelve Thousand Three Hundred Forty Five"
34281234567 -> "One Million Two Hundred Thirty Four Thousand Five
3429Hundred Sixty Seven"
3430 Did you see a pattern in dividing the number into chunk of words? 
3431For example, 123 and 123000.
3432 Group the number by thousands (3 digits). You can write a helper
3433function that takes a number less than 1000 and convert just that
3434chunk to words.
3435 There are many edge cases. What are some good test cases? Does
3436your code work with input such as 0? Or 1000010? (middle chunk is
3437zero and should not be printed out)
3438------------------------------
3439------------------------------
3440H-Index
3441------------------------------
3442Given an array of citations (each citation is a non-negative
3443integer) of a researcher, write a function to compute the
3444researcher's h-index.
3445According to the definition of h-index on Wikipedia: "A scientist
3446has index h if h of his/her N papers have at least h citations each,
3447and the other N − h papers have no more than h citations each."
3448For example, given citations = [3, 0, 6, 1, 5], which means the
3449researcher has 5 papers in total and each of them had received 3, 0,
34506, 1, 5 citations respectively. Since the researcher has 3 papers
3451with at least 3 citations each and the remaining two with no more
3452than 3 citations each, his h-index is 3.
3453Note: If there are several possible values for h, the maximum one is
3454taken as the h-index.
3455 An easy approach is to sort the array first.
3456 What are the possible values of h-index?
3457 A faster approach is to use extra space.
3458Credits:Special thanks to @jianchao.li.fighter for adding this
3459problem and creating all test cases.
3460------------------------------
3461------------------------------
3462H-Index II
3463------------------------------
3464Follow up for H-Index: What if the citations array is sorted in
3465ascending order? Could you optimize your algorithm?
3466 Expected runtime complexity is in O(log n) and the input is
3467sorted.
3468------------------------------
3469------------------------------
3470------------------------------
3471------------------------------
3472First Bad Version
3473------------------------------
3474You are a product manager and currently leading a team to develop a
3475new product. Unfortunately, the latest version of your product fails
3476the quality check. Since each version is developed based on the
3477previous version, all the versions after a bad version are also bad.
3478Suppose you have n versions [1, 2, ..., n] and you want to find out
3479the first bad one, which causes all the following ones to be bad.
3480You are given an API bool isBadVersion(version) which will return
3481whether version is bad. Implement a function to find the first bad
3482version. You should minimize the number of calls to the API.
3483Credits:Special thanks to @jianchao.li.fighter for adding this
3484problem and creating all test cases.
3485------------------------------
3486------------------------------
3487Perfect Squares
3488------------------------------
3489Given a positive integer n, find the least number of perfect square
3490numbers (for example, 1, 4, 9, 16, ...) which sum to n.
3491For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n
3492= 13, return 2 because 13 = 4 + 9.
3493Credits:Special thanks to @jianchao.li.fighter for adding this
3494problem and creating all test cases.
3495------------------------------
3496------------------------------
3497------------------------------
3498------------------------------
3499Expression Add Operators
3500------------------------------
3501Given a string that contains only digits 0-9 and a target value, 
3502return all possibilities to add binary operators (not unary) +, -,
3503or * between the digits so they evaluate to the target value.
3504Examples:
3505"123", 6 -> ["1+2+3", "1*2*3"]
3506"232", 8 -> ["2*3+2", "2+3*2"]
3507"105", 5 -> ["1*0+5","10-5"]
3508"00", 0 -> ["0+0", "0-0", "0*0"]
3509"3456237490", 9191 -> []
3510Credits:Special thanks to @davidtan1890 for adding this problem and
3511creating all test cases.
3512------------------------------
3513------------------------------
3514Move Zeroes
3515------------------------------
3516Given an array nums, write a function to move all 0's to the end of
3517it while maintaining the relative order of the non-zero elements.
3518For example, given nums = [0, 1, 0, 3, 12], after calling your
3519function, nums should be [1, 3, 12, 0, 0].
3520Note:
3521You must do this in-place without making a copy of the array.
3522Minimize the total number of operations.
3523Credits:Special thanks to @jianchao.li.fighter for adding this
3524problem and creating all test cases.
3525------------------------------
3526------------------------------
3527Peeking Iterator
3528------------------------------
3529Given an Iterator class interface with methods: next() and
3530hasNext(), design and implement a PeekingIterator that support the
3531peek() operation -- it essentially peek() at the element that will
3532be returned by the next call to next().
3533Here is an example. Assume that the iterator is initialized to the
3534beginning of the list: [1, 2, 3].
3535Call next() gets you 1, the first element in the list.
3536Now you call peek() and it returns 2, the next element. Calling 
3537next() after that still return 2.
3538You call next() the final time and it returns 3, the last element.
3539Calling hasNext() after that should return false.
3540 Think of "looking ahead". You want to cache the next element.
3541 Is one variable sufficient? Why or why not?
3542 Test your design with call order of peek() before next() vs next()
3543before peek().
3544 For a clean implementation, check out Google's guava library
3545source code.
3546Follow up: How would you extend your design to be generic and work
3547with all types, not just integer?
3548Credits:Special thanks to @porker2008 for adding this problem and
3549creating all test cases.
3550------------------------------
3551------------------------------
3552------------------------------
3553------------------------------
3554Find the Duplicate Number
3555------------------------------
3556Given an array nums containing n + 1 integers where each integer is
3557between 1 and n (inclusive), prove that at least one duplicate
3558number must exist. Assume that there is only one duplicate number,
3559find the duplicate one.
3560Note:
3561You must not modify the array (assume the array is read only).
3562You must use only constant, O(1) extra space.
3563Your runtime complexity should be less than O(n2).
3564There is only one duplicate number in the array, but it could be
3565repeated more than once.
3566Credits:Special thanks to @jianchao.li.fighter for adding this
3567problem and creating all test cases.
3568------------------------------
3569------------------------------
3570------------------------------
3571Game of Life
3572------------------------------
3573According to the Wikipedia's article: "The Game of Life, also known
3574simply as Life, is a cellular automaton devised by the British 
3575mathematician John Horton Conway in 1970."
3576Given a board with m by n cells, each cell has an initial state live
3577(1) or dead (0). Each cell interacts with its eight neighbors
3578(horizontal, vertical, diagonal) using the following four rules
3579(taken from the above Wikipedia article):
3580Any live cell with fewer than two live neighbors dies, as if caused
3581by under-population.
3582Any live cell with two or three live neighbors lives on to the next
3583generation.
3584Any live cell with more than three live neighbors dies, as if by
3585over-population..
3586Any dead cell with exactly three live neighbors becomes a live cell,
3587as if by reproduction.
3588Write a function to compute the next state (after one update) of the
3589board given its current state.
3590Follow up:
3591Could you solve it in-place? Remember that the board needs to be
3592updated at the same time: You cannot update some cells first and
3593then use their updated values to update other cells.
3594In this question, we represent the board using a 2D array. In
3595principle, the board is infinite, which would cause problems when
3596the active area encroaches the border of the array. How would you
3597address these problems?
3598Credits:Special thanks to @jianchao.li.fighter for adding this
3599problem and creating all test cases.
3600------------------------------
3601------------------------------
3602Word Pattern
3603------------------------------
3604Given a pattern and a string str, find if str follows the same
3605pattern.
3606 Here follow means a full match, such that there is a bijection
3607between a letter in pattern and a non-empty word in str.
3608Examples:
3609pattern = "abba", str = "dog cat cat dog" should return true.
3610pattern = "abba", str = "dog cat cat fish" should return false.
3611pattern = "aaaa", str = "dog cat cat dog" should return false.
3612pattern = "abba", str = "dog dog dog dog" should return false.
3613Notes:
3614You may assume pattern contains only lowercase letters, and str
3615contains lowercase letters separated by a single space.
3616Credits:Special thanks to @minglotus6 for adding this problem and
3617creating all test cases.
3618------------------------------
3619------------------------------
3620------------------------------
3621Nim Game
3622------------------------------
3623You are playing the following Nim Game with your friend: There is a
3624heap of stones on the table, each time one of you take turns to
3625remove 1 to 3 stones. The one who removes the last stone will be the
3626winner. You will take the first turn to remove the stones.
3627Both of you are very clever and have optimal strategies for the
3628game. Write a function to determine whether you can win the game
3629given the number of stones in the heap.
3630For example, if there are 4 stones in the heap, then you will never
3631win the game: no matter 1, 2, or 3 stones you remove, the last stone
3632will always be removed by your friend.
3633 If there are 5 stones in the heap, could you figure out a way to
3634remove the stones such that you will always be the winner?
3635Credits:Special thanks to @jianchao.li.fighter for adding this
3636problem and creating all test cases.
3637------------------------------
3638------------------------------
3639------------------------------
3640------------------------------
3641Find Median from Data Stream
3642------------------------------
3643Median is the middle value in an ordered integer list. If the size
3644of the list is even, there is no middle value. So the median is the
3645mean of the two middle value.
3646Examples:
3647[2,3,4] , the median is 3
3648[2,3], the median is (2 + 3) / 2 = 2.5
3649Design a data structure that supports the following two operations:
3650void addNum(int num) - Add a integer number from the data stream to
3651the data structure.
3652double findMedian() - Return the median of all elements so far.
3653For example:
3654addNum(1)
3655addNum(2)
3656findMedian() -> 1.5
3657addNum(3)
3658findMedian() -> 2
3659Credits:Special thanks to @Louis1992 for adding this problem and
3660creating all test cases.
3661------------------------------
3662------------------------------
3663------------------------------
3664Serialize and Deserialize Binary Tree
3665------------------------------
3666Serialization is the process of converting a data structure or
3667object into a sequence of bits so that it can be stored in a file or
3668memory buffer, or transmitted across a network connection link to be
3669reconstructed later in the same or another computer environment.
3670Design an algorithm to serialize and deserialize a binary tree.
3671There is no restriction on how your serialization/deserialization
3672algorithm should work. You just need to ensure that a binary tree
3673can be serialized to a string and this string can be deserialized to
3674the original tree structure.
3675For example, you may serialize the following tree
3676 1
3677 / \
3678 2 3
3679 / \
3680 4 5
3681as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ
3682serializes a binary tree. You do not necessarily need to follow this
3683format, so please be creative and come up with different approaches
3684yourself.
3685Note: Do not use class member/global/static variables to store
3686states. Your serialize and deserialize algorithms should be
3687stateless.
3688Credits:Special thanks to @Louis1992 for adding this problem and
3689creating all test cases.
3690------------------------------
3691------------------------------
3692------------------------------
3693Bulls and Cows
3694------------------------------
3695You are playing the following Bulls and Cows game with your friend:
3696You write down a number and ask your friend to guess what the number
3697is. Each time your friend makes a guess, you provide a hint that
3698indicates how many digits in said guess match your secret number
3699exactly in both digit and position (called "bulls") and how many
3700digits match the secret number but locate in the wrong position
3701(called "cows"). Your friend will use successive guesses and hints
3702to eventually derive the secret number.
3703For example:
3704Secret number: "1807"
3705Friend's guess: "7810"
3706Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
3707Write a function to return a hint according to the secret number and
3708friend's guess, use A to indicate the bulls and B to indicate the
3709cows. In the above example, your function should return "1A3B".
3710Please note that both secret number and friend's guess may contain
3711duplicate digits, for example:
3712Secret number: "1123"
3713Friend's guess: "0111"
3714In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd
37151 is a cow, and your function should return "1A1B".
3716You may assume that the secret number and your friend's guess only
3717contain digits, and their lengths are always equal.
3718Credits:Special thanks to @jeantimex for adding this problem and
3719creating all test cases.
3720------------------------------
3721------------------------------
3722Longest Increasing Subsequence
3723------------------------------
3724Given an unsorted array of integers, find the length of longest
3725increasing subsequence.
3726For example,
3727Given [10, 9, 2, 5, 3, 7, 101, 18],
3728The longest increasing subsequence is [2, 3, 7, 101], therefore the
3729length is 4. Note that there may be more than one LIS combination,
3730it is only necessary for you to return the length.
3731Your algorithm should run in O(n2) complexity.
3732Follow up: Could you improve it to O(n log n) time complexity?
3733Credits:Special thanks to @pbrother for adding this problem and
3734creating all test cases.
3735------------------------------
3736------------------------------
3737Remove Invalid Parentheses
3738------------------------------
3739Remove the minimum number of invalid parentheses in order to make
3740the input string valid. Return all possible results.
3741Note: The input string may contain letters other than the
3742parentheses ( and ).
3743Examples:
3744"()())()" -> ["()()()", "(())()"]
3745"(a)())()" -> ["(a)()()", "(a())()"]
3746")(" -> [""]
3747Credits:Special thanks to @hpplayer for adding this problem and
3748creating all test cases.
3749------------------------------
3750------------------------------
3751------------------------------
3752Range Sum Query - Immutable
3753------------------------------
3754Given an integer array nums, find the sum of the elements between
3755indices i and j (i &le; j), inclusive.
3756Example:
3757Given nums = [-2, 0, 3, -5, 2, -1]
3758sumRange(0, 2) -> 1
3759sumRange(2, 5) -> -1
3760sumRange(0, 5) -> -3
3761Note:
3762You may assume that the array does not change.
3763There are many calls to sumRange function.
3764------------------------------
3765------------------------------
3766Range Sum Query 2D - Immutable
3767------------------------------
3768Given a 2D matrix matrix, find the sum of the elements inside the
3769rectangle defined by its upper left corner (row1, col1) and lower
3770right corner (row2, col2).
3771The above rectangle (with the red border) is defined by (row1, col1)
3772= (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
3773Example:
3774Given matrix = [
3775 [3, 0, 1, 4, 2],
3776 [5, 6, 3, 2, 1],
3777 [1, 2, 0, 1, 5],
3778 [4, 1, 0, 1, 7],
3779 [1, 0, 3, 0, 5]
3780]
3781sumRegion(2, 1, 4, 3) -> 8
3782sumRegion(1, 1, 2, 2) -> 11
3783sumRegion(1, 2, 2, 4) -> 12
3784Note:
3785You may assume that the matrix does not change.
3786There are many calls to sumRegion function.
3787You may assume that row1 &le; row2 and col1 &le; col2.
3788------------------------------
3789------------------------------
3790------------------------------
3791Additive Number
3792------------------------------
3793Additive number is a string whose digits can form additive sequence.
3794A valid additive sequence should contain at least three numbers.
3795Except for the first two numbers, each subsequent number in the
3796sequence must be the sum of the preceding two.
3797For example:
3798"112358" is an additive number because the digits can form an
3799additive sequence: 1, 1, 2, 3, 5, 8.
38001 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
3801"199100199" is also an additive number, the additive sequence is: 1,
380299, 100, 199.
38031 + 99 = 100, 99 + 100 = 199
3804Note: Numbers in the additive sequence cannot have leading zeros, so
3805sequence 1, 2, 03 or 1, 02, 3 is invalid.
3806Given a string containing only digits '0'-'9', write a function to
3807determine if it's an additive number.
3808Follow up:
3809How would you handle overflow for very large input integers?
3810Credits:Special thanks to @jeantimex for adding this problem and
3811creating all test cases.
3812------------------------------
3813------------------------------
3814Range Sum Query - Mutable
3815------------------------------
3816Given an integer array nums, find the sum of the elements between
3817indices i and j (i &le; j), inclusive.
3818The update(i, val) function modifies nums by updating the element at
3819index i to val.
3820Example:
3821Given nums = [1, 3, 5]
3822sumRange(0, 2) -> 9
3823update(1, 2)
3824sumRange(0, 2) -> 8
3825Note:
3826The array is only modifiable by the update function.
3827You may assume the number of calls to update and sumRange function
3828is distributed evenly.
3829------------------------------
3830------------------------------
3831------------------------------
3832Minimum Height Trees
3833------------------------------
3834 For a undirected graph with tree characteristics, we can choose
3835any node as the root. The result graph is then a rooted tree. Among
3836all possible rooted trees, those with minimum height are called
3837minimum height trees (MHTs).
3838 Given such a graph, write a function to find all the MHTs and
3839return a list of their root labels.
3840 Format
3841 The graph contains n nodes which are labeled from 0 to n - 1.
3842 You will be given the number n and a list of undirected edges
3843(each edge is a pair of labels).
3844You can assume that no duplicate edges will appear in edges. Since
3845all edges are
3846 undirected, [0, 1] is the same as [1, 0] and thus will not
3847appear together in
3848 edges.
3849 Example 1:
3850 Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
3851 0
3852 |
3853 1
3854 / \
3855 2 3
3856 return [1]
3857 Example 2:
3858 Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
3859 0 1 2
3860 \ | /
3861 3
3862 |
3863 4
3864 |
3865 5
3866 return [3, 4]
3867 How many MHTs can a graph have at most?
3868 Note:
3869 (1) According to the definition
3870 of tree on Wikipedia: “a tree is an undirected graph in which
3871any two vertices are connected by
3872 exactly one path. In other words, any connected graph without
3873simple cycles is a tree.”
3874 (2) The height of a rooted tree is the number of edges on the
3875longest downward path between the root and a
3876 leaf.
3877Credits:Special thanks to @dietpepsi for adding this problem and
3878creating all test cases.
3879------------------------------
3880------------------------------
3881------------------------------
3882Burst Balloons
3883------------------------------
3884 Given n balloons, indexed from 0 to n-1. Each balloon is painted
3885with a
3886 number on it represented by array nums.
3887 You are asked to burst all the balloons. If the you burst
3888 balloon i you will get nums[left] * nums[i] * nums[right] coins.
3889Here left
3890 and right are adjacent indices of i. After the burst, the left
3891and right
3892 then becomes adjacent.
3893 Find the maximum coins you can collect by bursting the balloons
3894wisely.
3895 Note:
3896 (1) You may imagine nums[-1] = nums[n] = 1. They are not real
3897therefore you can not burst them.
3898 (2) 0 &le; n &le; 500, 0 &le; nums[i] &le; 100
3899 Example:
3900 Given [3, 1, 5, 8]
3901 Return 167
3902 nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
3903 coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
3904Credits:Special thanks to @dietpepsi for adding this problem and
3905creating all test cases.
3906------------------------------
3907------------------------------
3908Super Ugly Number
3909------------------------------
3910 Write a program to find the nth super ugly number.
3911 Super ugly numbers are positive numbers whose all prime factors
3912are in the given prime list
3913 primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19,
391426, 28, 32]
3915 is the sequence of the first 12 super ugly numbers given primes
3916 = [2, 7, 13, 19] of size 4.
3917 Note:
3918 (1) 1 is a super ugly number for any given primes.
3919 (2) The given numbers in primes are in ascending order.
3920 (3) 0 < k &le; 100, 0 < n &le; 106, 0 < primes[i] < 1000.
3921 (4) The nth super ugly number is guaranteed to fit in a 32-bit
3922signed integer.
3923Credits:Special thanks to @dietpepsi for adding this problem and
3924creating all test cases.
3925------------------------------
3926------------------------------
3927------------------------------
3928Count of Smaller Numbers After Self
3929------------------------------
3930You are given an integer array nums and you have to return a new
3931counts array.
3932The counts array has the property where counts[i] is
3933the number of smaller elements to the right of nums[i].
3934Example:
3935Given nums = [5, 2, 6, 1]
3936To the right of 5 there are 2 smaller elements (2 and 1).
3937To the right of 2 there is only 1 smaller element (1).
3938To the right of 6 there is 1 smaller element (1).
3939To the right of 1 there is 0 smaller element.
3940Return the array [2, 1, 1, 0].
3941------------------------------
3942------------------------------
3943Remove Duplicate Letters
3944------------------------------
3945Given a string which contains only lowercase letters, remove
3946duplicate letters so that every letter appear once and only once.
3947You must make sure your result is the smallest in lexicographical
3948order among all possible results.
3949Example:
3950Given "bcabc"
3951Return "abc"
3952Given "cbacdcbc"
3953Return "acdb"
3954Credits:Special thanks to @dietpepsi for adding this problem and
3955creating all test cases.
3956------------------------------
3957------------------------------
3958------------------------------
3959Maximum Product of Word Lengths
3960------------------------------
3961 Given a string array words, find the maximum value of
3962length(word[i]) * length(word[j]) where the two words do not share
3963common letters.
3964 You may assume that each word will contain only lower case
3965letters.
3966 If no such two words exist, return 0.
3967 Example 1:
3968 Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
3969 Return 16
3970 The two words can be "abcw", "xtfn".
3971 Example 2:
3972 Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
3973 Return 4
3974 The two words can be "ab", "cd".
3975 Example 3:
3976 Given ["a", "aa", "aaa", "aaaa"]
3977 Return 0
3978 No such pair of words.
3979Credits:Special thanks to @dietpepsi for adding this problem and
3980creating all test cases.
3981------------------------------
3982------------------------------
3983Bulb Switcher
3984------------------------------
3985There are n bulbs that are initially off. You first turn on all the
3986bulbs. Then, you turn off every second bulb. On the third round, you
3987toggle every third bulb (turning on if it's off or turning off if
3988it's on). For the ith round, you toggle every i bulb. For the nth
3989round, you only toggle the last bulb.
3990Find how many bulbs are on after n rounds.
3991Example:
3992Given n = 3.
3993At first, the three bulbs are [off, off, off].
3994After first round, the three bulbs are [on, on, on].
3995After second round, the three bulbs are [on, off, on].
3996After third round, the three bulbs are [on, off, off].
3997So you should return 1, because there is only one bulb is on.
3998------------------------------
3999------------------------------
4000------------------------------
4001Create Maximum Number
4002------------------------------
4003 Given two arrays of length m and n with digits 0-9 representing
4004two numbers.
4005 Create the maximum number of length k <= m + n from digits of
4006the two. The relative order of the digits
4007 from the same array must be preserved. Return an array of the k
4008digits. You should try to optimize your time and space complexity.
4009 Example 1:
4010 nums1 = [3, 4, 6, 5]
4011 nums2 = [9, 1, 2, 5, 8, 3]
4012 k = 5
4013 return [9, 8, 6, 5, 3]
4014 Example 2:
4015 nums1 = [6, 7]
4016 nums2 = [6, 0, 4]
4017 k = 5
4018 return [6, 7, 6, 0, 4]
4019 Example 3:
4020 nums1 = [3, 9]
4021 nums2 = [8, 9]
4022 k = 3
4023 return [9, 8, 9]
4024Credits:Special thanks to @dietpepsi for adding this problem and
4025creating all test cases.
4026------------------------------
4027------------------------------
4028Coin Change
4029------------------------------
4030You are given coins of different denominations and a total amount of
4031money amount. Write a function to compute the fewest number of coins
4032that you need to make up that amount. If that amount of money cannot
4033be made up by any combination of the coins, return -1.
4034Example 1:
4035coins = [1, 2, 5], amount = 11
4036return 3 (11 = 5 + 5 + 1)
4037Example 2:
4038coins = [2], amount = 3
4039return -1.
4040Note:
4041You may assume that you have an infinite number of each kind of
4042coin.
4043Credits:Special thanks to @jianchao.li.fighter for adding this
4044problem and creating all test cases.
4045------------------------------
4046------------------------------
4047------------------------------
4048Wiggle Sort II
4049------------------------------
4050 Given an unsorted array nums, reorder it such that
4051 nums[0] < nums[1] > nums[2] < nums[3]....
4052 Example:
4053 (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1,
40544, 1, 5, 1, 6].
4055 (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2,
40563, 1, 3, 1, 2].
4057 Note:
4058 You may assume all input has valid answer.
4059 Follow Up:
4060 Can you do it in O(n) time and/or in-place with O(1) extra
4061space?
4062Credits:Special thanks to @dietpepsi for adding this problem and
4063creating all test cases.
4064------------------------------
4065------------------------------
4066------------------------------
4067Power of Three
4068------------------------------
4069 Given an integer, write a function to determine if it is a power
4070of three.
4071 Follow up:
4072 Could you do it without using any loop / recursion?
4073Credits:Special thanks to @dietpepsi for adding this problem and
4074creating all test cases.
4075------------------------------
4076------------------------------
4077Count of Range Sum
4078------------------------------
4079 Given an integer array nums, return the number of range sums
4080that lie in [lower, upper] inclusive.
4081 Range sum S(i, j) is defined as the sum of the elements in nums
4082between indices i and
4083 j (i ≤ j), inclusive.
4084 Note:
4085 A naive algorithm of O(n2) is trivial. You MUST do better than
4086that.
4087 Example:
4088 Given nums = [-2, 5, -1], lower = -2, upper = 2,
4089 Return 3.
4090 The three ranges are : [0, 0], [2, 2], [0, 2] and their
4091respective sums are: -2, -1, 2.
4092Credits:Special thanks to @dietpepsi for adding this problem and
4093creating all test cases.
4094------------------------------
4095------------------------------
4096Odd Even Linked List
4097------------------------------
4098Given a singly linked list, group all odd nodes together followed by
4099the even nodes. Please note here we are talking about the node
4100number and not the value in the nodes.
4101You should try to do it in place. The program should run in O(1)
4102space complexity and O(nodes) time complexity.
4103Example:
4104Given 1->2->3->4->5->NULL,
4105return 1->3->5->2->4->NULL.
4106Note:
4107The relative order inside both the even and odd groups should remain
4108as it was in the input.
4109The first node is considered odd, the second node even and so on ...
4110Credits:Special thanks to @DjangoUnchained for adding this problem
4111and creating all test cases.
4112------------------------------
4113------------------------------
4114Longest Increasing Path in a Matrix
4115------------------------------
4116Given an integer matrix, find the length of the longest increasing
4117path.
4118From each cell, you can either move to four directions: left, right,
4119up or down. You may NOT move diagonally or move outside of the
4120boundary (i.e. wrap-around is not allowed).
4121Example 1:
4122nums = [
4123 [9,9,4],
4124 [6,6,8],
4125 [2,1,1]
4126]
4127Return 4
4128The longest increasing path is [1, 2, 6, 9].
4129Example 2:
4130nums = [
4131 [3,4,5],
4132 [3,2,6],
4133 [2,2,1]
4134]
4135Return 4
4136The longest increasing path is [3, 4, 5, 6]. Moving diagonally is
4137not allowed.
4138Credits:Special thanks to @dietpepsi for adding this problem and
4139creating all test cases.
4140------------------------------
4141------------------------------
4142Patching Array
4143------------------------------
4144Given a sorted positive integer array nums and an integer n, add/
4145patch elements to the array such that any number in range [1, n]
4146inclusive can be formed by the sum of some elements in the array.
4147Return the minimum number of patches required.
4148Example 1:
4149nums = [1, 3], n = 6
4150Return 1.
4151Combinations of nums are [1], [3], [1,3], which form possible sums
4152of: 1, 3, 4.
4153Now if we add/patch 2 to nums, the combinations are: [1], [2], [3],
4154[1,3], [2,3], [1,2,3].
4155Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1,
41566].
4157So we only need 1 patch.
4158Example 2:
4159nums = [1, 5, 10], n = 20
4160Return 2.
4161The two patches can be [2, 4].
4162Example 3:
4163nums = [1, 2, 2], n = 5
4164Return 0.
4165Credits:Special thanks to @dietpepsi for adding this problem and
4166creating all test cases.
4167------------------------------
4168------------------------------
4169Verify Preorder Serialization of a Binary Tree
4170------------------------------
4171One way to serialize a binary tree is to use pre-order traversal. 
4172When we encounter a non-null node, we record the node's value. If it
4173is a null node, we record using a sentinel value such as #.
4174 _9_
4175 / \
4176 3 2
4177 / \ / \
4178 4 1 # 6
4179/ \ / \ / \
4180# # # # # #
4181For example, the above binary tree can be serialized to the string
4182"9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
4183Given a string of comma separated values, verify whether it is a
4184correct preorder traversal serialization of a binary tree. Find an
4185algorithm without reconstructing the tree.
4186Each comma separated value in the string must be either an integer
4187or a character '#' representing null pointer.
4188You may assume that the input format is always valid, for example it
4189could never contain two consecutive commas such as "1,,3".
4190Example 1:
4191"9,3,4,#,#,1,#,#,2,#,6,#,#"
4192Return true
4193Example 2:
4194"1,#"
4195Return false
4196Example 3:
4197"9,#,#,1"
4198Return false
4199Credits:Special thanks to @dietpepsi for adding this problem and
4200creating all test cases.
4201------------------------------
4202------------------------------
4203Reconstruct Itinerary
4204------------------------------
4205Given a list of airline tickets represented by pairs of departure
4206and arrival airports [from, to], reconstruct the itinerary in order.
4207All of the tickets belong to a man who departs from JFK. Thus, the
4208itinerary must begin with JFK.
4209Note:
4210If there are multiple valid itineraries, you should return the
4211itinerary that has the smallest lexical order when read as a single
4212string. For example, the itinerary ["JFK", "LGA"] has a smaller 
4213lexical order than ["JFK", "LGB"].
4214All airports are represented by three capital letters (IATA code).
4215You may assume all tickets form at least one valid itinerary.
4216 Example 1:
4217 tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"],
4218["LHR", "SFO"]]
4219 Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
4220 Example 2:
4221 tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],
4222["ATL","JFK"],["ATL","SFO"]]
4223 Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
4224 Another possible reconstruction is
4225["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical
4226order.
4227Credits:Special thanks to @dietpepsi for adding this problem and
4228creating all test cases.
4229------------------------------
4230------------------------------
4231------------------------------
4232Increasing Triplet Subsequence
4233------------------------------
4234Given an unsorted array return whether an increasing subsequence of
4235length 3 exists or not in the array.
4236Formally the function should:
4237Return true if there exists i, j, k
4238such that arr[i] &lt; arr[j] &lt; arr[k] given 0 &le; i &lt; j &lt;
4239k &le; n-1
4240else return false.
4241Your algorithm should run in O(n) time complexity and O(1) space
4242complexity.
4243Examples:
4244Given [1, 2, 3, 4, 5],
4245return true.
4246Given [5, 4, 3, 2, 1],
4247return false.
4248Credits:Special thanks to @DjangoUnchained for adding this problem
4249and creating all test cases.
4250------------------------------
4251------------------------------
4252Self Crossing
4253------------------------------
4254 You are given an array x of n positive numbers. You start at
4255point (0,0) and moves x[0] metres to the north, then x[1] metres to
4256the west,
4257 x[2] metres to the south,
4258 x[3] metres to the east and so on. In other words, after each
4259move your direction changes
4260 counter-clockwise.
4261 Write a one-pass algorithm with O(1) extra space to determine,
4262if your path crosses itself, or not.
4263Example 1:
4264Given x = [2, 1, 1, 2],
4265┌───┐
4266│ │
4267└───┼──>
4268 │
4269Return true (self crossing)
4270Example 2:
4271Given x = [1, 2, 3, 4],
4272┌──────┐
4273│ │
4274│
4275│
4276└────────────>
4277Return false (not self crossing)
4278Example 3:
4279Given x = [1, 1, 1, 1],
4280┌───┐
4281│ │
4282└───┼>
4283Return true (self crossing)
4284Credits:Special thanks to @dietpepsi for adding this problem and
4285creating all test cases.
4286------------------------------
4287------------------------------
4288Palindrome Pairs
4289------------------------------
4290 Given a list of unique words, find all pairs of distinct indices
4291(i, j) in the given list, so that the concatenation of the two
4292words, i.e. words[i] + words[j] is a palindrome.
4293 Example 1:
4294 Given words = ["bat", "tab", "cat"]
4295 Return [[0, 1], [1, 0]]
4296 The palindromes are ["battab", "tabbat"]
4297 Example 2:
4298 Given words = ["abcd", "dcba", "lls", "s", "sssll"]
4299 Return [[0, 1], [1, 0], [3, 2], [2, 4]]
4300 The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
4301Credits:Special thanks to @dietpepsi for adding this problem and
4302creating all test cases.
4303------------------------------
4304------------------------------
4305House Robber III
4306------------------------------
4307The thief has found himself a new place for his thievery again.
4308There is only one entrance to this area, called the "root." Besides
4309the root, each house has one and only one parent house. After a
4310tour, the smart thief realized that "all houses in this place forms
4311a binary tree". It will automatically contact the police if two
4312directly-linked houses were broken into on the same night.
4313Determine the maximum amount of money the thief can rob tonight
4314without alerting the police.
4315Example 1:
4316 3
4317 / \
4318 2 3
4319 \ \
4320 3 1
4321Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
4322Example 2:
4323 3
4324 / \
4325 4 5
4326 / \ \
4327 1 3 1
4328Maximum amount of money the thief can rob = 4 + 5 = 9.
4329Credits:Special thanks to @dietpepsi for adding this problem and
4330creating all test cases.
4331------------------------------
4332------------------------------
4333Counting Bits
4334------------------------------
4335Given a non negative integer number num. For every numbers i in the
4336range 0 &le; i &le; num calculate the number of 1's in their binary
4337representation and return them as an array.
4338Example:
4339For num = 5 you should return [0,1,1,2,1,2].
4340Follow up:
4341It is very easy to come up with a solution with run time
4342O(n*sizeof(integer)). But can you do it in linear time O(n) /
4343possibly in a single pass?
4344Space complexity should be O(n).
4345Can you do it like a boss? Do it without using any builtin function
4346like __builtin_popcount in c++ or in any other language.
4347 You should make use of what you have produced already.
4348 Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on.
4349And try to generate new range from previous.
4350 Or does the odd/even status of the number help you in calculating
4351the number of 1s?
4352Credits:Special thanks to @ syedee for adding this problem and 
4353creating all test cases.
4354------------------------------
4355------------------------------
4356------------------------------
4357------------------------------
4358Flatten Nested List Iterator
4359------------------------------
4360Given a nested list of integers, implement an iterator to flatten
4361it.
4362Each element is either an integer, or a list -- whose elements may
4363also be integers or other lists.
4364Example 1:
4365Given the list [[1,1],2,[1,1]],
4366By calling next repeatedly until hasNext returns false, the order of
4367elements returned by next should be: [1,1,2,1,1].
4368Example 2:
4369Given the list [1,[4,[6]]],
4370By calling next repeatedly until hasNext returns false, the order of
4371elements returned by next should be: [1,4,6].
4372------------------------------
4373------------------------------
4374Power of Four
4375------------------------------
4376Given an integer (signed 32 bits), write a function to check whether
4377it is a power of 4.
4378Example:
4379Given num = 16, return true.
4380Given num = 5, return false.
4381Follow up: Could you solve it without loops/recursion?
4382Credits:Special thanks to @yukuairoy for adding this problem and
4383creating all test cases.
4384------------------------------
4385------------------------------
4386Integer Break
4387------------------------------
4388Given a positive integer n, break it into the sum of at least two
4389positive integers and maximize the product of those integers. Return
4390the maximum product you can get.
4391For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return
439236 (10 = 3 + 3 + 4).
4393Note: You may assume that n is not less than 2 and not larger than
439458.
4395 There is a simple O(n) solution to this problem.
4396 You may check the breaking results of n ranging from 7 to 10 to
4397discover the regularities.
4398Credits:Special thanks to @jianchao.li.fighter for adding this
4399problem and creating all test cases.
4400------------------------------
4401------------------------------
4402Reverse String
4403------------------------------
4404Write a function that takes a string as input and returns the string
4405reversed.
4406Example:
4407Given s = "hello", return "olleh".
4408------------------------------
4409------------------------------
4410Reverse Vowels of a String
4411------------------------------
4412Write a function that takes a string as input and reverse only the
4413vowels of a string.
4414Example 1:
4415Given s = "hello", return "holle".
4416Example 2:
4417Given s = "leetcode", return "leotcede".
4418Note:
4419The vowels does not include the letter "y".
4420------------------------------
4421------------------------------
4422------------------------------
4423Top K Frequent Elements
4424------------------------------
4425Given a non-empty array of integers, return the k most frequent
4426elements.
4427For example,
4428Given [1,1,1,2,2,3] and k = 2, return [1,2].
4429Note:
4430You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
4431Your algorithm's time complexity must be better than O(n log n),
4432where n is the array's size.
4433------------------------------
4434------------------------------
4435------------------------------
4436Intersection of Two Arrays
4437------------------------------
4438Given two arrays, write a function to compute their intersection.
4439Example:
4440Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
4441Note:
4442Each element in the result must be unique.
4443The result can be in any order.
4444------------------------------
4445------------------------------
4446Intersection of Two Arrays II
4447------------------------------
4448Given two arrays, write a function to compute their intersection.
4449Example:
4450Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
4451Note:
4452Each element in the result should appear as many times as it shows
4453in both arrays.
4454The result can be in any order.
4455Follow up:
4456What if the given array is already sorted? How would you optimize
4457your algorithm?
4458What if nums1's size is small compared to nums2's size? Which
4459algorithm is better?
4460What if elements of nums2 are stored on disk, and the memory is
4461limited such that you cannot load all elements into the memory at
4462once?
4463------------------------------
4464------------------------------
4465------------------------------
4466Data Stream as Disjoint Intervals
4467------------------------------
4468Given a data stream input of non-negative integers a1, a2, ...,
4469an, ..., summarize the numbers seen so far as a list of disjoint
4470intervals.
4471For example, suppose the integers from the data stream are 1, 3, 7,
44722, 6, ..., then the summary will be:
4473[1, 1]
4474[1, 1], [3, 3]
4475[1, 1], [3, 3], [7, 7]
4476[1, 3], [7, 7]
4477[1, 3], [6, 7]
4478Follow up:
4479What if there are lots of merges and the number of disjoint
4480intervals are small compared to the data stream's size?
4481Credits:Special thanks to @yunhong for adding this problem and
4482creating most of the test cases.
4483------------------------------
4484------------------------------
4485------------------------------
4486Russian Doll Envelopes
4487------------------------------
4488You have a number of envelopes with widths and heights given as a
4489pair of integers (w, h). One envelope can fit into another if and
4490only if both the width and height of one envelope is greater than
4491the width and height of the other envelope.
4492What is the maximum number of envelopes can you Russian doll? (put
4493one inside other)
4494Example:
4495Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of
4496envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
4497------------------------------
4498------------------------------
4499Design Twitter
4500------------------------------
4501Design a simplified version of Twitter where users can post tweets,
4502follow/unfollow another user and is able to see the 10 most recent
4503tweets in the user's news feed. Your design should support the
4504following methods:
4505postTweet(userId, tweetId): Compose a new tweet.
4506getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the
4507user's news feed. Each item in the news feed must be posted by users
4508who the user followed or by the user herself. Tweets must be ordered
4509from most recent to least recent.
4510follow(followerId, followeeId): Follower follows a followee.
4511unfollow(followerId, followeeId): Follower unfollows a followee.
4512Example:
4513Twitter twitter = new Twitter();
4514// User 1 posts a new tweet (id = 5).
4515twitter.postTweet(1, 5);
4516// User 1's news feed should return a list with 1 tweet id -> [5].
4517twitter.getNewsFeed(1);
4518// User 1 follows user 2.
4519twitter.follow(1, 2);
4520// User 2 posts a new tweet (id = 6).
4521twitter.postTweet(2, 6);
4522// User 1's news feed should return a list with 2 tweet ids -> [6,
45235].
4524// Tweet id 6 should precede tweet id 5 because it is posted after
4525tweet id 5.
4526twitter.getNewsFeed(1);
4527// User 1 unfollows user 2.
4528twitter.unfollow(1, 2);
4529// User 1's news feed should return a list with 1 tweet id -> [5],
4530// since user 1 is no longer following user 2.
4531twitter.getNewsFeed(1);
4532------------------------------
4533------------------------------
4534------------------------------
4535------------------------------
4536------------------------------
4537------------------------------
4538------------------------------
4539------------------------------
4540Max Sum of Rectangle No Larger Than K
4541------------------------------
4542Given a non-empty 2D matrix matrix and an integer k, find the max
4543sum of a rectangle in the matrix such that its sum is no larger than
4544k.
4545Example:
4546Given matrix = [
4547 [1, 0, 1],
4548 [0, -2, 3]
4549]
4550k = 2
4551The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2
4552and 2 is the max number no larger than k (k = 2).
4553Note:
4554The rectangle inside the matrix must have an area > 0.
4555What if the number of rows is much larger than the number of
4556columns?
4557Credits:Special thanks to @fujiaozhu for adding this problem and
4558creating all test cases.
4559------------------------------
4560------------------------------
4561------------------------------
4562Water and Jug Problem
4563------------------------------
4564You are given two jugs with capacities x and y litres. There is an
4565infinite amount of water supply available.
4566You need to determine whether it is possible to measure exactly z
4567litres using these two jugs.
4568If z liters of water is measurable, you must have z liters of water
4569contained within one or both buckets by the end.
4570Operations allowed:
4571Fill any of the jugs completely with water.
4572Empty any of the jugs.
4573Pour water from one jug into another till the other jug is
4574completely full or the first jug itself is empty.
4575Example 1: (From the famous "Die Hard" example)
4576Input: x = 3, y = 5, z = 4
4577Output: True
4578Example 2:
4579Input: x = 2, y = 6, z = 5
4580Output: False
4581Credits:Special thanks to @vinod23 for adding this problem and
4582creating all test cases.
4583------------------------------
4584------------------------------
4585------------------------------
4586Valid Perfect Square
4587------------------------------
4588Given a positive integer num, write a function which returns True if
4589num is a perfect square else False.
4590Note: Do not use any built-in library function such as sqrt.
4591Example 1:
4592Input: 16
4593Returns: True
4594Example 2:
4595Input: 14
4596Returns: False
4597Credits:Special thanks to @elmirap for adding this problem and
4598creating all test cases.
4599------------------------------
4600------------------------------
4601Largest Divisible Subset
4602------------------------------
4603Given a set of distinct positive integers, find the largest subset
4604such that every pair (Si, Sj) of elements in this subset satisfies:
4605Si % Sj = 0 or Sj % Si = 0.
4606If there are multiple solutions, return any subset is fine.
4607Example 1:
4608nums: [1,2,3]
4609Result: [1,2] (of course, [1,3] will also be ok)
4610Example 2:
4611nums: [1,2,4,8]
4612Result: [1,2,4,8]
4613Credits:Special thanks to @Stomach_ache for adding this problem and
4614creating all test cases.
4615------------------------------
4616------------------------------
4617------------------------------
4618------------------------------
4619Sum of Two Integers
4620------------------------------
4621Calculate the sum of two integers a and b, but you are not allowed
4622to use the operator + and -.
4623Example:
4624Given a = 1 and b = 2, return 3.
4625Credits:Special thanks to @fujiaozhu for adding this problem and
4626creating all test cases.
4627------------------------------
4628------------------------------
4629Super Pow
4630------------------------------
4631Your task is to calculate ab mod 1337 where a is a positive integer
4632and b is an extremely large positive integer given in the form of an
4633array.
4634Example1:
4635a = 2
4636b = [3]
4637Result: 8
4638Example2:
4639a = 2
4640b = [1,0]
4641Result: 1024
4642Credits:Special thanks to @Stomach_ache for adding this problem and
4643creating all test cases.
4644------------------------------
4645------------------------------
4646Find K Pairs with Smallest Sums
4647------------------------------
4648You are given two integer arrays nums1 and nums2 sorted in ascending
4649order and an integer k.
4650Define a pair (u,v) which consists of one element from the first
4651array and one element from the second array.
4652Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
4653Example 1:
4654Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3
4655Return: [1,2],[1,4],[1,6]
4656The first 3 pairs are returned from the sequence:
4657[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
4658Example 2:
4659Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2
4660Return: [1,1],[1,1]
4661The first 2 pairs are returned from the sequence:
4662[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
4663Example 3:
4664Given nums1 = [1,2], nums2 = [3], k = 3
4665Return: [1,3],[2,3]
4666All possible pairs are returned from the sequence:
4667[1,3],[2,3]
4668Credits:Special thanks to @elmirap and @StefanPochmann for adding
4669this problem and creating all test cases.
4670------------------------------
4671------------------------------
4672Guess Number Higher or Lower
4673------------------------------
4674We are playing the Guess Game. The game is as follows:
4675I pick a number from 1 to n. You have to guess which number I
4676picked.
4677Every time you guess wrong, I'll tell you whether the number is
4678higher or lower.
4679You call a pre-defined API guess(int num) which returns 3 possible
4680results (-1, 1, or 0):
4681-1 : My number is lower
4682 1 : My number is higher
4683 0 : Congrats! You got it!
4684Example:
4685n = 10, I pick 6.
4686Return 6.
4687------------------------------
4688------------------------------
4689Guess Number Higher or Lower II
4690------------------------------
4691We are playing the Guess Game. The game is as follows:
4692I pick a number from 1 to n. You have to guess which number I
4693picked.
4694Every time you guess wrong, I'll tell you whether the number I
4695picked is higher or lower.
4696However, when you guess a particular number x, and you guess wrong,
4697you pay $x. You win the game when you guess the number I picked.
4698Example:
4699n = 10, I pick 8.
4700First round: You guess 5, I tell you that it's higher. You pay $5.
4701Second round: You guess 7, I tell you that it's higher. You pay $7.
4702Third round: You guess 9, I tell you that it's lower. You pay $9.
4703Game over. 8 is the number I picked.
4704You end up paying $5 + $7 + $9 = $21.
4705Given a particular n &ge; 1, find out how much money you need to
4706have to guarantee a win.
4707 The best strategy to play the game is to minimize the maximum
4708loss you could possibly face. Another strategy is to minimize the
4709expected loss. Here, we are interested in the first scenario.
4710 Take a small example (n = 3). What do you end up paying in the
4711worst case?
4712 Check out this article if you're still stuck.
4713 The purely recursive implementation of minimax would be worthless
4714for even a small n. You MUST use dynamic programming.
4715 As a follow-up, how would you modify your code to solve the problem
4716of minimizing the expected loss, instead of the worst-case loss?
4717Credits:Special thanks to @agave and @StefanPochmann for adding this
4718problem and creating all test cases.
4719------------------------------
4720------------------------------
4721Wiggle Subsequence
4722------------------------------
4723A sequence of numbers is called a wiggle sequence if the differences
4724between successive numbers strictly alternate between positive and
4725negative. The first difference (if one exists) may be either
4726positive or negative. A sequence with fewer than two elements is
4727trivially a wiggle sequence.
4728For example, [1,7,4,9,2,5] is a wiggle sequence because the
4729differences (6,-3,5,-7,3) are alternately positive and negative. In
4730contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the
4731first because its first two differences are positive and the second
4732because its last difference is zero.
4733Given a sequence of integers, return the length of the longest
4734subsequence that is a wiggle sequence. A subsequence is obtained by
4735deleting some number of elements (eventually, also zero) from the
4736original sequence, leaving the remaining elements in their original 
4737order.
4738Examples:
4739Input: [1,7,4,9,2,5]
4740Output: 6
4741The entire sequence is a wiggle sequence.
4742Input: [1,17,5,10,13,15,10,5,16,8]
4743Output: 7
4744There are several subsequences that achieve this length. One is
4745[1,17,10,13,10,16,8].
4746Input: [1,2,3,4,5,6,7,8,9]
4747Output: 2
4748Follow up:
4749Can you do it in O(n) time?
4750Credits:Special thanks to @agave and @StefanPochmann for adding this
4751problem and creating all test cases.
4752------------------------------
4753------------------------------
4754Combination Sum IV
4755------------------------------
4756 Given an integer array with all positive numbers and no duplicates,
4757find the number of possible combinations that add up to a positive
4758integer target.
4759Example:
4760nums = [1, 2, 3]
4761target = 4
4762The possible combination ways are:
4763(1, 1, 1, 1)
4764(1, 1, 2)
4765(1, 2, 1)
4766(1, 3)
4767(2, 1, 1)
4768(2, 2)
4769(3, 1)
4770Note that different sequences are counted as different combinations.
4771Therefore the output is 7.
4772Follow up:
4773What if negative numbers are allowed in the given array?
4774How does it change the problem?
4775What limitation we need to add to the question to allow negative
4776numbers?
4777Credits:Special thanks to @pbrother for adding this problem and
4778creating all test cases.
4779------------------------------
4780------------------------------
4781Kth Smallest Element in a Sorted Matrix
4782------------------------------
4783Given a n x n matrix where each of the rows and columns are sorted
4784in ascending order, find the kth smallest element in the matrix.
4785Note that it is the kth smallest element in the sorted order, not
4786the kth distinct element.
4787Example:
4788matrix = [
4789 [ 1, 5, 9],
4790 [10, 11, 13],
4791 [12, 13, 15]
4792],
4793k = 8,
4794return 13.
4795Note:
4796You may assume k is always valid, 1 ≤ k ≤ n2.
4797------------------------------
4798------------------------------
4799------------------------------
4800Insert Delete GetRandom O(1)
4801------------------------------
4802Design a data structure that supports all following operations in
4803average O(1) time.
4804insert(val): Inserts an item val to the set if not already present.
4805remove(val): Removes an item val from the set if present.
4806getRandom: Returns a random element from current set of elements.
4807Each element must have the same probability of being returned.
4808Example:
4809// Init an empty set.
4810RandomizedSet randomSet = new RandomizedSet();
4811// Inserts 1 to the set. Returns true as 1 was inserted
4812successfully.
4813randomSet.insert(1);
4814// Returns false as 2 does not exist in the set.
4815randomSet.remove(2);
4816// Inserts 2 to the set, returns true. Set now contains [1,2].
4817randomSet.insert(2);
4818// getRandom should return either 1 or 2 randomly.
4819randomSet.getRandom();
4820// Removes 1 from the set, returns true. Set now contains [2].
4821randomSet.remove(1);
4822// 2 was already in the set, so return false.
4823randomSet.insert(2);
4824// Since 2 is the only number in the set, getRandom always return 2.
4825randomSet.getRandom();
4826------------------------------
4827------------------------------
4828Insert Delete GetRandom O(1) - Duplicates allowed
4829------------------------------
4830Design a data structure that supports all following operations in
4831average O(1) time.
4832Note: Duplicate elements are allowed.
4833insert(val): Inserts an item val to the collection.
4834remove(val): Removes an item val from the collection if present.
4835getRandom: Returns a random element from current collection of
4836elements. The probability of each element being returned is linearly
4837related to the number of same value the collection contains.
4838Example:
4839// Init an empty collection.
4840RandomizedCollection collection = new RandomizedCollection();
4841// Inserts 1 to the collection. Returns true as the collection did
4842not contain 1.
4843collection.insert(1);
4844// Inserts another 1 to the collection. Returns false as the
4845collection contained 1. Collection now contains [1,1].
4846collection.insert(1);
4847// Inserts 2 to the collection, returns true. Collection now
4848contains [1,1,2].
4849collection.insert(2);
4850// getRandom should return 1 with the probability 2/3, and returns 2
4851with the probability 1/3.
4852collection.getRandom();
4853// Removes 1 from the collection, returns true. Collection now
4854contains [1,2].
4855collection.remove(1);
4856// getRandom should return 1 and 2 both equally likely.
4857collection.getRandom();
4858------------------------------
4859------------------------------
4860Linked List Random Node
4861------------------------------
4862Given a singly linked list, return a random node's value from the
4863linked list. Each node must have the same probability of being
4864chosen.
4865Follow up:
4866What if the linked list is extremely large and its length is unknown
4867to you? Could you solve this efficiently without using extra space?
4868Example:
4869// Init a singly linked list [1,2,3].
4870ListNode head = new ListNode(1);
4871head.next = new ListNode(2);
4872head.next.next = new ListNode(3);
4873Solution solution = new Solution(head);
4874// getRandom() should return either 1, 2, or 3 randomly. Each
4875element should have equal probability of returning.
4876solution.getRandom();
4877------------------------------
4878------------------------------
4879Ransom Note
4880------------------------------
4881Given an arbitrary ransom note string and another string containing
4882letters from all the magazines, write a function that will return
4883true if the ransom
4884note can be constructed from the magazines ; otherwise, it will
4885return false. 
4886Each letter in the magazine string can only be used once in your
4887ransom note.
4888Note:
4889You may assume that both strings contain only lowercase letters.
4890canConstruct("a", "b") -> false
4891canConstruct("aa", "ab") -> false
4892canConstruct("aa", "aab") -> true
4893------------------------------
4894------------------------------
4895Shuffle an Array
4896------------------------------
4897Shuffle a set of numbers without duplicates.
4898Example:
4899// Init an array with set 1, 2, and 3.
4900int[] nums = {1,2,3};
4901Solution solution = new Solution(nums);
4902// Shuffle the array [1,2,3] and return its result. Any permutation
4903of [1,2,3] must equally likely to be returned.
4904solution.shuffle();
4905// Resets the array back to its original configuration [1,2,3].
4906solution.reset();
4907// Returns the random shuffling of array [1,2,3].
4908solution.shuffle();
4909------------------------------
4910------------------------------
4911Mini Parser
4912------------------------------
4913Given a nested list of integers represented as a string, implement a
4914parser to deserialize it.
4915Each element is either an integer, or a list -- whose elements may
4916also be integers or other lists.
4917Note:
4918You may assume that the string is well-formed:
4919String is non-empty.
4920String does not contain white spaces.
4921String contains only digits 0-9, [, - ,, ].
4922Example 1:
4923Given s = "324",
4924You should return a NestedInteger object which contains a single
4925integer 324.
4926Example 2:
4927Given s = "[123,[456,[789]]]",
4928Return a NestedInteger object containing a nested list with 2
4929elements:
49301. An integer containing value 123.
49312. A nested list containing two elements:
4932 i. An integer containing value 456.
4933 ii. A nested list with one element:
4934 a. An integer containing value 789.
4935------------------------------
4936------------------------------
4937Lexicographical Numbers
4938------------------------------
4939Given an integer n, return 1 - n in lexicographical order.
4940For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
4941Please optimize your algorithm to use less time and space. The input
4942size may be as large as 5,000,000.
4943------------------------------
4944------------------------------
4945First Unique Character in a String
4946------------------------------
4947Given a string, find the first non-repeating character in it and
4948return it's index. If it doesn't exist, return -1.
4949Examples:
4950s = "leetcode"
4951return 0.
4952s = "loveleetcode",
4953return 2.
4954Note: You may assume the string contain only lowercase letters.
4955------------------------------
4956------------------------------
4957Longest Absolute File Path
4958------------------------------
4959Suppose we abstract our file system by a string in the following
4960manner:
4961The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
4962dir
4963 subdir1
4964 subdir2
4965 file.ext
4966The directory dir contains an empty sub-directory subdir1 and a subdirectory subdir2 containing a file file.ext.
4967The string
4968"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsu
4969bdir2\n\t\t\tfile2.ext" represents:
4970dir
4971 subdir1
4972 file1.ext
4973 subsubdir1
4974 subdir2
4975 subsubdir2
4976 file2.ext
4977The directory dir contains two sub-directories subdir1 and subdir2.
4978subdir1 contains a file file1.ext and an empty second-level subdirectory subsubdir1. subdir2 contains a second-level sub-directory
4979subsubdir2 containing a file file2.ext.
4980We are interested in finding the longest (number of characters)
4981absolute path to a file within our file system. For example, in the
4982second example above, the longest absolute path is "dir/subdir2/
4983subsubdir2/file2.ext", and its length is 32 (not including the
4984double quotes).
4985Given a string representing the file system in the above format,
4986return the length of the longest absolute path to file in the
4987abstracted file system. If there is no file in the system, return 0.
4988Note:
4989The name of a file contains at least a . and an extension.
4990The name of a directory or sub-directory will not contain a ..
4991Time complexity required: O(n) where n is the size of the input
4992string.
4993Notice that a/aa/aaa/file1.txt is not the longest file path, if
4994there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.
4995------------------------------
4996------------------------------
4997Find the Difference
4998------------------------------
4999Given two strings s and t which consist of only lowercase letters.
5000String t is generated by random shuffling string s and then add one
5001more letter at a random position.
5002Find the letter that was added in t.
5003Example:
5004Input:
5005s = "abcd"
5006t = "abcde"
5007Output:
5008e
5009Explanation:
5010'e' is the letter that was added.
5011------------------------------
5012------------------------------
5013Elimination Game
5014------------------------------
5015There is a list of sorted integers from 1 to n. Starting from left
5016to right, remove the first number and every other number afterward
5017until you reach the end of the list.
5018Repeat the previous step again, but this time from right to left,
5019remove the right most number and every other number from the
5020remaining numbers.
5021We keep repeating the steps again, alternating left to right and
5022right to left, until a single number remains.
5023Find the last number that remains starting with a list of length n.
5024Example:
5025Input:
5026n = 9,
50271 2 3 4 5 6 7 8 9
50282 4 6 8
50292 6
50306
5031Output:
50326
5033------------------------------
5034------------------------------
5035Perfect Rectangle
5036------------------------------
5037Given N axis-aligned rectangles where N > 0, determine if they all
5038together form an exact cover of a rectangular region.
5039Each rectangle is represented as a bottom-left point and a top-right
5040point. For example, a unit square is represented as [1,1,2,2].
5041(coordinate of bottom-left point is (1, 1) and top-right point is
5042(2, 2)).
5043Example 1:
5044rectangles = [
5045 [1,1,3,3],
5046 [3,1,4,2],
5047 [3,2,4,4],
5048 [1,3,2,4],
5049 [2,3,3,4]
5050]
5051Return true. All 5 rectangles together form an exact cover of a
5052rectangular region.
5053Example 2:
5054rectangles = [
5055 [1,1,2,3],
5056 [1,3,2,4],
5057 [3,1,4,2],
5058 [3,2,4,4]
5059]
5060Return false. Because there is a gap between the two rectangular
5061regions.
5062Example 3:
5063rectangles = [
5064 [1,1,3,3],
5065 [3,1,4,2],
5066 [1,3,2,4],
5067 [3,2,4,4]
5068]
5069Return false. Because there is a gap in the top center.
5070Example 4:
5071rectangles = [
5072 [1,1,3,3],
5073 [3,1,4,2],
5074 [1,3,2,4],
5075 [2,2,4,4]
5076]
5077Return false. Because two of the rectangles overlap with each other.
5078------------------------------
5079------------------------------
5080Is Subsequence
5081------------------------------
5082Given a string s and a string t, check if s is subsequence of t.
5083You may assume that there is only lower case English letters in both
5084s and t. t is potentially a very long (length ~= 500,000) string,
5085and s is a short string (<=100).
5086A subsequence of a string is a new string which is formed from the
5087original string by deleting some (can be none) of the characters
5088without disturbing the relative positions of the remaining
5089characters. (ie, "ace" is a subsequence of "abcde" while "aec" is
5090not).
5091Example 1:
5092s = "abc", t = "ahbgdc"
5093Return true.
5094Example 2:
5095s = "axc", t = "ahbgdc"
5096Return false.
5097Follow up:
5098If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B,
5099and you want to check one by one to see if T has its subsequence. In
5100this scenario, how would you change your code?
5101Credits:Special thanks to @pbrother for adding this problem and
5102creating all test cases.
5103------------------------------
5104------------------------------
5105UTF-8 Validation
5106------------------------------
5107A character in UTF8 can be from 1 to 4 bytes long, subjected to the
5108following rules:
5109For 1-byte character, the first bit is a 0, followed by its unicode
5110code.
5111For n-bytes character, the first n-bits are all one's, the n+1 bit
5112is 0, followed by n-1 bytes with most significant 2 bits being 10.
5113This is how the UTF-8 encoding would work:
5114 Char. number range | UTF-8 octet sequence
5115 (hexadecimal) | (binary)
5116 --------------------
5117+---------------------------------------------
5118 0000 0000-0000 007F | 0xxxxxxx
5119 0000 0080-0000 07FF | 110xxxxx 10xxxxxx
5120 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
5121 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
5122Given an array of integers representing the data, return whether it
5123is a valid utf-8 encoding.
5124Note:
5125The input is an array of integers. Only the least significant 8 bits
5126of each integer is used to store the data. This means each integer
5127represents only 1 byte of data.
5128Example 1:
5129data = [197, 130, 1], which represents the octet sequence: 11000101
513010000010 00000001.
5131Return true.
5132It is a valid utf-8 encoding for a 2-bytes character followed by a
51331-byte character.
5134Example 2:
5135data = [235, 140, 4], which represented the octet sequence: 11101011
513610001100 00000100.
5137Return false.
5138The first 3 bits are all one's and the 4th bit is 0 means it is a 3-
5139bytes character.
5140The next byte is a continuation byte which starts with 10 and that's
5141correct.
5142But the second continuation byte does not start with 10, so it is
5143invalid.
5144------------------------------
5145------------------------------
5146Decode String
5147------------------------------
5148Given an encoded string, return it's decoded string.
5149The encoding rule is: k[encoded_string], where the encoded_string
5150inside the square brackets is being repeated exactly k times. Note
5151that k is guaranteed to be a positive integer.
5152You may assume that the input string is always valid; No extra white
5153spaces, square brackets are well-formed, etc.
5154Furthermore, you may assume that the original data does not contain
5155any digits and that digits are only for those repeat numbers, k. For
5156example, there won't be input like 3a or 2[4].
5157Examples:
5158s = "3[a]2[bc]", return "aaabcbc".
5159s = "3[a2[c]]", return "accaccacc".
5160s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
5161------------------------------
5162------------------------------
5163Longest Substring with At Least K Repeating Characters
5164------------------------------
5165Find the length of the longest substring T of a given string
5166(consists of lowercase letters only) such that every character in T
5167appears no less than k times.
5168Example 1:
5169Input:
5170s = "aaabb", k = 3
5171Output:
51723
5173The longest substring is "aaa", as 'a' is repeated 3 times.
5174Example 2:
5175Input:
5176s = "ababbc", k = 2
5177Output:
51785
5179The longest substring is "ababb", as 'a' is repeated 2 times and 'b'
5180is repeated 3 times.
5181------------------------------
5182------------------------------
5183Rotate Function
5184------------------------------
5185Given an array of integers A and let n to be its length.
5186Assume Bk to be an array obtained by rotating the array A k
5187positions clock-wise, we define a "rotation function" F on A as
5188follow:
5189F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
5190Calculate the maximum value of F(0), F(1), ..., F(n-1).
5191Note:
5192n is guaranteed to be less than 105.
5193Example:
5194A = [4, 3, 2, 6]
5195F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
5196F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
5197F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
5198F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
5199So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
5200------------------------------
5201------------------------------
5202Integer Replacement
5203------------------------------
5204Given a positive integer n and you can do operations as follow:
5205If n is even, replace n with n/2.
5206If n is odd, you can replace n with either n + 1 or n - 1.
5207What is the minimum number of replacements needed for n to become 1?
5208Example 1:
5209Input:
52108
5211Output:
52123
5213Explanation:
52148 -> 4 -> 2 -> 1
5215Example 2:
5216Input:
52177
5218Output:
52194
5220Explanation:
52217 -> 8 -> 4 -> 2 -> 1
5222or
52237 -> 6 -> 3 -> 2 -> 1
5224------------------------------
5225------------------------------
5226Random Pick Index
5227------------------------------
5228Given an array of integers with possible duplicates, randomly output
5229the index of a given target number. You can assume that the given
5230target number must exist in the array.
5231Note:
5232The array size can be very large. Solution that uses too much extra
5233space will not pass the judge.
5234Example:
5235int[] nums = new int[] {1,2,3,3,3};
5236Solution solution = new Solution(nums);
5237// pick(3) should return either index 2, 3, or 4 randomly. Each
5238index should have equal probability of returning.
5239solution.pick(3);
5240// pick(1) should return 0. Since in the array only nums[0] is equal
5241to 1.
5242solution.pick(1);
5243------------------------------
5244------------------------------
5245Evaluate Division
5246------------------------------
5247Equations are given in the format A / B = k, where A and B are
5248variables represented as strings, and k is a real number (floating
5249point number). Given some queries, return the answers. If the answer
5250does not exist, return -1.0.
5251Example:
5252Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a
5253= ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0,
52541.0, -1.0 ].
5255The input is: vector&lt;pair&lt;string, string&gt;&gt; equations,
5256vector&lt;double&gt;&amp; values, vector&lt;pair&lt;string,
5257string&gt;&gt; queries , where equations.size() == values.size(),
5258and the values are positive. This represents the equations. Return
5259vector&lt;double&gt;.
5260According to the example above:
5261equations = [ ["a", "b"], ["b", "c"] ],
5262values = [2.0, 3.0],
5263queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x",
5264"x"] ].
5265The input is always valid. You may assume that evaluating the
5266queries will result in no division by zero and there is no
5267contradiction.
5268------------------------------
5269------------------------------
5270Nth Digit
5271------------------------------
5272Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5,
52736, 7, 8, 9, 10, 11, ...
5274Note:
5275n is positive and will fit within the range of a 32-bit signed
5276integer (n < 231).
5277Example 1:
5278Input:
52793
5280Output:
52813
5282Example 2:
5283Input:
528411
5285Output:
52860
5287Explanation:
5288The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
528911, ... is a 0, which is part of the number 10.
5290------------------------------
5291------------------------------
5292Binary Watch
5293------------------------------
5294A binary watch has 4 LEDs on the top which represent the hours
5295(0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
5296Each LED represents a zero or one, with the least significant bit on
5297the right.
5298For example, the above binary watch reads "3:25".
5299Given a non-negative integer n which represents the number of LEDs
5300that are currently on, return all possible times the watch could
5301represent.
5302Example:
5303Input: n = 1Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02",
5304"0:04", "0:08", "0:16", "0:32"]
5305Note:
5306The order of output does not matter.
5307The hour must not contain a leading zero, for example "01:00" is not
5308valid, it should be "1:00".
5309The minute must be consist of two digits and may contain a leading
5310zero, for example "10:2" is not valid, it should be "10:02".
5311------------------------------
5312------------------------------
5313Remove K Digits
5314------------------------------
5315Given a non-negative integer num represented as a string, remove k
5316digits from the number so that the new number is the smallest
5317possible.
5318Note:
5319The length of num is less than 10002 and will be &ge; k.
5320The given num does not contain any leading zero.
5321Example 1:
5322Input: num = "1432219", k = 3
5323Output: "1219"
5324Explanation: Remove the three digits 4, 3, and 2 to form the new
5325number 1219 which is the smallest.
5326Example 2:
5327Input: num = "10200", k = 1
5328Output: "200"
5329Explanation: Remove the leading 1 and the number is 200. Note that
5330the output must not contain leading zeroes.
5331Example 3:
5332Input: num = "10", k = 2
5333Output: "0"
5334Explanation: Remove all the digits from the number and it is left
5335with nothing which is 0.
5336------------------------------
5337------------------------------
5338Frog Jump
5339------------------------------
5340A frog is crossing a river. The river is divided into x units and at
5341each unit there may or may not exist a stone. The frog can jump on a
5342stone, but it must not jump into the water.
5343Given a list of stones' positions (in units) in sorted ascending
5344order, determine if the frog is able to cross the river by landing
5345on the last stone. Initially, the frog is on the first stone and
5346assume the first jump must be 1 unit.
5347If the frog's last jump was k units, then its next jump must be
5348either k - 1, k, or k + 1 units. Note that the frog can only jump in
5349the forward direction.
5350Note:
5351The number of stones is &ge; 2 and is < 1,100.
5352Each stone's position will be a non-negative integer < 231.
5353The first stone's position is always 0.
5354Example 1:
5355[0,1,3,5,6,8,12,17]
5356There are a total of 8 stones.
5357The first stone at the 0th unit, second stone at the 1st unit,
5358third stone at the 3rd unit, and so on...
5359The last stone at the 17th unit.
5360Return true. The frog can jump to the last stone by jumping
53611 unit to the 2nd stone, then 2 units to the 3rd stone, then
53622 units to the 4th stone, then 3 units to the 6th stone,
53634 units to the 7th stone, and 5 units to the 8th stone.
5364Example 2:
5365[0,1,2,3,4,8,9,11]
5366Return false. There is no way to jump to the last stone as
5367the gap between the 5th and 6th stone is too large.
5368------------------------------
5369------------------------------
5370Sum of Left Leaves
5371------------------------------
5372Find the sum of all left leaves in a given binary tree.
5373Example:
5374 3
5375 / \
5376 9 20
5377 / \
5378 15 7
5379There are two left leaves in the binary tree, with values 9 and 15
5380respectively. Return 24.
5381------------------------------
5382------------------------------
5383Convert a Number to Hexadecimal
5384------------------------------
5385Given an integer, write an algorithm to convert it to hexadecimal.
5386For negative integer, two’s complement method is used.
5387Note:
5388All letters in hexadecimal (a-f) must be in lowercase.
5389The hexadecimal string must not contain extra leading 0s. If the
5390number is zero, it is represented by a single zero character '0';
5391otherwise, the first character in the hexadecimal string will not be
5392the zero character.
5393The given number is guaranteed to fit within the range of a 32-bit
5394signed integer.
5395You must not use any method provided by the library which converts/
5396formats the number to hex directly.
5397Example 1:
5398Input:
539926
5400Output:
5401"1a"
5402Example 2:
5403Input:
5404-1
5405Output:
5406"ffffffff"
5407------------------------------
5408------------------------------
5409Queue Reconstruction by Height
5410------------------------------
5411Suppose you have a random list of people standing in a queue. Each
5412person is described by a pair of integers (h, k), where h is the
5413height of the person and k is the number of people in front of this
5414person who have a height greater than or equal to h. Write an
5415algorithm to reconstruct the queue.
5416Note:
5417The number of people is less than 1,100.
5418Example
5419Input:
5420[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
5421Output:
5422[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
5423------------------------------
5424------------------------------
5425Trapping Rain Water II
5426------------------------------
5427Given an m x n matrix of positive integers representing the height
5428of each unit cell in a 2D elevation map, compute the volume of water
5429it is able to trap after raining.
5430Note:
5431Both m and n are less than 110. The height of each unit cell is
5432greater than 0 and is less than 20,000.
5433Example:
5434Given the following 3x6 height map:
5435[
5436 [1,4,3,1,3,2],
5437 [3,2,1,3,2,4],
5438 [2,3,3,2,3,1]
5439]
5440Return 4.
5441The above image represents the elevation map [[1,4,3,1,3,2],
5442[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.
5443After the rain, water are trapped between the blocks. The total
5444volume of water trapped is 4.
5445------------------------------
5446------------------------------
5447------------------------------
5448Longest Palindrome
5449------------------------------
5450Given a string which consists of lowercase or uppercase letters,
5451find the length of the longest palindromes that can be built with
5452those letters.
5453This is case sensitive, for example "Aa" is not considered a
5454palindrome here.
5455Note:
5456Assume the length of given string will not exceed 1,010.
5457Example:
5458Input:
5459"abccccdd"
5460Output:
54617
5462Explanation:
5463One longest palindrome that can be built is "dccaccd", whose length
5464is 7.
5465------------------------------
5466------------------------------
5467Split Array Largest Sum
5468------------------------------
5469Given an array which consists of non-negative integers and an
5470integer m, you can split the array into m non-empty continuous
5471subarrays. Write an algorithm to minimize the largest sum among
5472these m subarrays.
5473Note:
5474If n is the length of array, assume the following constraints are
5475satisfied:
54761 &le; n &le; 1000
54771 &le; m &le; min(50, n)
5478Examples:
5479Input:
5480nums = [7,2,5,10,8]
5481m = 2
5482Output:
548318
5484Explanation:
5485There are four ways to split nums into two subarrays.
5486The best way is to split it into [7,2,5] and [10,8],
5487where the largest sum among the two subarrays is only 18.
5488------------------------------
5489------------------------------
5490------------------------------
5491Fizz Buzz
5492------------------------------
5493Write a program that outputs the string representation of numbers
5494from 1 to n.
5495But for multiples of three it should output “Fizz” instead of the
5496number and for the multiples of five output “Buzz”. For numbers
5497which are multiples of both three and five output “FizzBuzz”.
5498Example:
5499n = 15,
5500Return:
5501[
5502 "1",
5503 "2",
5504 "Fizz",
5505 "4",
5506 "Buzz",
5507 "Fizz",
5508 "7",
5509 "8",
5510 "Fizz",
5511 "Buzz",
5512 "11",
5513 "Fizz",
5514 "13",
5515 "14",
5516 "FizzBuzz"
5517]
5518------------------------------
5519------------------------------
5520Arithmetic Slices
5521------------------------------
5522A sequence of number is called arithmetic if it consists of at least
5523three elements and if the difference between any two consecutive
5524elements is the same.
5525For example, these are arithmetic sequence:
55261, 3, 5, 7, 9
55277, 7, 7, 7
55283, -1, -5, -9
5529The following sequence is not arithmetic. 1, 1, 2, 5, 7
5530A zero-indexed array A consisting of N numbers is given. A slice of
5531that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
5532A slice (P, Q) of array A is called arithmetic if the sequence:
5533 A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In 
5534particular, this means that P + 1 < Q.
5535The function should return the number of arithmetic slices in the
5536array A.
5537Example:
5538A = [1, 2, 3, 4]
5539return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and
5540[1, 2, 3, 4] itself.
5541------------------------------
5542------------------------------
5543Third Maximum Number
5544------------------------------
5545Given a non-empty array of integers, return the third maximum number
5546in this array. If it does not exist, return the maximum number. The
5547time complexity must be in O(n).
5548Example 1:
5549Input: [3, 2, 1]
5550Output: 1
5551Explanation: The third maximum is 1.
5552Example 2:
5553Input: [1, 2]
5554Output: 2
5555Explanation: The third maximum does not exist, so the maximum (2) is
5556returned instead.
5557Example 3:
5558Input: [2, 2, 3, 1]
5559Output: 1
5560Explanation: Note that the third maximum here means the third
5561maximum distinct number.
5562Both numbers with value 2 are both considered as second maximum.
5563------------------------------
5564------------------------------
5565Add Strings
5566------------------------------
5567Given two non-negative integers num1 and num2 represented as string,
5568return the sum of num1 and num2.
5569Note:
5570The length of both num1 and num2 is < 5100.
5571Both num1 and num2 contains only digits 0-9.
5572Both num1 and num2 does not contain any leading zero.
5573You must not use any built-in BigInteger library or convert the
5574inputs to integer directly.
5575------------------------------
5576------------------------------
5577Partition Equal Subset Sum
5578------------------------------
5579Given a non-empty array containing only positive integers, find if
5580the array can be partitioned into two subsets such that the sum of
5581elements in both subsets is equal.
5582Note:
5583Each of the array element will not exceed 100.
5584The array size will not exceed 200.
5585Example 1:
5586Input: [1, 5, 11, 5]
5587Output: true
5588Explanation: The array can be partitioned as [1, 5, 5] and [11].
5589Example 2:
5590Input: [1, 2, 3, 5]
5591Output: false
5592Explanation: The array cannot be partitioned into equal sum subsets.
5593------------------------------
5594------------------------------
5595Pacific Atlantic Water Flow
5596------------------------------
5597Given an m x n matrix of non-negative integers representing the
5598height of each unit cell in a continent, the "Pacific ocean" touches
5599the left and top edges of the matrix and the "Atlantic ocean"
5600touches the right and bottom edges.
5601Water can only flow in four directions (up, down, left, or right)
5602from a cell to another one with height equal or lower.
5603Find the list of grid coordinates where water can flow to both the
5604Pacific and Atlantic ocean.
5605Note:
5606The order of returned grid coordinates does not matter.
5607Both m and n are less than 150.
5608Example:
5609Given the following 5x5 matrix:
5610 Pacific ~ ~ ~ ~ ~
5611 ~ 1 2 2 3 (5) *
5612 ~ 3 2 3 (4) (4) *
5613 ~ 2 4 (5) 3 1 *
5614 ~ (6) (7) 1 4 5 *
5615 ~ (5) 1 1 2 4 *
5616 * * * * * Atlantic
5617Return:
5618[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions
5619with parentheses in above matrix).
5620------------------------------
5621------------------------------
5622------------------------------
5623Battleships in a Board
5624------------------------------
5625Given an 2D board, count how many battleships are in it. The
5626battleships are represented with 'X's, empty slots are represented
5627with '.'s. You may assume the following rules:
5628You receive a valid board, made of only battleships or empty slots.
5629Battleships can only be placed horizontally or vertically. In other
5630words, they can only be made of the shape 1xN (1 row, N columns) or
5631Nx1 (N rows, 1 column), where N can be of any size.
5632At least one horizontal or vertical cell separates between two
5633battleships - there are no adjacent battleships.
5634Example:
5635X..X
5636...X
5637...X
5638In the above board there are 2 battleships.
5639Invalid Example:
5640...X
5641XXXX
5642...X
5643This is an invalid board that you will not receive - as battleships
5644will always have a cell separating between them.
5645Follow up:Could you do it in one-pass, using only O(1) extra memory
5646and without modifying the value of the board?
5647------------------------------
5648------------------------------
5649Strong Password Checker
5650------------------------------
5651A password is considered strong if below conditions are all met:
5652 It has at least 6 characters and at most 20 characters.
5653 It must contain at least one lowercase letter, at least one
5654uppercase letter, and at least one digit.
5655 It must NOT contain three repeating characters in a row
5656("...aaa..." is weak, but "...aa...a..." is strong, assuming other
5657conditions are met).
5658Write a function strongPasswordChecker(s), that takes a string s as
5659input, and return the MINIMUM change required to make s a strong
5660password. If s is already strong, return 0.
5661Insertion, deletion or replace of any one character are all
5662considered as one change.
5663------------------------------
5664------------------------------
5665Maximum XOR of Two Numbers in an Array
5666------------------------------
5667Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0
5668&le; ai < 231.
5669Find the maximum result of ai XOR aj, where 0 &le; i, j &lt; n.
5670Could you do this in O(n) runtime?
5671Example:
5672Input: [3, 10, 5, 25, 2, 8]
5673Output: 28
5674Explanation: The maximum result is 5 ^ 25 = 28.
5675------------------------------
5676------------------------------
5677------------------------------
5678Reconstruct Original Digits from English
5679------------------------------
5680Given a non-empty string containing an out-of-order English
5681representation of digits 0-9, output the digits in ascending order.
5682Note:
5683Input contains only lowercase English letters.
5684Input is guaranteed to be valid and can be transformed to its
5685original digits. That means invalid inputs such as "abc" or "zerone"
5686are not permitted.
5687Input length is less than 50,000.
5688Example 1:
5689Input: "owoztneoer"
5690Output: "012"
5691Example 2:
5692Input: "fviefuro"
5693Output: "45"
5694------------------------------
5695------------------------------
5696Longest Repeating Character Replacement
5697------------------------------
5698Given a string that consists of only uppercase English letters, you
5699can replace any letter in the string with another letter at most k
5700times. Find the length of a longest substring containing all
5701repeating letters you can get after performing the above operations.
5702Note:
5703Both the string's length and k will not exceed 104.
5704Example 1:
5705Input:
5706s = "ABAB", k = 2
5707Output:
57084
5709Explanation:
5710Replace the two 'A's with two 'B's or vice versa.
5711Example 2:
5712Input:
5713s = "AABABBA", k = 1
5714Output:
57154
5716Explanation:
5717Replace the one 'A' in the middle with 'B' and form "AABBBBA".
5718The substring "BBBB" has the longest repeating letters, which is 4.
5719------------------------------
5720------------------------------
5721------------------------------
5722All O`one Data Structure
5723------------------------------
5724Implement a data structure supporting the following operations:
5725Inc(Key) - Inserts a new key with value 1. Or increments an
5726existing key by 1. Key is guaranteed to be a non-empty string.
5727Dec(Key) - If Key's value is 1, remove it from the data structure.
5728Otherwise decrements an existing key by 1. If the key does not
5729exist, this function does nothing. Key is guaranteed to be a nonempty string.
5730GetMaxKey() - Returns one of the keys with maximal value. If no
5731element exists, return an empty string "".
5732GetMinKey() - Returns one of the keys with minimal value. If no
5733element exists, return an empty string "".
5734Challenge: Perform all these in O(1) time complexity.
5735------------------------------
5736------------------------------
5737Number of Segments in a String
5738------------------------------
5739Count the number of segments in a string, where a segment is defined
5740to be a contiguous sequence of non-space characters.
5741Please note that the string does not contain any non-printable
5742characters.
5743Example:
5744Input: "Hello, my name is John"
5745Output: 5
5746------------------------------
5747------------------------------
5748Non-overlapping Intervals
5749------------------------------
5750Given a collection of intervals, find the minimum number of
5751intervals you need to remove to make the rest of the intervals nonoverlapping.
5752Note:
5753You may assume the interval's end point is always bigger than its
5754start point.
5755Intervals like [1,2] and [2,3] have borders "touching" but they
5756don't overlap each other.
5757Example 1:
5758Input: [ [1,2], [2,3], [3,4], [1,3] ]
5759Output: 1
5760Explanation: [1,3] can be removed and the rest of intervals are nonoverlapping.
5761Example 2:
5762Input: [ [1,2], [1,2], [1,2] ]
5763Output: 2
5764Explanation: You need to remove two [1,2] to make the rest of
5765intervals non-overlapping.
5766Example 3:
5767Input: [ [1,2], [2,3] ]
5768Output: 0
5769Explanation: You don't need to remove any of the intervals since
5770they're already non-overlapping.
5771------------------------------
5772------------------------------
5773Find Right Interval
5774------------------------------
5775Given a set of intervals, for each of the interval i, check if there
5776exists an interval j whose start point is bigger than or equal to
5777the end point of the interval i, which can be called that j is on
5778the "right" of i.
5779For any interval i, you need to store the minimum interval j's
5780index, which means that the interval j has the minimum start point
5781to build the "right" relationship for interval i. If the interval j
5782doesn't exist, store -1 for the interval i. Finally, you need output
5783the stored value of each interval as an array.
5784Note:
5785You may assume the interval's end point is always bigger than its
5786start point.
5787You may assume none of these intervals have the same start point.
5788Example 1:
5789Input: [ [1,2] ]
5790Output: [-1]
5791Explanation: There is only one interval in the collection, so it
5792outputs -1.
5793Example 2:
5794Input: [ [3,4], [2,3], [1,2] ]
5795Output: [-1, 0, 1]
5796Explanation: There is no satisfied "right" interval for [3,4].
5797For [2,3], the interval [3,4] has minimum-"right" start point;
5798For [1,2], the interval [2,3] has minimum-"right" start point.
5799Example 3:
5800Input: [ [1,4], [2,3], [3,4] ]
5801Output: [-1, 2, -1]
5802Explanation: There is no satisfied "right" interval for [1,4] and
5803[3,4].
5804For [2,3], the interval [3,4] has minimum-"right" start point.
5805------------------------------
5806------------------------------
5807Path Sum III
5808------------------------------
5809You are given a binary tree in which each node contains an integer
5810value.
5811Find the number of paths that sum to a given value.
5812The path does not need to start or end at the root or a leaf, but it
5813must go downwards
5814(traveling only from parent nodes to child nodes).
5815The tree has no more than 1,000 nodes and the values are in the
5816range -1,000,000 to 1,000,000.
5817Example:
5818root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
5819 10
5820 / \
5821 5 -3
5822 / \ \
5823 3 2 11
5824 / \ \
58253 -2 1
5826Return 3. The paths that sum to 8 are:
58271. 5 -> 3
58282. 5 -> 2 -> 1
58293. -3 -> 11
5830------------------------------
5831------------------------------
5832Find All Anagrams in a String
5833------------------------------
5834Given a string s and a non-empty string p, find all the start 
5835indices of p's anagrams in s.
5836Strings consists of lowercase English letters only and the length of
5837both strings s and p will not be larger than 20,100.
5838The order of output does not matter.
5839Example 1:
5840Input:
5841s: "cbaebabacd" p: "abc"
5842Output:
5843[0, 6]
5844Explanation:
5845The substring with start index = 0 is "cba", which is an anagram of
5846"abc".
5847The substring with start index = 6 is "bac", which is an anagram of
5848"abc".
5849Example 2:
5850Input:
5851s: "abab" p: "ab"
5852Output:
5853[0, 1, 2]
5854Explanation:
5855The substring with start index = 0 is "ab", which is an anagram of
5856"ab".
5857The substring with start index = 1 is "ba", which is an anagram of
5858"ab".
5859The substring with start index = 2 is "ab", which is an anagram of
5860"ab".
5861------------------------------
5862------------------------------
5863------------------------------
5864K-th Smallest in Lexicographical Order
5865------------------------------
5866Given integers n and k, find the lexicographically k-th smallest
5867integer in the range from 1 to n.
5868Note: 1 &le; k &le; n &le; 109.
5869Example:
5870Input:
5871n: 13 k: 2
5872Output:
587310
5874Explanation:
5875The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7,
58768, 9], so the second smallest number is 10.
5877------------------------------
5878------------------------------
5879Arranging Coins
5880------------------------------
5881You have a total of n coins that you want to form in a staircase
5882shape, where every k-th row must have exactly k coins.
5883Given n, find the total number of full staircase rows that can be
5884formed.
5885n is a non-negative integer and fits within the range of a 32-bit
5886signed integer.
5887Example 1:
5888n = 5
5889The coins can form the following rows:
5890¤
5891¤ ¤
5892¤ ¤
5893Because the 3rd row is incomplete, we return 2.
5894Example 2:
5895n = 8
5896The coins can form the following rows:
5897¤
5898¤ ¤
5899¤ ¤ ¤
5900¤ ¤
5901Because the 4th row is incomplete, we return 3.
5902------------------------------
5903------------------------------
5904Find All Duplicates in an Array
5905------------------------------
5906Given an array of integers, 1 &le; a[i] &le; n (n = size of array),
5907some elements appear twice and others appear once.
5908Find all the elements that appear twice in this array.
5909Could you do it without extra space and in O(n) runtime?
5910Example:
5911Input:
5912[4,3,2,7,8,2,3,1]
5913Output:
5914[2,3]
5915------------------------------
5916------------------------------
5917------------------------------
5918Add Two Numbers II
5919------------------------------
5920You are given two non-empty linked lists representing two nonnegative integers. The most significant digit comes first and each
5921of their nodes contain a single digit. Add the two numbers and
5922return it as a linked list.
5923You may assume the two numbers do not contain any leading zero,
5924except the number 0 itself.
5925Follow up:
5926What if you cannot modify the input lists? In other words, reversing
5927the lists is not allowed.
5928Example:
5929Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
5930Output: 7 -> 8 -> 0 -> 7
5931------------------------------
5932------------------------------
5933Arithmetic Slices II - Subsequence
5934------------------------------
5935A sequence of numbers is called arithmetic if it consists of at
5936least three elements and if the difference between any two
5937consecutive elements is the same.
5938For example, these are arithmetic sequences:
59391, 3, 5, 7, 9
59407, 7, 7, 7
59413, -1, -5, -9
5942The following sequence is not arithmetic. 1, 1, 2, 5, 7 
5943A zero-indexed array A consisting of N numbers is given. A
5944subsequence slice of that array is any sequence of integers (P0,
5945P1, ..., Pk) such that 0 &le; P0 < P1 < ... < Pk < N.
5946A subsequence slice (P0, P1, ..., Pk) of array A is called
5947arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is
5948arithmetic. In particular, this means that k &ge; 2.
5949The function should return the number of arithmetic subsequence
5950slices in the array A.
5951The input contains N integers. Every integer is in the range of -231
5952and 231-1 and 0 &le; N &le; 1000. The output is guaranteed to be
5953less than 231-1.
5954Example:
5955Input: [2, 4, 6, 8, 10]
5956Output: 7
5957Explanation:
5958All arithmetic subsequence slices are:
5959[2,4,6]
5960[4,6,8]
5961[6,8,10]
5962[2,4,6,8]
5963[4,6,8,10]
5964[2,4,6,8,10]
5965[2,6,10]
5966------------------------------
5967------------------------------
5968Number of Boomerangs
5969------------------------------
5970Given n points in the plane that are all pairwise distinct, a
5971"boomerang" is a tuple of points (i, j, k) such that the distance
5972between i and j equals the distance between i and k (the order of
5973the tuple matters).
5974Find the number of boomerangs. You may assume that n will be at most
5975500 and coordinates of points are all in the range [-10000, 10000]
5976(inclusive).
5977Example:
5978Input:
5979[[0,0],[1,0],[2,0]]
5980Output:
59812
5982Explanation:
5983The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
5984------------------------------
5985------------------------------
5986Find All Numbers Disappeared in an Array
5987------------------------------
5988Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array),
5989some elements appear twice and others appear once.
5990Find all the elements of [1, n] inclusive that do not appear in this
5991array.
5992Could you do it without extra space and in O(n) runtime? You may
5993assume the returned list does not count as extra space.
5994Example:
5995Input:
5996[4,3,2,7,8,2,3,1]
5997Output:
5998[5,6]
5999------------------------------
6000------------------------------
6001Serialize and Deserialize BST
6002------------------------------
6003Serialization is the process of converting a data structure or
6004object into a sequence of bits so that it can be stored in a file or
6005memory buffer, or transmitted across a network connection link to be
6006reconstructed later in the same or another computer environment.
6007Design an algorithm to serialize and deserialize a binary search
6008tree. There is no restriction on how your serialization/
6009deserialization algorithm should work. You just need to ensure that
6010a binary search tree can be serialized to a string and this string
6011can be deserialized to the original tree structure.
6012The encoded string should be as compact as possible.
6013Note: Do not use class member/global/static variables to store
6014states. Your serialize and deserialize algorithms should be
6015stateless.
6016------------------------------
6017------------------------------
6018Delete Node in a BST
6019------------------------------
6020Given a root node reference of a BST and a key, delete the node with
6021the given key in the BST. Return the root node reference (possibly
6022updated) of the BST.
6023Basically, the deletion can be divided into two stages:
6024Search for a node to remove.
6025If the node is found, delete the node.
6026Note: Time complexity should be O(height of tree).
6027Example:
6028root = [5,3,6,2,4,null,7]
6029key = 3
6030 5
6031 / \
6032 3 6
6033 / \ \
60342 4 7
6035Given key to delete is 3. So we find the node with value 3 and
6036delete it.
6037One valid answer is [5,4,6,2,null,null,7], shown in the following
6038BST.
6039 5
6040 / \
6041 4 6
6042 / \
60432 7
6044Another valid answer is [5,2,6,null,4,null,7].
6045 5
6046 / \
6047 2 6
6048 \ \
6049 4 7
6050------------------------------
6051------------------------------
6052Sort Characters By Frequency
6053------------------------------
6054Given a string, sort it in decreasing order based on the frequency
6055of characters.
6056Example 1:
6057Input:
6058"tree"
6059Output:
6060"eert"
6061Explanation:
6062'e' appears twice while 'r' and 't' both appear once.
6063So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also
6064a valid answer.
6065Example 2:
6066Input:
6067"cccaaa"
6068Output:
6069"cccaaa"
6070Explanation:
6071Both 'c' and 'a' appear three times, so "aaaccc" is also a valid
6072answer.
6073Note that "cacaca" is incorrect, as the same characters must be
6074together.
6075Example 3:
6076Input:
6077"Aabb"
6078Output:
6079"bbAa"
6080Explanation:
6081"bbaA" is also a valid answer, but "Aabb" is incorrect.
6082Note that 'A' and 'a' are treated as two different characters.
6083------------------------------
6084------------------------------
6085Minimum Moves to Equal Array Elements
6086------------------------------
6087Given a non-empty integer array of size n, find the minimum number
6088of moves required to make all array elements equal, where a move is
6089incrementing n - 1 elements by 1.
6090Example:
6091Input:
6092[1,2,3]
6093Output:
60943
6095Explanation:
6096Only three moves are needed (remember each move increments two
6097elements):
6098[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
6099------------------------------
6100------------------------------
61014Sum II
6102------------------------------
6103Given four lists A, B, C, D of integer values, compute how many
6104tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is
6105zero.
6106To make problem a bit easier, all A, B, C, D have same length of N
6107where 0 &le; N &le; 500. All integers are in the range of -228 to
6108228 - 1 and the result is guaranteed to be at most 231 - 1.
6109Example:
6110Input:
6111A = [ 1, 2]
6112B = [-2,-1]
6113C = [-1, 2]
6114D = [ 0, 2]
6115Output:
61162
6117Explanation:
6118The two tuples are:
61191. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 =
61200
61212. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 =
61220
6123------------------------------
6124------------------------------
6125Assign Cookies
6126------------------------------
6127Assume you are an awesome parent and want to give your children some
6128cookies. But, you should give each child at most one cookie. Each
6129child i has a greed factor gi, which is the minimum size of a cookie
6130that the child will be content with; and each cookie j has a size
6131sj. If sj >= gi, we can assign the cookie j to the child i, and the
6132child i will be content. Your goal is to maximize the number of your
6133content children and output the maximum number.
6134Note:
6135You may assume the greed factor is always positive.
6136You cannot assign more than one cookie to one child.
6137Example 1:
6138Input: [1,2,3], [1,1]
6139Output: 1
6140Explanation: You have 3 children and 2 cookies. The greed factors of
61413 children are 1, 2, 3.
6142And even though you have 2 cookies, since their size is both 1, you
6143could only make the child whose greed factor is 1 content.
6144You need to output 1.
6145Example 2:
6146Input: [1,2], [1,2,3]
6147Output: 2
6148Explanation: You have 2 children and 3 cookies. The greed factors of
61492 children are 1, 2.
6150You have 3 cookies and their sizes are big enough to gratify all of
6151the children,
6152You need to output 2.
6153------------------------------
6154------------------------------
6155132 Pattern
6156------------------------------
6157Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a
6158subsequence ai, aj, ak such
6159that i < j < k and ai < ak < aj. Design an algorithm that takes a
6160list of n numbers as input and checks whether there is a 132 pattern
6161in the list.
6162Note: n will be less than 15,000.
6163Example 1:
6164Input: [1, 2, 3, 4]
6165Output: False
6166Explanation: There is no 132 pattern in the sequence.
6167Example 2:
6168Input: [3, 1, 4, 2]
6169Output: True
6170Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
6171Example 3:
6172Input: [-1, 3, 2, 0]
6173Output: True
6174Explanation: There are three 132 patterns in the sequence: [-1, 3,
61752], [-1, 3, 0] and [-1, 2, 0].
6176------------------------------
6177------------------------------
6178Repeated Substring Pattern
6179------------------------------
6180Given a non-empty string check if it can be constructed by taking a
6181substring of it and appending multiple copies of the substring
6182together. You may assume the given string consists of lowercase
6183English letters only and its length will not exceed 10000.
6184Example 1:
6185Input: "abab"
6186Output: True
6187Explanation: It's the substring "ab" twice.
6188Example 2:
6189Input: "aba"
6190Output: False
6191Example 3:
6192Input: "abcabcabcabc"
6193Output: True
6194Explanation: It's the substring "abc" four times. (And the substring
6195"abcabc" twice.)
6196------------------------------
6197------------------------------
6198LFU Cache
6199------------------------------
6200Design and implement a data structure for Least Frequently Used
6201(LFU) cache. It should support the following operations: get and
6202put.
6203get(key) - Get the value (will always be positive) of the key if the
6204key exists in the cache, otherwise return -1.
6205put(key, value) - Set or insert the value if the key is not already
6206present. When the cache reaches its capacity, it should invalidate
6207the least frequently used item before inserting a new item. For the
6208purpose of this problem, when there is a tie (i.e., two or more keys
6209that have the same frequency), the least recently used key would be
6210evicted.
6211Follow up:
6212Could you do both operations in O(1) time complexity?
6213Example:
6214LFUCache cache = new LFUCache( 2 /* capacity */ );
6215cache.put(1, 1);
6216cache.put(2, 2);
6217cache.get(1); // returns 1
6218cache.put(3, 3); // evicts key 2
6219cache.get(2); // returns -1 (not found)
6220cache.get(3); // returns 3.
6221cache.put(4, 4); // evicts key 1.
6222cache.get(1); // returns -1 (not found)
6223cache.get(3); // returns 3
6224cache.get(4); // returns 4
6225------------------------------
6226------------------------------
6227Hamming Distance
6228------------------------------
6229The Hamming distance between two integers is the number of positions
6230at which the corresponding bits are different.
6231Given two integers x and y, calculate the Hamming distance.
6232Note:
62330 &le; x, y &lt; 231.
6234Example:
6235Input: x = 1, y = 4
6236Output: 2
6237Explanation:
62381 (0 0 0 1)
62394 (0 1 0 0)
6240 ↑ ↑
6241The above arrows point to positions where the corresponding bits are
6242different.
6243------------------------------
6244------------------------------
6245Minimum Moves to Equal Array Elements II
6246------------------------------
6247Given a non-empty integer array, find the minimum number of moves
6248required to make all array elements equal, where a move is
6249incrementing a selected element by 1 or decrementing a selected
6250element by 1.
6251You may assume the array's length is at most 10,000.
6252Example:
6253Input:
6254[1,2,3]
6255Output:
62562
6257Explanation:
6258Only two moves are needed (remember each move increments or
6259decrements one element):
6260[1,2,3] => [2,2,3] => [2,2,2]
6261------------------------------
6262------------------------------
6263Island Perimeter
6264------------------------------
6265You are given a map in form of a two-dimensional integer grid where
62661 represents land and 0 represents water. Grid cells are connected
6267horizontally/vertically (not diagonally). The grid is completely
6268surrounded by water, and there is exactly one island (i.e., one or
6269more connected land cells). The island doesn't have "lakes" (water 
6270inside that isn't connected to the water around the island). One
6271cell is a square with side length 1. The grid is rectangular, width
6272and height don't exceed 100. Determine the perimeter of the island.
6273Example:
6274[[0,1,0,0],
6275 [1,1,1,0],
6276 [0,1,0,0],
6277 [1,1,0,0]]
6278Answer: 16
6279Explanation: The perimeter is the 16 yellow stripes in the image
6280below:
6281------------------------------
6282------------------------------
6283Can I Win
6284------------------------------
6285In the "100 game," two players take turns adding, to a running
6286total, any integer from 1..10. The player who first causes the
6287running total to reach or exceed 100 wins.
6288What if we change the game so that players cannot re-use integers?
6289For example, two players might take turns drawing from a common pool
6290of numbers of 1..15 without replacement until they reach a total >=
6291100.
6292Given an integer maxChoosableInteger and another integer
6293desiredTotal, determine if the first player to move can force a win,
6294assuming both players play optimally.
6295You can always assume that maxChoosableInteger will not be larger
6296than 20 and desiredTotal will not be larger than 300.
6297Example
6298Input:
6299maxChoosableInteger = 10
6300desiredTotal = 11
6301Output:
6302false
6303Explanation:
6304No matter which integer the first player choose, the first player
6305will lose.
6306The first player can choose an integer from 1 up to 10.
6307If the first player choose 1, the second player can only choose
6308integers from 2 up to 10.
6309The second player will win by choosing 10 and get a total = 11,
6310which is >= desiredTotal.
6311Same with other integers chosen by the first player, the second
6312player will always win.
6313------------------------------
6314------------------------------
6315------------------------------
6316Count The Repetitions
6317------------------------------
6318Define S = [s,n] as the string S which consists of n connected
6319strings s. For example, ["abc", 3] ="abcabcabc".
6320On the other hand, we define that string s1 can be obtained from
6321string s2 if we can remove some characters from s2 such that it
6322becomes s1. For example, “abc” can be obtained from “abdbec” based
6323on our definition, but it can not be obtained from “acbbe”.
6324You are given two non-empty strings s1 and s2 (each at most 100
6325characters long) and two integers 0 &le; n1 &le; 106 and 1 &le; n2
6326&le; 106. Now consider the strings S1 and S2, where S1=[s1,n1] and
6327S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be
6328obtained from S1.
6329Example:
6330Input:
6331s1="acb", n1=4
6332s2="ab", n2=2
6333Return:
63342
6335------------------------------
6336------------------------------
6337Unique Substrings in Wraparound String
6338------------------------------
6339Consider the string s to be the infinite wraparound string of
6340"abcdefghijklmnopqrstuvwxyz", so s will look like this:
6341"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
6342Now we have another string p. Your job is to find out how many
6343unique non-empty substrings of p are present in s. In particular,
6344your input is the string p and you need to output the number of
6345different non-empty substrings of p in the string s.
6346Note: p consists of only lowercase English letters and the size of p
6347might be over 10000.
6348Example 1:
6349Input: "a"
6350Output: 1
6351Explanation: Only the substring "a" of string "a" is in the string
6352s.
6353Example 2:
6354Input: "cac"
6355Output: 2
6356Explanation: There are two substrings "a", "c" of string "cac" in
6357the string s.
6358Example 3:
6359Input: "zab"
6360Output: 6
6361Explanation: There are six substrings "z", "a", "b", "za", "ab",
6362"zab" of string "zab" in the string s.
6363------------------------------
6364------------------------------
6365Validate IP Address
6366------------------------------
6367Write a function to check whether an input string is a valid IPv4
6368address or IPv6 address or neither.
6369IPv4 addresses are canonically represented in dot-decimal notation,
6370which consists of four decimal numbers, each ranging from 0 to 255,
6371separated by dots ("."), e.g.,172.16.254.1;
6372Besides, leading zeros in the IPv4 is invalid. For example, the
6373address 172.16.254.01 is invalid.
6374IPv6 addresses are represented as eight groups of four hexadecimal
6375digits, each group representing 16 bits. The groups are separated by
6376colons (":"). For example, the address
63772001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we
6378could omit some leading zeros among four hexadecimal digits and some
6379low-case characters in the address to upper-case ones, so
63802001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit
6381leading zeros and using upper cases).
6382However, we don't replace a consecutive group of zero value with a
6383single empty group using two consecutive colons (::) to pursue
6384simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an
6385invalid IPv6 address.
6386Besides, extra leading zeros in the IPv6 is also invalid. For
6387example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is
6388invalid.
6389Note:
6390You may assume there is no extra space or special characters in the
6391input string.
6392Example 1:
6393Input: "172.16.254.1"
6394Output: "IPv4"
6395Explanation: This is a valid IPv4 address, return "IPv4".
6396Example 2:
6397Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"
6398Output: "IPv6"
6399Explanation: This is a valid IPv6 address, return "IPv6".
6400Example 3:
6401Input: "256.256.256.256"
6402Output: "Neither"
6403Explanation: This is neither a IPv4 address nor a IPv6 address.
6404------------------------------
6405------------------------------
6406------------------------------
6407------------------------------
6408Concatenated Words 
6409------------------------------
6410Given a list of words (without duplicates), please write a program
6411that returns all concatenated words in the given list of words.
6412A concatenated word is defined as a string that is comprised
6413entirely of at least two shorter words in the given array.
6414Example:
6415Input:
6416["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat
6417","ratcatdogcat"]
6418Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
6419Explanation: "catsdogcats" can be concatenated by "cats", "dog" and
6420"cats"; "dogcatsdog" can be concatenated by "dog", "cats" and
6421"dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and
6422"cat".
6423Note:
6424The number of elements of the given array will not exceed 10,000
6425The length sum of elements in the given array will not exceed
6426600,000.
6427All the input string will only include lower case letters.
6428The returned elements order does not matter.
6429------------------------------
6430------------------------------
6431Matchsticks to Square
6432------------------------------
6433Remember the story of Little Match Girl? By now, you know exactly
6434what matchsticks the little match girl has, please find out a way
6435you can make one square by using up all those matchsticks. You
6436should not break any stick, but you can link them up, and each
6437matchstick must be used exactly one time.
6438 Your input will be several matchsticks the girl has, represented
6439with their stick length. Your output will either be true or false,
6440to represent whether you could make one square using all the
6441matchsticks the little match girl has.
6442Example 1:
6443Input: [1,1,2,2,2]
6444Output: true
6445Explanation: You can form a square with length 2, one side of the
6446square came two sticks with length 1.
6447Example 2:
6448Input: [3,3,3,3,4]
6449Output: false
6450Explanation: You cannot find a way to form a square with all the
6451matchsticks.
6452Note:
6453The length sum of the given matchsticks is in the range of 0 to
645410^9.
6455The length of the given matchstick array will not exceed 15.
6456------------------------------
6457------------------------------
6458Ones and Zeroes
6459------------------------------
6460In the computer world, use restricted resource you have to generate
6461maximum benefit is what we always want to pursue.
6462For now, suppose you are a dominator of m 0s and n 1s respectively.
6463On the other hand, there is an array with strings consisting of only
64640s and 1s.
6465Now your task is to find the maximum number of strings that you can
6466form with given m 0s and n 1s. Each 0 and 1 can be used at most
6467once.
6468Note:
6469The given numbers of 0s and 1s will both not exceed 100
6470The size of given string array won't exceed 600.
6471Example 1:
6472Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
6473Output: 4
6474Explanation: This are totally 4 strings can be formed by the using
6475of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
6476Example 2:
6477Input: Array = {"10", "0", "1"}, m = 1, n = 1
6478Output: 2
6479Explanation: You could form "10", but then you'd have nothing left.
6480Better form "0" and "1".
6481------------------------------
6482------------------------------
6483Heaters
6484------------------------------
6485Winter is coming! Your first job during the contest is to design a
6486standard heater with fixed warm radius to warm all the houses.
6487Now, you are given positions of houses and heaters on a horizontal
6488line, find out minimum radius of heaters so that all houses could be
6489covered by those heaters.
6490So, your input will be the positions of houses and heaters
6491seperately, and your expected output will be the minimum radius
6492standard of heaters.
6493Note:
6494Numbers of houses and heaters you are given are non-negative and
6495will not exceed 25000.
6496Positions of houses and heaters you are given are non-negative and
6497will not exceed 10^9.
6498As long as a house is in the heaters' warm radius range, it can be
6499warmed.
6500All the heaters follow your radius standard and the warm radius will
6501the same.
6502Example 1:
6503Input: [1,2,3],[2]
6504Output: 1
6505Explanation: The only heater was placed in the position 2, and if we
6506use the radius 1 standard, then all the houses can be warmed.
6507Example 2:
6508Input: [1,2,3,4],[1,4]
6509Output: 1
6510Explanation: The two heater was placed in the position 1 and 4. We
6511need to use radius 1 standard, then all the houses can be warmed.
6512------------------------------
6513------------------------------
6514Number Complement
6515------------------------------
6516Given a positive integer, output its complement number. The
6517complement strategy is to flip the bits of its binary
6518representation.
6519Note:
6520The given integer is guaranteed to fit within the range of a 32-bit
6521signed integer.
6522You could assume no leading zero bit in the integer’s binary
6523representation.
6524Example 1:
6525Input: 5
6526Output: 2
6527Explanation: The binary representation of 5 is 101 (no leading zero
6528bits), and its complement is 010. So you need to output 2.
6529Example 2:
6530Input: 1
6531Output: 0
6532Explanation: The binary representation of 1 is 1 (no leading zero
6533bits), and its complement is 0. So you need to output 0.
6534------------------------------
6535------------------------------
6536Total Hamming Distance
6537------------------------------
6538The Hamming distance between two integers is the number of positions
6539at which the corresponding bits are different.
6540Now your job is to find the total Hamming distance between all pairs
6541of the given numbers.
6542Example:
6543Input: 4, 14, 2
6544Output: 6
6545Explanation: In binary representation, the 4 is 0100, 14 is 1110,
6546and 2 is 0010 (just
6547showing the four bits relevant in this case). So the answer will be:
6548HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14,
65492) = 2 + 2 + 2 = 6.
6550Note:
6551Elements of the given array are in the range of 0 to 10^9
6552Length of the array will not exceed 10^4.
6553------------------------------
6554------------------------------
6555Sliding Window Median
6556------------------------------
6557Median is the middle value in an ordered integer list. If the size
6558of the list is even, there is no middle value. So the median is the
6559mean of the two middle value.
6560Examples:
6561[2,3,4] , the median is 3
6562[2,3], the median is (2 + 3) / 2 = 2.5
6563Given an array nums, there is a sliding window of size k which is
6564moving from the very left of the array to the very right. You can
6565only see the k numbers in the window. Each time the sliding window
6566moves right by one position. Your job is to output the median array
6567for each window in the original array.
6568For example,
6569Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
6570Window position Median
6571--------------- -----
6572[1 3 -1] -3 5 3 6 7 1
6573 1 [3 -1 -3] 5 3 6 7 -1
6574 1 3 [-1 -3 5] 3 6 7 -1
6575 1 3 -1 [-3 5 3] 6 7 3
6576 1 3 -1 -3 [5 3 6] 7 5
6577 1 3 -1 -3 5 [3 6 7] 6
6578Therefore, return the median sliding window as [1,-1,-1,3,5,6].
6579Note:
6580You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for
6581non-empty array.
6582------------------------------
6583------------------------------
6584Magical String
6585------------------------------
6586A magical string S consists of only '1' and '2' and obeys the
6587following rules:
6588The string S is magical because concatenating the number of
6589contiguous occurrences of characters '1' and '2' generates the
6590string S itself.
6591The first few elements of string S is the following:
6592S = "1221121221221121122……"
6593If we group the consecutive '1's and '2's in S, it will be:
65941 22 11 2 1 22 1 22 11 2 11 22 ......
6595and the occurrences of '1's or '2's in each group are:
65961 2 2 1 1 2 1 2 2 1 2 2 ......
6597You can see that the occurrence sequence above is the S itself.
6598Given an integer N as input, return the number of '1's in the first
6599N number in the magical string S.
6600Note:
6601N will not exceed 100,000.
6602Example 1:
6603Input: 6
6604Output: 3
6605Explanation: The first 6 elements of magical string S is "12211" and
6606it contains three 1's, so return 3.
6607------------------------------
6608------------------------------
6609License Key Formatting
6610------------------------------
6611Now you are given a string S, which represents a software license
6612key which we would like to format. The string S is composed of
6613alphanumerical characters and dashes. The dashes split the
6614alphanumerical characters within the string into groups. (i.e. if
6615there are M dashes, the string is split into M+1 groups). The dashes 
6616in the given string are possibly misplaced.
6617We want each group of characters to be of length K (except for
6618possibly the first group, which could be shorter, but still must
6619contain at least one character). To satisfy this requirement, we
6620will reinsert dashes. Additionally, all the lower case letters in
6621the string must be converted to upper case.
6622So, you are given a non-empty string S, representing a license key
6623to format, and an integer K. And you need to return the license key
6624formatted according to the description above.
6625Example 1:
6626Input: S = "2-4A0r7-4k", K = 4
6627Output: "24A0-R74K"
6628Explanation: The string S has been split into two parts, each part
6629has 4 characters.
6630Example 2:
6631Input: S = "2-4A0r7-4k", K = 3
6632Output: "24-A0R-74K"
6633Explanation: The string S has been split into three parts, each part
6634has 3 characters except the first part as it could be shorter as
6635said above.
6636Note:
6637The length of string S will not exceed 12,000, and K is a positive
6638integer.
6639String S consists only of alphanumerical characters (a-z and/or A-Z
6640and/or 0-9) and dashes(-).
6641String S is non-empty.
6642------------------------------
6643------------------------------
6644Smallest Good Base
6645------------------------------
6646For an integer n, we call k>=2 a good base of n, if all digits of n
6647base k are 1.
6648Now given a string representing n, you should return the smallest
6649good base of n in string format. 
6650Example 1:
6651Input: "13"
6652Output: "3"
6653Explanation: 13 base 3 is 111.
6654Example 2:
6655Input: "4681"
6656Output: "8"
6657Explanation: 4681 base 8 is 11111.
6658Example 3:
6659Input: "1000000000000000000"
6660Output: "999999999999999999"
6661Explanation: 1000000000000000000 base 999999999999999999 is 11.
6662Note:
6663The range of n is [3, 10^18].
6664The string representing n is always valid and will not have leading
6665zeros.
6666------------------------------
6667------------------------------
6668------------------------------
6669Max Consecutive Ones
6670------------------------------
6671Given a binary array, find the maximum number of consecutive 1s in
6672this array.
6673Example 1:
6674Input: [1,1,0,1,1,1]
6675Output: 3
6676Explanation: The first two digits or the last three digits are
6677consecutive 1s.
6678 The maximum number of consecutive 1s is 3.
6679Note:
6680The input array will only contain 0 and 1.
6681The length of input array is a positive integer and will not exceed 
668210,000
6683------------------------------
6684------------------------------
6685Predict the Winner
6686------------------------------
6687Given an array of scores that are non-negative integers. Player 1
6688picks one of the numbers from either end of the array followed by
6689the player 2 and then player 1 and so on. Each time a player picks a
6690number, that number will not be available for the next player. This
6691continues until all the scores have been chosen. The player with the
6692maximum score wins.
6693Given an array of scores, predict whether player 1 is the winner.
6694You can assume each player plays to maximize his score.
6695Example 1:
6696Input: [1, 5, 2]
6697Output: False
6698Explanation: Initially, player 1 can choose between 1 and 2. If he
6699chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If
6700player 2 chooses 5, then player 1 will be left with 1 (or 2). So,
6701final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence,
6702player 1 will never be the winner and you need to return False.
6703Example 2:
6704Input: [1, 5, 233, 7]
6705Output: True
6706Explanation: Player 1 first chooses 1. Then player 2 have to choose
6707between 5 and 7. No matter which number player 2 choose, player 1
6708can choose 233.Finally, player 1 has more score (234) than player 2
6709(12), so you need to return True representing player1 can win.
6710Note:
67111 <= length of the array <= 20.
6712Any scores in the given array are non-negative integers and will not
6713exceed 10,000,000.
6714If the scores of both players are equal, then player 1 is still the
6715winner.
6716------------------------------
6717------------------------------
6718------------------------------
6719Zuma Game
6720------------------------------
6721Think about Zuma Game. You have a row of balls on the table, colored
6722red(R), yellow(Y), blue(B), green(G), and white(W). You also have
6723several balls in your hand.
6724Each time, you may choose a ball in your hand, and insert it into
6725the row (including the leftmost place and rightmost place). Then, if
6726there is a group of 3 or more balls in the same color touching,
6727remove these balls. Keep doing this until no more balls can be
6728removed.
6729Find the minimal balls you have to insert to remove all the balls on
6730the table. If you cannot remove all the balls, output -1.
6731Examples:
6732Input: "WRRBBW", "RB"
6733Output: -1
6734Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW
6735Input: "WWRRBBWW", "WRBRW"
6736Output: 2
6737Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW
6738-> empty
6739Input:"G", "GGGGG"
6740Output: 2
6741Explanation: G -> G[G] -> GG[G] -> empty
6742Input: "RBYYBBRRB", "YRBGB"
6743Output: 3
6744Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B ->
6745B[B] -> BB[B] -> empty
6746Note:
6747You may assume that the initial row of balls on the table won’t have
6748any 3 or more consecutive balls with the same color.
6749The number of balls on the table won't exceed 20, and the string
6750represents these balls is called "board" in the input.
6751The number of balls in your hand won't exceed 5, and the string
6752represents these balls is called "hand" in the input.
6753Both input strings will be non-empty and only contain characters
6754'R','Y','B','G','W'.
6755------------------------------
6756------------------------------
6757------------------------------
6758Increasing Subsequences
6759------------------------------
6760Given an integer array, your task is to find all the different 
6761possible increasing subsequences of the given array, and the length
6762of an increasing subsequence should be at least 2 .
6763Example:
6764Input: [4, 6, 7, 7]
6765Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7],
6766[7,7], [4,7,7]]
6767Note:
6768The length of the given array will not exceed 15.
6769The range of integer in the given array is [-100,100].
6770The given array may contain duplicates, and two equal integers
6771should also be considered as a special case of increasing sequence.
6772------------------------------
6773------------------------------
6774Construct the Rectangle
6775------------------------------
6776For a web developer, it is very important to know how to design a
6777web page's size. So, given a specific rectangular web page’s area,
6778your job by now is to design a rectangular web page, whose length L
6779and width W satisfy the following requirements:
67801. The area of the rectangular web page you designed must equal to
6781the given target area.
67822. The width W should not be larger than the length L, which means L
6783>= W.
67843. The difference between length L and width W should be as small as
6785possible.
6786You need to output the length L and the width W of the web page you
6787designed in sequence.
6788Example:
6789Input: 4
6790Output: [2, 2]
6791Explanation: The target area is 4, and all the possible ways to
6792construct it are [1,4], [2,2], [4,1].
6793But according to requirement 2, [1,4] is illegal; according to
6794requirement 3, [4,1] is not optimal compared to [2,2]. So the
6795length L is 2, and the width W is 2.
6796Note:
6797The given area won't exceed 10,000,000 and is a positive integer
6798The web page's width and length you designed must be positive
6799integers.
6800------------------------------
6801------------------------------
6802Reverse Pairs
6803------------------------------
6804Given an array nums, we call (i, j) an important reverse pair if i
6805&lt; j and nums[i] &gt; 2*nums[j].
6806You need to return the number of important reverse pairs in the
6807given array.
6808Example1:
6809Input: [1,3,2,3,1]
6810Output: 2
6811Example2:
6812Input: [2,4,3,5,1]
6813Output: 3
6814Note:
6815The length of the given array will not exceed 50,000.
6816All the numbers in the input array are in the range of 32-bit
6817integer.
6818------------------------------
6819------------------------------
6820Target Sum
6821------------------------------
6822You are given a list of non-negative integers, a1, a2, ..., an, and
6823a target, S. Now you have 2 symbols + and -. For each integer, you
6824should choose one from + and - as its new symbol.
6825Find out how many ways to assign symbols to make sum of integers
6826equal to target S.
6827Example 1:
6828Input: nums is [1, 1, 1, 1, 1], S is 3.
6829Output: 5
6830Explanation: 
6831-1+1+1+1+1 = 3
6832+1-1+1+1+1 = 3
6833+1+1-1+1+1 = 3
6834+1+1+1-1+1 = 3
6835+1+1+1+1-1 = 3
6836There are 5 ways to assign symbols to make the sum of nums be target
68373.
6838Note:
6839The length of the given array is positive and will not exceed 20.
6840The sum of elements in the given array will not exceed 1000.
6841Your output answer is guaranteed to be fitted in a 32-bit integer.
6842------------------------------
6843------------------------------
6844Teemo Attacking
6845------------------------------
6846In LLP world, there is a hero called Teemo and his attacking can
6847make his enemy Ashe be in poisoned condition. Now, given the Teemo's
6848attacking ascending time series towards Ashe and the poisoning time
6849duration per Teemo's attacking, you need to output the total time
6850that Ashe is in poisoned condition.
6851You may assume that Teemo attacks at the very beginning of a
6852specific time point, and makes Ashe be in poisoned condition
6853immediately.
6854Example 1:
6855Input: [1,4], 2
6856Output: 4
6857Explanation: At time point 1, Teemo starts attacking Ashe and makes
6858Ashe be poisoned immediately. This poisoned status will last 2
6859seconds until the end of time point 2. And at time point 4, Teemo
6860attacks Ashe again, and causes Ashe to be in poisoned status for
6861another 2 seconds. So you finally need to output 4.
6862Example 2:
6863Input: [1,2], 2
6864Output: 3
6865Explanation: At time point 1, Teemo starts attacking Ashe and makes
6866Ashe be poisoned. This poisoned status will last 2 seconds until the 
6867end of time point 2. However, at the beginning of time point 2,
6868Teemo attacks Ashe again who is already in poisoned status. Since
6869the poisoned status won't add up together, though the second
6870poisoning attack will still work at time point 2, it will stop at
6871the end of time point 3. So you finally need to output 3.
6872Note:
6873You may assume the length of given time series array won't exceed
687410000.
6875You may assume the numbers in the Teemo's attacking time series and
6876his poisoning time duration per attacking are non-negative integers,
6877which won't exceed 10,000,000.
6878------------------------------
6879------------------------------
6880Next Greater Element I
6881------------------------------
6882You are given two arrays (without duplicates) nums1 and nums2 where
6883nums1’s elements are subset of nums2. Find all the next greater
6884numbers for nums1's elements in the corresponding places of nums2.
6885The Next Greater Number of a number x in nums1 is the first greater
6886number to its right in nums2. If it does not exist, output -1 for
6887this number.
6888Example 1:
6889Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
6890Output: [-1,3,-1]
6891Explanation:
6892 For number 4 in the first array, you cannot find the next
6893greater number for it in the second array, so output -1.
6894 For number 1 in the first array, the next greater number for it
6895in the second array is 3.
6896 For number 2 in the first array, there is no next greater number
6897for it in the second array, so output -1.
6898Example 2:
6899Input: nums1 = [2,4], nums2 = [1,2,3,4].
6900Output: [3,-1]
6901Explanation:
6902 For number 2 in the first array, the next greater number for it 
6903in the second array is 3.
6904 For number 4 in the first array, there is no next greater number
6905for it in the second array, so output -1.
6906Note:
6907All elements in nums1 and nums2 are unique.
6908The length of both nums1 and nums2 would not exceed 1000.
6909------------------------------
6910------------------------------
6911Diagonal Traverse
6912------------------------------
6913Given a matrix of M x N elements (M rows, N columns), return all
6914elements of the matrix in diagonal order as shown in the below
6915image.
6916Example:
6917Input:
6918[
6919 [ 1, 2, 3 ],
6920 [ 4, 5, 6 ],
6921 [ 7, 8, 9 ]
6922]
6923Output: [1,2,4,7,5,3,6,8,9]
6924Explanation:
6925Note:
6926The total number of elements of the given matrix will not exceed
692710,000.
6928------------------------------
6929------------------------------
6930------------------------------
6931Keyboard Row
6932------------------------------
6933Given a List of words, return the words that can be typed using
6934letters of alphabet on only one row's of American keyboard like the
6935image below. 
6936Example 1:
6937Input: ["Hello", "Alaska", "Dad", "Peace"]
6938Output: ["Alaska", "Dad"]
6939Note:
6940You may use one character in the keyboard more than once.
6941You may assume the input string will only contain letters of
6942alphabet.
6943------------------------------
6944------------------------------
6945Find Mode in Binary Search Tree
6946------------------------------
6947Given a binary search tree (BST) with duplicates, find all the
6948mode(s) (the most frequently occurred element) in the given BST.
6949Assume a BST is defined as follows:
6950The left subtree of a node contains only nodes with keys less than
6951or equal to the node's key.
6952The right subtree of a node contains only nodes with keys greater
6953than or equal to the node's key.
6954Both the left and right subtrees must also be binary search trees.
6955For example:
6956Given BST [1,null,2,2],
6957 1
6958 \
6959 2
6960 /
6961 2
6962return [2].
6963Note:
6964If a tree has more than one mode, you can return them in any order.
6965Follow up:
6966Could you do that without using any extra space? (Assume that the
6967implicit stack space incurred due to recursion does not count).
6968------------------------------
6969------------------------------
6970IPO
6971------------------------------
6972Suppose LeetCode will start its IPO soon. In order to sell a good
6973price of its shares to Venture Capital, LeetCode would like to work
6974on some projects to increase its capital before the IPO. Since it
6975has limited resources, it can only finish at most k distinct
6976projects before the IPO. Help LeetCode design the best way to
6977maximize its total capital after finishing at most k distinct
6978projects.
6979You are given several projects. For each project i, it has a pure
6980profit Pi and a minimum capital of Ci is needed to start the
6981corresponding project. Initially, you have W capital. When you
6982finish a project, you will obtain its pure profit and the profit
6983will be added to your total capital.
6984To sum up, pick a list of at most k distinct projects from given
6985projects to maximize your final capital, and output your final
6986maximized capital.
6987Example 1:
6988Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
6989Output: 4
6990Explanation: Since your initial capital is 0, you can only start the
6991project indexed 0.
6992 After finishing it you will obtain profit 1 and your
6993capital becomes 1.
6994 With capital 1, you can either start the project
6995indexed 1 or the project indexed 2.
6996 Since you can choose at most 2 projects, you need to
6997finish the project indexed 2 to get the maximum capital.
6998 Therefore, output the final maximized capital, which is
69990 + 1 + 3 = 4.
7000Note:
7001You may assume all numbers in the input are non-negative integers.
7002The length of Profits array and Capital array will not exceed
700350,000.
7004The answer is guaranteed to fit in a 32-bit signed integer.
7005------------------------------
7006------------------------------
7007Next Greater Element II
7008------------------------------
7009Given a circular array (the next element of the last element is the
7010first element of the array), print the Next Greater Number for every
7011element. The Next Greater Number of a number x is the first greater
7012number to its traversing-order next in the array, which means you
7013could search circularly to find its next greater number. If it
7014doesn't exist, output -1 for this number.
7015Example 1:
7016Input: [1,2,1]
7017Output: [2,-1,2]
7018Explanation: The first 1's next greater number is 2; The number 2
7019can't find next greater number; The second 1's next greater number
7020needs to search circularly, which is also 2.
7021Note:
7022The length of given array won't exceed 10000.
7023------------------------------
7024------------------------------
7025Base 7
7026------------------------------
7027Given an integer, return its base 7 string representation.
7028Example 1:
7029Input: 100
7030Output: "202"
7031Example 2:
7032Input: -7
7033Output: "-10"
7034Note:
7035The input will be in range of [-1e7, 1e7].
7036------------------------------
7037------------------------------
7038------------------------------
7039Relative Ranks
7040------------------------------
7041Given scores of N athletes, find their relative ranks and the people
7042with the top three highest scores, who will be awarded medals: "Gold
7043Medal", "Silver Medal" and "Bronze Medal".
7044Example 1:
7045Input: [5, 4, 3, 2, 1]
7046Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
7047Explanation: The first three athletes got the top three highest
7048scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal".
7049For the left two athletes, you just need to output their relative
7050ranks according to their scores.
7051Note:
7052N is a positive integer and won't exceed 10,000.
7053All the scores of athletes are guaranteed to be unique.
7054------------------------------
7055------------------------------
7056Perfect Number
7057------------------------------
7058We define the Perfect Number is a positive integer that is equal to
7059the sum of all its positive divisors except itself.
7060Now, given an integer n, write a function that returns true when it
7061is a perfect number and false when it is not.
7062Example:
7063Input: 28
7064Output: True
7065Explanation: 28 = 1 + 2 + 4 + 7 + 14
7066Note:
7067The input number n will not exceed 100,000,000. (1e8)
7068------------------------------
7069------------------------------
7070Most Frequent Subtree Sum
7071------------------------------
7072Given the root of a tree, you are asked to find the most frequent
7073subtree sum. The subtree sum of a node is defined as the sum of all
7074the node values formed by the subtree rooted at that node (including
7075the node itself). So what is the most frequent subtree sum value? If
7076there is a tie, return all the values with the highest frequency in
7077any order.
7078Examples 1
7079Input:
7080 5
7081 / \
70822 -3
7083return [2, -3, 4], since all the values happen only once, return all
7084of them in any order.
7085Examples 2
7086Input:
7087 5
7088 / \
70892 -5
7090return [2], since 2 happens twice, however -5 only occur once.
7091Note:
7092You may assume the sum of values in any subtree is in the range of
709332-bit signed integer.
7094------------------------------
7095------------------------------
7096Find Bottom Left Tree Value
7097------------------------------
7098Given a binary tree, find the leftmost value in the last row of the
7099tree.
7100Example 1:
7101Input:
7102 2
7103 / \
7104 1 3
7105Output:
71061
7107 Example 2:
7108Input:
7109 1
7110 / \
7111 2 3
7112 / / \
7113 4 5 6
7114 /
7115 7
7116Output:
71177
7118Note:
7119You may assume the tree (i.e., the given root node) is not NULL.
7120------------------------------
7121------------------------------
7122Freedom Trail
7123------------------------------
7124In the video game Fallout 4, the quest "Road to Freedom" requires
7125players to reach a metal dial called the "Freedom Trail Ring", and
7126use the dial to spell a specific keyword in order to open the door.
7127Given a string ring, which represents the code engraved on the outer
7128ring and another string key, which represents the keyword needs to
7129be spelled. You need to find the minimum number of steps in order to
7130spell all the characters in the keyword.
7131Initially, the first character of the ring is aligned at 12:00
7132direction. You need to spell all the characters in the string key
7133one by one by rotating the ring clockwise or anticlockwise to make
7134each character of the string key aligned at 12:00 direction and then
7135by pressing the center button.
7136At the stage of rotating the ring to spell the key character key[i]:
7137You can rotate the ring clockwise or anticlockwise one place, which
7138counts as 1 step. The final purpose of the rotation is to align one
7139of the string ring's characters at the 12:00 direction, where this
7140character must equal to the character key[i].
7141If the character key[i] has been aligned at the 12:00 direction, you
7142need to press the center button to spell, which also counts as 1 
7143step. After the pressing, you could begin to spell the next
7144character in the key (next stage), otherwise, you've finished all
7145the spelling.
7146Example:
7147Input: ring = "godding", key = "gd"
7148Output: 4
7149Explanation: For the first key character 'g', since it is already in
7150place, we just need 1 step to spell this character. For the second
7151key character 'd', we need to rotate the ring "godding"
7152anticlockwise by two steps to make it become "ddinggo". Also, we
7153need 1 more step for spelling. So the final output is 4.
7154Note:
7155Length of both ring and key will be in range 1 to 100.
7156There are only lowercase letters in both strings and might be some
7157duplcate characters in both strings.
7158It's guaranteed that string key could always be spelled by rotating
7159the string ring.
7160------------------------------
7161------------------------------
7162Find Largest Value in Each Tree Row
7163------------------------------
7164You need to find the largest value in each row of a binary tree.
7165Example:
7166Input:
7167 1
7168 / \
7169 3 2
7170 / \ \
7171 5 3 9
7172Output: [1, 3, 9]
7173------------------------------
7174------------------------------
7175Longest Palindromic Subsequence 
7176------------------------------
7177Given a string s, find the longest palindromic subsequence's length
7178in s. You may assume that the maximum length of s is 1000.
7179Example 1:
7180Input:
7181"bbbab"
7182Output:
71834
7184One possible longest palindromic subsequence is "bbbb".
7185Example 2:
7186Input:
7187"cbbd"
7188Output:
71892
7190One possible longest palindromic subsequence is "bb".
7191------------------------------
7192------------------------------
7193Super Washing Machines
7194------------------------------
7195You have n super washing machines on a line. Initially, each washing
7196machine has some dresses or is empty.
7197For each move, you could choose any m (1 ≤ m ≤ n) washing machines,
7198and pass one dress of each washing machine to one of its adjacent
7199washing machines at the same time .
7200Given an integer array representing the number of dresses in each
7201washing machine from left to right on the line, you should find the
7202minimum number of moves to make all the washing machines have the
7203same number of dresses. If it is not possible to do it, return -1.
7204Example1
7205Input: [1,0,5]
7206Output: 3
7207Explanation:
72081st move: 1 0 <-- 5 => 1 1 4
72092nd move: 1 <-- 1 <-- 4 => 2 1 3
72103rd move: 2 1 <-- 3 => 2 2 2
7211Example2
7212Input: [0,3,0]
7213Output: 2
7214Explanation:
72151st move: 0 <-- 3 0 => 1 2 0
72162nd move: 1 2 --> 0 => 1 1 1
7217Example3
7218Input: [0,2,0]
7219Output: -1
7220Explanation:
7221It's impossible to make all the three washing machines have the same
7222number of dresses.
7223Note:
7224The range of n is [1, 10000].
7225The range of dresses number in a super washing machine is [0, 1e5].
7226------------------------------
7227------------------------------
7228Detect Capital
7229------------------------------
7230Given a word, you need to judge whether the usage of capitals in it
7231is right or not.
7232We define the usage of capitals in a word to be right when one of
7233the following cases holds:
7234All letters in this word are capitals, like "USA".
7235All letters in this word are not capitals, like "leetcode".
7236Only the first letter in this word is capital if it has more than
7237one letter, like "Google".
7238Otherwise, we define that this word doesn't use capitals in a right
7239way.
7240Example 1:
7241Input: "USA"
7242Output: True
7243Example 2:
7244Input: "FlaG"
7245Output: False
7246Note:
7247The input will be a non-empty word consisting of uppercase and
7248lowercase latin letters.
7249------------------------------
7250------------------------------
7251------------------------------
7252Longest Uncommon Subsequence II
7253------------------------------
7254Given a list of strings, you need to find the longest uncommon
7255subsequence among them. The longest uncommon subsequence is defined
7256as the longest subsequence of one of these strings and this
7257subsequence should not be any subsequence of the other strings.
7258A subsequence is a sequence that can be derived from one sequence by
7259deleting some characters without changing the order of the remaining
7260elements. Trivially, any string is a subsequence of itself and an
7261empty string is a subsequence of any string.
7262The input will be a list of strings, and the output needs to be the
7263length of the longest uncommon subsequence. If the longest uncommon
7264subsequence doesn't exist, return -1.
7265Example 1:
7266Input: "aba", "cdc", "eae"
7267Output: 3
7268Note:
7269All the given strings' lengths will not exceed 10.
7270The length of the given list will be in the range of [2, 50].
7271------------------------------
7272------------------------------
7273Continuous Subarray Sum
7274------------------------------
7275Given a list of non-negative numbers and a target integer k, write a
7276function to check if the array has a continuous subarray of size at
7277least 2 that sums up to the multiple of k, that is, sums up to n*k
7278where n is also an integer.
7279Example 1:
7280Input: [23, 2, 4, 6, 7], k=6
7281Output: True
7282Explanation: Because [2, 4] is a continuous subarray of size 2 and
7283sums up to 6.
7284Example 2:
7285Input: [23, 2, 6, 4, 7], k=6
7286Output: True
7287Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of
7288size 5 and sums up to 42.
7289Note:
7290The length of the array won't exceed 10,000.
7291You may assume the sum of all the numbers is in the range of a
7292signed 32-bit integer.
7293------------------------------
7294------------------------------
7295Longest Word in Dictionary through Deleting
7296------------------------------
7297Given a string and a string dictionary, find the longest string in
7298the dictionary that can be formed by deleting some characters of the
7299given string. If there are more than one possible results, return
7300the longest word with the smallest lexicographical order. If there
7301is no possible result, return the empty string.
7302Example 1:
7303Input:
7304s = "abpcplea", d = ["ale","apple","monkey","plea"]
7305Output:
7306"apple"
7307Example 2:
7308Input:
7309s = "abpcplea", d = ["a","b","c"]
7310Output:
7311"a"
7312Note:
7313All the strings in the input will only contain lower-case letters.
7314The size of the dictionary won't exceed 1,000.
7315The length of all the strings in the input won't exceed 1,000.
7316------------------------------
7317------------------------------
7318Contiguous Array
7319------------------------------
7320Given a binary array, find the maximum length of a contiguous
7321subarray with equal number of 0 and 1.
7322Example 1:
7323Input: [0,1]
7324Output: 2
7325Explanation: [0, 1] is the longest contiguous subarray with equal
7326number of 0 and 1.
7327Example 2:
7328Input: [0,1,0]
7329Output: 2
7330Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray
7331with equal number of 0 and 1.
7332Note:
7333The length of the given binary array will not exceed 50,000.
7334------------------------------
7335------------------------------
7336Beautiful Arrangement
7337------------------------------
7338Suppose you have N integers from 1 to N. We define a beautiful
7339arrangement as an array that is constructed by these N numbers
7340successfully if one of the following is true for the ith position (1
7341≤ i ≤ N) in this array:
7342The number at the ith position is divisible by i.
7343i is divisible by the number at the ith position.
7344Now given N, how many beautiful arrangements can you construct?
7345Example 1:
7346Input: 2
7347Output: 2
7348Explanation:
7349The first beautiful arrangement is [1, 2]:
7350Number at the 1st position (i=1) is 1, and 1 is divisible by i
7351(i=1).
7352Number at the 2nd position (i=2) is 2, and 2 is divisible by i
7353(i=2).
7354The second beautiful arrangement is [2, 1]:
7355Number at the 1st position (i=1) is 2, and 2 is divisible by i
7356(i=1).
7357Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by
73581.
7359Note:
7360N is a positive integer and will not exceed 15.
7361------------------------------
7362------------------------------
7363------------------------------
7364Minesweeper
7365------------------------------
7366Let's play the minesweeper game (Wikipedia, online game)!
7367You are given a 2D char matrix representing the game board. 'M'
7368represents an unrevealed mine, 'E' represents an unrevealed empty 
7369square, 'B' represents a revealed blank square that has no adjacent
7370(above, below, left, right, and all 4 diagonals) mines, digit ('1'
7371to '8') represents how many mines are adjacent to this revealed
7372square, and finally 'X' represents a revealed mine.
7373Now given the next click position (row and column indices) among all
7374the unrevealed squares ('M' or 'E'), return the board after
7375revealing this position according to the following rules:
7376If a mine ('M') is revealed, then the game is over - change it to
7377'X'.
7378If an empty square ('E') with no adjacent mines is revealed, then
7379change it to revealed blank ('B') and all of its adjacent unrevealed
7380squares should be revealed recursively.
7381If an empty square ('E') with at least one adjacent mine is
7382revealed, then change it to a digit ('1' to '8') representing the
7383number of adjacent mines.
7384Return the board when no more squares will be revealed.
7385Example 1:
7386Input:
7387[['E', 'E', 'E', 'E', 'E'],
7388 ['E', 'E', 'M', 'E', 'E'],
7389 ['E', 'E', 'E', 'E', 'E'],
7390 ['E', 'E', 'E', 'E', 'E']]
7391Click : [3,0]
7392Output:
7393[['B', '1', 'E', '1', 'B'],
7394 ['B', '1', 'M', '1', 'B'],
7395 ['B', '1', '1', '1', 'B'],
7396 ['B', 'B', 'B', 'B', 'B']]
7397Explanation:
7398Example 2:
7399Input:
7400[['B', '1', 'E', '1', 'B'],
7401 ['B', '1', 'M', '1', 'B'],
7402 ['B', '1', '1', '1', 'B'],
7403 ['B', 'B', 'B', 'B', 'B']]
7404Click : [1,2]
7405Output:
7406[['B', '1', 'E', '1', 'B'],
7407 ['B', '1', 'X', '1', 'B'],
7408 ['B', '1', '1', '1', 'B'],
7409 ['B', 'B', 'B', 'B', 'B']]
7410Explanation:
7411Note:
7412The range of the input matrix's height and width is [1,50].
7413The click position will only be an unrevealed square ('M' or 'E'),
7414which also means the input board contains at least one clickable
7415square.
7416The input board won't be a stage when game is over (some mines have
7417been revealed).
7418For simplicity, not mentioned rules should be ignored in this
7419problem. For example, you don't need to reveal all the unrevealed
7420mines when the game is over, consider any cases that you will win
7421the game or flag any squares.
7422------------------------------
7423------------------------------
7424Minimum Absolute Difference in BST
7425------------------------------
7426Given a binary search tree with non-negative values, find the
7427minimum absolute difference between values of any two nodes.
7428Example:
7429Input:
7430 1
7431 \
7432 3
7433 /
7434 2
7435Output:
74361
7437Explanation:
7438The minimum absolute difference is 1, which is the difference 
7439between 2 and 1 (or between 2 and 3).
7440Note:
7441There are at least two nodes in this BST.
7442------------------------------
7443------------------------------
7444------------------------------
7445K-diff Pairs in an Array
7446------------------------------
7447Given an array of integers and an integer k, you need to find the
7448number of unique k-diff pairs in the array. Here a k-diff pair is
7449defined as an integer pair (i, j), where i and j are both numbers in
7450the array and their absolute difference is k.
7451Example 1:
7452Input: [3, 1, 4, 1, 5], k = 2
7453Output: 2
7454Explanation: There are two 2-diff pairs in the array, (1, 3) and (3,
74555).Although we have two 1s in the input, we should only return the
7456number of unique pairs.
7457Example 2:
7458Input:[1, 2, 3, 4, 5], k = 1
7459Output: 4
7460Explanation: There are four 1-diff pairs in the array, (1, 2), (2,
74613), (3, 4) and (4, 5).
7462Example 3:
7463Input: [1, 3, 1, 5, 4], k = 0
7464Output: 1
7465Explanation: There is one 0-diff pair in the array, (1, 1).
7466Note:
7467The pairs (i, j) and (j, i) count as the same pair.
7468The length of the array won't exceed 10,000.
7469All the integers in the given input belong to the range: [-1e7,
74701e7].
7471------------------------------
7472------------------------------
7473------------------------------
7474Encode and Decode TinyURL
7475------------------------------
7476Note: This is a companion problem to the System Design problem:
7477Design TinyURL.
7478TinyURL is a URL shortening service where you enter a URL such as
7479https://leetcode.com/problems/design-tinyurl and it returns a short
7480URL such as http://tinyurl.com/4e9iAk.
7481Design the encode and decode methods for the TinyURL service. There
7482is no restriction on how your encode/decode algorithm should work.
7483You just need to ensure that a URL can be encoded to a tiny URL and
7484the tiny URL can be decoded to the original URL.
7485------------------------------
7486------------------------------
7487------------------------------
7488Complex Number Multiplication
7489------------------------------
7490Given two strings representing two complex numbers.
7491You need to return a string representing their multiplication. Note
7492i2 = -1 according to the definition.
7493Example 1:
7494Input: "1+1i", "1+1i"
7495Output: "0+2i"
7496Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need
7497convert it to the form of 0+2i.
7498Example 2:
7499Input: "1+-1i", "1+-1i"
7500Output: "0+-2i"
7501Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need
7502convert it to the form of 0+-2i.
7503Note:
7504The input strings will not have extra blank.
7505The input strings will be given in the form of a+bi, where the
7506integer a and b will both belong to the range of [-100, 100]. And 
7507the output should be also in this form.
7508------------------------------
7509------------------------------
7510Convert BST to Greater Tree
7511------------------------------
7512Given a Binary Search Tree (BST), convert it to a Greater Tree such
7513that every key of the original BST is changed to the original key
7514plus sum of all keys greater than the original key in BST.
7515Example:
7516Input: The root of a Binary Search Tree like this:
7517 5
7518 / \
7519 2 13
7520Output: The root of a Greater Tree like this:
7521 18
7522 / \
7523 20 13
7524------------------------------
7525------------------------------
7526Minimum Time Difference
7527------------------------------
7528Given a list of 24-hour clock time points in "Hour:Minutes" format,
7529find the minimum minutes difference between any two time points in
7530the list.
7531Example 1:
7532Input: ["23:59","00:00"]
7533Output: 1
7534Note:
7535The number of time points in the given list is at least 2 and won't
7536exceed 20000.
7537The input time is legal and ranges from 00:00 to 23:59.
7538------------------------------
7539------------------------------
7540Reverse String II
7541------------------------------
7542Given a string and an integer k, you need to reverse the first k
7543characters for every 2k characters counting from the start of the 
7544string. If there are less than k characters left, reverse all of
7545them. If there are less than 2k but greater than or equal to k
7546characters, then reverse the first k characters and left the other
7547as original.
7548Example:
7549Input: s = "abcdefg", k = 2
7550Output: "bacdfeg"
7551Restrictions:
7552 The string consists of lower English letters only.
7553 Length of the given string and k will in the range [1, 10000]
7554------------------------------
7555------------------------------
755601 Matrix
7557------------------------------
7558Given a matrix consists of 0 and 1, find the distance of the nearest
75590 for each cell.
7560The distance between two adjacent cells is 1.
7561Example 1:
7562Input:
75630 0 0
75640 1 0
75650 0 0
7566Output:
75670 0 0
75680 1 0
75690 0 0
7570Example 2:
7571Input:
75720 0 0
75730 1 0
75741 1 1
7575Output:
75760 0 0
75770 1 0
75781 2 1
7579Note:
7580The number of elements of the given matrix will not exceed 10,000.
7581There are at least one 0 in the given matrix.
7582The cells are adjacent in only four directions: up, down, left and
7583right.
7584------------------------------
7585------------------------------
7586Diameter of Binary Tree
7587------------------------------
7588Given a binary tree, you need to compute the length of the diameter
7589of the tree. The diameter of a binary tree is the length of the
7590longest path between any two nodes in a tree. This path may or may
7591not pass through the root.
7592Example:
7593Given a binary tree
7594 1
7595 / \
7596 2 3
7597 / \
7598 4 5
7599Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
7600Note:
7601The length of path between two nodes is represented by the number of
7602edges between them.
7603------------------------------
7604------------------------------
7605------------------------------
7606------------------------------
7607Remove Boxes
7608------------------------------
7609Given several boxes with different colors represented by different
7610positive numbers.
7611You may experience several rounds to remove boxes until there is no
7612box left. Each time you can choose some continuous boxes with the
7613same color (composed of k boxes, k >= 1), remove them and get k*k
7614points.
7615Find the maximum points you can get.
7616Example 1:
7617Input:
7618[1, 3, 2, 2, 2, 3, 4, 3, 1]
7619Output:
762023
7621Explanation:
7622[1, 3, 2, 2, 2, 3, 4, 3, 1]
7623----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
7624----> [1, 3, 3, 3, 1] (1*1=1 points)
7625----> [1, 1] (3*3=9 points)
7626----> [] (2*2=4 points)
7627Note:
7628The number of boxes n would not exceed 100.
7629------------------------------
7630------------------------------
7631Friend Circles
7632------------------------------
7633There are N students in a class. Some of them are friends, while
7634some are not. Their friendship is transitive in nature. For example,
7635if A is a direct friend of B, and B is a direct friend of C, then A
7636is an indirect friend of C. And we defined a friend circle is a
7637group of students who are direct or indirect friends.
7638Given a N*N matrix M representing the friend relationship between
7639students in the class. If M[i][j] = 1, then the ith and jth students
7640are direct friends with each other, otherwise not. And you have to
7641output the total number of friend circles among all the students.
7642Example 1:
7643Input:
7644[[1,1,0],
7645 [1,1,0],
7646 [0,0,1]]
7647Output: 2
7648Explanation:The 0th and 1st students are direct friends, so they are
7649in a friend circle. The 2nd student himself is in a friend circle.
7650So return 2.
7651Example 2:
7652Input:
7653[[1,1,0],
7654 [1,1,1],
7655 [0,1,1]]
7656Output: 1
7657Explanation:The 0th and 1st students are direct friends, the 1st and
76582nd students are direct friends, so the 0th and 2nd students are
7659indirect friends. All of them are in the same friend circle, so
7660return 1.
7661Note:
7662N is in range [1,200].
7663M[i][i] = 1 for all students.
7664If M[i][j] = 1, then M[j][i] = 1.
7665------------------------------
7666------------------------------
7667------------------------------
7668Design TinyURL
7669------------------------------
7670Note: For the coding companion problem, please see: Encode and
7671Decode TinyURL.
7672How would you design a URL shortening service that is similar to
7673TinyURL?
7674Background:
7675TinyURL is a URL shortening service where you enter a URL such as
7676https://leetcode.com/problems/design-tinyurl and it returns a short
7677URL such as http://tinyurl.com/4e9iAk.
7678Requirements:
7679For instance, "http://tinyurl.com/4e9iAk" is the tiny url for the
7680page "https://leetcode.com/problems/design-tinyurl". The identifier
7681(the highlighted part) can be any string with 6 alphanumeric
7682characters containing 0-9, a-z, A-Z.
7683Each shortened URL must be unique; that is, no two different URLs
7684can be shortened to the same URL.
7685Note about Questions:Below are just a small subset of questions to
7686get you started. In real world, there could be many follow ups and
7687questions possible and the discussion is open-ended (No one true or
7688correct way to solve a problem). If you have more ideas or
7689questions, please ask in Discuss and we may compile it here!
7690Questions:
7691How many unique identifiers possible? Will you run out of unique
7692URLs?
7693Should the identifier be increment or not? Which is easier to
7694design? Pros and cons?
7695Mapping an identifier to an URL and its reversal - Does this problem
7696ring a bell to you?
7697How do you store the URLs? Does a simple flat file database work?
7698What is the bottleneck of the system? Is it read-heavy or writeheavy?
7699Estimate the maximum number of URLs a single machine can store.
7700Estimate the maximum number of queries per second (QPS) for decoding
7701a shortened URL in a single machine.
7702How would you scale the service? For example, a viral link which is
7703shared in social media could result in a peak QPS at a moment's
7704notice.
7705How could you handle redundancy? i,e, if a server is down, how could
7706you ensure the service is still operational?
7707Keep URLs forever or prune, pros/cons? How we do pruning?
7708(Contributed by @alex_svetkin)
7709What API would you provide to a third-party developer? (Contributed
7710by @alex_svetkin)
7711If you can enable caching, what would you cache and what's the
7712expiry time? (Contributed by @Humandroid)
7713.hilight {
7714 color: #d14;
7715 background-color: #f7f7f9;
7716 padding: 1px 3px;
7717 border: 1px solid #e1e1e8"
7718}
7719------------------------------
7720------------------------------
7721License Key Formatting
7722------------------------------
7723Now you are given a string S, which represents a software license
7724key which we would like to format. The string S is composed of
7725alphanumerical characters and dashes. The dashes split the
7726alphanumerical characters within the string into groups. (i.e. if
7727there are M dashes, the string is split into M+1 groups). The dashes
7728in the given string are possibly misplaced.
7729We want each group of characters to be of length K (except for 
7730possibly the first group, which could be shorter, but still must
7731contain at least one character). To satisfy this requirement, we
7732will reinsert dashes. Additionally, all the lower case letters in
7733the string must be converted to upper case.
7734So, you are given a non-empty string S, representing a license key
7735to format, and an integer K. And you need to return the license key
7736formatted according to the description above.
7737Example 1:
7738Input: S = "2-4A0r7-4k", K = 4
7739Output: "24A0-R74K"
7740Explanation: The string S has been split into two parts, each part
7741has 4 characters.
7742Example 2:
7743Input: S = "2-4A0r7-4k", K = 3
7744Output: "24-A0R-74K"
7745Explanation: The string S has been split into three parts, each part
7746has 3 characters except the first part as it could be shorter as
7747said above.
7748Note:
7749The length of string S will not exceed 12,000, and K is a positive
7750integer.
7751String S consists only of alphanumerical characters (a-z and/or A-Z
7752and/or 0-9) and dashes(-).
7753String S is non-empty.
7754------------------------------
7755------------------------------
7756Longest Absolute File Path
7757------------------------------
7758Suppose we abstract our file system by a string in the following
7759manner:
7760The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
7761dir
7762 subdir1
7763 subdir2
7764 file.ext
7765The directory dir contains an empty sub-directory subdir1 and a subdirectory subdir2 containing a file file.ext.
7766The string
7767"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsu
7768bdir2\n\t\t\tfile2.ext" represents:
7769dir
7770 subdir1
7771 file1.ext
7772 subsubdir1
7773 subdir2
7774 subsubdir2
7775 file2.ext
7776The directory dir contains two sub-directories subdir1 and subdir2.
7777subdir1 contains a file file1.ext and an empty second-level subdirectory subsubdir1. subdir2 contains a second-level sub-directory
7778subsubdir2 containing a file file2.ext.
7779We are interested in finding the longest (number of characters)
7780absolute path to a file within our file system. For example, in the
7781second example above, the longest absolute path is "dir/subdir2/
7782subsubdir2/file2.ext", and its length is 32 (not including the
7783double quotes).
7784Given a string representing the file system in the above format,
7785return the length of the longest absolute path to file in the
7786abstracted file system. If there is no file in the system, return 0.
7787Note:
7788The name of a file contains at least a . and an extension.
7789The name of a directory or sub-directory will not contain a ..
7790Time complexity required: O(n) where n is the size of the input
7791string.
7792Notice that a/aa/aaa/file1.txt is not the longest file path, if
7793there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.
7794------------------------------
7795------------------------------
7796Encode and Decode TinyURL
7797------------------------------
7798Note: This is a companion problem to the System Design problem:
7799Design TinyURL.
7800TinyURL is a URL shortening service where you enter a URL such as
7801https://leetcode.com/problems/design-tinyurl and it returns a short
7802URL such as http://tinyurl.com/4e9iAk.
7803Design the encode and decode methods for the TinyURL service. There
7804is no restriction on how your encode/decode algorithm should work.
7805You just need to ensure that a URL can be encoded to a tiny URL and
7806the tiny URL can be decoded to the original URL.
7807------------------------------
7808------------------------------
7809Coin Change 2
7810------------------------------
7811You are given coins of different denominations and a total amount of
7812money. Write a function to compute the number of combinations that
7813make up that amount. You may assume that you have infinite number of
7814each kind of coin.
7815Note:
7816You can assume that
7817 0 <= amount <= 5000
7818 1 <= coin <= 5000
7819 the number of coins is less than 500
7820 the answer is guaranteed to fit into signed 32-bit integer
7821Example 1:
7822Input: amount = 5, coins = [1, 2, 5]
7823Output: 4
7824Explanation: there are four ways to make up the amount:
78255=5
78265=2+2+1
78275=2+1+1+1
78285=1+1+1+1+1
7829Example 2:
7830Input: amount = 3, coins = [2]
7831Output: 0
7832Explanation: the amount of 3 cannot be made up just with coins of 2.
7833Example 3:
7834Input: amount = 10, coins = [10]
7835Output: 1
7836------------------------------
7837------------------------------
7838Poor Pigs
7839------------------------------
7840There are 1000 buckets, one and only one of them contains poison,
7841the rest are filled with water. They all look the same. If a pig
7842drinks that poison it will die within 15 minutes. What is the
7843minimum amount of pigs you need to figure out which bucket contains
7844the poison within one hour.
7845Answer this question, and write an algorithm for the follow-up
7846general case.
7847Follow-up:
7848If there are n buckets and a pig drinking poison will die within m
7849minutes, how many pigs (x) you need to figure out the "poison"
7850bucket within p minutes? There is exact one bucket with poison.
7851------------------------------
7852------------------------------
7853Minimum Genetic Mutation
7854------------------------------
7855A gene string can be represented by an 8-character long string, with
7856choices from "A", "C", "G", "T".
7857Suppose we need to investigate about a mutation (mutation from
7858"start" to "end"), where ONE mutation is defined as ONE single
7859character changed in the gene string.
7860For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.
7861Also, there is a given gene "bank", which records all the valid gene
7862mutations. A gene must be in the bank to make it a valid gene
7863string.
7864Now, given 3 things - start, end, bank, your task is to determine
7865what is the minimum number of mutations needed to mutate from
7866"start" to "end". If there is no such a mutation, return -1.
7867Note:
7868Starting point is assumed to be valid, so it might not be included
7869in the bank.
7870If multiple mutations are needed, all mutations during in the
7871sequence must be valid.
7872You may assume start and end string is not the same.
7873Example 1:
7874start: "AACCGGTT"
7875end: "AACCGGTA"
7876bank: ["AACCGGTA"]
7877return: 1
7878Example 2:
7879start: "AACCGGTT"
7880end: "AAACGGTA"
7881bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
7882return: 2
7883Example 3:
7884start: "AAAAACCC"
7885end: "AACCCCCC"
7886bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
7887return: 3
7888------------------------------
7889------------------------------
7890LFU Cache
7891------------------------------
7892Design and implement a data structure for Least Frequently Used
7893(LFU) cache. It should support the following operations: get and
7894put.
7895get(key) - Get the value (will always be positive) of the key if the
7896key exists in the cache, otherwise return -1.
7897put(key, value) - Set or insert the value if the key is not already
7898present. When the cache reaches its capacity, it should invalidate
7899the least frequently used item before inserting a new item. For the
7900purpose of this problem, when there is a tie (i.e., two or more keys
7901that have the same frequency), the least recently used key would be
7902evicted.
7903Follow up:
7904Could you do both operations in O(1) time complexity?
7905Example:
7906LFUCache cache = new LFUCache( 2 /* capacity */ );
7907cache.put(1, 1);
7908cache.put(2, 2);
7909cache.get(1); // returns 1
7910cache.put(3, 3); // evicts key 2
7911cache.get(2); // returns -1 (not found)
7912cache.get(3); // returns 3.
7913cache.put(4, 4); // evicts key 1.
7914cache.get(1); // returns -1 (not found)
7915cache.get(3); // returns 3
7916cache.get(4); // returns 4
7917------------------------------
7918------------------------------
7919------------------------------
7920Longest Palindromic Subsequence
7921------------------------------
7922Given a string s, find the longest palindromic subsequence's length
7923in s. You may assume that the maximum length of s is 1000.
7924Example 1:
7925Input:
7926"bbbab"
7927Output:
79284
7929One possible longest palindromic subsequence is "bbbb".
7930Example 2:
7931Input:
7932"cbbd"
7933Output:
79342
7935One possible longest palindromic subsequence is "bb".