当前位置:网站首页>Leetcode sword finger offer brush questions - day 20
Leetcode sword finger offer brush questions - day 20
2022-07-07 07:31:00 【DEGv587】
Leetcode The finger of the sword Offer How to brush questions :
The finger of the sword Offer 07. Reconstruction of binary tree
Topic information : The results of preorder traversal and inorder traversal do not contain duplicate numbers
solution : Divide and conquer thoughts
class Solution {
int[] preorder;// Preserved preorder traversal
HashMap<Integer, Integer> map = new HashMap<>();// Tag middle order traversal
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; ++i) {
map.put(inorder[i], i);
}
return func(0, 0, inorder.length - 1);
}
private TreeNode func(int root, int left, int right) {
if (left > right) return null;
TreeNode node = new TreeNode(preorder[root]);// Establish root node
int i = map.get(preorder[root]);// Partition root node , Left and right subtrees
node.left = func(root + 1, left, i - 1);// Left subtree recursion
node.right = func(root + i - left + 1, i + 1, right);// Right subtree recursion
return node;
}
}
The finger of the sword Offer 16. Integer power of value
solution : Fast power
Stepwise decomposition
Even transformation , One more odd number for processing
2^10 = (2^5) * (2^5) = (4^2) * (4^2) * 4 = 16 * 16 * 4
class Solution {
public double myPow(double x, int n) {
if (x == 0) return 0;
long b = n;// To prevent cross-border
double ret = 1.0;
if (b < 0) {
x = 1 / x;
b = -b;
}
while (b > 0) {
if ((b & 1) == 1) {
// Deal with odd numbers
ret *= x;
}
x *= x;
b >>= 1;
}
return ret;
}
}
The finger of the sword Offer 33. The post order traversal sequence of binary search tree
Solution 1 : Recursive divide and conquer
Ergodic sequence ergodic [i, j] Interval elements , seek The first is larger than the root node The node of , The index is marked as m
postorder[j] Is the root node
Left subtree interval [i, m - 1] All nodes in the should < postorder[j]
Right subtree interval [m, j-1] All nodes in the should > postorder[j]
class Solution {
public boolean verifyPostorder(int[] postorder) {
return verifyHelp(postorder, 0, postorder.length - 1);
}
private boolean verifyHelp(int[] postorder, int i, int j) {
if (i >= j) return true;
int p = i;
while (postorder[p] < postorder[j]) {
// If it is smaller than the root node, continue to walk backwards
p++;
}
// Encounter the first value greater than the root node , Record as m
int m = p;
while (postorder[p] > postorder[j]) {
// If it is larger than the root node, continue to walk backwards
p++;
}
// Recursively divide and conquer left subtree and right subtree
return p == j && verifyHelp(postorder, i, m - 1) && verifyHelp(postorder, m, j - 1);
}
}
Solution 2 : Auxiliary monotone stack
class Solution {
public boolean verifyPostorder(int[] postorder) {
Stack<Integer> stack = new Stack<>();
int root = Integer.MAX_VALUE;
for (int i = postorder.length - 1; i >= 0; --i) {
// If the current node is larger than the root node , Then return directly false
if (postorder[i] > root) return false;
while (!stack.isEmpty() && stack.peek() > postorder[i]) {
// Find the parent node of the current node
root = stack.pop();
}
stack.add(postorder[i]);
}
return true;
}
}
边栏推荐
- BGP experiment (1)
- Advanced practice of C language (high level) pointer
- Flexible layout (I)
- Abnova membrane protein lipoprotein technology and category display
- L'externalisation a duré trois ans.
- "Xiaodeng in operation and maintenance" meets the compliance requirements of gdpr
- Outsourcing for three years, abandoned
- [Linux] process control and parent-child processes
- Talk about seven ways to realize asynchronous programming
- 机器人技术创新与实践旧版本大纲
猜你喜欢
Kuboard can't send email and nail alarm problem is solved
Simple example of ros2 planning system plansys2
About some details of final, I have something to say - learn about final CSDN creation clock out from the memory model
URP - shaders and materials - simple lit
RuntimeError: CUDA error: CUBLAS_ STATUS_ ALLOC_ Failed when calling `cublascreate (handle) `problem solving
Role of virtual machine
Fast quantitative, abbkine protein quantitative kit BCA method is coming!
95后CV工程师晒出工资单,狠补了这个,真香...
Dynamics CRM server deployment - restore database prompt: the database is in use
[semantic segmentation] - multi-scale attention
随机推荐
How to reduce inventory with high concurrency on the Internet
普通测试年薪15w,测试开发年薪30w+,二者差距在哪?
考研失败,卷不进大厂,感觉没戏了
The currently released SKU (sales specification) information contains words that are suspected to have nothing to do with baby
抽丝剥茧C语言(高阶)指针进阶练习
Bindingexception exception (error reporting) processing
L'externalisation a duré trois ans.
Introduction to abnova's in vitro mRNA transcription workflow and capping method
Hidden Markov model (HMM) learning notes
Modify the jupyter notebook file path
$refs: get the element object or sub component instance in the component:
Jesd204b clock network
Outlier detection technology of time series data
[semantic segmentation] - multi-scale attention
一、Go知识查缺补漏+实战课程笔记 | 青训营笔记
Talk about seven ways to realize asynchronous programming
Non empty verification of collection in SQL
Flexible layout (I)
抽丝剥茧C语言(高阶)数据的储存+练习
Reflection (II)