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.

转载于:https://www.cnblogs.com/exhausttolive/p/10533993.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/94969781

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。