LeetCode习题集(Keep updating)

leetCode

Posted by Bill on November 13, 2018

LeetCode习题集

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true
Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false
Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if((p == null && q != null) || (p != null && q ==null))
            return false;
        if(p.val == q.val){
            if(isNode(p) && isNode(q)){
                return true;
            }
            else if((p.left == null && q.left != null) ||
                    (p.left != null&& q.left ==null) ||
                    (p.right == null && p.right != null) ||
                    (p.right != null && p.right == null)
            ){
                return false;
            }
            else{
                return isSameTree(p.left,q.left) &&
                        isSameTree(p.right,q.right);
            }
        }
        else{
            return false;
        }
    }

    private boolean isNode(TreeNode node){
        if(node.left == null && node.right == null){
            return true;
        }
        else return false;
    }
}

Approach 1: Recursion Intuition

The simplest strategy here is to use recursion. Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public boolean isSameTree(TreeNode p, TreeNode q) {
    // p and q are both null
    if (p == null && q == null) return true;
    // one of p and q is null
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return isSameTree(p.right, q.right) &&
            isSameTree(p.left, q.left);
  }
}

Complexity Analysis

  • Time complexity : \mathcal{O}(N)O(N), where N is a number of nodes in the tree, since one visits each node exactly once.

  • Space complexity : \mathcal{O}(\log(N))O(log(N)) in the best case of completely balanced tree and \mathcal{O}(N)O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.


Approach 2: Iteration Intuition

Start from the root and then at each iteration pop the current node out of the deque. Then do the same checks as in the approach 1 :

p and p are not None,

p.val is equal to q.val,

and if checks are OK, push the child nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
  public boolean check(TreeNode p, TreeNode q) {
    // p and q are null
    if (p == null && q == null) return true;
    // one of p and q is null
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return true;
  }

  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (!check(p, q)) return false;

    // init deques
    ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
    ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();
    deqP.addLast(p);
    deqQ.addLast(q);

    while (!deqP.isEmpty()) {
      p = deqP.removeFirst();
      q = deqQ.removeFirst();

      if (!check(p, q)) return false;
      if (p != null) {
        // in Java nulls are not allowed in Deque
        if (!check(p.left, q.left)) return false;
        if (p.left != null) {
          deqP.addLast(p.left);
          deqQ.addLast(q.left);
        }
        if (!check(p.right, q.right)) return false;
        if (p.right != null) {
          deqP.addLast(p.right);
          deqQ.addLast(q.right);
        }
      }
    }
    return true;
  }
}

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

1
2
3
4
5
6
7
8
9
10
11
Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private LinkedList<Integer> myLinkedList = new LinkedList<>();

    public TreeNode convertBST(TreeNode root) {
        if(root == null){
            return null;
        }
        getGreaterValList(root);
        Queue<TreeNode> myQueue = new LinkedList<>();
        myQueue.add(root);
        while(!myQueue.isEmpty()){
            TreeNode tmp = myQueue.poll();
            int sum = 0;
            for(int val : myLinkedList){
                if(tmp.val < val){
                    sum += val;
                }
            }
            tmp.val += sum;
            if(tmp.left != null){
                myQueue.add(tmp.left);
            }
            if(tmp.right != null){
                myQueue.add(tmp.right);
            }
        }
        return root;
    }

    void getGreaterValList(TreeNode root){
        if(root != null){
            myLinkedList.add(root.val);
        }
        if(root.left != null){
            getGreaterValList(root.left);
        }
        if(root.right != null){
            getGreaterValList(root.right);
        }
    }
}

Approach #1 Recursion [Accepted] Intuition

One way to perform a reverse in-order traversal is via recursion. By using the call stack to return to previous nodes, we can easily visit the nodes in reverse order.

Algorithm

For the recursive approach, we maintain some minor “global” state so each recursive call can access and modify the current total sum. Essentially, we ensure that the current node exists, recurse on the right subtree, visit the current node by updating its value and the total sum, and finally recurse on the left subtree. If we know that recursing on root.right properly updates the right subtree and that recursing on root.left properly updates the left subtree, then we are guaranteed to update all nodes with larger values before the current node and all nodes with smaller values after.

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

1
2
3
4
5
6
7
8
Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void reverseString(char[] s) {
		int head = 0;
		int tail = s.length - 1;
		while(head < tail){
			char tmp = s[head];
			s[head] = s[tail];
			s[tail] = tmp;
			head++;
			tail--;
		}
	}
}

429. N-ary Tree Level Order Traversal

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

[ [1], [3,2,4], [5,6] ]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> myList = new LinkedList<>();
        Queue<Node> myQueue = new LinkedList<>();
        if(root == null) return myList;
        myQueue.add(root);
        int currentSize = 1;
        int nextSize = 0;
        List<Integer> tmpList = new LinkedList<>();
        while(!myQueue.isEmpty()){
            Node tmp = myQueue.poll();
            tmpList.add(tmp.val);

            if(tmp.children != null){
                for(int i = 0; i < tmp.children.size();i++){
                    myQueue.add(tmp.children.get(i));
                }
                nextSize += tmp.children.size();
            }
            currentSize = currentSize - 1;
            if(currentSize == 0){
                myList.add(tmpList);
                tmpList = new LinkedList<>();
                currentSize = nextSize;
                nextSize = 0;
            }

        }
        return myList;
    }
}

476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation.

1
2
3
4
5
6
7
8
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findComplement(int num) {
        int divisor = num;
        Stack<Integer>mStack = new Stack<>();
        while(divisor != 1){
            int remainder = divisor % 2;
            divisor /= 2;
            remainder = remainder == 1 ? 0 : 1;
            mStack.push(remainder);
        }
        mStack.push(0);
        int sum = 0;
        while(!mStack.isEmpty()){
            sum = sum * 2 + mStack.pop();
        }


        return sum;
    }
}

500. Keyboard Row

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

1
2
3
4
Example:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Solutioni:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
    private Set<Character> firstSet = new HashSet<>();
    private Set<Character> secondSet = new HashSet<>();
    private Set<Character> thirdSet = new HashSet<>();

    String firstRow = "qwertyuiop";
    String secondRow = "asdfghjkl";
    String thirdRow = "zxcvbnm";

    public void initSets(){
        for (char mChar:firstRow.toCharArray()) {
            firstSet.add(mChar);
            firstSet.add(Character.toUpperCase(mChar));
        }

        for (char mChar:secondRow.toCharArray()) {
            secondSet.add(mChar);
            secondSet.add(Character.toUpperCase(mChar));
        }

        for (char mChar:thirdRow.toCharArray()) {
            thirdSet.add(mChar);
            thirdSet.add(Character.toUpperCase(mChar));
        }
    }

    Solution(){
        initSets();
    }

    public String[] findWords(String[] words) {
        List<String> ret = new LinkedList<>();
        for(String str: words){
            int []whichRows = {0,0,0};
            for(char mChar:str.toCharArray()){
                if(isFromFirstSets(mChar)){
                    whichRows[0] = 1;
                }
                else if(isFromSecondSets(mChar)){
                    whichRows[1] = 1;
                }
                else if (isFromThirdSets(mChar)){
                    whichRows[2] = 1;
                }
            }
            int sum = 0;
            for(int ele:whichRows){
               sum += ele;
            }
            if(sum == 1){
                ret.add(str);
            }
        }
        String []retStr = new String[ret.size()];
        ret.toArray(retStr);
        return retStr;
    }

    private Boolean isFromFirstSets(char mChar){
        return firstSet.contains(mChar);
    }

    private Boolean isFromSecondSets(char mChar){
        return secondSet.contains(mChar);
    }

    private Boolean isFromThirdSets(char mChar){
        return thirdSet.contains(mChar);
    }
}

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

1
2
3
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Eample 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Solution:

recursion

1
2
3
4
5
6
7
8
9
public int fib(int N) {
        if(N == 0){
            return 0;
        }
        else if(N == 1){
            return 1;
        }
        return fib(N-1) + fib(N-2);
    }

iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int fib(int N) {
        int fib_0 = 0;
        int fib_1 = 1;
        int ret = 0;
        if(N == 0) return fib_0;
        if(N == 1) return fib_1;
        for(int i = 1; i < N;i++){
            //fib(N) = fib(N-1) + fib(N-2)
            int left = fib_0;
            int right = fib_1;
            ret = left + right;
            fib_0 = right;
            fib_1 = ret;
        }
        return ret;
    }

538. Convert BST to Greater Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

Complexity Analysis

  • Time complexity : O(n)O(n)

A binary tree has no cycles by definition, so convertBST gets called on each node no more than once. Other than the recursive calls, convertBST does a constant amount of work, so a linear number of calls to convertBST will run in linear time.

  • Space complexity : O(n)O(n)

Using the prior assertion that convertBST is called a linear number of times, we can also show that the entire algorithm has linear space complexity. Consider the worst case, a tree with only right (or only left) subtrees. The call stack will grow until the end of the longest path is reached, which in this case includes all nn nodes.

Approach #2 Iteration with a Stack [Accepted] Intuition

If we don’t want to use recursion, we can also perform a reverse in-order traversal via iteration and a literal stack to emulate the call stack.

Algorithm

One way to describe the iterative stack method is in terms of the intuitive recursive solution. First, we initialize an empty stack and set the current node to the root. Then, so long as there are unvisited nodes in the stack or node does not point to null, we push all of the nodes along the path to the rightmost leaf onto the stack. This is equivalent to always processing the right subtree first in the recursive solution, and is crucial for the guarantee of visiting nodes in order of decreasing value. Next, we visit the node on the top of our stack, and consider its left subtree. This is just like visiting the current node before recursing on the left subtree in the recursive solution. Eventually, our stack is empty and node points to the left null child of the tree’s minimum value node, so the loop terminates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public TreeNode convertBST(TreeNode root) {
        int sum = 0;
        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (!stack.isEmpty() || node != null) {
            /* push all nodes up to (and including) this subtree's maximum on
             * the stack. */
            while (node != null) {
                stack.add(node);
                node = node.right;
            }

            node = stack.pop();
            sum += node.val;
            node.val = sum;

            /* all nodes with values between the current and its parent lie in
             * the left subtree. */
            node = node.left;
        }

        return root;
    }
}

Approach #3 Reverse Morris In-order Traversal [Accepted] Intuition

There is a clever way to perform an in-order traversal using only linear time and constant space, first described by J. H. Morris in his 1979 paper “Traversing Binary Trees Simply and Cheaply”. In general, the recursive and iterative stack methods sacrifice linear space for the ability to return to a node after visiting its left subtree. The Morris traversal instead exploits the unused null pointer(s) of the tree’s leaves to create a temporary link out of the left subtree, allowing the traversal to be performed using only constant additional memory. To apply it to this problem, we can simply swap all “left” and “right” references, which will reverse the traversal.

Algorithm

First, we initialize node, which points to the root. Then, until node points to null (specifically, the left null of the tree’s minimum-value node), we repeat the following. First, consider whether the current node has a right subtree. If it does not have a right subtree, then there is no unvisited node with a greater value, so we can visit this node and move into the left subtree. If it does have a right subtree, then there is at least one unvisited node with a greater value, and thus we must visit first go to the right subtree. To do so, we obtain a reference to the in-order successor (the smallest-value node larger than the current) via our helper function getSuccessor. This successor node is the node that must be visited immediately before the current node, so it by definition has a null left pointer (otherwise it would not be the successor). Therefore, when we first find a node’s successor, we temporarily link it (via its left pointer) to the node and proceed to the node’s right subtree. Then, when we finish visiting the right subtree, the leftmost left pointer in it will be our temporary link that we can use to escape the subtree. After following this link, we have returned to the original node that we previously passed through, but did not visit. This time, when we find that the successor’s left pointer loops back to the current node, we know that we have visited the entire right subtree, so we can now erase the temporary link and move into the left subtree.

The figure above shows an example of the modified tree during a reverse Morris traversal. Left pointers are illustrated in blue and right pointers in red. Dashed edges indicate temporary links generated at some point during the algorithm (which will be erased before it terminates). Notice that blue edges can be dashed, as we always exploit the empty left pointer of successor nodes. Additionally, notice that every node with a right subtree has a link from its in-order successor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    /* Get the node with the smallest value greater than this one. */
    private TreeNode getSuccessor(TreeNode node) {
        TreeNode succ = node.right;
        while (succ.left != null && succ.left != node) {
            succ = succ.left;
        }
        return succ;
    }

    public TreeNode convertBST(TreeNode root) {
        int sum = 0;
        TreeNode node = root;

        while (node != null) {
            /*
             * If there is no right subtree, then we can visit this node and
             * continue traversing left.
             */
            if (node.right == null) {
                sum += node.val;
                node.val = sum;
                node = node.left;
            }
            /*
             * If there is a right subtree, then there is at least one node that
             * has a greater value than the current one. therefore, we must
             * traverse that subtree first.
             */
            else {
                TreeNode succ = getSuccessor(node);
                /*
                 * If the left subtree is null, then we have never been here before.
                 */
                if (succ.left == null) {
                    succ.left = node;
                    node = node.right;
                }
                /*
                 * If there is a left subtree, it is a link that we created on a
                 * previous pass, so we should unlink it and visit this node.
                 */
                else {
                    succ.left = null;
                    sum += node.val;
                    node.val = sum;
                    node = node.left;
                }
            }
        }

        return root;
    }
}

543. Diameter of Binary Tree

iven a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

1
2
3
4
5
6
7
8
Example:
Given a binary tree
          1
         / \
        2   3
       / \
      4   5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        int maxLeft = diameterOfBinaryTree(root.left);
        int maxRight = diameterOfBinaryTree(root.right);
        int max = maxLeft > maxRight ? maxLeft : maxRight;

        int diameter = getDepth(root.left) + getDepth(root.right);
        if(max < diameter){
            return diameter;
        }
        else{
            return max;
        }
    }

    private int getDepth(TreeNode root){
        if(root != null){
            return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
        }
        return 0;
    }
}

Approach #1: Depth-First Search [Accepted] Intuition

Any path can be written as two arrows (in different directions) from some node, where an arrow is a path that starts at some node and only travels down to child nodes.

If we knew the maximum length arrows L, R for each child, then the best path touches L + R + 1 nodes.

Algorithm

Let’s calculate the depth of a node in the usual way: max(depth of node.left, depth of node.right) + 1. While we do, a path “through” this node uses 1 + (depth of node.left) + (depth of node.right) nodes. Let’s search each node and remember the highest number of nodes used in some path. The desired length is 1 minus this number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) return 0;
        int L = depth(node.left);
        int R = depth(node.right);
        ans = Math.max(ans, L+R+1);
        return Math.max(L, R) + 1;
    }
}

Complexity Analysis

  • Time Complexity: O(N)O(N). We visit every node once.

  • Space Complexity: O(N)O(N), the size of our implicit call stack during our depth-first search.

589. N-ary Tree Preorder Traversal

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

//Reverse Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
public class Solution {
    List<Integer> myList;
    Solution(){
       myList = new LinkedList<>();
    }

    public List<Integer> preorder(Node root) {
        reversePreorder(root);
        return myList;
    }

    private void reversePreorder(Node root){
        if(root == null) return;
        if(root.children == null){
            myList.add(root.val);
        }
        else{
            myList.add(root.val);
            for(Node ele: root.children){
                reversePreorder(ele);
            }
        }
    }
}

//Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> preorder(Node root) {
        Deque<Node> myDequeue = new LinkedList<>();
        List<Integer> myList = new LinkedList<>();
        if(root == null) return myList;
        myDequeue.addFirst(root);
        while(!myDequeue.isEmpty()){
            Node tmp = myDequeue.pollFirst();
            myList.add(tmp.val);
            if(tmp.children != null){
                Collections.reverse(tmp.children);
                for(Node ele: tmp.children){
                    myDequeue.addFirst(ele);
                }
            }
        }
        return myList;
    }
}

590. N-ary Tree Postorder Traversal

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its postorder traversal as: [5,6,3,2,4,1].

Note:

Recursive solution is trivial, could you do it iteratively?

//iterator Solution:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
 public List<Integer> postorder(Node root) {
        List<Integer> myList = new LinkedList<>();
        Stack<Node> myStack = new Stack<>();
        if(root == null) return myList;
        myStack.add(root);
        while(!myStack.isEmpty()){
            Node tmp = myStack.pop();
            myList.add(tmp.val);
            if(tmp.children == null) continue;
            for(Node node: tmp.children){
                myStack.add(node);
            }
        }
        Collections.reverse(myList);
        return myList;
    }
}

//recursive Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public List<Integer> myList;
    public List<Integer> postorder(Node root) {
        myList = new LinkedList<>();
        postReverse(root);
        return myList;
    }
    private void postReverse(Node root){
        if(root == null) return;
        if(root.children == null){
            myList.add(root.val);
        }
        else{
            for(Node node:root.children){
                postReverse(node);
            }
            myList.add(root.val);
        }
    }
}

654. Maximum Binary Tree

Description

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1
2
3
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    /
     2  0
       \
        1

Note:

  • The size of the given array will be in the range [1,1000].

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
         if(nums.length == 0){
            return null;
        }
        int maxIndex = 0;
        int maxVal = nums[0];
        for(int index = 0;index < nums.length; index++){
            if(nums[index] > maxVal){
                maxVal = nums[index];
                maxIndex = index;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        if(maxIndex - 1 >= 0){
            root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums,0,maxIndex));
        }
        if(maxIndex + 1 <= nums.length - 1){
            root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums,maxIndex + 1,nums.length));
        }
        return root;
    }
}

A better Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            TreeNode curr = new TreeNode(nums[i]);
            while(!stack.isEmpty() && stack.peek().val < nums[i]) {
                curr.left = stack.pop();
            }
            if(!stack.isEmpty()) {
                stack.peek().right = curr;
            }
            stack.push(curr);
        }

        return stack.isEmpty() ? null : stack.removeLast();
    }
}

669. Trim a Binary Search Tree

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Example 1:
Input:
    1
   / \
  0   2

  L = 1
  R = 2

Output:
    1
      \
       2
Example 2:
Input:
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output:
      3
     /
   2
  /
 1

java Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if(root == null){
           return root;
        }

        if(root.val > R){
            return trimBST(root.left,L,R);
        }
        else if(root.val < L){
            return trimBST(root.right,L,R);
        }
        else{
            root.left = trimBST(root.left,L,R);
            root.right = trimBST(root.right,L,R);
        }
        return root;
    }
}

Kotlin Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fun trimBST(root: TreeNode?, L: Int, R: Int): TreeNode? {
        if (root == null) {
            return root
        }

        if (root.`val` > R) {
            return trimBST(root.left, L, R)
        } else if (root.`val` < L) {
            return trimBST(root.right, L, R)
        } else {
            root.left = trimBST(root.left, L, R)
            root.right = trimBST(root.right, L, R)
        }
        return root
    }

728. Self Dividing Numbers

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1: Input: left = 1, right = 22 Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22] Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> myList = new LinkedList<>();
        for(int i = left;i <= right; i++){
            int copy = i;
            boolean isSelfDividing = true;
            while(copy != 0 ){
                int dividend = copy % 10;
                copy = copy / 10;
                if(dividend == 0 || i % dividend != 0){
                    isSelfDividing = false;
                    break;
                }
            }
            if(isSelfDividing)
                myList.add(i);
        }

        return myList;
    }
}

804. Unique Morse Code Words

Description

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: “a” maps to “.-“, “b” maps to “-…”, “c” maps to “-.-.”, and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

1
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cba” can be written as “-.-.-….-“, (which is the concatenation “-.-.” + “-…” + “.-“). We’ll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

1
2
3
4
5
6
7
8
9
Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation:
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, “–…-.” and “–…–.”.

Note:

  • The length of words will be at most 100.
  • Each words[i] will have length in range [1, 12].
  • words[i] will only consist of lowercase letters.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.HashSet;
import java.util.Set;

/**
 * Created by bill on 11/13/18.
 */
public class Solution {
    public final String []morseDict = {
	    ".-","-...","-.-.","-..",".","..-.","--.","....","..",
	    ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
	    "...","-","..-","...-",".--","-..-","-.--","--.."};
    public int uniqueMorseRepresentations(String[] words) {
        Set<String> myHashSet = new HashSet<String>();
        for(String word: words){
            StringBuilder myStringBuilder = new StringBuilder();
            for(char ele: word.toCharArray()){
                myStringBuilder.append(morseDict[ele - 'a']);
            }
            String myStr = myStringBuilder.toString();
            if(!myHashSet.contains(myStr)){
                 myHashSet.add(myStr);
            }
        }
        return myHashSet.size();
    }
}

806. Number of Lines To Write String

We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.

Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example :
Input:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation:
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.
Example :
Input:
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
Output: [2, 4]
Explanation:
All letters except 'a' have the same length of 10, and
"bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units.
For the last 'a', it is written on the second line because
there is only 2 units left in the first line.
So the answer is 2 lines, plus 4 units in the second line.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] numberOfLines(int[] widths, String S) {
        int lines = 1;
        int MAXLINE = 100;
        int sum = 0;
        for (char mChar:
             S.toCharArray()) {
            int num = widths[mChar - 'a'];
            if( sum + num <= MAXLINE){
                sum += num;
            }
            else{
                lines++;
                sum = num;
            }
        }
        return new int[]{lines, sum};
    }
}

811. Subdomain Visit Count

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:
Input:
["9001 discuss.leetcode.com"]
Output:
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation:
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:
Input:
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output:
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation:
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

  • The length of cpdomains will not exceed 100.
  • The length of each domain name will not exceed 100.
  • Each address will have either 1 or 2 “.” characters.
  • The input count in any count-paired domain will not exceed 10000.
  • The answer output can be returned in any order.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> myList = new LinkedList<>();
        Map<String, Integer> myMap = new HashMap<>();
        for(String domain: cpdomains){
            String[]domainStr = domain.split(" ");
            int value = Integer.valueOf(domainStr[0]);
            String key = domainStr[1];
            if(!myMap.containsKey(key)){
                myMap.put(key, value);
            }
            else{
                int old = myMap.get(key);
                myMap.put(key, old + value);
            }
            int tmp = key.indexOf(".");
            String tmpDomain = key.substring(tmp + 1);
            while(tmp > 0){
                if(!myMap.containsKey(tmpDomain)){
                    myMap.put(tmpDomain, value);
                }
                else{
                    int old = myMap.get(tmpDomain);
                    myMap.put(tmpDomain, old + value);
                }
                tmp = tmpDomain.indexOf(".");
                tmpDomain = tmpDomain.substring(tmp + 1);
            }
        }
        Iterator<Map.Entry<String, Integer>> it = myMap.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry<String ,Integer> entry = it.next();
            StringBuilder myBuilder = new StringBuilder();
            myBuilder.append(entry.getValue() + " "+ entry.getKey());
            myList.add(myBuilder.toString());
        }
        return myList;
    }
}

821.Shortest Distance to a Character

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

1
2
3
4
Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

  • S string length is in [1, 10000].
  • C is a single character, and guaranteed to be in string S. All letters in S and C are lowercase.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] shortestToChar(String S, char C) {
		Queue<Integer> mQueue = new LinkedList<>();
		int [] ret = new int[S.length()];
		for (int i = 0; i < S.length();i++) {
			if(S.charAt(i) == C){
				mQueue.add(i);
			}
		}

		for (int i = 0; i < S.length();i++) {
			int min = S.length();
			for (int ele: mQueue) {
				int distance = Math.abs(ele - i);
				if(min > distance){
					min = distance;
				}
			}
			ret[i] = min;
		}
		return ret;
	}
}

832. Flipping an Image

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

  • 1 <= A.length = A[0].length <= 20
  • 0 <= A[i][j] <= 1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
     public int[][] flipAndInvertImage(int[][] A) {
        for(int i = 0; i < A[0].length; i++){
            A[i] = reverseRow(A[i]);
            A[i] = invertRow(A[i]);
        }
        return A;
    }

    public int[] reverseRow(int[] input){
        if(input.length <= 1) return input;
        int head = 0;
        int tail = input.length - 1;
        while(head < tail){
            int tmp = input[head];
            input[head] = input[tail];
            input[tail] = tmp;
            tail--;
            head++;
        }
        return input;
    }

    public int[] invertRow(int[] input){
        if(input.length < 1) return input;
        for(int i = 0; i < input.length; i++){
            input[i] ^= 1;
        }
        return input;
    }

}

893. Groups of Special-Equivalent Strings

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Example 1:

Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]
Example 2:

Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]
Example 4:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]
Example 4:

Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSpecialEquivGroups(String[] A) {
        Set<String> seen = new HashSet();
        for (String S: A) {
            int[] count = new int[52];
            for (int i = 0; i < S.length(); ++i)
                count[S.charAt(i) - 'a' + 26 * (i % 2)]++;
            seen.add(Arrays.toString(count));
        }
        return seen.size();
    }
}

  • What does S.charAt(i) - ‘a’ do? The character a is 97 in ASCII. By subtracting a from another letter in the alphabet, we can convert the ASCII to represent a as 0 instead - thereby making the alphabet 0-indexed.
  • What does 26 * (i % 2) do? There are 26 letters in the alphabet i % 2 returns 0 if even and 1 if odd 26 * (i % 2) returns 0 if even and 26 if odd S.charAt(i) - a <— this brings the letter to be 0-indexed
  • Where did 52 come from in int[] count = new int[52] ? There are 26 letters in the alphabet A letter could be in an odd index or an even index. This makes 26 + 26 = 52 “kind of letters” The index of the count array represents the property of the letter –> 1. the value of the letter and 2. if it is odd of even If the string has two letter ‘a’s and both of the letters are at an even index, then count[26] == 2.

897. Increasing Order Search Tree

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

Note:

The number of nodes in the given tree will be between 1 and 100. Each node will have a unique integer value from 0 to 1000.

1
2
3
4
5
6
7
8
9
10
11
public TreeNode increasingBST(TreeNode root) {
        return increasingBST(root, null);
    }

    public TreeNode increasingBST(TreeNode root, TreeNode tail) {
        if (root == null) return tail;
        TreeNode res = increasingBST(root.left, root);
        root.left = null;
        root.right = increasingBST(root.right, tail);
        return res;
    }

908. Smallest Range I

Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add x to A[i].

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: A = [1], K = 0
Output: 0
Explanation: B = [1]
Example 2:

Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]
Example 3:

Input: A = [1,3,6], K = 3
Output: 0
Explanation: B = [3,3,3] or B = [4,4,4]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int smallestRangeI(int[] A, int K) {
        if(A.length <= 1)
            return 0;
        int size = A.length;
        int[] tmpArray = A;

        int min = tmpArray[0];
        int max = tmpArray[0];
        for(int i = 1;i < size;i++){
            if(min > tmpArray[i])
                min = tmpArray[i];
            if(max < tmpArray[i])
                max = tmpArray[i];
        }

        if(min + K >= max - K){
            return 0;
        }
        else{
            return max - min - 2 * K;
        }
    }

}

912. Sort an Array

Given an array of integers nums, sort the array in ascending order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
 

Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {

    public:
        vector<int> sortArray(vector<int>& nums) {
            quick_sort(nums, 0, nums.size() - 1);
            return nums;
        }

        void quick_sort(vector<int>& nums, int l, int r)
        {

            if (l < r)
            {

                int i = l, j = r, x = nums[l];
                while (i < j)
                {

                    while(i < j && nums[j] >= x)
                        j--;  
                    if(i < j) 
                        nums[i++] = nums[j];

                    while(i < j && nums[i] < x)
                        i++;  
                    if(i < j) 
                        nums[j--] = nums[i];
                }   
                nums[i] = x;
                quick_sort(nums, l, i - 1); 
                quick_sort(nums, i + 1, r);
            }
        }
};

938. Range Sum of BST

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

1
2
3
4
5
6
7
8
Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sum;
    public Solution(){
        sum = 0;
    }
    public int rangeSumBST(TreeNode root, int L, int R) {
        DFS(root, L, R);
        return sum;
    }

    public void DFS(TreeNode root, int L, int R){
        if(root != null){
            if(root.val >= L && root.val <= R){
                sum+=root.val;
            }
            if(root.val > L){
                DFS(root.left, L, R);
            }
            if(root.val < R){
                DFS(root.right, L, R);
            }
        }
    }
}

944. Delete Columns to Make Sorted

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”, “vyz”], and the remaining columns of A are [“b”,”v”], [“e”,”y”], and [“f”,”z”]. (Formally, the c-th column is [A[0][c], A[1][c], …, A[A.length-1][c]].)

Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.

Return the minimum possible value of D.length.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Example 1:

Input: ["cba","daf","ghi"]
Output: 1
Explanation:
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.
Example 2:

Input: ["a","b"]
Output: 0
Explanation: D = {}
Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}


Note:

1 <= A.length <= 100
1 <= A[i].length <= 1000

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDeletionSize(String[] A) {
        int sum = 0;
        int len = A.length;
        int strLen = A[0].length();
        for(int i = 0; i < strLen; i++){
            char tmp = A[0].charAt(i);
            for(int j = 1; j < len; j++){
                if(tmp > A[j].charAt(i)){
                    sum++;
                    break;
                }
                tmp = A[j].charAt(i);
            }
        }

        return sum;
    }
}

961. N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Example 1:

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

Example 2:

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

Example 3:

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



Note:

    4 <= A.length <= 10000
    0 <= A[i] < 10000
    A.length is even

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.HashMap;
import java.util.Map;

/**
 * Created by bill on 2/18/19.
 */
public class Solution {
    Map<Integer, Integer> myMap = new HashMap();
    public int repeatedNTimes(int[] A) {
        int N = A.length/2;
        for (int ele: A) {
            int tmp = 0;
            if(!myMap.containsKey(ele)){
                myMap.put(ele,1);
            }
            else{
                tmp = myMap.get(ele) + 1;
                myMap.replace(ele,tmp);
            }
            if(tmp == N){ return ele;}
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution mySolution = new Solution();
        int [] array = {2,1,2,5,3,2};
        int ret = mySolution.repeatedNTimes(array);
        System.out.println(ret);
    }
}

965. Univalued Binary Tree

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

  • Input: [1,1,1,1,1,null,1]
  • Output: true

  • Input: [2,2,2,5,2]
  • Output: false

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public boolean isUnivalTree(TreeNode root) {
        int val = root.val;
        if(root.left == null && root.right == null){
            return true;
        }
        if(root.left == null){
            return isUnivalTree(root.right) &&(root.val == root.right.val);
        }
        else if(root.right == null){
            return isUnivalTree(root.left) &&(root.val == root.left.val);
        }
        else{
            return isUnivalTree(root.left) && isUnivalTree(root.right)
                    && (root.val == root.left.val) && (root.val == root.right.val);
        }
    }
}

973. K Closest Points to Origin

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    class point{
        point(int x,int y){
            this.x = x;
            this.y = y;
        }
        int x;
        int y;
    }

    class pointId{
        pointId(point mid, int mDis){
            id = mid;
            distance = mDis;
        }
        point id;
        int distance;
    }

    private Comparator<pointId> mComparator = new Comparator<pointId>(){
        @Override
        public int compare(pointId t1, pointId t2) {
            return t1.distance - t2.distance;
        }
    };

    public int[][] kClosest(int[][] points, int K) {
        int len = points.length;
        Queue<pointId> mQueue = new PriorityQueue<>(K, mComparator);
        for (int []ele:points) {
            int distance = EuclideanDistance(ele[0],ele[1],0,0);
            pointId mId = new pointId(new point(ele[0],ele[1]), distance);
            mQueue.add(mId);
        }

        int [][] closest = new int[K][2];
        int i = 0;
        while(i < K){
            pointId tmp = mQueue.poll();
            closest[i][0] = tmp.id.x;
            closest[i][1] = tmp.id.y;
            i++;
        }
        return closest;
    }

    private static int EuclideanDistance(int X, int Y, int oX, int oY){
        int tmp = (X - oX) * (X - oX) + (Y - oY) * (Y - oY);
        return tmp;
    }
}

977. Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]


Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private boolean less(int v, int w) {
        return v < w;
    }

    private void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }


    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int [] tmp = new int[N];
        for (int i = 0; i < N; i++) {
            tmp[i] = Math.abs(A[i]);
        }

        for(int i = 1 ; i < N; i++){
            for(int j = i; j > 0 && less(tmp[j], tmp[j-1]);j--){
                exch(tmp, j, j-1);
            }
        }

        for (int i = 0; i <N; i++) {
            int var = tmp[i];
            tmp[i] = var * var;
        }
        return tmp;
    }
}

985. Sum of Even Numbers After Queries

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

1
2
3
4
5
6
7
8
9
10
Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation:
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int N = A.length;
        int[] sumEventQueries = new int[N];
        int num = queries.length;

        for(int i = 0; i < num; i++){
            int index = queries[i][1];
            int val = queries[i][0];
            A[index] = A[index] + val;
            for(int ele: A){
                if(isEvent(ele)){
                    sumEventQueries[i] += ele;
                }
            }
        }
        return sumEventQueries;
    }

    private boolean isEvent(int a){
        if(a % 2 == 0){
           return true;
        }
        else
            return false;
    }

}

993. Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

1
2
Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

1
2
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

1
2
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

The number of nodes in the tree will be between 2 and 100. Each node has a unique integer value from 1 to 100.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        TreeNode ParentFirst = getParentWithChild(root, x);
        TreeNode ParentSecond = getParentWithChild(root, y);

        if(ParentFirst == null || ParentSecond == null){
            return false;
        }

        if((ParentFirst.val != ParentSecond.val) &&
                getDepth(root,ParentFirst) == getDepth(root,ParentSecond)){
            return true;
        }
        else{
            return false;
        }
    }

    int getDepth(TreeNode root,TreeNode target){
        if(root == null){
            return -1;
        }
        if(root.val == target.val){
            return 0;
        }
        int leftDepth = getDepth(root.left,target);
        int righttDepth = getDepth(root.right,target);
        if(leftDepth != -1){
            return leftDepth + 1;
        }
        if(righttDepth != -1){
            return righttDepth + 1;
        }
        return -1;
    }


    TreeNode getParentWithChild(TreeNode root, int x){
        if(root == null){ return null;}
        if((root.left != null && root.left.val == x) ||
                (root.right!= null && root.right.val == x)){
            return root;
        }
        TreeNode left = getParentWithChild(root.left,x);
        TreeNode right = getParentWithChild(root.right,x);
        if(left != null){
            return left;
        }
        if(right != null){
            return right;
        }
        return null;
    }
}

999. Available Captures for Rook

On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters ‘R’, ‘.’, ‘B’, and ‘p’ respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move into the same square as other friendly bishops.

Return the number of pawns the rook can capture in one move.

Example 1:

1
2
3
4
Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
In this example the rook is able to capture all the pawns.

Example 2:

1
2
3
4
Input: [[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 0
Explanation:
Bishops are blocking the rook to capture any pawn.

Example 3:

1
2
3
4
Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
The rook can capture the pawns at positions b5, d6 and f5.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
public class Solution {

    Boolean north = false;
    Boolean south = false;
    Boolean east = false;
    Boolean west = false;
    class Rooks extends Point{
        Rooks(int x, int y){
            super(x,y);
        }
    }

    class Point{
        Point(int x,int y){
            this.x = x;
            this.y = y;
        }
        int x;
        int y;
    }

    List<Point> blackPawns = new LinkedList<>();
    List<Point> whiteBishops = new LinkedList<>();
    Rooks mRooks;
    public int numRookCaptures(char[][] board) {
        int height = board.length;
        int width = board[0].length;
        int sum = 0;
        for(int i = 0; i < height ;i++){
            for(int j = 0; j < width ;j++) {
                char tmp = board[i][j];
                switch (tmp){
                    case 'R':
                        mRooks = new Rooks(i,j);
                        break;
                    case 'B':
                        blackPawns.add(new Point(i,j));
                        break;
                    case 'p':
                        whiteBishops.add(new Point(i,j));
                        break;
                    default: break;
                }
            }
        }
        for(int i = 0; i < whiteBishops.size();i++){
            if(whiteBishops.get(i).x == mRooks.x){
                int whiteBishopsY = whiteBishops.get(i).y;
                int max = whiteBishopsY > mRooks.y ? whiteBishopsY  : mRooks.y;
                int min = whiteBishopsY < mRooks.y ? whiteBishopsY  : mRooks.y;
                if(blackPawns.size() == 0){
                    if(whiteBishopsY > mRooks.y) {
                        if(!north){
                            north = true;
                            sum++;
                        }
                    }
                    if(whiteBishopsY < mRooks.y) {
                        if(!south){
                            south = true;
                            sum++;
                        }
                    }
                    continue;
                }
                Boolean hasBlackPawns = false;
                for(int j = 0; j < blackPawns.size();j++){
                    int blackPawnsY = blackPawns.get(j).y;
                    if(blackPawns.get(j).x == mRooks.x){
                        if(blackPawnsY < max && blackPawnsY > min){
                            if(!north||!south){
                                hasBlackPawns = true;
                                break;
                            }
                        }
                    }
                }

                if(!hasBlackPawns){
                    if(whiteBishopsY > mRooks.y) {
                        if(!north){
                            north = true;
                            sum++;
                        }
                    }
                    if(whiteBishopsY < mRooks.y) {
                        if(!south){
                            south = true;
                            sum++;
                        }
                    }
                }
            }
        }
        for(int i = 0; i < whiteBishops.size();i++){
            if(whiteBishops.get(i).y == mRooks.y){
                int whiteBishopsX = whiteBishops.get(i).x;
                int max = whiteBishopsX > mRooks.x ? whiteBishopsX : mRooks.x;
                int min = whiteBishopsX < mRooks.x ? whiteBishopsX : mRooks.x;
                if(blackPawns.size() == 0){
                    if(whiteBishopsX > mRooks.x) {
                        if(!east){
                            east = true;
                            sum++;
                        }
                    }
                    if(whiteBishopsX < mRooks.x) {
                        if(!west){
                            west = true;
                            sum++;
                        }
                    }
                    continue;
                }
                Boolean hasBlackPawns = false;
                for(int j = 0; j < blackPawns.size();j++){
                    int blackPawnsX = blackPawns.get(j).x;
                    if(blackPawns.get(j).y == mRooks.y){
                        if(blackPawnsX < max && blackPawnsX > min){
                            if(!east||!west) {
                                hasBlackPawns = true;
                                break;
                            }
                        }
                    }
                }
                if(!hasBlackPawns){
                    if(whiteBishopsX > mRooks.x) {
                        if(!east){
                            east = true;
                            sum++;
                        }
                    }
                    if(whiteBishopsX < mRooks.x) {
                        if(!west){
                            west = true;
                            sum++;
                        }
                    }
                }
            }
        }
        return sum;
    }
}

1002. Find Common Characters

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

1
2
3
4
5
6
7
8
Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]
Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {

    public List<String> commonChars(String[] A) {
        int len = A.length;
        List<Integer[]> myList = new LinkedList<>();
        for(int i = 0;i < len; i++){
            Integer[] myVal = new Integer[26];
            for(int k = 0;k < 26;k++){
               myVal[k] = 0;
            }
            String tmp = A[i];
            for(int j = 0; j < tmp.length();j++){
                myVal[tmp.charAt(j) - 'a']++;
            }
            myList.add(myVal);
        }
        List<String> myString = new LinkedList<>();
        for(int i = 0; i < 26 ;i++){
            int min = Integer.MAX_VALUE;
            for(Integer[] ele:myList){
                int num = ele[i];
                if(num == 0){
                    min = 0;
                    break;
                }
                if(num < min){
                    min = num;
                }
            }
            for(int j = 0;j < min;j++){
                myString.add(String.valueOf(Character.toChars('a' + i)));
            }
        }
        return myString;
    }
}

1480. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. Example 2:

Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]. Example 3:

Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]

Constraints:

1 <= nums.length <= 1000 -10^6 <= nums[i] <= 10^6

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> ret;
        int last = 0;
        for(int i = 0 ; i < nums.size(); i++){
            ret.push_back(last + nums[i]);
            last = ret.back();
        }
        return ret;
    }
};

1512. Number of Good Pairs

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.
Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

1 <= nums.length <= 100 1 <= nums[i] <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int ret = 0;
        for(int i = 0; i < nums.size() - 1; i++){
            for(int j = nums.size() - 1; j > i; j--){
                if(nums[i] == nums[j]){
                    ret++;
                }
            }
        }
        return ret;
    }
};