Han Zhu's Study Notes

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

Say you have an array for which the  i th  element is the price of a given stock on day  i . Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Thought process: Greedy. As soon as price drops, I sell. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int maxProfit ( int [] prices ) { if ( prices . length <= 1 ) { return 0 ; } int low = prices [ 0 ]; int high = prices [ 0 ]; int profit = 0 ; for ( int i = 1 ; i < prices . length ; i ++) { if ( prices [ i ] < prices [ i - 1 ]) { profit += high - low ; low = pric...

Implement wildcard pattern matching with support for  '?'  and  '*' . '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") ? false isMatch("aa","aa") ? true isMatch("aaa","aa") ? false isMatch("aa", "*") ? true isMatch("aa", "a*") ? true isMatch("ab", "?*") ? true isMatch("aab", "c*a*b") ? false Thought process: Recursively match s and p's substrings. Base case: If s and p are both empty, return true. If p's length is 1: If p is *, return true. If p is ? and s's length is 1, return true. Else if s and p are equal, return true. Recurrence: If p's first char...

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval  n  that means between two  same tasks , there must be at least n intervals that CPU are doing different tasks or just be idle. You need to return the  least  number of intervals the CPU will take to finish all the given tasks. Example 1: Input: tasks = ['A','A','A','B','B','B'], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B. Note: The number of tasks is in the range [1, 10000]. The integer n is in the range [0, 100]. Thought process: The tasks with higher numbers of instances should be executed before the ones with lower numbers of insta...

Given a string  s  and a string  t , check if  s  is subsequence of  t . You may assume that there is only lower case English letters in both  s  and  t .  t  is potentially a very long (length ~= 500,000) string, and  s is a short string (<=100). A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  "ace"  is a subsequence of  "abcde"  while  "aec"  is not). Example 1: s  =  "abc" ,  t  =  "ahbgdc" Return  true . Example 2: s  =  "axc" ,  t  =  "ahbgdc" Return  false . Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code? ...

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A =  [2,3,1,1,4] The minimum number of jumps to reach the last index is  2 . (Jump  1  step from index 0 to 1, then  3  steps to the last index.) Note: You can assume that you can always reach the last index. Thought process: Since we can assume that we can always reach the last index, we know that every index can be reached. Sub-problem: reach any index in the minimum number of jumps. Formula: f[i] = min(f[j]) + 1, where 0 <= j < i and j + jumps[j] >= i. Initialization: f[0] = 0. We don't need to jump at all to reach the first index. Answer: f[last index]. Here we can also be greedy. If indexes a and b can both jump to c and a < b, then we...

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A =  [2,3,1,1,4] , return  true . A =  [3,2,1,0,4] , return  false . Thought process: Sub-problem: if you are able to reach any index. Formula: f[i] = (f[0] && 0 + jump[0] >= i) || (f[1] && 1 + jump[1] >= i) || . . . || (f[i - 1] && i - 1 + jump[i - 1] >= i). Initialization: f[0] = true. Answer: f[last index]. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Solution { public boolean canJump ( int [] nums ) { int length = nums . length ; boolean [] f = new boolean [ length ]; f [ 0 ] = true ; for ( int i = 1 ; i < length ; ...