题目
Segmemt Tree Build II
The structure of Segment Tree is a binary tree which each node has two attributes start
and end
denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
- The root's start and end is given by
build
method. - The left child of node A has
start=A.left, end=(A.left + A.right) / 2
. - The right child of node A has
start=(A.left + A.right) / 2 + 1, end=A.right
. - if start equals to end, there will be no children for this node.
Implement a build
method with a given array, so that we can create a corresponding segment tree with every node value represent the corresponding interval max value in the array, return the root of this segment tree.
Given [3,2,1,4]
. The segment tree will be:
[0, 3] (max = 4)
/ \
[0, 1] (max = 3) [2, 3] (max = 4)
/ \ / \
[0, 0](max = 3) [1, 1](max = 2)[2, 2](max = 1) [3, 3] (max = 4)
Segment Tree (a.k.a Interval Tree) is an advanced data structure which can support queries like:
- which of these intervals contain a given point
- which of these points are in a given interval
See wiki: Segment Tree Interval Tree
解题
理解题意:根据给的数组构建段树,该节点有区间及其该区间的最大值组成。区间的左右节点利用上面的规则计算。
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, max;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int max) {
* this.start = start;
* this.end = end;
* this.max = max
* this.left = this.right = null;
* }
* }
*/
这个节点定义要好好理解。
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, max;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int max) {
* this.start = start;
* this.end = end;
* this.max = max
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param A: a list of integer
*@return: The root of Segment Tree
*/
public SegmentTreeNode build(int[] A) {
// write your code here
return build(0,A.length-1,A);
}
public SegmentTreeNode build(int start,int end,int[] A){
if(start > end ){
return null;
}
SegmentTreeNode root = new SegmentTreeNode(start,end);
if( start != end){
int mid = (start + end)/2;
root.left = build(start,mid,A);
root.right = build(mid+1,end,A);
root.max = Math.max(root.left.max,root.right.max);
}else{
root.max = A[start];
}
return root;
}
}
Java Code
总耗时: 2532 ms
"""
Definition of SegmentTreeNode:
class SegmentTreeNode:
def __init__(self, start, end, max):
self.start, self.end, self.max = start, end, max
self.left, self.right = None, None
""" class Solution:
# @oaram A: a list of integer
# @return: The root of Segment Tree
def build(self, A):
# write your code here
return self.buildX(0,len(A) - 1,A)
def buildX(self,start,end,A):
if start > end:
return None
maxX = 0
root = SegmentTreeNode(start,end)
if start != end:
mid = int((start + end)/2)
root.left = self.buildX(start,mid,A)
root.right = self.buildX(mid+1,end,A)
root.max = max(root.left.max,root.right.max)
else:
root.max = A[start]
return root
Python Code
总耗时: 750 ms
lintcode :Segmemt Tree Build II的更多相关文章
-
[LintCode] Segment Tree Build II 建立线段树之二
The structure of Segment Tree is a binary tree which each node has two attributes startand end denot ...
-
lintcode :Coins in Line II 硬币排成线 II
题目 硬币排成线 II 有 n 个不同价值的硬币排成一条线.两个参赛者轮流从左边依次拿走 1 或 2 个硬币,直到没有硬币为止.计算两个人分别拿到的硬币总价值,价值高的人获胜. 请判定 第一个玩家 是 ...
-
lintcode:最大子数组II
题目 最大子数组 II 给定一个整数数组,找出两个不重叠子数组使得它们的和最大. 每个子数组的数字在数组中的位置应该是连续的. 返回最大的和. 样例 给出数组[1, 3, -1, 2, -1, 2], ...
-
lintcode:Binary Tree Postorder Traversal 二叉树的后序遍历
题目: 二叉树的后序遍历 给出一棵二叉树,返回其节点值的后序遍历. 样例 给出一棵二叉树 {1,#,2,3}, 1 \ 2 / 3 返回 [3,2,1] 挑战 你能使用非递归实现么? 解题: 递归程序 ...
-
lintcode :Binary Tree Preorder Traversal 二叉树的前序遍历
题目: 二叉树的前序遍历 给出一棵二叉树,返回其节点值的前序遍历. 样例 给出一棵二叉树 {1,#,2,3}, 1 \ 2 / 3 返回 [1,2,3]. 挑战 你能使用非递归实现么? 解题: 通过递 ...
-
439. Segment Tree Build II
最后更新 08-Jan-2017 开始介绍线段树的主要作用了,可以快速在区间查找极值,我猜是这样的..... 一个NODE的最大值取决于它左边和右边最大值里大 按个,所以,所以什么?对了,我们该用po ...
-
Segment Tree Build I &; II
Segment Tree Build I The structure of Segment Tree is a binary tree which each node has two attribut ...
-
Lintcode247 Segment Tree Query II solution 题解
[题目描述] For an array, we can build a Segment Tree for it, each node stores an extra attribute count t ...
-
[Locked] Closest Binary Search Tree Value &; Closest Binary Search Tree Value II
Closest Binary Search Tree Value Given a non-empty binary search tree and a target value, find the ...
随机推荐
-
[转]ThinkPHP中实例化对象M()和D()的区别,select和find的区别
1.ThinkPHP中实例化对象M()和D()的区别 在实例化的过程中,经常使用D方法和M方法,这两个方法的区别在于M方法实例化模型无需用户为每个数据表定义模型类,如果D方法没有找到定义的模型类,则会 ...
-
【效率】专为Win7系统设计的极简番茄计时器 - MiniPomodoro (附源码)
时光飞逝,一转眼坚持使用番茄工作法已经快3年了!能坚持这么长时间,主要还是得益于它的简单.但是令人纠结的是,这么长时间以来,换了7款不同的番茄计时器,仍然没有找到非常满意的: ■ 机械的噪音太大,会妨 ...
-
set -x与set +x指令
转载自:http://www.2cto.com/os/201304/205118.html 参考: http://blog.csdn.net/t0nsha/article/details/860688 ...
-
BZOJ 2424: [HAOI2010]订货 费用流
2424: [HAOI2010]订货 Description 某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月 ...
-
SQLite支持的SQL数据操作
事务处理 Posted on 2013 年 1 月 1 日 by 林溪 事务为一组SQL命令的集合,这些SQL命令在执行时不可进行分割,即要么全部执行这些SQL命令,要么一个都不进行执行,事务操作 ...
-
转发:python 装饰器--这篇文章讲的通俗易懂
转 http://www.cnblogs.com/wupeiqi/articles/4980620.html 1.必备 #### 第一波 #### def foo(): print 'foo' ...
-
将本地项目部署到github远程仓库
近期写了一些项目,想把项目代码保存并分享出来,所以就想到了github. 下面就为大家介绍部署过程: 安装git客户端,请大家百度自行下载,这里就不做介绍了. 注册github账号,这个很简单,这里就 ...
-
Generative Adversarial Nets[content]
0. Introduction 基于纳什平衡,零和游戏,最大最小策略等角度来作为GAN的引言 1. GAN GAN开山之作 图1.1 GAN的判别器和生成器的结构图及loss 2. Condition ...
-
vue学习之三常用命令
一.插值 1.1 +号运用 <!DOCTYPE html> <html lang="en"> <head> <meta charset=& ...
-
delphi中使用MSWINSCK.OCX控件
1.首先是把winsck控件导入到delphi中,就是导入一个ActiveX控件,步骤略过. 2.将导入的winsck控件拖入你的Form中. 3.对winsck进行基本设置(IP,Port). 4. ...