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] . 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 ); } } int [] array = new

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 != 0

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. Solution: 1 2 3 4 5 6

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. Iterate through the windows and find