Han Zhu's Study Notes

Equations are given in the format  A / B = k , where  A  and  B  are variables represented as strings, and  k  is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return  -1.0 . Example: Given  a / b = 2.0, b / c = 3.0. queries are:  a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return  [6.0, 0.5, -1.0, 1.0, -1.0 ]. The input is:  vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries  , where  equations.size() == values.size() , and the values are positive. This represents the equations. Return  vector<double> . According to the example above: equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. The...

You are given two integer arrays  nums1  and  nums2  sorted in ascending order and an integer  k . Define a pair  (u,v)  which consists of one element from the first array and one element from the second array. Find the k pairs  (u 1 ,v 1 ),(u 2 ,v 2 ) ...(u k ,v k )  with the smallest sums. Example 1: Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] Example 2: Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Return: [1,1],[1,1] The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3] Example 3: Given nums1 = [1,2], nums2 = [3], k = 3 Return: [1,3],[2,3] All possible pairs are returned from the sequence: [1,3],[2,3] Thought process: Maintain a min heap of size k. At first, offer all (nums1[i], nums2[0]) to the heap. Do k iterations. For eac...

Assume you have an array of length  n  initialized with all  0 's and are given  k  update operations. Each operation is represented as a triplet:  [startIndex, endIndex, inc]  which increments each element of subarray  A[startIndex ... endIndex]  (startIndex and endIndex inclusive) with  inc . Return the modified array after all  k  operations were executed. Example: Given: length = 5, updates = [ [1, 3, 2], [2, 4, 3], [0, 2, -2] ] Output: [-2, 0, 3, 5, 3] Explanation: Initial state: [ 0, 0, 0, 0, 0 ] After applying operation [1, 3, 2]: [ 0, 2, 2, 2, 0 ] After applying operation [2, 4, 3]: [ 0, 2, 5, 5, 3 ] After applying operation [0, 2, -2]: [-2, 0, 3, 5, 3 ] Thought process: The brute force solution has a time complexity of O(kn), where length = n. How can we improve this? We are running a lot of duplicate iterations over the array. Multiple updates may have...

Validate if a given string is numeric. Some examples: "0"  =>  true " 0.1 "  =>  true "abc"  =>  false "1 a"  =>  false "2e10"  =>  true Note:  It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. Thought process: There are several rules to enforce: There must be at least one number. e must come after some number and be followed by some number. Point cannot come after e. + and - can only appear in two positions: at the start of the string or right after e. There cannot be characters other than digits, e, point, + or -, or space. We can use several boolean flags to make these happen. 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 class Solution { public boolean isNumber ( String s ) { s = s . trim (); boolea...

According to the  Wikipedia's article : "The  Game of Life , also known simply as  Life , is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a  board  with  m  by  n  cells, each cell has an initial state  live  (1) or  dead  (0). Each cell interacts with its  eight neighbors  (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state. Follow up :  Could you solve ...

Given an array of  n  integers  nums  and a  target , find the number of index triplets  i, j, k  with  0 <= i < j < k < n  that satisfy the condition  nums[i] + nums[j] + nums[k] < target . For example, given  nums  =  [-2, 0, 1, 3] , and  target  = 2. Return 2. Because there are two triplets which sums are less than 2: [-2, 0, 1] [-2, 0, 3] Follow up: Could you solve it in  O ( n 2 ) runtime? Thought process: Although the question requires that 0 <= i < j < k < n, we can still sort the array, because as long as we can find a triplet that satisfy nums[i] + nums[j] + nums[k] < target, we can always swap i, j, and k to make them in the right order. So the idea is to sort the array and use two pointers. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int threeSumSmaller ( int [] nums , i...

Given a non-negative integer represented as a  non-empty  array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list. Thought process: We don't know if the result array will have the same length as the input array. Therefore, we can use a list to hold the sum, and copy the numbers over to the result array. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int [] plusOne ( int [] digits ) { List < Integer > list = new ArrayList <>(); int sum = digits [ digits . length - 1 ] + 1 ; int carry = sum / 10 ; list . add ( sum % 10 ); int i = digits . length - 2 ; while ( i >= 0 || carry > 0 ) { int digit = i >= 0 ? digits [ i...

Given  n  non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given  [0,1,0,2,1,0,1,3,2,1,2,1] , return  6 . The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.  Thanks Marcos  for contributing this image! Thought process: Iterate through the array. For each element, calculate the amount of water trapped in the current position. To do this, we need to iterate through the elements to the left and the right, and find the cap (top of water). Solution 1 (brute force): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int trap ( int [] height ) { int len = height . length ; int trapped = 0 ; for ( int i = 1 ; i < len - 1 ; i ++) { int leftTop =...