lintcode :Segmemt Tree Build II

时间:2022-09-21 13:38:06

题目

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 hasstart=(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的更多相关文章

  1. [LintCode] Segment Tree Build II 建立线段树之二

    The structure of Segment Tree is a binary tree which each node has two attributes startand end denot ...

  2. lintcode :Coins in Line II 硬币排成线 II

    题目 硬币排成线 II 有 n 个不同价值的硬币排成一条线.两个参赛者轮流从左边依次拿走 1 或 2 个硬币,直到没有硬币为止.计算两个人分别拿到的硬币总价值,价值高的人获胜. 请判定 第一个玩家 是 ...

  3. lintcode:最大子数组II

    题目 最大子数组 II 给定一个整数数组,找出两个不重叠子数组使得它们的和最大. 每个子数组的数字在数组中的位置应该是连续的. 返回最大的和. 样例 给出数组[1, 3, -1, 2, -1, 2], ...

  4. lintcode:Binary Tree Postorder Traversal 二叉树的后序遍历

    题目: 二叉树的后序遍历 给出一棵二叉树,返回其节点值的后序遍历. 样例 给出一棵二叉树 {1,#,2,3}, 1 \ 2 / 3 返回 [3,2,1] 挑战 你能使用非递归实现么? 解题: 递归程序 ...

  5. lintcode :Binary Tree Preorder Traversal 二叉树的前序遍历

    题目: 二叉树的前序遍历 给出一棵二叉树,返回其节点值的前序遍历. 样例 给出一棵二叉树 {1,#,2,3}, 1 \ 2 / 3 返回 [1,2,3]. 挑战 你能使用非递归实现么? 解题: 通过递 ...

  6. 439. Segment Tree Build II

    最后更新 08-Jan-2017 开始介绍线段树的主要作用了,可以快速在区间查找极值,我猜是这样的..... 一个NODE的最大值取决于它左边和右边最大值里大 按个,所以,所以什么?对了,我们该用po ...

  7. Segment Tree Build I & II

    Segment Tree Build I The structure of Segment Tree is a binary tree which each node has two attribut ...

  8. 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 ...

  9. [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 ...

随机推荐

  1. [转]ThinkPHP中实例化对象M()和D()的区别,select和find的区别

    1.ThinkPHP中实例化对象M()和D()的区别 在实例化的过程中,经常使用D方法和M方法,这两个方法的区别在于M方法实例化模型无需用户为每个数据表定义模型类,如果D方法没有找到定义的模型类,则会 ...

  2. 【效率】专为Win7系统设计的极简番茄计时器 - MiniPomodoro (附源码)

    时光飞逝,一转眼坚持使用番茄工作法已经快3年了!能坚持这么长时间,主要还是得益于它的简单.但是令人纠结的是,这么长时间以来,换了7款不同的番茄计时器,仍然没有找到非常满意的: ■ 机械的噪音太大,会妨 ...

  3. set -x与set +x指令

    转载自:http://www.2cto.com/os/201304/205118.html 参考: http://blog.csdn.net/t0nsha/article/details/860688 ...

  4. BZOJ 2424: [HAOI2010]订货 费用流

    2424: [HAOI2010]订货 Description 某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月 ...

  5. SQLite支持的SQL数据操作

    事务处理 Posted on 2013 年 1 月 1 日 by 林溪   事务为一组SQL命令的集合,这些SQL命令在执行时不可进行分割,即要么全部执行这些SQL命令,要么一个都不进行执行,事务操作 ...

  6. 转发:python 装饰器--这篇文章讲的通俗易懂

    转 http://www.cnblogs.com/wupeiqi/articles/4980620.html 1.必备 #### 第一波 #### def foo():     print 'foo' ...

  7. 将本地项目部署到github远程仓库

    近期写了一些项目,想把项目代码保存并分享出来,所以就想到了github. 下面就为大家介绍部署过程: 安装git客户端,请大家百度自行下载,这里就不做介绍了. 注册github账号,这个很简单,这里就 ...

  8. Generative Adversarial Nets[content]

    0. Introduction 基于纳什平衡,零和游戏,最大最小策略等角度来作为GAN的引言 1. GAN GAN开山之作 图1.1 GAN的判别器和生成器的结构图及loss 2. Condition ...

  9. vue学习之三常用命令

    一.插值 1.1 +号运用 <!DOCTYPE html> <html lang="en"> <head> <meta charset=& ...

  10. delphi中使用MSWINSCK&period;OCX控件

    1.首先是把winsck控件导入到delphi中,就是导入一个ActiveX控件,步骤略过. 2.将导入的winsck控件拖入你的Form中. 3.对winsck进行基本设置(IP,Port). 4. ...