LeetCode刷题笔记 10月

Posted on By Guanzhou Song

Go to Leetcode

2019-10-03

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.length-1;
        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];
    }
}

2019-10-06

207. Course Schedule

Description

There are a total of n courses you have to take, labeled from 0 to n-1.

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 single-level, doubly linked list. You are given the head of the first level of the list.


Example:

Input:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

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 in-place 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 two-pass 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 one-pass algorithm using only constant space?

Solution

class Solution {
    public void sortColors(int[] nums) {
        int second = nums.length-1, 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 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 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 sub-box, 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 1-9 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;
}