Sunday, June 5, 2016

LeetCode Challenges 

       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
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        
        bool same = false;
        
        if((p != null) && (q != null))
        {
            bool leftTreeSame = IsSameTree(p.left, q.left);
            bool rightTreeSame = IsSameTree(p.right, q.right);
            same = leftTreeSame && rightTreeSame;            
            same = same && (p.val == q.val ? true : false);
        }

        return same;
    }
}

  • Invert Binary Tree
    • In-Place Recursive Solution (Huge improvement possible if a check for null is added before recursing root.left and root.right)
       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 {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private void PreOrder(TreeNode root)
    {
        if (root == null) return;            
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        PreOrder(root.left);
        PreOrder(root.right);
    }

    public TreeNode InvertTree(TreeNode root)
    {
        if (root == null) return root;
        PreOrder(root);
        return root;
    }
}
    • Not In Place (Has a very bad run time performance)
       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
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode minvertedroot;
    
    private void PreOrder(TreeNode root, TreeNode invertedroot)
    {
            if (root == null || invertedroot == null) return;

            TreeNode left = null;
            if (root.left != null)
            {
                left = new TreeNode(root.left.val);
            }

            TreeNode right = null;
            if (root.right != null)
            {
                right = new TreeNode(root.right.val);
            }

            invertedroot.val = root.val;
            invertedroot.left = right;
            invertedroot.right = left;

            if (root.right != null)
            {
                PreOrder(root.right, invertedroot.left);
            }

            if (root.left != null)
            {
                PreOrder(root.left, invertedroot.right);
            }

    }

    public TreeNode InvertTree(TreeNode root)
    {
        if (root == null) return root;
        minvertedroot = new TreeNode(root.val);
        PreOrder(root, minvertedroot);
        return minvertedroot;
    }
}


       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
      class Solution {
private:
    void Transpose(vector<vector<int>>& matrix)
    {
        auto rows = matrix.size();
        auto cols = rows;

        for (auto row = 0UL; row < rows; ++row)
        {
            for (auto col = row; col < cols; ++col)
            {
                std::swap(matrix[row][col], matrix[col][row]);
            }
        }
    }

    void SwapCols(vector<vector<int>>& matrix)
    {
        auto rows = matrix.size();
        auto cols = rows;

        for (auto row = 0UL; row < rows; ++row)
        {
            for (auto col = 0UL; col < cols / 2; ++col)
            {
                std::swap(matrix[row][col], matrix[row][cols - col - 1]);
            }
        }
    }

public:
    void rotate(vector<vector<int>>& matrix) {
        Transpose(matrix);
        SwapCols(matrix);
    }
};

int main()
{
    int n = 3;

    vector<vector<int>> v(n, std::vector<int>{});

    int start = 1;
    for (auto index = 0; index < n; ++index)
    {
        std::vector<int> row(n, 0);
        for (int v = 0; v < n; ++v)
        {
            row[v] = start++;
        }
        v[index].swap(row);
    }

    Solution s;
    s.rotate(v);

    for (auto const &e : v)
    {
        for (auto const &i : e)
        {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    }
}

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)