Han Zhu's Study Notes

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the  top  to the  bottom  and cross the  least  bricks. The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right. If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks. Example: Input: [[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]] Output: 2 Explanation: Note: The width sum of bricks in different rows are the same and won't exceed INT_MAX. The number of bricks in each row is in...

Note: This is a companion problem to the  System Design  problem:  Design TinyURL . TinyURL is a URL shortening service where you enter a URL such as  https://leetcode.com/problems/design-tinyurl  and it returns a short URL such as  http://tinyurl.com/4e9iAk . Design the  encode  and  decode  methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL. Thought process: Use a simple counter. Solution 1 (counter): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class Codec { private int i ; private Map < Integer , String > map ; public Codec () { i = 0 ; map = new HashMap <>(); } // Encodes a URL to a shortened URL. public String encode ( String longUrl )...

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Note:  The length of the given binary array will not exceed 50,000. Thought process: Iterate through the array. Use a variable count to keep track of 0s and 1s. If I see a 1, increment count; Else, decrement count. The trick is that when I see two indices with the same count, the sub-array between them must have equal number of 0 and 1. Use a hash map of count -> index to keep track of this information. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int findMaxLength ( int [] nums ) { Map < Integer , Integer > map = new HashMap ...

Given two  sparse matrices   A  and  B , return the result of  AB . You may assume that  A 's column number is equal to  B 's row number. Example: A = [ [ 1, 0, 0], [-1, 0, 3] ] B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ] | 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | | 0 0 1 | Thought process: Create product matrix. Iterate through it and calculate result for each position. This ignores the fact that the matrices are sparse. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int [][] multiply ( int [][] A , int [][] B ) { int Arow = A . length ; int Acolumn = A [ 0 ]. length ; int Brow = B . length ; int Bcolumn = B [ 0 ]. length ; int [][] product = new int [ Arow ][ Bcolumn ]; for ( int i = 0 ; i < Arow ; i ++) { ...

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S  =  "ADOBECODEBANC" T  =  "ABC" Minimum window is  "BANC" . Note: If there is no such window in S that covers all characters in T, return the empty string  "" . If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. Thought process: Hash map + two pointers. Use a hash map to keep track of the occurrence of T's letters in S. The hash map maps a character in T to the remaining number of it to be matched. The value can also be negative, which means that there is one extra such character in the current window. Iterate through T. Populate map<letter, count>. This map represents the remaining characters in T to be matched. Iterate through S. Initialize variable count = t.length, window = empty string. Pointer i is the le...

Given an array of strings, group anagrams together. For example, given:  ["eat", "tea", "tan", "ate", "nat", "bat"] , Return: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] Note:  All inputs will be in lower-case. Thought process: Hash map. If two words have the same letter counts, they can be grouped together. Since all inputs are in lower-case, my first thought is to use and int[26] as the map's key, and a list of strings as the value. However, java does not have a hash function for integer array. So instead, I'll use a char array and store it as a string. 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 class Solution { public List < List < String >> groupAnagrams ( String [] strs ) { Map < String , List < String >> map = new HashMap <>(...

A message containing letters from  A-Z  is being encoded to numbers using the following mapping way: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9. Given the encoded message containing digits and the character '*', return the total number of ways to decode it. Also, since the answer may be very large, you should return the output mod 10 9  + 7. Example 1: Input: "*" Output: 9 Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I". Example 2: Input: "1*" Output: 9 + 9 = 18 Note: The length of the input string will fit in range [1, 10 5 ]. The input string will only contain the character '*' and digits '0' - '9'. ...