SDE答案

K Smallest In Unsorted Array

// min heap: offline算法
// Time: O((n+k)logn)
// Space: O(n)
public class Solution {
  public int[] kSmallest(int[] array, int k) {
    // Write your solution here
    if (array.length == 0 || k == 0) {
      return new int[0];
    }
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int i = 0; i < array.length; i++) {
      minHeap.offer(array[i]);
    }
    int[] result = new int[k];
    for (int j = 0; j < k; j++) {
      result[j] = minHeap.poll();
    }
    return result;
  }
}

// priorityqueue heapify O(n)建堆
public class Solution {
    public int[] kSmallest(int[] array, int k) {
        // Write your solution here
        if (array.length == 0 || k == 0) {
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            list.add(array[i]);
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(list);
        int[] result = new int[k];
        for (int j = 0; j < k; j++) {
            result[j] = minHeap.poll();
        }
        return result;
    }

}

// max heap: online算法
// Time: O((n+k)logk)
// Space: O(k)
public class Solution {
  public int[] kSmallest(int[] array, int k) {
    // Write your solution here
    if (array.length == 0 || k == 0) {
      return new int[0];
    }
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder());
    for (int i = 0; i < array.length; i++) {
      if (i < k) {
        maxHeap.offer(array[i]);
      } else if (array[i] < maxHeap.peek()) {
        maxHeap.poll();
        maxHeap.offer(array[i]);
      }
    }
    int[] result = new int[k];
    for (int j = k - 1; j >= 0; j--) {
      result[j] = maxHeap.poll();
    }
    return result;
  }
}

Rainbow Sort

public class Solution {
  public int[] rainbowSort(int[] array) {
    // Write your solution here
    int i = 0;
    int j = 0;
    int k = array.length - 1;
    while (j <= k) {
        if (array[j] == -1) {
          swap(array, i, j);
          i++;
          j++;
        } else if (array[j] == 0) {
          j++;
        } else if (array[j] == 1) {
          swap(array, j, k);
          k--;
        }
    }
    return array;
  }
  private void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }
}

Overview

Array and Sorting Algorithms

4. Selection Sort

// 4. Selection Sort
// selection sort an array a[] with size n.
public class Solution {
  public int[] solve(int[] array) {
    // Write your solution here
    if (array == null || array.length <= 1) {
      return array;
    }
    // outer loop: how many iterations
    for (int i = 0; i < array.length - 1; i++) {
      int minIndex = i;
      // inner loop: find the global min from the rest elements.
      for (int j = i; j < array.length; j++) {
        if (array[j] < array[minIndex]) {
          // record the index of the smallest element.
          minIndex = j;
        }
      }
      swap(array, i, minIndex);
    }
    return array;
  }

  private void swap(int[] array, int i, int minIndex) {
    int temp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = temp;
  }
}

279. Sort With 3 Stacks

// 279. Sort With 3 Stacks
public class Solution {
  public void sort(LinkedList<Integer> s1) {
    LinkedList<Integer> s2 = new LinkedList<Integer>();
    LinkedList<Integer> s3 = new LinkedList<Integer>();
    // Write your solution here.
    while (!s1.isEmpty() || !s2.isEmpty()) {
      int globalMin = Integer.MAX_VALUE;
      while (!s1.isEmpty()) {
        int temp = s1.pop();
        globalMin = temp < globalMin ? temp : globalMin;
        s2.push(temp);
      }
      while (!s2.isEmpty()) {
        int temp = s2.pop();
        if (temp != globalMin) {
          s1.push(temp);
        } else {
          s3.push(globalMin);
        }
      }
    }
    while (!s3.isEmpty()) {
      s1.push(s3.pop());
    }
    
  }
}

// time: O(n^2), space: O(n)

280. Sort With 2 Stacks

// 280. Sort With 2 Stacks
public class Solution {
  public void sort(LinkedList<Integer> s1) {
    LinkedList<Integer> s2 = new LinkedList<Integer>();
    // Write your solution here.
    int cnt = 0;
    while (!s1.isEmpty()) {
      int globalMin = Integer.MAX_VALUE;
      while (!s1.isEmpty()) {
        int temp = s1.pop();
        if (temp < globalMin) {
          globalMin = temp;
        }
        s2.push(temp);
      }
      while (!s2.isEmpty() && s2.peek() >= globalMin) {
        int temp = s2.pop();
        if (temp == globalMin) {
          cnt++;
        } else {
          s1.push(temp);
        }
      }
      while (cnt > 0) {
        s2.push(globalMin);
        cnt--;
      }
    }

    while  (!s2.isEmpty()) {
      s1.push(s2.pop());
    }
  }
}

// time: O(n^2), space: O(n)

9. Merge Sort

// 9. Merge Sort
public class Solution {
  public int[] mergeSort(int[] array) {
    // Write your solution here
    if (array == null || array.length <= 1) {
      return array;
    }
    int[] temp = new int[array.length];
    helper(array, temp, 0, array.length - 1);
    return array;
  }

  private void helper(int[] array, int[] temp, int left, int right) {
    if (left >= right) {
      return;
    }
    int mid = (left + right) / 2;
    helper(array, temp, left, mid);
    helper(array, temp, mid + 1, right);
    merge(array, temp, left, mid, right);
  }

  private void merge(int[] array, int[] temp, int left, int mid, int right) {
    int leftIndex = left;
    int rightIndex = mid + 1;
    int index = left;
    while (leftIndex <= mid && rightIndex <= right) {
      if (array[leftIndex] < array[rightIndex]) {
        temp[index++] = array[leftIndex++];
      } else {
        temp[index++] = array[rightIndex++];
      }
    }
    while (leftIndex <= mid) {
      temp[index++] = array[leftIndex++];
    }
    while (rightIndex <= right) {
      temp[index++] = array[rightIndex++];
    }

    // copy temp back to array
    // right is included
    for (index = left; index <= right; index++) {
      array[index] = temp[index];
    }
  }
}

29. Merge Sort Linked List

// 29. Merge Sort Linked List
/**
 * class ListNode {
 *   public int value;
 *   public ListNode next;
 *   public ListNode(int value) {
 *     this.value = value;
 *     next = null;
 *   }
 * }
 */
public class Solution {
  public ListNode mergeSort(ListNode head) {
    // Write your solution here
    if (head == null || head.next == null) {
      return head;
    }
    ListNode left = head;
    ListNode mid =  finMid(head);
    left = mergeSort(left);
    mid = mergeSort(mid);
    head = merge（left, mid);
    return head;
  }

  private ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;
  }

  private ListNode merge(ListNode left, ListNode mid) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (left != null && mid != null) {
      if (left.value < mid.value) {
        cur.next = left;
        left = left.next;
      } else {
        cur.next = right;
        right = right.next;
      }
      cur = cur.next;
    }
    cur.next = (left == null) ? right : left;
    return dummy.next;
  }
}

10. Quick Sort

// 10. Quick Sort
public class Solution {
  public int[] quickSort(int[] array) {
    if (array == null) {  // 1
      return array;
    }
    quickSort(array, 0, array.length - 1);
    return array;
  }

  private void quickSort(int[] array, int left, int right) {
    if (left >= right) {  // 1
      return;
    }

    int pivotPos = partition(array, left, right);
    quickSort(array, left, pivotPos - 1);
    quickSort(array, pivotPos + 1, right);
  }

  private int partition(int[] array, int left, int right) {
    int pivotIndex = pivotIndex(left, right);
    int pivot = array[pivotIndex];
    swap(array, pivotIndex, right);
    int leftBound = left;
    int rightBound = right - 1;
    while (leftBound <= rightBound) {
      if (array[leftBound] < pivot) {
        leftBound++;
      } else if (array[rightBound] >= pivot) {
        rightBound--;
      } else {
        swap(array, leftBound++, rightBound--); // 2
      }
    }
    swap(array, leftBound, right); // 3
    return leftBound;
  }

  private int pivotIndex(int left, int right) {
    return left + (int) (Math.random() * (right - left + 1));
  }
  
  private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
  }
}

10. Quick Sort (jiuzhang solution)

// 10. Quick Sort
// jiuzhang solution
public class Solution {
  public Random rand;
  public int[] quickSort(int[] array) {
    // Write your solution here
    rand = new Random();
    helper(array, 0, array.length - 1);
    return array;
  }

  private void helper(int[] array, int start, int end) {
    if (start >= end) {
      return;
    }

    // rand.nextInt(end - start + 1)
    // generate a random number in range [0,end - start + 1)
    // index in range [start, end]
    int index = rand.nextInt(end - start + 1) + start;
    // 1. pivot不选择array[start]或array[end]，选择中点也可，避免升序降序最坏情况
    // get value not index
    int pivot = array[index];
    int left = start;
    int right = end;

    // 2. left <= right not left < right
    // array = {1, 2} pivot = 1 会死循环，解决办法是在left == right时仍进入操作，排除掉一个元素
    while (left <= right) {
      // 3. array[left] < pivot not <= 避免数组中大部分重复元素导致的效率下降
      // array = {1, 1, 1, 1, 1, 1}
      while (left <= right && array[left] < pivot) {
        left++;
      }
      while (left <= right && array[right] > pivot) {
        right--;
      }
      if (left <= right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
        left++;
        right--;
      }
    }

    helper(array, start, right);
    helper(array, left, end);
  }
}

258. Move 0s To The End I

// 258. Move 0s To The End I
// The relative order of the elements in the original array does not need to be maintained.
// 两根指针，相向而行
public class Solution {
  public int[] moveZero(int[] array) {
    // Write your solution here
    if (array == null || array.length <= 1) {
      return array;
    }
    int left = 0, right = array.length - 1;
    while (left <= right) {
      if (array[left] != 0) {
        left++;
      } else if (array[right] == 0) {
        right--;
      } else {
        swap(array, left, right);
      }
    }
    return array;
  }

  private void swap(int[] array, int left, int right) {
		int temp = array[left];
		array[left] = array[right];
		array[right] = temp;
	}
}

// Time complexity is O(n).
// Space complexity is O(1).

259. Move 0s To The End II

// 259. Move 0s To The End II
// The relative order of the elements in the original array need to be maintained.
// 两根指针，同向而行
public class Solution {
  public int[] moveZero(int[] array) {
    // left指针左侧是非零元素
    // right指针遍历整个数组
    int left = 0, right = 0;
    while (right < array.length) {
      if (array[right] != 0) {
        swap(array, left, right);
        left++;
      }
      right++;
    }
    return array;
  }
  private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
  }
}

// Time complexity is O(n).
// Space complexity is O(1).

519. Move zeros

// 519. Move zeros
// 1. maintain order.
// 2. Minimize the total number of operations.
public class Solution {
  public int[] moveZeroes(int[] nums) {
    // Write your solution here
    if (nums == null || nums.length <= 1) {
      return nums;
    }
    int left = 0, right = 0;
    while (right < nums.length) {
      if (nums[right] != 0) {
        if (left != right) {
          nums[left] = nums[right];
        }
        left++;
      }
      right++;
    }
    
    for (int i = left; i < nums.length; i++) {
      if (nums[i] != 0) {
        nums[i] = 0;
      }
    }

    return nums;
  }
}

395. Remove Certain Characters

// 395. Remove Certain Characters
// Remove given characters in input string, the relative order of other characters should be remained. 
// Return the new string after deletion.
public class Solution {
  public String remove(String input, String t) {
    // Write your solution here
    Set<Character> set = new HashSet<>();
    for (int i = 0; i < t.length(); i++) {
      set.add(t.charAt(i));
    }
    char[] array = input.toCharArray();
    int slow = 0;
    for (int fast = 0; fast < array.length; fast++) {
      if (!set.contains(array[fast])) {
        array[slow++] = array[fast];
      }
    }
    return new String(Arrays.copyOf(array, slow));
  }
}

// Time complexity is O(m + n).
// Space complexitty is O(m + n).

281. Remove Spaces

// 281. Remove Spaces
// Given a string, remove all leading/trailing/duplicated empty spaces.
public class Solution {
  public String removeSpaces(String input) {
    // Write your solution here
    char[] array = input.toCharArray();
    int slow = 0;
    for (int fast = 0; fast < array.length; fast++) {
      if (array[fast] != ' ' || fast > 0 && array[fast - 1] != ' ') {
        array[slow++] = array[fast];
      }
    }
    if (slow - 1 >= 0 && array[slow - 1] == ' ') {
      slow--;
    }
    return new String(Arrays.copyOf(array, slow));
  }
}

// Time complexity is O(n).
// Space complexity is O(n).

549. Partition

// 549. Partition
class Solution {
	public void partition(int[] array, int pivotIndex) {
    int pivot = array[pivotIndex];
    int left = 0;
    int right = array.length - 1;
    swap(array, pivotIndex, right);
    while (left <= right) {
      if (array[left] < pivot) {
        left++;
      } else if (array[right] >= pivot) {
        right--;
      } else {
        swap(array, left++, right--);
      }
    }
    swap(array, left, array.length - 1);
  }

  private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
  }
}

Recursion I

12. Fibonacci Number

// 12. Fibonacci Number
// Calculating Fibonacci value
// Recursion solution
public class Solution {
  public long fibonacci(int K) {
    // Base case. (进入function之后首先check是否要停下来)
    if (K <= 0) {
      return 0;
    }
    if (K == 1) {
      return 1;
    }
    // Recursive rule
    return fibonacci(K-1) + fibonacci(K-2);
  }
}
// Time complexity is O(2^k).
// Space complexity is O(k).

// DP solution
public class Solution {
  public long fibonacci(int K) {
    // Write your solution here
    if (K <= 0) {
      return 0;
    }
    if (K == 1) {
      return 1;
    }
    long prev = 0, cur = 1, next = 1;
    for (int i = 2; i <= K; i++) {
      next = prev + cur;
      prev = cur;
      cur = next;
    }
    return next;
  }
}
// Time complexity is O(k).
// Space complexity is O(1).

538. Calculate a to the power of b (naive)

// 538. Calculate a to the power of b (naive)
public class Solution {
  public int power(int a, int b) {
    if (b == 0) {
        return 1;
    }
    int half_result = power(a, b/2);
    
    if (b % 2 == 0) {
        return half_result * half_result;
    } else {
        return half_result * half_result * a;
    }
  }
}

Binary Search

14. Classical Binary Search

public class Solution {
  public int binarySearch(int[] array, int target) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return -1;
    }
    int low = 0;
		int high = array.length - 1;
		while (low <= high) {
			int mid = low + (high - low) / 2;
			if (array[mid] == target) {
				return mid;
			} else if (array[mid] < target) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		return -1;
	}
}

15. First Occurrence

public class Solution {
  public int firstOccur(int[] array, int target) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return -1;
    }
    int start = 0, end = array.length - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] == target) {
        end = mid;
      } else if (array[mid] < target) {
        start = mid;
      } else {
        end = mid;
      }
    }

    if (array[start] == target) {
      return start;
    } else if (array[end] == target) {
      return end;
    } else {
      return -1;
    }
  }
}

16. Last Occurrence

public class Solution {
  public int lastOccur(int[] array, int target) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return -1;
    }
    int start = 0, end = array.length - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] == target) {
        start = mid;
      } else if (array[mid] < target) {
        start = mid;
      } else {
        end = mid;
      }
    }

    if (array[end] == target) {
      return end;
    } else if (array[start] == target) {
      return start;
    } else {
      return -1;
    }
  }
}

17. Closest In Sorted Array

public class Solution {
  public int closest(int[] array, int target) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return -1;
    }
    int start = 0, end = array.length - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] == target) {
        return mid;
      } else if (array[mid] < target) {
        start = mid;
      } else {
        end = mid;
      }
    }
    if (Math.abs(array[start] - target) > Math.abs(array[end] - target)) {
      return end;
    } else {
      return start;
    }
  }
}

19. K Closest In Sorted Array

public class Solution {
  public int[] kClosest(int[] array, int target, int k) {
    // Write your solution here
    int[] result = new int[k];
    int loc = locHelper(array, target);
    int start = loc - 1;
    int end = loc;
    for (int i = 0; i < k; i++) {
      if (start < 0) {
        result[i] = array[end++];
      } else if (end >= array.length) {
        result[i] = array[start--];
      } else {
        if (target - array[start] <= array[end] - target) {
          result[i] = array[start--];
        } else {
          result[i] = array[end++];
        }
      }
    }
    return result;
  }

  // find smallest number larger than target position
  private int locHelper(int[] array, int target) {
    int start = 0, end = array.length - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] == target) {
        start = mid;
      } else if (array[mid] < target) {
        start = mid;
      } else if (array[mid] > target) {
        end = mid;
      }
    }

    if (array[start] >= target) {
      return start;
    }
    if (array[end] >= target) {
      return end;
    }
    return array.length;

  }
}

636. Smallest Element Larger than Target

public class Solution {
  public int smallestElementLargerThanTarget(int[] array, int target) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return -1;
    }
    int start = 0, end = array.length - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] == target) {
        start = mid;
      } else if (array[mid] < target) {
        start = mid;
      } else if (array[mid] > target) {
        end = mid;
      }
    }

    if (array[start] > target) {
      return start;
    }
    if (array[end] > target) {
      return end;
    }
    return -1;
  }
}

20. Search In Unknown Sized Sorted Array

/*
*  interface Dictionary {
*    public Integer get(int index);
*  }
*/

// You do not need to implement the Dictionary interface.
// You can use it directly, the implementation is provided when testing your solution.
public class Solution {
  public int search(Dictionary dict, int target) {
    // Write your solution here
    int start = 0, end = 1;
    while (dict.get(end) != null && dict.get(end) < target) {
      start = end;
      end = 10 * end;
    }
    while (end >= start && dict.get(end) == null) {
      end--;
    }
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (dict.get(mid) == target) {
        return mid;
      }
      else if (dict.get(mid) < target) {
        start = mid + 1;
      }
      else {
        end = mid - 1;
      }
    }
    return -1;
  }
}

267. Search In Sorted Matrix I

// 267. Search In Sorted Matrix I
public class Solution {
  public int[] search(int[][] matrix, int target) {
    // Write your solution here
    int[] result = new int[]{-1, -1};
    if (matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] > target) {
      return result;
    }
    int row = findRow(matrix, target);
    int col = findCol(matrix[row], target);

    if (col == -1) {
      return result;
    } else {
      result[0] = row;
      result[1] = col;
      return result;
    }
  }

  // up = down + 1
  // make sure matrix[down][0] <= target
  private int findRow(int[][] matrix, int target) {
    int up = 0, down = matrix.length - 1;
    while (up <= down) {
      int mid = up + (down - up) / 2;
      if (matrix[mid][0] > target) {
        down = mid - 1;
      } else {
        up = mid + 1;
      }
    }
    return down;
  }

  private int findCol(int[] array, int target) {
    int left = 0, right = array.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (array[mid] == target) {
        return mid;
      } else if (array[mid] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }
}

267. Search In Sorted Matrix I (M2)

// 267. Search In Sorted Matrix I
public class Solution {
  public int[] search(int[][] matrix, int target) {
    // {}, {{}}
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return new int[] { -1, -1 };
		}
		int rows = matrix.length, cols = matrix[0].length;
		int left = 0, right = rows * cols - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int row = mid / cols, col = mid % cols;
			if (matrix[row][col] == target) {
				return new int[] { row, col };
			} else if (matrix[row][col] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return new int[] { -1, -1 };
	}
}

// Time complexity is O(log(n*m)).
// Space complexity is O(1).

Queue & Stack

31. Queue By Two Stacks

// 31. Queue By Two Stacks
public class Solution {

  private LinkedList<Integer> input;
  private LinkedList<Integer> output;

  public Solution() {
    // Write your solution here.
    input = new LinkedList<>();
    output = new LinkedList<>();
  }
  
  public Integer poll() {
    if (isEmpty()) {
      return null;
    }
    if (output.isEmpty()) {
      while (!input.isEmpty()) {
        output.offerFirst(input.pollFirst());
      }
    }
    return output.pollFirst();
  }
  
  public void offer(int element) {
    input.offerFirst(element);
  }
  
  public Integer peek() {
    if (isEmpty()) {
      return null;
    }
    if (output.isEmpty()) {
      while (!input.isEmpty()) {
        output.offerFirst(input.pollFirst());
      }
    }
    return output.peekFirst();
  }
  
  public int size() {
    return input.size() + output.size();
  }
  
  public boolean isEmpty() {
    return input.size() == 0 && output.size() == 0;
  }
}

32. Stack With min()

// 32. Stack With min()
public class Solution {
  private Deque<Integer> stack;
  private Deque<Integer> minStack;

  public Solution() {
    stack = new LinkedList<Integer>();
    minStack = new LinkedList<Integer>();
  }

  public int min() {
    if(minStack.isEmpty()) {
			return -1;
		}
    return minStack.peekFirst();
  }

  public void push(int value) {
    stack.offerFirst(value);
    // when value <= current min value in stack,
    // need to push the value to minStack.
    if (minStack.isEmpty() || value <= minStack.peekFirst()) {
      minStack.offerFirst(value);
    }
  }

  public int pop() {
    if(stack.isEmpty()) {
			return -1;
		}
    Integer result = stack.pollFirst();
    // when the popped value is the same as top value of minStack, the value
    // need to be popped from minStack as well.
    if (minStack.peekFirst().equals(result)) {
      minStack.pollFirst();
    }
    return result;
  }

  public int top() {
    if (stack.isEmpty()) {
      return -1;
    }
    return stack.peekFirst();
  }
}

32. Stack With min() (M2)

// 32. Stack With min()
class Wrapper {
    int min;
    int pos;
    public Wrapper(int min, int pos) {
      this.min = min;
      this.pos = pos;
    }
}

public class Solution {
  private Deque<Integer> stack;
  private Deque<Wrapper> minStack;

  public Solution() {
    stack = new LinkedList<Integer>();
    minStack = new LinkedList<Wrapper>();
  }

  public int min() {
    if(minStack.isEmpty()) {
			return -1;
		}
    return minStack.peekFirst().min;
  }

  public void push(int value) {
    stack.offerFirst(value);
    // when value <= current min value in stack,
    // need to push the value to minStack.
    if (minStack.isEmpty() || value < minStack.peekFirst().min){
      minStack.offerFirst(new Wrapper(value, stack.size() - 1));
    }
  }

  public int pop() {
    if(stack.isEmpty()) {
			return -1;
		}
    Integer result = stack.pollFirst();
    // when the popped value is the same as top value of minStack and the popped value's index is the same as top position of minStack, the wrapper object need to be popped from minStack as well.
    if (new Integer(minStack.peekFirst().min).equals(result) && stack.size() == minStack.peekFirst().pos) {
      minStack.pollFirst();
    }
    return result;
  }

  public int top() {
    if (stack.isEmpty()) {
      return -1;
    }
    return stack.peekFirst();
  }
}

8. Evaluate Reverse Polish Notation

public class Solution {
  public int evalRPN(String[] tokens) {
    // Write your solution here
    LinkedList<Integer> s = new LinkedList<>();
    for (String c : tokens) {
    //for (int i = 0; i < tokens.length; i++) {
      switch(c) {
        case "+":
          s.push(s.pop() + s.pop());
          break;
        case "-":
          s.push(-s.pop() + s.pop());
          break;
        case "*":
          s.push(s.pop() * s.pop());
          break;
        case "/":
          int b = s.pop();
          int a = s.pop();
          s.push(a / b);
          break;
        default:
          s.push(Integer.parseInt(c));
      }
    }
    return s.pop();
  }
}

LinkedList

36. Middle Node Of Linked List

public class Solution {
  public ListNode middleNode(ListNode head) {
    // Write your solution here
    if (head == null) {
      return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    } 
    return slow;
  }
}

37. Check If Linked List Has A Cycle

public class Solution {
  public boolean hasCycle(ListNode head) {
    // write your solution here
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) {
        return true;
      }
    }
    return false;
  }
}

38. Cycle Node In Linked List

题解：

• 使用双指针判断链表中是否有环，慢指针每次走一步，快指针每次走两步，若链表中有环，则两指针必定相遇。
• 假设环的长度为l，环上入口距离链表头距离为a，两指针第一次相遇处距离环入口为b，则另一段环的长度为c=l-b，由于快指针走过的距离是慢指针的两倍，则有a+l+b=2 * (a+b),又有l=b+c，可得a=c，故当判断有环时(slow==fast)时，移动头指针，同时移动慢指针，两指针相遇处即为环的入口。

public class Solution {
  public ListNode cycleNode(ListNode head) {
    // write your solution here
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) {
        while (head != slow) {
          head = head.next;
          slow = slow.next;
        }
        return head;
      }
    }
    return null;
  }
}

39. Insert In Sorted Linked List

// Good taste!
public class Solution {
  public ListNode insert(ListNode head, int value) {
    // Write your solution here
    ListNode dummy = new ListNode(0);
    ListNode node = new ListNode(value);
    dummy.next = head;
    ListNode prev = dummy;
    while (head != null && head.value < value) {
      prev = head;
      head = head.next;
    }
    node.next = prev.next;
    prev.next = node;
    return dummy.next;
  }
}

29. Merge Sort Linked List

public class Solution {
  public ListNode mergeSort(ListNode head) {
    // Write your solution here
    if (head == null || head.next == null) {
      return head;
    }
    ListNode left = head;
    ListNode mid = findMid(head);
    left = mergeSort(left);
    mid = mergeSort(mid);
    head = merge(left, mid);
    return head;
  }

  private ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;
    return mid;
  }

  private ListNode merge(ListNode left, ListNode right) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (left != null && right != null) {
      if (left.value < right.value) {
        cur.next = left;
        left = left.next;
      } else {
        cur.next = right;
        right = right.next;
      }
      cur = cur.next;
    }
    cur.next = (left == null) ? right : left;
    return dummy.next;
  }
}

\42. Partition Linked List

\41. ReOrder Linked List

Binary Tree & Binary Search Tree

Heap

Breadth-First Search (BFS-1):

Best First Search (BFS-2)

Depth First Search

62. All Subsets I

// 62. All Subsets I
// Given a set of characters represented by a String, return a list containing all subsets of the characters.
public class Solution {
  public List<String> subSets(String set) {
		List<String> result = new ArrayList<>();
		if (set == null) {
			return result;
		}
		if (set.length() == 0) {
			result.add("");
			return result;
		}
		StringBuilder sb = new StringBuilder();
		DFS(set, sb, result, 0);
		return result;
	}

	private void DFS(String set, StringBuilder sb, List<String> result, int level) {
		if (level == set.length()) {
			result.add(sb.toString());
			return;
		}
		sb.append(set.charAt(level));
		DFS(set, sb, result, level + 1);
		sb.deleteCharAt(sb.length() - 1);
		DFS(set, sb, result, level + 1);
	}
}

63. All Subsets II

// 63. All Subsets II
// String with duplicate character
public class Solution {
  public List<String> subSets(String set) {
    // Write your solution here.
    List<String> result = new ArrayList<>();
    if (set == null) {
      return result;
    }
    if (set.length() == 0) {
      result.add("");
      return result;
    }
    char[] array = set.toCharArray();
    Arrays.sort(array);
    StringBuilder sb = new StringBuilder();
    dfs(array, sb, result, 0);
    return result;
  }

  private void dfs(char[] array, StringBuilder sb, List<String> result, int level) {
    if (level == array.length) {
      result.add(sb.toString());
      return;
    }
    sb.append(array[level]);
    dfs(array, sb, result, level + 1);
    sb.deleteCharAt(sb.length() - 1);
    while (level < array.length - 1 && array[level] == array[level + 1]) {
      level++;
    }
    dfs(array, sb, result, level + 1);
  }
}

nowcoder subsets

// input: [1, 2, 3]
// output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
  public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    ArrayList<Integer> subset = new ArrayList<>();
    Arrays.sort(S);
    if (S == null || S.length == 0) {
      return result;
    }
    dfs(S, subset, result, 0);
    Collections.sort(result, new Comparator<ArrayList<Integer>>() {
      @Override
      public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
        int size1 = o1.size(), size2 = o2.size();
        if (size1 != size2)
          return size1 < size2 ? -1 : 1;
        else {
          for (int i = 0; i < o1.size(); i++) {
            if (o1.get(i) == o2.get(i))
              continue;
            else
              return o1.get(i) < o2.get(i) ? -1 : 1;
          }
        }
       return 0;
      }
 
    });
    return result;
  }
  private void dfs(int[] S, ArrayList<Integer> subset, ArrayList<ArrayList<Integer>> result, int level) {
    if (level == S.length) {
      result.add(new ArrayList(subset));
      return;
    }
    subset.add(S[level]);
    dfs(S, subset, result, level + 1);
    subset.remove(subset.size() - 1);
    dfs(S, subset, result, level + 1);
  }
}

64. All Permutations I

// 64. All Permutations I
public class Solution {
  public List<String> permutations(String input) {
    // Write your solution here
    List<String> result = new ArrayList<>();
    if (input == null) {
      return result;
    }
    if (input.length() == 0) {
      result.add("");
      return result;
    }
    char[] array = input.toCharArray();
    dfs(array, result, 0);
    return result;
  }

  private void dfs(char[] array, List<String> result, int level) {
    if (level == array.length) {
      result.add(new String(array));
      return;
    }
    for (int i = level; i < array.length; i++) {
      swap(array, i, level);
      dfs(array, result, level + 1);
      swap(array, i, level);
    }
  }

  private void swap(char[] array, int i, int j) {
		char temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}

65. All Permutations II

// 65. All Permutations II
public class Solution {
  public List<String> permutations(String input) {
    // Write your solution here
    List<String> result = new ArrayList<>();
    if (input == null) {
      return result;
    }
    if (input.length() == 0) {
      result.add("");
      return result;
    }
    char[] array = input.toCharArray();
    dfs(array, result, 0);
    return result;
  }

  private void dfs(char[] array, List<String> result, int level) {
    if (level == array.length) {
      result.add(new String(array));
      return;
    }
    Set<Character> set = new HashSet<>();
    for (int i = level; i < array.length; i++) {
      if (set.add(array[i])) {
        swap(array, i, level);
        dfs(array, result, level + 1);
        swap(array, i, level);
      }
    }
  }

  private void swap(char[] array, int i, int j) {
		char temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}

String I

String II

Recursion II

Dynamic Programming I

Dynamic Programming II

Probability, Sampling, Randomization, etc.

Recursion III