Han Zhu's Study Notes

Given a non negative integer number  num . For every numbers  i  in the range  0 ≤ i ≤ num  calculate the number of 1's in their binary representation and return them as an array. Example: For  num = 5  you should return  [0,1,1,2,1,2] . Follow up: It is very easy to come up with a solution with run time  O(n*sizeof(integer)) . But can you do it in linear time  O(n)  /possibly in a single pass? Space complexity should be  O(n) . Can you do it like a boss? Do it without using any builtin function like  __builtin_popcount  in c++ or in any other language. Hint: You should make use of what you have produced already. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous. Or does the odd/even status of the number help you in calculating the number of 1s? Thought process: GCC has a built-in function called "__builtin_popcount", which can return the number of 1 bits of an integer in constant time

Given an unsorted array  nums , reorder it  in-place  such that  nums[0] <= nums[1] >= nums[2] <= nums[3]... . For example, given  nums = [3, 5, 2, 1, 6, 4] , one possible answer is  [1, 6, 2, 5, 3, 4] . Thought process: The result needs to guarantee that when i is odd, nums[i] >= nums[i - 1]; when i is even, nums[i] <= nums[i - 1]. The idea is that, whenever we see a nums[i] that violates this rule, we swap it with nums[i - 1]. This will work because if i is odd and nums[i] < nums[i - 1], nums[i] is also always less than nums[i - 2]; if i is even and nums[i] > nums[i - 1], nums[i] is also always larger than nums[i - 2]. So swapping will not violate the relationship between nums[i - 1] and nums[i - 2]. Solution: 1 2 3 4 5 6 7 8 9 10 class Solution { public: void wiggleSort(vector < int >& nums) { for ( int i = 1 ; i < nums.size(); i ++ ) { if (((i & 1 ) && nums[i] < nums[i -

You are given an  n  x  n  2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] Example 2: Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] Thought process: Iterate the matrix from the outer-most layer to the inner most layer. Rotate the layers one by one. Solution (C++): 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public: void rotate(vector < vector < int >>& matrix) { reverse(matrix.begin(), matrix.

Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 click to show hints. Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal. Thought process: Each node's right sub-tree is linked to its largest left child. So the idea is to recursively flatten a node's right sub-tree, then flatten its left sub-tree, and finally link the right sub-tree after the left sub-tree and move the sub-tree to the right. The key point is to keep a prev pointer that points to the previously finished node, and attach it to the current node. Solution 1 (C++): 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 /** * Definition for a binar

Given  n  pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given  n  = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Thought process: The idea is to recursively add and remove parentheses in a string. When the string's length reaches 2 * n, we have our base case and we can add the string to result list. To make sure the parentheses are well-formed, we can use two counters: open and close, which tracks open parenthesis and close parenthesis respectively. When open < n, we can add more open parentheses; when close < open, we can add more close parentheses. 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: vector < string > generateParenthesis( int n) { vector < string > parentheses; generateParentheses(n, "" , pa

Implement a trie with  insert ,  search , and  startsWith  methods. Note: You may assume that all inputs are consist of lowercase letters  a-z . Thought process: Insert: create a new node and add it to the map if current node does not contain current character. Search: return false if current node does not contain current character, or if the node at the end of searching is not a word. Startswith: return false if current node does not contain current character. Solution 1 (Java): 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 52 53 54 55 56 57 58 59 60 61 62 63 64 class Trie { class TrieNode { TrieNode [] children ; boolean isWord ; TrieNode () { children = new TrieNode [ 26 ]; } } private TrieNode root ; /** Initialize your data structure here. */ public Trie ()

File is a logical collection of 1's and 0's. There are two basic types of files: Text / ASCII files: Plain printable text. Generally human readable and editable. Examples: .c, .java, .txt. Binary files: Everything other than text files. It's kind of a misnomer, because text files are essentially binary as well. Generally not human readable and editable.  Usually generated and interpreted by some program. Endianness: Endianness refers to how the binary data in a file is ordered. There are two types of Endianness conventions: Big Endian: bytes are stored in file from most significant bits (MSB) to least significant bits (LSB). Example: CADE 0000 0002 Little Endian: bytes are stored in file from LSB to MSB. Example: DECA 0000 0200 In the UNIX operating system, I/O devices are modeled as files. You could open them, write bytes to them, and read bytes from them. C library defines three constant (always open, cannot close) file handlers: stdin:

The Big Ideas: High-level and a low-level language: C is a compiled language (C -> assembly -> machine language). It has a few high-level constructs that can be readily translated into assembly. Imperative: Assignment statements explicitly change memory values. As opposed to declarative, where statements describe function. Procedural: All code statements are contained in functions. Functions can be bundled into libraries which allow you to build large programs from smaller pieces. Functions are implemented using a stack. File-oriented. Portability: the same C code can be compiled for different ISAs. The Compilation Process: The code files that you write are compiled into assembly code which is then assembled into machine code. Some compilers, like clang, perform both phases and simply output the binary, executable result. All C programs must start in the function "main". Recall that C is procedural. Everything is inside a function. Var

Given an integer, write a function to determine if it is a power of two. Thought process: If the number is not positive, return false directly. Divide the number by 2 until it becomes an odd number. If it's not 1, return false. Otherwise, return true. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: bool isPowerOfTwo( int n) { if (n <= 0 ) { return false ; } while ( ! (n & 1 )) { n /= 2 ; } return n == 1 ; } }; Time complexity: O(logn).

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only  distinct  numbers from the original list. For example, Given  1->2->3->3->4->4->5 , return  1->2->5 . Given  1->1->1->2->3 , return  2->3 . Thought process: It's not clear that we can return head as the result because head might need to be deleted. We can solve this by inserting a dummy node before head. After deleting duplicate nodes, we can return dummy->next. 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 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode deleteDuplicates ( ListNode head ) { ListNode dummy = new ListNode ( 0 ); dummy . next = head ; ListNode current = dummy ;

Given a sorted linked list, delete all duplicates such that each element appear only  once . For example, Given  1->1->2 , return  1->2 . Given  1->1->2->3->3 , return  1->2->3 . Thought process: Iterate through the list, and check if the value of the next node is the same as this node. There are two cases: Value of the next node == value of this node: delete next node. Otherwise, increment current node. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode deleteDuplicates ( ListNode head ) { ListNode current = head ; while ( current != null ) { if ( current . next != null && current . next . val == current . val ) { current . n

Follow up for " Remove Duplicates ": What if duplicates are allowed at most  twice ? For example, Given sorted array  nums  =  [1,1,1,2,2,3] , Your function should return length =  5 , with the first five elements of  nums  being  1 ,  1 ,  2 ,  2  and  3 . It doesn't matter what you leave beyond the new length. Thought process: We can still use two pointers. The slow pointer points to current element in the new array, and the fast pointer points to the current element in the old array. Only write to new array if nums[fast] > nums[slow - 2]. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public int removeDuplicates ( int [] nums ) { int i = 0 ; for ( int num : nums ) { if ( i < 2 || num > nums [ i - 2 ]) { nums [ i ] = num ; i ++; } } return i ; } } Time complexity: O(n). Space complexity: O(1).

Given a sorted array, remove the duplicates in place such that each element appear only  once  and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array  nums  =  [1,1,2] , Your function should return length =  2 , with the first two elements of  nums  being  1  and  2  respectively. It doesn't matter what you leave beyond the new length. Thought process: Because what I leave beyond the new length doesn't matter, I can overwrite the duplicate elements with the unique elements. The idea is to iterate through the array and keep a count of duplicate elements seen so far. If we see a duplicate element, we increment the count. Otherwise, we write the element into its right position. Solution 1:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int removeDuplicates(vector < int >& nums) { int duplicates = 0 ;

Given an array of integers, 1 ≤ a[i] ≤  n  ( n  = size of array), some elements appear  twice  and others appear  once . Find all the elements that appear  twice  in this array. Could you do it without extra space and in O( n ) runtime? Example: Input: [4,3,2,7,8,2,3,1] Output: [2,3] Thought process: Iterate through the array and maintain a hashset of all elements seen. If an element is in the hashset already, it is a duplicate. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: vector < int > findDuplicates(vector < int >& nums) { vector < int > duplicates; unordered_set < int > set; for ( int num : nums) { if (set.find(num) != set.end()) { duplicates.push_back(num); } else { set.insert(num); } } return duplicates; } }; Time complexity: O(n). Sp