Han Zhu's Study Notes

Given two arrays, write a function to compute their intersection. Example: Given  nums1  =  [1, 2, 2, 1] ,  nums2  =  [2, 2] , return  [2, 2] . Note: Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Follow up: What if the given array is already sorted? How would you optimize your algorithm? What if  nums1 's size is small compared to  nums2 's size? Which algorithm is better? What if elements of  nums2  are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once? Thought process: Iterate through both arrays. Count the number of each number and put the counts into two maps. Iterate through both maps. For numbers that appear in both maps, put min(count1, count2) of that number into result. 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 ...

Given two arrays, write a function to compute their intersection. Example: Given  nums1  =  [1, 2, 2, 1] ,  nums2  =  [2, 2] , return  [2] . Note: Each element in the result must be unique. The result can be in any order. Thought process: Iterate through nums1. Put the elements into a hash set. Iterate through nums2. The elements that the hash set contains are the intersection. 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 [] intersection ( int [] nums1 , int [] nums2 ) { Set < Integer > set = new HashSet <>(); for ( int num : nums1 ) { set . add ( num ); } Set < Integer > intersection = new HashSet <>(); for ( int num : nums2 ) { if ( set . contains ( num )) { intersection . add ( num ); } } ...

Given two strings  s  and  t , write a function to determine if  t  is an anagram of  s . For example, s  = "anagram",  t  = "nagaram", return true. s  = "rat",  t  = "car", return false. Note: You may assume the string contains only lowercase alphabets. Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case? Thought process: Iterate through both strings, count the number of each character, and compare the counts. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean isAnagram ( String s , String t ) { int [] count = new int [ 26 ]; for ( char c : s . toCharArray ()) { count [ c - 'a' ]++; } for ( char c : t . toCharArray ()) { count [ c - 'a' ]--; } for ( int i : count ) { if ( i !=...

Given a string, find the length of the  longest substring  without repeating characters. Examples: Given  "abcabcbb" , the answer is  "abc" , which the length is 3. Given  "bbbbb" , the answer is  "b" , with the length of 1. Given  "pwwkew" , the answer is  "wke" , with the length of 3. Note that the answer must be a  substring ,  "pwke"  is a  subsequence  and not a substring. Thought process: Two pointers + sliding window: Pointer i points to the left end of current window. Pointer j points to the right end of current window. Use a hash set to keep track of the characters in current window. Iterate through the string using j. If s[j] is a repeating character, increment i and remove s[i] from set until no repeating character is there. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int lengthOfLongestSubstring ( String s ) { ...

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Note: The input string length won't exceed 1000. Thought process: Dynamic programming. Use a matrix to check if s[i,j] is a palindrome. If so, add one to count. Sub-problem: check if a sub-string of s is a palindrome. Function:  If s[i] == s[j]: If j - i < 2 (one character or two characters), f[i][j] = true. Otherwise, f[i][j] = f[i + 1][j - 1]. Otherwise, f[i][j] = false. Initialization: none. Answer: f[0][n - 1] will sa...

Your are given an array of integers  prices , for which the  i -th element is the price of a given stock on day  i ; and a non-negative integer  fee  representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.) Return the maximum profit you can make. Example 1: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: Buying at prices[0] = 1 Selling at prices[3] = 8 Buying at prices[4] = 4 Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Note: 0 < prices.length <= 50000 . 0 < prices[i] < 50000 . 0 <= fee < 50000 . Thought process: Each day there are two options, buy or sell. Use two variables buy and sell to keep track of the max profit. Solutio...

In a given array  nums  of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size  k , and we want to maximize the sum of all  3*k  entries. Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one. Example: Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger. Note: nums.length  will be between 1 and 20000. nums[i]  will be between 1 and 65535. k  will be between 1 and floor(nums.length / 3). Thought process: Dynamic programming. Create an array of sums of windows of size k. This array's length will be nums.length - k + 1, because an array can have this many choices of windows. I...

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...