LeetCode刷题笔记 12月

Posted on By Guanzhou Song

Go to Leetcode

2019-12-04

334. Increasing Triplet Subsequence

Description

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

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

Input: [5,4,3,2,1]
Output: false

Solution

class Solution {
	// start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true.
    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE, large = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= small) {
            	// update small if n is smaller than both
                small = n;
            } else if (n <= large) {
            	// update big only if greater than small but smaller than big
                large = n;
            } else {
                return true;
            }
        }
        return false;
    }
}

274. H-Index

Description

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Solution

class Solution {

    public int hIndex(int[] citations) {
        int len = citations.length;
        int[] sum = new int[len + 1];
        for (int c : citations) {
            if (c < len) {
                sum[c]++;
            } else {
                sum[len]++;
            }
        }

        int count = 0;
        for (int i = len; i >= 0; i--) {
            count += sum[i];
            if (count >= i) {
                return i;
            }

        }
        return 0;
    }

991. Broken Calculator

Description

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or; Decrement: Subtract 1 from the number on the display. Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.
Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.
Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.
Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Solution

class Solution {
    /**
Intuition:
Considering how to change Y to X
Opertation 1: Y = Y / 2 if Y is even
Opertation 2: Y = Y + 1


Explanation:
Obviously,
If Y <= X, we won't do Y / 2 anymore.
We will increase Y until it equals to X

So before that, while Y > X, we'll keep reducing Y, until it's smaller than X.
If Y is odd, we can do only Y = Y + 1
If Y is even, if we plus 1 to Y, then Y is odd, we need to plus another 1.
And because (Y + 1 + 1) / 2 = (Y / 2) + 1, 3 operations are more than 2.
We always choose Y / 2 if Y is even.


Why it's right
Actually, what we do is:
If Y is even, Y = Y / 2
If Y is odd, Y = (Y + 1) / 2

We reduce Y with least possible operations, until it's smaller than X.

And we know that, we won't do Y + 1 twice in a row.
Becasue we will always end with an operation Y / 2.

2N times Y + 1 and once Y / 2 needs 2N + 1 operations.
Once Y / 2 first and N times Y + 1 will end up with same result, but needs only N + 1 operations.


Time complexity
We do Y/2 all the way until it's smaller than X,
time complexity is O(log(Y/X)).
    **/
    public int brokenCalc(int X, int Y) {
        int res = 0;
        while (Y > X) {
            Y = Y % 2 > 0 ? Y + 1 : Y / 2;
            res++;
        }
        return res+(X-Y);
    }
}

2019-12-05

840. Magic Squares In Grid

Description

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).


Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.
Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

class Solution {

/**
The intuition is brute force, don't need any tricky.
One thing to pay attention: A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9.
I just find many sumbmission ignoring this condition.

Here I just want share two observatons with this 1-9 condition:

Assume a magic square:
a1,a2,a3
a4,a5,a6
a7,a8,a9

a2 + a5 + a8 = 15
a4 + a5 + a6 = 15
a1 + a5 + a9 = 15
a3 + a5 + a7 = 15

Accumulate all, then we have:
sum(ai) + 3 * a5 = 60
3 * a5 = 15
a5 = 5

The center of magic square must be 5.

Another observation for other 8 numbers:
The even must be in the corner, and the odd must be on the edge.
And it must be in a order like "43816729" (clockwise or anticlockwise)

**/
  public int numMagicSquaresInside(int[][] grid) {
    int count = 0;
    for (int i = 1; i < grid.length - 1; i++) {
      for (int j = 1; j < grid[0].length - 1; j++) {
        if (grid[i][j] == 5) {
          count += isMagic(i, j, grid) ? 1 : 0;
        }
      }
    }
    return count;
  }


  private boolean isMagic(int i, int j, int[][] grid) {
    String s =
        "" + grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j + 1] + grid[i
            + 1][j + 1] + grid[i + 1][j] + grid[i + 1][j - 1] + grid[i][j - 1];
    return "4381672943816729".contains(s) || "9276183492761834".contains(s);
  }
}

819. Most Common Word

Description

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.


Example:

Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.
 

Note:

1 <= paragraph.length <= 1000.
0 <= banned.length <= 100.
1 <= banned[i].length <= 10.
The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
There are no hyphens or hyphenated words.
Words only consist of letters, never apostrophes or other punctuation symbols.

Solution

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {

  public String mostCommonWord(String paragraph, String[] banned) {
    // split paragraph
    // \w means non-word character.
    String[] words = paragraph.toLowerCase().split("\\W+");

    // add banned words to set
    Set<String> set = new HashSet<>(Arrays.asList(banned));

    // add paragraph words to hash map
    Map<String, Integer> map = new HashMap<>();
    for (String word : words) {
      if (!set.contains(word)) {
        map.put(word, map.getOrDefault(word, 0) + 1);
      }
    }

    // get the most frequent word
    int max = 0; // max frequency
    String res = "";
    for (Map.Entry<String,Integer> e : map.entrySet()) {
      if (e.getValue() > max) {
        max = e.getValue();
        res = e.getKey();
      }
    }

    return res;
  }
}

116. Populating Next Right Pointers in Each Node

Description

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node { int val; Node *left; Node *right; Node *next; }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:



Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
 

Constraints:

The number of nodes in the given tree is less than 4096.
-1000 <= node.val <= 1000

Solution

//(1) Loop through level 0 to level n - 2; (2) Traverse this level and connect children.
class Solution {
  public Node connect(Node root) {
    if(root == null){
      return null;
    }
    Node pre = root;
    Node cur = null;
    while(pre.left!=null){
      cur = pre;
      while(cur!=null){
        cur.left.next = cur.right;
        if(cur.next!=null){
          cur.right.next = cur.next.left;
        }
        cur = cur.next;
      }
      pre = pre.left;
    }
    return root;
  }
}

2019-12-14

366. Find Leaves of Binary Tree

Description

Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]

      1
     / \
    2   3
   / \     
  4   5    

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2          
 

2. Now removing the leaf [2] would result in this tree:

          1          
 

3. Now removing the leaf [1] would result in the empty tree:

          []         

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>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root,res);
        return res;
    }

    private int helper(TreeNode root, List<List<Integer>> res) {
        if (root == null) {
            return -1;
        }
        int level = Math.max(helper(root.left,res),helper(root.right,res))+1;
        if(res.size() == level){
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        root.left = root.right = null;
        return level;
    }
}

314. Binary Tree Vertical Order Traversal

Description

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

3 /\ / \ 9 20 /\ / \ 15 7

Output:

[ [9], [3,15], [20], [7] ] Examples 2:

Input: [3,9,8,4,0,1,7]

 3
/\    /  \    9   8   /\  /\  /  \/  \  4  01   7 

Output:

[ [4], [9], [3,0,1], [8], [7] ] Examples 3:

Input: {3,9,8,4,0,1,7,null,null,null,2,5} (0’s right child is 2 and 1’s left child is 5)

 3
/\    /  \    9   8   /\  /\  /  \/  \  4  01   7
/\    /  \    5   2

Output:

[ [4], [9,5], [3,0,1], [8,2], [7] ]

Solution

/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
 */
public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        //map's key is column, we assume the root column is zero, the left node will minus 1 ,and the right node will plus 1
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        //use a HashMap to store the TreeNode and the according cloumn value
        HashMap<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>();
        queue.offer(root);
        weight.put(root, 0);
        int min = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int w = weight.get(node);
            if (!map.containsKey(w)) {
                map.put(w, new ArrayList<>());
            }
            map.get(w).add(node.val);
            if (node.left != null) {
                queue.add(node.left);
                weight.put(node.left, w - 1);
            }
            if (node.right != null) {
                queue.add(node.right);
                weight.put(node.right, w + 1);
            }
            //update min ,min means the minimum column value, which is the left most node
            min = Math.min(min, w);
        }
        while (map.containsKey(min)) {
            res.add(map.get(min++));
        }
        return res;
    }
}

2019-12-16

785. Is Graph Bipartite?

Description

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
 

Note:

graph will have length in range [1, 100]. graph[i] will contain integers in range [0, graph.length - 1]. graph[i] will not contain i or duplicate values. The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

Solution

class Solution {

//BFS
    public boolean isBipartite(int[][] graph) {
        int len = graph.length;
        int[] colors = new int[len];
        for (int i = 0; i < len; i++) {
            if (colors[i] != 0) {
                continue;
            }
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            colors[i] = 1;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int next : graph[cur]) {
                    if (colors[next] == 0) {
                        queue.offer(next);
                        colors[next] = -colors[cur];
                    } else if (colors[next] != -colors[cur]) {
                        return false;
                    }
                }
            }
        }
        return true;

    }

}

855. Exam Room

Description

In an exam room, there are N seats in a single row, numbered 0, 1, 2, …, N-1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. (Also, if no one is in the room, then the student sits at seat number 0.)

Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room. It is guaranteed that any calls to ExamRoom.leave(p) have a student sitting in seat p.

Example 1:

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
Output: [null,0,9,4,2,null,5]
Explanation:
ExamRoom(10) -> null
seat() -> 0, no one is in the room, then the student sits at seat number 0.
seat() -> 9, the student sits at the last seat number 9.
seat() -> 4, the student sits at the last seat number 4.
seat() -> 2, the student sits at the last seat number 2.
leave(4) -> null
seat() -> 5, the student sits at the last seat number 5.
​​​​​​​

Note: 1 <= N <= 10^9 ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases. Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.

Solution

class ExamRoom {

    PriorityQueue<Interval> pq;
    int N;

    class Interval {

        int left, right, len;

        public Interval(int left, int right) {
            this.left = left;
            this.right = right;
            if (left == -1) {
                this.len = right;
            } else if (right == N) {
                this.len = N - 1 - left;
            } else {
                this.len = Math.abs(left - right) / 2;
            }

        }
    }

    public ExamRoom(int N) {
        this.pq = new PriorityQueue<Interval>((a, b) -> (a.len == b.len ? a.left - b.left : b.len - a.len));
        this.N = N;
        pq.offer(new Interval(-1, N));
    }

    // O(logn): poll top candidate, split into two new intervals
    public int seat() {
        int seat = 0;
        Interval interval = this.pq.poll();
        if (interval.left == -1) {
            seat = 0;
        } else if (interval.right == N) {
            seat = N - 1;
        } else {
            seat = (interval.left + interval.right) / 2;
        }

        pq.offer(new Interval(interval.left, seat));
        pq.offer(new Interval(seat, interval.right));
        return seat;
    }

    // O(n)Find head and tail based on p. Delete and merge two ends
    public void leave(int p) {
        Interval head = null, tail = null;
        List<Interval> list = new ArrayList<>(pq);
        for (Interval i : list) {
            if (i.left == p) {
                tail = i;
            }
            if (i.right == p) {
                head = i;
            }
            if (head != null && tail != null){
                break;
            }
        }
        pq.remove(head);
        pq.remove(tail);
        pq.offer(new Interval(head.left,tail.right));
    }
}