Day: March 3, 2016

226. Invert Binary Tree

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

Invert a binary tree.

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

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        invert(root);
        return root;
    }
    void invert(TreeNode *node) {
        if (!node) return;
        TreeNode *tmp = node->left;
        node->left = node->right;
        node->right = tmp;
        invert(node->left);
        invert(node->right);
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

235. Lowest Common Ancestor of a Binary Search Tree

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || !p || !q) return NULL;
        if (p->val == q->val) return p;
        int large = max(p->val, q->val), small = min(p->val, q->val);
        while (root) {
            if (root->val > large) {
                root = root->left;
            } else if (root->val < small) {
                root = root->right;
            } else return root;
        }
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

270. (Locked)Closest Binary Search Tree Value

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/** 
 * Definition for a binary tree node. 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    int closestValue(TreeNode* root, double target) {
        if (!root) return 0;
        int closest = root->val;
        while (root) {
            if (abs(closest - target) >= abs(root->val - target))
                closest = root->val;
            root = target > closest ? root->right : root->left;
        }
        return closest;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

201. Bitwise AND of Numbers Range

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m != n) {
            shift++;
            m = m >> 1;
            n = n >> 1;
        }
        return m << shift;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

103. Binary Tree Zigzag Level Order Traversal

fightingminion1 Comment

Difficulty: Medium

Frequency: N/A

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

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if (!root) return results;
        deque<TreeNode*> deq;
        deq.push_front(root);
        bool front = true;
        while (!deq.empty()) {
            int s_size = deq.size();
            vector<int> result;
            while (s_size) {
                if (front) {
                    TreeNode *cur = deq.front();
                    deq.pop_front();
                    result.push_back(cur->val);
                    if (cur->left) deq.push_back(cur->left);
                    if (cur->right) deq.push_back(cur->right);
                } else {
                    TreeNode *cur = deq.back();
                    deq.pop_back();
                    result.push_back(cur->val);
                    if (cur->right) deq.push_front(cur->right);
                    if (cur->left) deq.push_front(cur->left);
                }
                s_size--;
            }
            front = !front;
            results.push_back(result);
        }
        return results;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

317. (Locked)Shortest Distance from All Buildings

fightingminionLeave a comment

Difficulty: Hard

Frequency: N/A

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x – p1.x| + |p2.y – p1.y|.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 – 0 – 2 – 0 – 1
|    |     |     |    |
0 – 0 – 0 – 0 – 0
|     |     |     |    |
0 – 0 – 1 – 0 – 0
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        int nb = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) nb++;
            }
        }
        int result = INT_MAX;
        bool found = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) continue;
                int dist = 0, cnt = 0;
                vector<int> start = {i, j, 0};
                queue<vector<int>> myQ;
                myQ.push(start);
                vector<vector<bool>> visited = (m, vector<int>(n, false));
                visited[i][j] = true;
                while (!myQ.empty()) {
                    int p = myQ.front()[0];
                    int q = myQ.front()[1];
                    int steps = myQ.front()[2];
                    myQ.pop();
                    if (grid[p][q] == 1) {
                        cnt++;
                        dist += steps;
                    }
                    if (grid[p][q] == 0 || (p == i) && (q == j)) {
                        if (p - 1 >= 0 && grid[p - 1][q] > 2 && !visisted[p - 1][q]) {
                            vector<int> tmp = {p - 1, q, steps + 1};
                            myQ.push(tmp);
                            visited[p - 1][q] = true;
                        }
                        if (p + 1 < m && grid[p + 1][q] > 2 && !visisted[p + 1][q]) {
                            vector<int> tmp = {p + 1, q, steps + 1};
                            myQ.push(tmp);
                            visited[p + 1][q] = true;
                        } 
                        if (q - 1 >= 0 && grid[p][q - 1] > 2 && !visisted[p][q - 1]) {
                            vector<int> tmp = {p, q - 1, steps + 1};
                            myQ.push(tmp);
                            visited[p][q - 1] = true;
                        }
                        if (q + 1 < n && grid[p][q + 1] > 2 && !visisted[p][q + 1]) {
                            vector<int> tmp = {p, q + 1, steps + 1};
                            myQ.push(tmp);
                            visited[p][q + 1] = true;
                        }       
                    }
                }
                if (grid[i][j] == 1 && cnt < nb) return -1;
                if (grid[i][j] == 0 && cnt == nb) {
                    found = true;
                    result = min(disk, result);
                }
            }
        }
        return found ? result : -1;
    }
}
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

286. (Locked)Walls and Gates

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

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 than2147483647.

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, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
private:
    struct Grid {
        int p, q, d;
        Grid(int p_, int q_, int d_) : p(p_), q(q_), d(d_) {}
    };
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty()) return;
        int m = rooms.size(), n = rooms[0].size();
        queue<Grid> myQ;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!rooms[i][j]) {
                    myQ.push(Grid(i - 1, j, 1));
                    myQ.push(Grid(i + 1, j, 1));
                    myQ.push(Grid(i, j - 1, 1));
                    myQ.push(Grid(i, j + 1, 1));
                    while (!myQ.empty()) {
                        Grid cur = myQ.front();
                        myQ.pop();
                        if (cur.p < 0 || cur.p >= m || cur.q < 0 || cur.q > n || rooms[cur.p][cur.q] < d) continue;
                        rooms[cur.p][cur.q] = d;
                        myQ.push(Grid(cur.p - 1, cur.q, d + 1));
                        myQ.push(Grid(cur.p + 1, cur.q, d + 1));
                        myQ.push(Grid(cur.p, cur.q - 1, d + 1));
                        myQ.push(Grid(cur.p, cur.q + 1, d + 1));                    
                    }
                }
            }
        }
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn: