LeetCode | Learn for Master

Leetcode Symmetric Tree

August 8, 2016 Author: david
No comment yet

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1 / \ 2 2 / \ / \ 3 4 4 3

1
2
3
4
5
6

    1
   / \
  2   2
/ \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1 / \ 2 2 \ \ 3 3

1
2
3
4
5
6

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Analysis
This problem can be easily solved using a recursive algorithm. We defined a method with the following signature:

equal(left, right)

then we recursively call equal(left.left, right.right) and equal(left.right, right.left).

The method returns false as long as only one of the two nodes is null,
[Read More...]
Leetcode Remove Linked List Elements

August 7, 2016 Author: david
No comment yet

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

Analysis

To solve this problem, we keep two pointers pre and cur when scanning the LinkedList. Once the current node’s value equals to the target value, we remove the cur node by set pre.next = cur.next;

To make the implementation easier,
[Read More...]
Leetcode Intersection of Two Arrays

August 7, 2016 Author: david
No comment yet
Intersection of Two unsorted Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
- Each element in the result must be unique.
- The result can be in any order.
Analysis

Since the two arrays are unsorted, we can use HashSet to solve the problem easily.

We can also solve the problem by first sorting the two arrays, and using the algorithm of finding intersection of two sorted arrays.
[Read More...]
LeetCode move zeroes

August 7, 2016 Author: david
No comment yet
Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.
Analysis

We can use a pointer zeroIndex to always point to the index of the first 0. We scan the array, if we encounter a non-zero element,
[Read More...]
Leetcode Invert Binary Tree

August 7, 2016 Author: david
No comment yet

Invert a binary tree.

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

1
2
3
4
5

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

to

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

1
2
3
4
5

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

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Analysis

This problem can be solved by using both recursion and bread first traverse or Level order traverse.

We first invert the left tree and right tree, then put the inverted right tree as the left child,
[Read More...]
LeetCode Shortest Word Distance I II and III

August 7, 2016 Author: david
No comment yet

Shortest Word Distance I

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example, Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = “makes”, word2 = “coding”, return 1.

Note

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Analysis

We can scan the list and use two pointers to record the most recent indexes of the two words.
[Read More...]

Leetcode – Maximum Depth of Binary Tree

August 7, 2016 Author: david

No comment yet

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Analysis:

This problem can be easily solved using a recursive algorithm. As

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right) + 1 if root != null;

and maxDepth(root) == 0 if root == null;

Java solution:

//Definition for a binary tree node.
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}
class MaxDepth {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);
        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }
}

//Definition for a binary tree node.

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

class MaxDepth {

public int maxDepth(TreeNode root) {

if(root == null) return 0;

int leftMaxDepth = maxDepth(root.left);

int rightMaxDepth = maxDepth(root.right);

return Math.max(leftMaxDepth, rightMaxDepth) + 1;

}

https://leetcode.com/problems/maximum-depth-of-binary-tree/

[Read More...]

Leetcode – Add Digits

August 7, 2016 Author: david
No comment yet
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:
1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur,
[Read More...]
Leetcode – Wall and Gates

August 7, 2016 Author: david
No comment yet
You are given a m x n 2D grid initialized with these three possible values.
1. -1 – A wall or an obstacle.
2. 0 – A gate.
3. INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
For example,
[Read More...]
LeetCode － Flip Game

August 7, 2016 Author: david
No comment yet

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–“. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = “++++”, after one move, it may become one of the following states:

[ "--++", "+--+", "++--" ]

1
2
3
4
5
6

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move,
[Read More...]