leetcode 1007 Minimum Domino Rotations For Equal Row & leetcode 1008 Construct Binary Search Tree from Preorder Traversal

leetcode 1007 Minimum Domino Rotations For Equal Row

Use three int array of size 6

The first one invalid array records valid(or invalid) numbers which can be the same in A or B

the rest two records the count of valid numbers in A and B

class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int N = A.length;
        if (N != B.length) return -1;
        int[] invalid = new int[6];
        int[] ac = new int[6];
        int[] bc = new int[6];
        for (int i = 0; i < N; ++i) {
            for (int j = 1; j <= 6; ++j) {
                //find invalid numbers
                if (A[i] != j && B[i] != j) invalid[j - 1] = 1;
            }
            //for valid number, record A's count and B's count
            if (invalid[A[i] - 1] == 0) ac[A[i] - 1] += 1;
            if (invalid[B[i] - 1] == 0) bc[B[i] - 1] += 1;
        }
        int ret = 20001;
        for (int i = 0; i < 6; ++i) {
            if (invalid[i] == 1) continue;
            ret = Math.min(ret, Math.min(N - ac[i], N - bc[i]));
        }
        return ret == 20001? -1: ret;
    }
}

leetcode 1008 Construct Binary Search Tree from Preorder Traversal

Non-recursive solution, I first came up with the below solution

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        for (int i = 1; i < preorder.length; ++i) {
            TreeNode node = s.peek();
            if (preorder[i] < node.val) {
                node.left = new TreeNode(preorder[i]);
                s.push(node.left);
            }
            else {
                s.pop();
                while (s.size() != 0 && s.peek().val < preorder[i]) {
                    node = s.pop();
                }
                node.right = new TreeNode(preorder[i]);
                s.push(node.right);
            }
        }
        return root;
    }
}

But the code seemed a little weird, especially in the else code block. So with some modification it seemed much better.

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode node = root;
        for (int i = 1; i < preorder.length; ++i) {
            if (preorder[i] < node.val) {
                node.left = new TreeNode(preorder[i]);
                s.push(node);
                node = node.left;
            }
            else {
                while (s.size() != 0 && s.peek().val < preorder[i]) {
                    node = s.pop();
                }
                node.right = new TreeNode(preorder[i]);
                node = node.right;
            }
        }
        return root;
    }
}

I figured out the non-recursive version really quick, but after that I spent quite some time trying the recursive version and failed….

I‘ll come back to post the recursive version when finishing it.

leetcode 1007 Minimum Domino Rotations For Equal Row & leetcode 1008 Construct Binary Search Tree from Preorder Traversal

原文：https://www.cnblogs.com/exhausttolive/p/10533993.html