Leetcode Easy Collection Top Interview Questions Punching diary

# # # # # # # # # # # # # # #

NumSoFar: 49

# # # # # # # # # # # # # # #

26. Remove Duplicates from Sorted Array

double pointers, one slow one quick to test equal or not.

class Solution { public int removeDuplicates(int[] nums) { if(nums == null || nums.length == 0) return 0; if(nums.length == 1) return 1; int i = 0, j = 1; int len = 1; while(i < nums.length && j < nums.length){ if(nums[i] == nums[j]) j++; else{ nums[i+1] = nums[j]; i++; j++; len++; } } return len; }}Copy the code

1. Two Sum

HashMap

class Solution { public int[] twoSum(int[] nums, int target) { if(nums == null || nums.length == 0) throw new IllegalArgumentException(); HashMap<Integer, Integer> m = new HashMap<>(); for(int i = 0; i < nums.length; i++){ int res = target - nums[i]; if(m.containsKey(res)) return new int[] {m.get(res), i}; else m.put(nums[i], i); } throw new IllegalArgumentException(); }}Copy the code

412. FizzBuzz actual question @ Lutron onsite…. datastructure announcement:

class Solution { public List<String> fizzBuzz(int n) { List<String> ls = new ArrayList<>(); String s = new String(); for(int i = 1; i <= n; i++){ if(i % 3 == 0 && i % 5 == 0) s = "FizzBuzz"; else if(i % 3 == 0) s = "Fizz"; else if(i % 5 == 0) s = "Buzz"; else s = Integer.toString(i); ls.add(s); } return ls; }}Copy the code

Given in the Java online submissions for Fizz Buzz. Memory Usage: Submissions in Java online submissions for Fizz Buzz.

. idont understand since i am using the simplest way…

136. Single Number

xor method:

class Solution { public int singleNumber(int[] nums) { int a = 0; for(int i = 0; i < nums.length; i++){ a ^= nums[i]; } return a; }}Copy the code

hashset method(used extra space):

the trick:

Iterator it = s.iterator();
Integer ans = it.next();
Copy the code

will return error because the type in first line of code is wrong.

but:

Iterator<Integer> it = s.iterator();
Integer ans = it.next();
Copy the code

is correct.

class Solution { public int singleNumber(int[] nums) { HashSet<Integer> s = new HashSet<>(); for(int i = 0; i < nums.length; i++){ if(s.contains(nums[i])) s.remove(nums[i]); else s.add(nums[i]); } Iterator<Integer> it = s.iterator(); Integer ans = it.next(); return ans; }}Copy the code

21. Merge Two Sorted Lists

    class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2){ if(l1 == null || l2 == null) return l1 == null ? l2 : l1; ListNode dummy = new ListNode(0); ListNode trans = dummy; while(l1 ! = null || l2 ! = null){ int v1 = l1 ! = null ? l1.val : Integer.MAX_VALUE; int v2 = l2 ! = null ? l2.val : Integer.MAX_VALUE; if(v1 <= v2){ trans.next = l1; trans = trans.next; l1 = l1.next; } else{ trans.next = l2; trans = trans.next; l2 = l2.next; } } return dummy.next; } } class Solution { ListNode dummy = new ListNode(0); public ListNode mergeTwoLists(ListNode l1, ListNode l2){ if(l1 == null || l2 == null) return l1 == null ? l2 : l1; ListNode cur = dummy; merge(cur, l1, l2); return dummy.next;

    } private void merge(ListNode cur, ListNode l1, ListNode l2){ if(l1 == null && l2 == null) return; int v1 = l1 == null ? Integer.MAX_VALUE : l1.val; int v2 = l2 == null ? Integer.MAX_VALUE : l2.val; if(v1 <= v2){ cur.next = l1; cur = cur.next; l1 = l1.next; } else{ cur.next = l2; cur = cur.next; l2 = l2.next; } merge(cur, l1, l2); }}

22. Contains Duplicate

class Solution { public boolean containsDuplicate(int[] nums) { if(nums == null || nums.length == 0) return false; HashSet<Integer> s = new HashSet<>(); for(int i = 0; i < nums.length; i++){ if(s.contains(nums[i])) return true; else s.add(nums[i]); } return false; }}Copy the code

result:

Success Details Runtime: 9 ms, faster than 57.49% of Java online submissions for Contains duplicates. Submissions in Java online submissions for Contains duplicates.

obviously not the best solution

class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> s = new HashSet<>(); for(int i = 0; i < nums.length; i++){ s.add(nums[i]); } if(nums.length == s.size()) return false; else return true; }}Copy the code

result:

Success Details Runtime: 8 ms, faster than 71.12% of Java online submissions for Contains duplicates. Memory Usage: Submissions in Java online submissions for Contains duplicates.

much better i guess.

283. Move Zeros

class Solution { public void moveZeroes(int[] nums) { for(int quick = 0, slow = 0; quick < nums.length; quick++){ if(nums[quick] ! = 0){ int temp = nums[slow]; nums[slow] = nums[quick]; nums[quick] = temp; slow++; }}}}Copy the code

two pointers starting with 0, check the number of quick index if it equals to 0 every time. if so, leave slow one not moving, increase the quick only to the next. this ensures that the numbers between index quick and slow are 0s. if quick meets a non-zero number, exchange the number of slow and quick index. this makes sure the non-zero numbers with right order goes to the front. then increase both quick and slow since the slow index number is swapped and is non-zero and the quick is zero.

go unitl the quick reaches the end of the array. all zeros should be in the back and the rest should be in the front with correct order.

20. Valid Parentheses

    class Solution { public boolean isValid(String s) { Stack stack = new Stack<>(); HashMap<Character, Character> hm = new HashMap<>(); hm.put(‘)’, ‘(‘); hm.put(‘]’, ‘[‘); hm.put(‘}’, ‘{‘); for(int i = 0; i < s.length(); i++){ if(hm.containsKey(s.charAt(i))){ if(stack.size() == 0 || stack.peek() ! = hm.get(s.charAt(i))) return false; else stack.pop(); } else stack.push(s.charAt(i)); } return stack.isEmpty(); } }

21. Best Time to Buy and Sell Stock II

class Solution{ public int maxProfit(int[] prices) { int maxProfit = 0; for(int i = 1; i < prices.length; i++){ if(prices[i] > prices[i-1]){ maxProfit += prices[i] - prices[i-1]; } } return maxProfit; }}Copy the code

189. Rotate Array

basic idea:

reverse all numbers

reverse first k numbers

reverse last n-k numbers

note that when k > the length of array, rotating k times is the same as rotating k % n times

class Solution { public void rotate(int[] nums, int k) { int n = nums.length; if(n == 0 || n == 1) return; int valid_k = k > n ? k % n : k; reverse(nums, 0, n-1); reverse(nums, 0, valid_k-1); reverse(nums, valid_k, n-1); } public void reverse(int[] nums, int start, int end){ while(start < end){ int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; }}}Copy the code

Result: Success Details Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate array. Memory Usage: The linked list is given in the Java online submissions for the Rotate Array.

350. Intersection of Two Arrays II

class Solution { public int[] intersect(int[] nums1, int[] nums2) { List<Integer> l = new ArrayList<>(); Arrays.sort(nums1); Arrays.sort(nums2); int p1 = 0, p2 = 0; while(p1 < nums1.length && p2 < nums2.length){ if(nums1[p1] < nums2[p2]) p1++; else if(nums1[p1] > nums2[p2]) p2++; else{ l.add(nums1[p1++]); p2++; } } int[] ans = new int[l.size()]; for(int i = 0; i < ans.length; i++){ ans[i] = l.get(i); } return ans; }}Copy the code

66. Plus One

    class Solution { public int[] plusOne(int[] digits) { for(int i = digits.length-1; i >= 0; i–){ digits[i]++; //add last, if carry then add next digits[i] %= 10; //if carry, then 0, other case remain the same if(digits[i] != 0) return digits; //no carry, then return; else loop to add next } //if all looped and still get carry, then must be all 9 //return an array with original length +1 digits = new int[digits.length+1]; digits[0] = 1; return digits; } }

67. Valid Sudoku

some math tricks on calculating index, how to declare a HashSet array, and in the wrong way by adding element to one HashSet in an array, you get all the HashSets in the array added this element which was a nightmare.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet[] row = new HashSet[9];
        HashSet[] col = new HashSet[9];
        HashSet[] box = new HashSet[9];
        
        for(int i = 0; i < 9; i++){
            row[i] = new HashSet<Integer>();
            col[i] = new HashSet<Integer>();
            box[i] = new HashSet<Integer>();
        }//tested way to add hashsets
        
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                int box_num = i / 3 * 3 + j / 3;
                if(board[i][j] != '.'){
                    int cur = Character.getNumericValue(board[i][j]);
                    if(row[i].contains(cur) || col[j].contains(cur) || box[box_num].contains(cur)) return false;
                    else{
                        row[i].add(cur);
                        col[j].add(cur);
                        box[box_num].add(cur);
                    }
                }
            }
        }
        return true;
    }
}
Copy the code

48. Rotate Image

Given the input matrix = [[1, 2, 3], [4 and 6], [7,8,9]].

Rotate the input matrix in-place such that it becomes: [[7,4,1], [8,5,2], [9,6,3]]

not hard to assume that in order to rotate it, we:

1.see n by n matrix as a n dimension matrix 2.reverse this n-d matrix 3.mirror the new n by n matrix by diagnol line

class Solution { public void rotate(int[][] matrix) { int n = matrix.length; int first = 0, last = n-1; while(first < last){ int[] temp = matrix[first]; matrix[first] = matrix[last]; matrix[last] = temp; first++; last--; } //reverse finished for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; }}}}Copy the code

344. Reverse String

no much to say, two pointers, but a better way to increase/decrease index:

class Solution { public void reverseString(char[] s) { int i = 0, j = s.length-1; while(i < j){ char temp = s[i]; s[i++] = s[j]; s[j--] = temp; }}}Copy the code

7. Reverse Integer

when try to separate integer, use more % and /

in this problem, notice the boudary case, and the number won’t cross boundary only when they are >Integer.MAX_VALUE /10 || (==Integer.MAX_VALUE && nextdigit > 7) since the 2^31-1 is xxxxxxxxxx7, same for negative number.

class Solution {
public int reverse(int x) {
    int ans = 0;
    while(x != 0){
        int pop = x % 10;
        if(ans > Integer.MAX_VALUE/10 || (ans == Integer.MAX_VALUE/10 && pop > 7)) return 0;
        if(ans < Integer.MIN_VALUE/10 || (ans == Integer.MIN_VALUE/10 && pop < -8)) return 0;
        ans = ans * 10 + pop;
        x /= 10;
    }
    return ans;
}
}
Copy the code

387. First Unique Character in a String

new method in hashmap .getOrDefault():

hm.getOrDefault(a,b) returns the value of key a in hashmap hm if hm contains key a, else it returns the value of default (but won’t put the pair in the hm)

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> hm = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            hm.put(c, hm.getOrDefault(c, 0) + 1);
            //here this line equals to:
            //if(!hm.containsKey(c)) hm.put(c,1);
            //else hm.put(c,hm.get(c)+1);
        }
        for(int i = 0; i < s.length(); i++){
            if(hm.get(s.charAt(i)) == 1) return i;
            //since we iterate each one
        }        
        return -1;
    }
}
Copy the code

but this shit is so fxxking slow

242. Valid Anagram

very slow…

class Solution { public boolean isAnagram(String s, String t) { if(s.length() ! = t.length()) return false; HashMap<Character,Integer> hm = new HashMap<>(); for(int i = 0; i < s.length(); i++){ char c1 = s.charAt(i), c2 = t.charAt(i); hm.put(c1, hm.getOrDefault(c1, 0) + 1); hm.put(c2, hm.getOrDefault(c2, 0) - 1); } for(int i = 0; i < s.length(); i++){ char c = s.charAt(i); if(hm.get(c) ! = 0) return false; } return true; } } class Solution { public boolean isAnagram(String s, String t) { if(s.length() ! = t.length()) return false; int[] table = new int[26]; for(int i = 0; i < s.length(); i++){ table[s.charAt(i) - 'a']++; } for(int i = 0; i < s.length(); i++){ int cur = --table[t.charAt(i) - 'a']; if(cur < 0) return false; } return true; }}Copy the code

a little faster than standard.

new method:

public boolean isAnagram(String s, String t) { if(s.length() ! = t.length()) return false; if(s.length() == 0 && t.length() == 0) return true; char[] ch1 = s.toCharArray(); char[] ch2 = t.toCharArray(); Arrays.sort(ch1); Arrays.sort(ch2); int i = 0 , j = 0, n = s.length(); while(i < n && j < n){ if(ch1[i] ! = ch2[j]) return false; i++; j++; } return true; }Copy the code

237. Delete Node in a Linked List

understand linkedlist

class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; }}Copy the code

125. Valid Palindrome two pointers, magical .toLowerCase() and .toCharArray() and .isLetterOrDigit() will satisfy the requirements

class Solution { public static boolean isPalindrome(String s) { s = s.toLowerCase(); char[] chars = s.toCharArray(); int i = 0, j = chars.length - 1; while(i < j){ if(! Character.isLetterOrDigit(chars[i])){ i++; continue; } if(! Character.isLetterOrDigit(chars[j])){ j--; continue; } if(chars[i++] ! = chars[j--]) return false; } return true; }}Copy the code

326. Power of Three

let’s take a look at three methods of this problem as follow up:

1. for loop:

if n cant be divided by 3, false, even so, after many times, it won’t, if divided with no reserved number, then it is 1, else is 0

class Solution { public boolean isPowerOfThree(int n) { if(n < 1) return false; //3^0 = 1 while(n % 3 == 0) n /= 3; return n == 1; }}Copy the code

2. math: log function:

firstly, if 3^x == n, then x == log3(n) and x is integer next, know that loga(b) == logc(b)/logc(a) mathmetically, however, in java we should use log10(b)/log10(a) instead of log(b)/log(a) which represents loge(b)/loge(a) for performance difference.

last, if the result of log3(n) is integer, log3(n) % 1 should be 0, i did not know we could do it this way.

so if to identify whether a result x is integer, we can do: x% 1== 0 ?

class Solution { public boolean isPowerOfThree(int n) { return (Math.log10(n) / Math.log10(3)) % 1 == 0; }}Copy the code

3. Integer limitation:

this is more tricky but easy to understand, all powers of three can be divided by bigger powers of three, like 27 % 9 == 0. in the environment, we have 32 bit signed int and the largest power of 3 is 3^(int)(log(MAX_VALUE)/log(3)), which is 19, so determine whether largest power of 3 is divisible by n. notice in this method negative numbers can also be divisible, so we need positive check.

class Solution {
public boolean isPowerOfThree(int n) {
    return n > 0 && Math.pow(3,(int)(Math.log10(Integer.MAX_VALUE) / Math.log10(3))) % n == 0;
    }
}
Copy the code

8. String to Integer (atoi) so many limitations in this problem: 1.if you see spaces, skip them 2.if you meet non-digit chars first, return 0 3.if you meet ‘-‘/ ‘+’ they are legal 4.count the number and trans to int, if cross 32 bit signed int boundary, return Integer.MAX_VALUE or Integer.MIN_VALUE 5.if non-digit chars after number, skip

   class Solution { public int myAtoi(String str) { if(str == null || str.length() == 0) return 0; //leetcode won’t recognize str.isBlank() for some reason, damn int i = 0; for(; i < str.length(); i++){ if(str.charAt(i) ! = ‘ ‘) break; //skip all spaces } //check if outside the string if(i == str.length()) return 0; char ch = str.charAt(i); // in case satisfy one condition below and i++ then out of boundary int flag = 1; //1 as default, or assign in first if condition if(ch == ‘+’){ i++; } if(ch == ‘-‘){ flag = -1; i++; } if(i == str.length() || ! Character.isDigit(str.charAt(i))) return 0; //it must be numbers at index i int ans = 0; while(i < str.length() && Character.isDigit(str.charAt(i))){ int pop = Character.getNumericValue(str.charAt(i++)); if(ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7)){ return flag > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE; } // here’s the trick: 1. check overflow 2.if the absolute of number is bigger than Integer.MAX_VALUE, it must be smaller than Integer.MIN_VALUE since the boundary is [-2^31, 2^31-1] ans = ans * 10 + pop; } return flag * ans;

   }}

9. Implement strStr() “neelde in the hay”

use substring window

class Solution { public int strStr(String haystack, String needle) { if(needle.length() == 0) return 0; if(haystack.length() < needle.length()) return -1; int i = 0, j = needle.length(); while(j <= haystack.length()){ String sub = haystack.substring(i++,j++); if(needle.equals(sub)) return i-1; } return -1; }}Copy the code

38. Count and Say

my program is 7ms which is too slow, and the main difference between mine and a great one is the way to store the answer string.

class Solution { public static String countAndSay(int n) { if(n == 1) return "1"; String last = countAndSay(n-1); int counter = 1; char val = last.charAt(0); StringBuilder ans = new StringBuilder(); for(int i = 1; i < last.length(); i++){ if(last.charAt(i) == val){ counter++; } else{ ans.append(counter).append(val); counter = 1; val = last.charAt(i); } } if(counter > 0) ans.append(counter).append(val); return ans.toString(); }}Copy the code

14. Longest Common Prefix still utilize the great tool of StringBuilder.

    class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length == 0 || strs[0].length() == 0) return “”; StringBuilder s = new StringBuilder(); int i = 0; while(checker(strs,i)){ s.append(strs[0].charAt(i++)); } return s.toString(); } public boolean checker(String[] strs, int i){ for(int j = 0; j < strs.length; j++){ if(i >= strs[j].length() || (strs[j].charAt(i) != strs[0].charAt(i))) return false; } return true; } }

got time and space better than 100%

class Solution {
public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode first = head;
    ListNode second = head;
    while(n-- > 0){
        second = second.next;
    }
    if(second == null){
    //assume the length is m, and n can only be 
    //between 0-m-1, then second pointer out of listnode means delete target is the //first listnode
        head = head.next;
        return head;
    }
    while(second.next != null){
        //if second.next happens to be null
        //means delete target is the second one
        //if not, move both to the last element.
        first = first.next;
        second = second.next;
    }
    first.next = first.next.next;
    return head;
    
}
}
Copy the code

19. Remove Nth Node From End of List

    class Solution { public static ListNode removeNthFromEnd(ListNode head, int n) { ListNode first = head; ListNode second = head; while(n– > 0){ second = second.next; } if(second == null){ //assume the length is m, and n can only be //between 0-m-1, then second pointer out of listnode means delete target is the //first listnode head = head.next; return head; } while(second.next ! = null){ //if second.next happens to be null //means delete target is the second one //if not, move both to the last element. first = first.next; second = second.next; } first.next = first.next.next; return head;

    }}

20. Reverse Linked List

1. iterative

   class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while(curr != null){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } }

2. recursive

   class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode newhead = reverseList(head.next); head.next.next = head; head.next = null; return newhead; }}

234. *Palindrome Linked List this one is visually harder and more complicated than other problems of linked list, so the general idea is:

1.from the start(either head or your own list works) initialize two listnode

2.one is slow and another is twice faster, check if fast.next == null or fast.next.next == null, if so, then slow one reaches the middle

3.by the position of end and i to relocate j (i is slow one j is fast one)

4.reverse j -> end listnode

5.from end and start to compare equal, then return

6.necessary for each

class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode p = new ListNode(-1); p.next = head; ListNode i = p, j = p; while(j.next ! = null && j.next.next ! = null){ j = j.next.next; i = i.next; } //if odd length, mid is between i and i.next //if even, mid is i.next, then rejust j position j = (j.next == null) ? i.next : i.next.next; //then reverse use iterative way ListNode prev = null; while(j ! = null){ ListNode temp = j.next; j.next = prev; prev = j; j = temp; } //now reversed and j should be null, prev should be new head //so we use j j = prev; p = p.next; while(p ! = null && j ! = null){ if(p.val ! = j.val) return false; p = p.next; j = j.next; } return true; } } new method: class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; List<Integer> list = new ArrayList<>(); Stack<Integer> stack = new Stack<>(); while(head ! = null){ list.add(head.val); stack.push(head.val); head = head.next; } int i = 0; while(! stack.isEmpty()){ if(! stack.pop().equals(list.get(i))) return false; i++; } return true; }}Copy the code

141. Linked List Cycle

1. hashset for self defined data type

   public class Solution { public boolean hasCycle(ListNode head) { //it seems abstract to identify a ListNode //but we can have a HashSet with ListNode type Set s = new HashSet<>(); while(head ! = null) { if(s.contains(head)) return true; s.add(head); head = head.next; } return false; }}

2. two pointers //two runners with different speed running on a track, if the track is not circle //fast one will reach the end //if circle, eventually they will meet

   public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next == null) return false; ListNode f = head.next, s = head; while(f != s){ if(f.next == null || f.next.next == null) return false; f = f.next.next; s = s.next; } return true; } }

104. Maximum Depth of Binary Tree

class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; if(root.right == null && root.left == null) return 1; //otherwise the depth is the maximum of root.left and root.right plus one for root return Math.max( (root.right == null) ? 0 : 1 + maxDepth(root.right), (root.left == null) ? 0 : 1 + maxDepth(root.left)); }}Copy the code

98. Validate Binary Search Tree

1. recursion with recursive method, each tree root not only: 1.root.left.val < root.val and root.right.val > root.val but also: 2.root.val satisfies the upper and lower bound

   class Solution { public boolean isValidBST(TreeNode root) { return valid(root, null, null); } public boolean valid(TreeNode root, Integer upper, Integer lower){ //notice only Integer has null type, not int if(root == null) return true; int val = root.val; if((upper ! = null && val >= upper) || (lower ! = null && val <= lower)) return false; return (valid(root.left, val, lower) && valid(root.right, upper, val)); }}

*2) in-order in-order method for BST returns a ascending sequences, where each element is smaller thant next.

class Solution { public boolean isValidBST(TreeNode root) { Stack<TreeNode> s = new Stack(); double lastval = - Double.MAX_VALUE; //with some extreme case, and the range of double, this is the only feasible way while(! s.isEmpty() || root ! = null){ while(root ! = null){ s.push(root); root = root.left; } root = s.pop(); if(root.val <= lastval) return false; lastval = root.val; root = root.right; } return true; }}Copy the code

101. Symmetric Tree

1. recursive

   class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; return isMirror(root.left, root.right); } public boolean isMirror(TreeNode l, TreeNode r){ if(l == null && r == null) return true; if(l == null || r == null) return false; return (l.val == r.val) && isMirror(l.left, r.right) && isMirror(l.right, r.left); }}

2. iterative

   class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; Queue q = new LinkedList<>(); q.add(root.left); q.add(root.right); while(! q.isEmpty()){ TreeNode l = q.poll(); TreeNode r = q.poll(); if(l == null && r == null) continue; if(l == null || r == null || l.val ! = r.val) return false; q.add(l.left); q.add(r.right); q.add(l.right); q.add(r.left); } return true; }}

102. Binary Tree Level Order Traversal to understand the data structure is the key: the goal is to iterate each node and store in a list of a list, each sub-list in the list represents a level of the tree, and the vals in the sub-list are the nodes of this level.

notice that the length of the list is the number of levels, the length of sub-list is the nodes in this level

class Solution { public List<List<Integer>> tree = new ArrayList<List<Integer>>(); public void traversal(TreeNode node, int level){ if(tree.size() == level) tree.add(new ArrayList<Integer>()); //level starts from 0, if tree has same length as level, means //one more level of nodes needed tree.get(level).add(node.val); //tree.get() has a type of List, and add current value if(node.left ! = null) traversal(node.left, level + 1); if(node.right ! = null) traversal(node.right, level + 1); } public List<List<Integer>> levelOrder(TreeNode root) { if(root == null) return tree; traversal(root, 0); return tree; }}Copy the code

108. Convert Sorted Array to Binary Search Tree

class Solution { public TreeNode sortedArrayToBST(int[] nums) { return sortedArrayToBST(nums, 0, nums.length); } private TreeNode sortedArrayToBST(int[] nums, int start, int end){ if(start == end) return null; int mid = start + (end - start) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = sortedArrayToBST(nums, start, mid); root.right = sortedArrayToBST(nums, mid + 1, end); return root; }}Copy the code

88. Merge Sorted Array both beat 100% lol, this is a weird one since the structure of nums1.

    class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] nums = Arrays.copyOfRange(nums1, 0, m + 1); //notice this function copies from 0 – m, so m+1 needed int i = 0, j = 0, k = 0; while(i < m || j < n){ int n1 = (i == m) ? Integer.MAX_VALUE : nums[i]; int n2 = (j == n) ? Integer.MAX_VALUE : nums2[j]; if(n1 <= n2) nums1[k++] = nums[i++]; if(n1 > n2) nums1[k++] = nums2[j++]; }}}

89. First Bad Version notice that in binary search, mid = (start + end) / 2 could overflow, a better way: mid = start + (end – start) / 2

public class Solution extends VersionControl { public int firstBadVersion(int n) { int hi = n, lo = 1; while(lo <= hi){ int mid = lo + (hi - lo) / 2; if(isBadVersion(mid)) hi = mid - 1; else lo = mid + 1; } return lo; }}Copy the code

70. *Climbing Stairs not quite understand dynamic programming, just to get a quick review and code.

    class Solution { public int climbStairs(int n) { if(n == 1) return 1; int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for(int i = 3; i < n + 1; i++){ dp[i] = dp[i – 1] + dp[i – 2]; } return dp[n]; }}

71. Best Time to Buy and Sell Stock there’s only two cases for each prices in the array:

72. higher than the lowest price recorded

73. lower than it

for the first case, we calculate the profit from lowest price recorded to this price, if it generates more profit than the max profit recorded, replace it

for the second case, this mean lower prices occurs, but the profit could still be the same

class Solution { public int maxProfit(int[] prices) { int profit = 0; int lowestPrice = Integer.MAX_VALUE; for(int i = 0; i < prices.length; i++){ if(prices[i] < lowestPrice) lowestPrice = prices[i]; else if(profit < prices[i] - lowestPrice) profit = prices[i] - lowestPrice; } return profit; }}Copy the code

53. Maximum Subarray

1. brute force

   class Solution { public int maxSubArray(int[] nums) { int sum = 0; int ans = Integer.MIN_VALUE; for(int i = 0; i < nums.length; i++){ for(int j = 0; j <= i; j++){ sum = sumOfSub(nums, j, i); ans = Math.max(sum, ans); } } return ans; } private int sumOfSub(int[] nums, int start, int end){ int sum = 0; for(int i = start; i <= end; i++){ sum += nums[i]; } return sum; }}

2. dynamic programming

   class Solution { public int maxSubArray(int[] nums) { if(nums.length == 0) return 0; int ans = nums[0]; int sumBeforeCur = nums[0]; for(int i = 1; i < nums.length; i++){ sumBeforeCur = Math.max(sumBeforeCur + nums[i], nums[i]); ans = Math.max(ans, sumBeforeCur); } return ans; }}

198. House Robber 1)optimal structure for each state 2)state transfer equation

class Solution { public int rob(int[] nums) { int n = nums.length; if(n == 0) return 0; if(n == 1) return nums[0]; if(n == 2) return Math.max(nums[0], nums[1]); int first = nums[0]; int second = nums[1]; for(int i = 3; i <= n; i++){ int max = Math.max(first + nums[i - 1], second); first = second; second = max; } return second; }}Copy the code

268. Missing Number 1)my way: 1ms

class Solution { public int missingNumber(int[] nums) { int maxNum = Integer.MIN_VALUE; int realSum = 0; int expectSum = 0; for(int num:nums){ maxNum = Math.max(maxNum, num); realSum += num; } for(int i = 0; i <= maxNum; i++) expectSum += i; if(nums.length == maxNum) return expectSum - realSum; else return maxNum + 1; }}Copy the code

2)sorting: even worse… 7ms

class Solution { public int missingNumber(int[] nums) { Arrays.sort(nums); if(nums[nums.length-1] ! = nums.length) return nums.length; else if(nums[0] ! = 0) return 0; for(int i = 0; i < nums.length; i++){ if(nums[i] ! = i) return i; } return -1; }}Copy the code

3)hashset: even worse ??? 9ms

class Solution {
public int missingNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for(int num:nums) set.add(num);
    for(int i = 0; i < nums.length + 1; i++){
        if(!set.contains(i)) return i;
    }
    return -1;
   
}
}
Copy the code

4)gauss formula: with this hint, i realize my method 1) can be improved: 0ms

class Solution { public int missingNumber(int[] nums) { int n = nums.length; int expSum = (n + 1) * n / 2; int actSum = 0; for(int num:nums) actSum += num; return expSum - actSum; }}Copy the code

so the difference (main diff is the if statement in the end of method 1)) is because in my method, i use sum of 0 – num.length (also is maxValue seen) as expected sum, but in fact, for a n-length array, the expected sum is sum of 0 – (n + 1) (e.g. when given [0], the exp sum is 1)

public class Solution { private int[] oriarray; private int[] numsarray; public Solution(int[] nums){ this.oriarray = Arrays.copyOf(nums,nums.length); this.numsarray = nums; } public int[] reset(){ return oriarray; } public int[] shuffle(){ Random randomgen = new Random(); for(int i = 0; i < numsarray.length; i++){ int temp = numsarray[i]; int randomIndex = randomgen.nextInt(numsarray.length); numsarray[i] = numsarray[randomIndex]; numsarray[randomIndex] = temp; } return numsarray; }}Copy the code

155. Min Stack

class MinStack { /** initialize your data structure here. */ Stack<Integer> s; int min; public MinStack() { s = new Stack<>(); min = Integer.MAX_VALUE; } public void push(int x) { if(x <= min){//this must be leq,if it only is < // when x == min pushed into stack, when pop there will be two numbers // popped since min is the same as the x s.push(min); min = x; } s.push(x); } public void pop() { if(min == s.pop()) min = s.pop(); } public int top() { return s.peek(); } public int getMin() { return min; }}Copy the code

204. Count Primes

1. not optimal:

   class Solution { public int countPrimes(int n) { boolean[] isPrimes = new boolean[n+1]; Arrays.fill(isPrimes, true);

    for(int i = 2; i < n; i++){
        if(isPrimes[i]){
            for(int j = i * 2; j < n; j += i){
                isPrimes[j] = false;
            }
        }
    }
    int count = 0;
    for(int i = 2; i < n; i++){
        if(isPrimes[i]) count++;
    }
    return count;
   Copy the code

   }}

2. with improvement [Sieve of Eratosthenes]

   class Solution{ public int countPrimes(int n){ boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime, true); for(int i = 2; i < Math.sqrt(n); i++){ if(isPrime[i]){ for(int j = i * i; j < n; j += i) isPrime[j] = false; } } int ans = 0; for(int i = 2; i < n; i++) ans = isPrime[i] ? ans + 1 : ans; return ans; }}

13. Roman to Integer

    class Solution { public static int romanToInt(String s) { if(s == null || s.length() == 0) return 0; Map<Character, Integer> hm = new HashMap<>(); hm.put(‘I’, 1); hm.put(‘V’, 5); hm.put(‘X’, 10); hm.put(‘L’, 50); hm.put(‘C’, 100); hm.put(‘D’, 500); hm.put(‘M’, 1000); // int sum = 0, n = s.length(); for(int i = 0; i < n; i++){ int value = hm.get(s.charAt(i)); if(i != n – 1 && value < hm.get(s.charAt(i + 1))) sum -= value; else sum += value; } return sum; } }

14. Number of 1 Bits

another method uses no less memory, i dont wanna spend time on it.

public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int ans = 0; int mask = 1; / / 00000... 0001b for(int i = 0; i < 32; i++){ if((n & mask) ! = 0) ans++; //& bit operation, && boolean operation mask <<= 1; //left shift 1 bit } return ans; }}Copy the code

461. Hamming Distance

class Solution { public int hammingDistance(int x, int y) { int ans = (x ^ y); int mask = 1, counter = 0; for(int i = 0; i < 32; i++){ if((mask & ans) ! = 0) counter++; //notice (mask & ans) == 1 is wrong //since the result of "and" operation is 32 bit //and its not gonna be 1 mask <<= 1;  } return counter; }}Copy the code

190. Reverse Bits use bit operation to solve bit problems

public class Solution { // you need treat n as an unsigned value public static int reverseBits(int n) { int ans = 0; //use 0 to have 32 bit 0s for(int i = 0; i < 32; i++){ int cur = (n >> i); //cur to be i-th digit cur &= 1; //filter all other digits cur <<= (31 - i); //left shift 31 - i to reverse ans |= cur; // store the result; } return ans; }}Copy the code

118. Pascal’s Triangle

class Solution { public static List<List<Integer>> generate(int numRows){ List<List<Integer>> ans = new ArrayList<>(); if(numRows == 0) return ans; List<Integer> first = new ArrayList<>(); first.add(1); ans.add(first); if(numRows == 1) return ans; for(int i = 1; i < numRows; i++){ List<Integer> curRow = new ArrayList<>(); for(int j = 0; j < i + 1; j++){ if(j == 0 || j == i) curRow.add(1); else curRow.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j)); } ans.add(curRow); } return ans; }}Copy the code

############# so far this section is finished, then I am gonna review on those problems, it’s gonna be in a new article #############