20191003
153. Find Minimum in Rotated Sorted Array
Description
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
Solution
class Solution {
public int findMin(int[] nums) {
int start = 0;
int end = nums.length1;
int min = Integer.MAX_VALUE;
while(start<end){
int mid = (start+end)/2;
if(nums[mid]<nums[end]){
end = mid;
}else if(nums[mid]>nums[end]){
//need to add one otherwise will loop forever.
start = mid + 1;
}
}
return nums[start];
}
}
20191006
207. Course Schedule
Description
There are a total of n courses you have to take, labeled from 0 to n1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.
Solution
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import javax.imageio.ImageTranscoder;
class Solution {
//main idea is topological sort.
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] graph = new int[numCourses][numCourses];
int[] inDegree = new int[numCourses];
for(int i=0;i<prerequisites.length;i++){
int cur = prerequisites[i][0];
int pre = prerequisites[i][1];
//to prevent duplication.
if(graph[pre][cur]==0){
inDegree[cur]++;
}
graph[pre][cur] = 1;
}
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for(int i =0;i<numCourses;i++){
if(inDegree[i]==0){
queue.offer(i);
}
}
while (!queue.isEmpty()){
int course = queue.poll();
count++;
for(int i = 0;i<numCourses;i++){
if(graph[course][i]!=0){
if(inDegree[i]==0){
queue.offer(i);
}
}
}
}
return count == numCourses;
}
}
430. Flatten a Multilevel Doubly Linked List
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.
Flatten the list so that all the nodes appear in a singlelevel, doubly linked list. You are given the head of the first level of the list.
Example:
Input:
123456NULL

78910NULL

1112NULL
Output:
123781112910456NULL
SOlution
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
public Node() {}
public Node(int _val,Node _prev,Node _next,Node _child) {
val = _val;
prev = _prev;
next = _next;
child = _child;
}
};
*/
class Solution {
public Node flatten(Node head) {
if(head == null){
return head;
}
Node temp = head;
while(temp!=null){
if(temp.child == null){
temp = temp.next;
continue;
}
Node c = flatten(temp.child);
Node tempNx = temp.next;
temp.next = c;
c.prev = temp;
while(c.next!=null){
c = c.next;
}
c.next = tempNx;
if(tempNx!=null){
tempNx.prev = c;
}
temp.child = null;
temp = tempNx;
}
return head;
}
75. Sort Colors
Description
Given an array with n objects colored red, white or blue, sort them inplace so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
A rather straight forward solution is a twopass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s. Could you come up with a onepass algorithm using only constant space?
Solution
class Solution {
public void sortColors(int[] nums) {
int second = nums.length1, zero = 0;
for(int i = 0;i<=second;i++){
while(nums[i]==2 && i<second) swap(i,second,nums);
while(nums[i] == 0 && i>zero) swap(i,zero++,nums);
}
}
private void swap(int i, int j, int[] nums){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
36. Valid Sudoku
Description
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 19 without repetition. Each column must contain the digits 19 without repetition. Each of the 9 3x3 subboxes of the grid must contain the digits 19 without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
Example 1:
Input:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: true
Example 2:
Input:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8's in the top left 3x3 subbox, it is invalid.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules. The given board contain only digits 19 and the character ‘.’. The given board size is always 9x9.
Solution
class Solution {
public boolean isValidSudoku(char[][] board) {
HashSet<String> seen = new HashSet<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if(board[i][j]!='.'){
String temp = "(" + board[i][j] + ")";
if(seen.contains(i+temp)  seen.contains(temp + j)  seen.contains(i/3+temp+j/3))return false;
seen.add(i+temp) ;
seen.add(temp+j) ;
seen.add(i/3+temp+j/3);
}
}
}
return true;
}
}
442. Find All Duplicates in an Array
Description
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]
Solution
public List<Integer> findDuplicates(int[] nums) {
//use negative to store information.
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i])1;
if (nums[index] < 0){
res.add(Math.abs(index+1));
continue;
}
nums[index] = nums[index];
}
return res;
}