Han Zhu's Study Notes

Given an encoded string, return it's decoded string. The encoding rule is:  k[encoded_string] , where the  encoded_string  inside the square brackets is being repeated exactly  k  times. Note that  k  is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,  k . For example, there won't be input like  3a  or  2[4] . Examples: s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef". Thought process: Recursively decode strings inside brackets and append them to result. Solution 1 (Recursive): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { p...

Given a 2D grid, each cell is either a wall  'W' , an enemy  'E'  or empty  '0'  (the number zero), return the maximum enemies you can kill using one bomb. The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed. Note that you can only put the bomb at an empty cell. Example: For the given grid 0 E 0 0 E 0 W E 0 E 0 0 return 3. (Placing a bomb at (1,1) kills 3 enemies) Thought process: Iterate through the matrix. Use global variables to keep track of row hits and column hits. These will propagate until we reach a wall. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int maxKilledEnemies ( char [][] grid ) { int height = grid . length ; if ( height == 0 ) { return 0 ; } int width = grid [ 0 ]. length ;...

Given a set of words  (without duplicates) , find all  word squares  you can build from them. A sequence of words forms a valid word square if the  k th  row and column read the exact same string, where 0 ≤  k  < max(numRows, numColumns). For example, the word sequence  ["ball","area","lead","lady"]  forms a word square because each word reads the same both horizontally and vertically. b a l l a r e a l e a d l a d y Note: There are at least 1 and at most 1000 words. All words will have the exact same length. Word length is at least 1 and at most 5. Each word contains only lowercase English alphabet  a-z . Example 1: Input: ["area","lead","wall","lady","ball"] Output: [ [ "wall", "area", "lead", "lady" ], [ "ball", "area", "lead", "lady" ] ] Explanation: The ou...

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. For example, MovingAverage m = new MovingAverage(3); m.next(1) = 1 m.next(10) = (1 + 10) / 2 m.next(3) = (1 + 10 + 3) / 3 m.next(5) = (10 + 3 + 5) / 3 Thought process: Use queue. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class MovingAverage { private double sum ; private int capacity ; private Queue < Integer > queue ; /** Initialize your data structure here. */ public MovingAverage ( int size ) { capacity = size ; sum = 0 ; queue = new LinkedList <>(); } public double next ( int val ) { if ( queue . size () == capacity ) { sum -= queue . poll (); } queue . offer ( val ); sum += val ; return sum / queue . size (); } } /** * Your MovingAvera...

Given two 1d vectors, implement an iterator to return their elements alternately. For example, given two 1d vectors: v1 = [1, 2] v2 = [3, 4, 5, 6] By calling  next  repeatedly until  hasNext  returns  false , the order of elements returned by  next  should be:  [1, 3, 2, 4, 5, 6] . Follow up : What if you are given  k  1d vectors? How well can your code be extended to such cases? Clarification for the follow up question -  Update (2015-09-18): The "Zigzag" order is not clearly defined and is ambiguous for  k > 2  cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input: [1,2,3] [4,5,6,7] [8,9] It should return  [1,4,8,2,5,9,3,6,7] . Thought process: Combine two lists into one zigzag list in the constructor. Solution 1 (iterator): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public...

Given a  rows x cols  screen and a sentence represented by a list of  non-empty  words, find  how many times  the given sentence can be fitted on the screen. Note: A word cannot be split into two lines. The order of words in the sentence must remain unchanged. Two consecutive words  in a line  must be separated by a single space. Total words in the sentence won't exceed 100. Length of each word is greater than 0 and won't exceed 10. 1 ≤ rows, cols ≤ 20,000. Example 1: Input: rows = 2, cols = 8, sentence = ["hello", "world"] Output: 1 Explanation: hello--- world--- The character '-' signifies an empty space on the screen. Example 2: Input: rows = 3, cols = 6, sentence = ["a", "bcd", "e"] Output: 2 Explanation: a-bcd- e-a--- bcd-e- The character '-' signifies an empty space on the screen. Example 3: Input: rows = 4, cols = 5, sentence = ["I", "had", ...

Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse). For example, 1 \ 3 / \ 2 4 \ 5 Longest consecutive sequence path is  3-4-5 , so return  3 . 2 \ 3 / 2 / 1 Longest consecutive sequence path is  2-3 ,not 3-2-1 , so return  2 . Thought process: Recursion. Use an instance variable to keep track of longest path. Base case: Node == null: update longest and return. Node.val != parent.val + 1: update longest and reset current path length. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeN...

Given a 2D matrix   matrix , find the sum of the elements inside the rectangle defined by its upper left corner ( row 1,   col 1) and lower right corner ( row 2,   col 2). The above rectangle (with the red border) is defined by (row1, col1) =  (2, 1)  and (row2, col2) =  (4, 3) , which contains sum =  8 . Example: Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 update(3, 2, 2) sumRegion(2, 1, 4, 3) -> 10 Note: The matrix is only modifiable by the  update  function. You may assume the number of calls to  update  and  sumRegion  function is distributed evenly. You may assume that  row 1 ≤  row 2 and  col 1 ≤  col 2. Thought process: Binary indexed tree. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3...