Han Zhu's Study Notes

Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Thought process: Iterate through haystack. When I find the first character of needle, iterate through needle. Check if all the rest of the characters match. Solution: 1 2 3 4 5 6 7 8 9 10 class Solution { public int strStr ( String haystack , String needle ) { for ( int i = 0 ; i < haystack . length () - needle . length () + 1 ; i ++) { if ( haystack . substring ( i , i + needle . length ()). equals ( needle )) { return i ; } } return - 1 ; } } Time complexity: Say the length of haystack is h and needle is n. The overall time complexity is O((h - n)n).

Given the running logs of  n  functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions. Each function has a unique id, start from  0  to  n-1 . A function may be called recursively or by another function. A log is a string has this format :  function_id:start_or_end:timestamp . For example,  "0:start:0"  means function 0 starts from the very beginning of time 0.  "0:end:0"  means function 0 ends to the very end of time 0. Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id. Example 1: Input: n = 2 logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"] Output: [3, 4] Explanation: Function 0 starts at time 0, then it executes 2 units of time and r

Given an absolute path for a file (Unix-style), simplify it. For example, path  =  "/home/" , =>  "/home" path  =  "/a/./b/../../c/" , =>  "/c" click to show corner cases. Corner Cases: Did you consider the case where  path  =  "/../" ? In this case, you should return  "/" . Another corner case is the path might contain multiple slashes  '/'  together, such as  "/home//foo/" . In this case, you should ignore redundant slashes and return  "/home/foo" . Thought process: Use stack. Split the string by '/'. Iterate through the elements. There are several cases: Word: push onto stack. '.': ignore. '..': pop the top element from stack. Empty string: two '/' together. Ignore. At the end, concatenate the words to a StringBuilder and reverse it. Push a '/' onto stack at the beginning so that the returned path will have a '/'

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note: The array size can be very large. Solution that uses too much extra space will not pass the judge. Example: int[] nums = new int[] {1,2,3,3,3}; Solution solution = new Solution(nums); // pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning. solution.pick(3); // pick(1) should return 0. Since in the array only nums[0] is equal to 1. solution.pick(1); Thought process: The question doesn't have a required time complexity on pick, but rather it doesn't allow using too much extra space. The idea is to store the given array as is. Iterate through the array. Use a variable count to keep track of the number of occurrences of target. And use count as an upper bound for random. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2 31  - 1. For example, 123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Thought process: Iterate the number from right to left. One thousand at a time. For each thousand, iterate through the digits from right to left. Based on the index of the current digit, there are several cases: index == 1:  digit == 0: left > 0: append "x-ty" to words. Increment index and right shift number. left == 0: continue. left == 1: append "x-teen" to words. Increment index and right shift number. Otherwise, append number to words. index == 2: digit == 0: continue. digit > 0: since the special cases are already covered in the previous case. Append "x-ty" to words. index == 3: di

Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB Thought process: Think of the result as a number format where each digit can have 26 numbers. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public String convertToTitle ( int n ) { StringBuilder sb = new StringBuilder (); while ( n > 0 ) { n --; sb . append (( char )( 'A' + n % 26 )); n /= 26 ; } return sb . reverse (). toString (); } } Time complexity: O(n / 26) = O(n).

Given two non-negative integers  num1  and  num2  represented as strings, return the product of  num1  and  num2 . Note: The length of both  num1  and  num2  is < 110. Both  num1  and  num2  contains only digits  0-9 . Both  num1  and  num2  does not contain any leading zero. You  must not use any built-in BigInteger library  or  convert the inputs to integer  directly. Thought process: Use an array to keep track of the products of each pair of digits and add them together. When doing multiplication, I need to align the numbers to the right. So I need to iterate through the product array from right to left. 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 class Solution { public String multiply ( String num1 , String num2 ) { int [] products = new int [ num1 . length () + num2 . length () - 1 ]; for ( int i = num1 . length () - 1 ; i >= 0 ; i --) { for ( int j =

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. Thought process: Iterate the numeral. Add every character together and subtract the special cases (e.g. IV). There is going to be at most one occurrence of each special case. 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 37 38 39 40 41 42 class Solution { public int romanToInt ( String s ) { int sum = 0 ; for ( char c : s . toCharArray ()) { switch ( c ) { case 'I' : sum ++; break ; case 'V' : sum += 5 ; break ; case 'X' : sum += 10 ; break ; case 'L' : sum += 50 ; break ;

Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? Thought process: Use a fast and a slow pointer to iterate through the list. At the end, slow is at the middle of the list and fast is at the end. Reverse the second half of the list. Iterate through both halves in the same time and check if they match. 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 37 38 39 40 41 42 43 44 45 46 47 48 49 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome ( ListNode head ) { if ( head == null ) { return true ; } ListNode mid = getMid ( head ); ListNode midReversed = reverse ( mid ); while ( midReversed != nu

Given a linked list, reverse the nodes of a linked list  k  at a time and return its modified list. k  is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of  k  then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed. For example, Given this linked list:  1->2->3->4->5 For  k  = 2, you should return:  2->1->4->3->5 For  k  = 3, you should return:  3->2->1->4->5 Thought process: Iterate through the linked list. Use two pointers to reverse k nodes at a time. 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) {