LeetCode刷题笔记 9月

Posted on By Guanzhou Song

Go to Leetcode

2019-09-02

155. Min Stack

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solution

class MinStack {

    Stack<Integer> stack;
    int min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        if(x <= min){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }
    
    public void pop() {
        int peek = stack.pop();
        //right now the min value must be the one before cur position
        //as the order theyt pushed into the stack.
        if(peek == min){
            min = stack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}

2019-09-03

127. Word Ladder

Description

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note:

Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

Solution

public class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<String>(wordList);
    if(!wordSet.contains(endWord)) return 0;
    Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();

    int len = 1;
    HashSet<String> visited = new HashSet<String>();
    
    beginSet.add(beginWord);
    endSet.add(endWord);
    while (!beginSet.isEmpty() && !endSet.isEmpty()) {
        //exchange two set to ensure beginset is smaller so it will run faster.
        if (beginSet.size() > endSet.size()) {
            Set<String> set = beginSet;
            beginSet = endSet;
            endSet = set;
        }

        Set<String> temp = new HashSet<String>();
        for (String word : beginSet) {
            char[] chs = word.toCharArray();

            for (int i = 0; i < chs.length; i++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    //main idea is to try every word and see if it's in the endSet.
                    char old = chs[i];
                    chs[i] = c;
                    String target = String.valueOf(chs);

                    //when it comes to end. endset is all word that can be reached.
                    if (endSet.contains(target)) {
                        return len + 1;
                    }

                    if (!visited.contains(target) && wordSet.contains(target)) {
                        temp.add(target);
                        visited.add(target);
                    }
                    chs[i] = old;
                }
            }
        }

        beginSet = temp;
        len++;
    }
    
    return 0;
}
}

2019-09-05

322. Coin Change

Description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

Note: You may assume that you have an infinite number of each kind of coin.

Solution

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1;i<=amount;i++){
            for(int coin : coins){
                //try each coin and see the min value of dp[i-coin]+1 or dp[i] itself.
                if(coin <= i && dp[i-coin]!=Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i-coin]+1,dp[i]);
                }
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}

986. Interval List Intersections

Description

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Solution

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        if(null == A || null == B || A.length==0 || B.length==0){
            return new int[][]{};
        }
        List<int[]> res = new ArrayList();
        //main idea is two pointer.
        int i = 0, j=0;
        while(i<A.length && j<B.length){
            int[] a = A[i];
            int[] b = B[j];
            
            //find interval.
            int startMax = Math.max(a[0],b[0]);
            int endMin = Math.min(a[1],b[1]);
            if(startMax<=endMin){
                res.add(new int[]{startMax,endMin});
            }
            
            //if the interval end is smaller, move on to the next.
            if(endMin == a[1])i++;
            if(endMin == b[1])j++;
            
        }
        int[][] res_b = new int[res.size()][2];
        
        return res.toArray(res_b);
    }
}

2019-09-08

221. Maximal Square

Description

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solution

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(null == matrix || matrix.length==0){
            return 0;
        }
        int yLength = matrix.length;
        int xLength = matrix[0].length;
        int[][] dp = new int[yLength+1][xLength+1];
        int max = 0;
        for(int i = 1;i<=yLength;i++){
            for(int j = 1;j<=xLength;j++){
                if(matrix[i-1][j-1]=='1'){
                    //dp[i][j] is limited by its neighbor.
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max * max;
    }
}

2019-09-11

6. ZigZag Conversion

Description

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N A P L S I I G Y I R And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

Solution

//Using slot.
class Solution {
    public String convert(String s, int numRows) {
    
        if(numRows==1){
            return s;
        }
        int len = s.length();
        int i = 0;
        int index = 0;
        boolean reverse = true;
        StringBuilder[] sb = new StringBuilder[numRows];
        for(int j = 0;j<numRows;j++){
            sb[j] = new StringBuilder();
        }
        while(i<len){
            sb[index].append(s.charAt(i));
            if(index==numRows-1){
                index--;
                reverse = !reverse;
            }else if(index==0){
                index++;
                reverse = !reverse;
            }else{
                if(reverse)index--;
                else index++;
            }
            i++;
        }
        StringBuilder sbRes = new StringBuilder();
        for(StringBuilder _sb:sb){
            sbRes.append(_sb.toString());
        }
        return sbRes.toString();
    }
    
    
}

364. Nested List Weight Sum II

Description

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8 
Explanation: Four 1's at depth 1, one 2 at depth 2.
Example 2:

Input: [1,[4,[6]]]
Output: 17 
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.

Solution

class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int weighted = 0, unweighted = 0;
        while(!nestedList.isEmpty()){
            List<NestedInteger> temp = new LinkedList<>();
            for(NestedInteger n:nestedList){
                if(n.isInteger()){
                    unweighted += n.getInteger();
                }else{
                    temp.addAll(n.getList());
                }
            }
            nestedList = temp;
            weighted += unweighted;
        }
        return weighted;
    }
}

412. Fizz Buzz

Description

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

Solution

//if using stringbuilder will be slower.
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res = new ArrayList();
        int fizz =0,buzz=0;
        for(int i = 1;i<=n;i++){
            StringBuilder sb = new StringBuilder();
            fizz++;
            buzz++;
            if(fizz == 3 && buzz == 5){
                res.add("FizzBuzz");
                fizz = 0;
                buzz = 0;
                continue;
            }else if(fizz ==3){
                res.add("Fizz");
                fizz = 0;
                continue;
            }else if(buzz == 5){
                res.add("Buzz");
                buzz = 0;
                continue;
            }
            res.add(String.valueOf(i));
        }
        return res;
    }
}

103. Binary Tree Zigzag Level Order Traversal

Description

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList();
        if(null == root){
            return res;
        }
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        boolean rev = false;
        while(!q.isEmpty()){
            Queue<TreeNode> temp = new LinkedList<TreeNode>();
            Deque<Integer> ans = new LinkedList();
            rev = !rev;
            while(!q.isEmpty()){
                TreeNode cur = q.poll();
                if(rev){
                    ans.offerLast(cur.val);
                }else{
                    ans.offerFirst(cur.val);
                }
                if(null!=cur.left){
                    temp.offer(cur.left);
                }
                if(null!=cur.right){
                    temp.offer(cur.right);
                }
            }
            q = temp;
            res.add(new LinkedList(ans));
        }
        return res;
    }
}

2019-09-17

98. Validate Binary Search Tree

Description

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.

Example 1:

2    / \   1   3

Input: [2,1,3] Output: true Example 2:

5    / \   1   4
 / \
3   6

Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node’s value is 5 but its right child’s value is 4.

Solution

//basiclly is a inorder traversal and compare.
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        TreeNode pre = null;
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(pre!=null && pre.val >= root.val) return false;
            pre = root;
            root = root.right;
        }
        return true;
    }
}


class Solution {
    
    TreeNode prev;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!isValidBST(root.left)){
            return false;
        }
        if(prev != null && prev.val >= root.val){
            return false;
        }
        prev = root;
        if(!isValidBST(root.right)){
            return false;
        }
        return true;
        
    }
}

547. Friend Circles

Description

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:
Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.
Example 2:
Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.

Solution

class Solution {
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        for(int i = 0;i<M.length;i++){
            //once go through a circle, all people will set as visited.
            if(visited[i]==0){
                dfs(M,visited,i);
                count++;
            }
        }
        return count;
    }
    
    //check circle and set all people in this circle to visited.
    private void dfs(int[][] M, int[] visited, int i){
        for(int j = 0;j<M.length;j++){
            if(M[i][j] == 1 && visited[j] == 0){
                visited[j] = 1;
                dfs(M,visited,j);
            }
        }
    }
}

43. Multiply Strings

Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = “2”, num2 = “3” Output: “6” Example 2:

Input: num1 = “123”, num2 = “456” Output: “56088” Note:

The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] pos = new int[m+n];
        
        for(int  i = m-1;i>=0;i--){
            for(int j = n-1; j>=0;j--){
                int mul = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
                int p1 = i+j;
                int p2 = i+j+1;
                int sum = mul + pos[p2];
                
                pos[p1] += sum /10;
                pos[p2] = sum % 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int p: pos){
            if(!(sb.length()==0 && p == 0)){
                sb.append(p);
            }
        }
        return sb.length()==0?"0":sb.toString();
    }
}