成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

[LintCode] Segment Tree Query I & Segment Tree

vibiu / 2937人閱讀

摘要：題目是要查詢(xún)到這個(gè)區(qū)間內(nèi)某一點(diǎn)的。值是從最底層的子節(jié)點(diǎn)值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。與所不同的是，對(duì)所給區(qū)間內(nèi)的元素個(gè)數(shù)求和，而非篩選。這樣就會(huì)出現(xiàn)的情況，視作本身處理。

Segment Tree Query Problem

For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end).

Design a query method with three parameters root, start and end, find the maximum number in the interval [start, end] by the given root of segment tree.

Example

For array [1, 4, 2, 3], the corresponding Segment Tree is:

                  [0, 3, max=4]
                 /             
          [0,1,max=4]        [2,3,max=3]
          /                 /         
   [0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]

query(root, 1, 1), return 4

query(root, 1, 2), return 4

query(root, 2, 3), return 3

query(root, 0, 2), return 4

Note

題目是要查詢(xún)start到end這個(gè)區(qū)間內(nèi)某一點(diǎn)的max。max值是從最底層的子節(jié)點(diǎn)max值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。

Solution 
public class Solution {
    public int query(SegmentTreeNode root, int start, int end) {
        if (root == null || end < root.start || start > root.end) return 0;
        if (root.start == root.end) return root.max;
        return Math.max(query(root.left, start, end), query(root.right, start, end));
    }
}
Segment Tree Query II Problem

For an array, we can build a SegmentTree for it, each node stores an extra attribute count to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)

Design a query method with three parameters root, start and end, find the number of elements in the in array"s interval [start, end] by the given root of value SegmentTree.

Example

For array [0, 2, 3], the corresponding value Segment Tree is:

                     [0, 3, count=3]
                     /             
          [0,1,count=1]             [2,3,count=2]
          /                        /            
   [0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]

query(1, 1), return 0

query(1, 2), return 1

query(2, 3), return 2

query(0, 2), return 2

Note

與Query I所不同的是，Query II對(duì)所給區(qū)間內(nèi)的元素個(gè)數(shù)求和，而非篩選。這樣就會(huì)出現(xiàn)start <= root.start && end >= root.end的情況，視作root本身處理。

Solution 
public class Solution {
    public int query(SegmentTreeNode root, int start, int end) {
        if (root == null || start > root.end || end < root.start) return 0;
        if (root.start == root.end || (start <= root.start && end >= root.end)) return root.count;
        return query(root.left, start, end) + query(root.right, start, end);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/66189.html

相關(guān)文章

  • [LintCode] Segment Tree Build &amp; Segment Tree B

    摘要：唯一需要注意的就是的賦值取左右子樹(shù)的的較大值，最后一層的獨(dú)立結(jié)點(diǎn)的為對(duì)應(yīng)數(shù)組中的值。 Segment Tree Build I Problem The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interv...

    honhon 評(píng)論0 收藏0

  • [LintCode] Segment Tree Modify

    摘要：和其它題目一樣，依然是遞歸的做法。注意若樹(shù)的結(jié)點(diǎn)范圍為，那么至少有個(gè)數(shù)在左子樹(shù)上，所以語(yǔ)句里用了號(hào)。另外，最后一句是調(diào)用遞歸之后的結(jié)果，必須寫(xiě)在最后面。 Problem For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this nodes i...

    CoffeX 評(píng)論0 收藏0

  • [LintCode] Interval Minimum Number

    摘要：這道題目是篩選出數(shù)組中的最小值，存入新數(shù)組。因此，聯(lián)想到和系列的題目，對(duì)于的處理，使用線(xiàn)段樹(shù)是非常有效的方法。之前我們創(chuàng)建的線(xiàn)段樹(shù)，有和兩個(gè)。參照這個(gè)參數(shù)，可以考慮在這道題增加一個(gè)的參數(shù)，代表每個(gè)結(jié)點(diǎn)的最小值。 Problem Given an integer array (index from 0 to n-1, where n is the size of this array),...

    taowen 評(píng)論0 收藏0

  • 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線(xiàn)段樹(shù)（SegmentTree）

    摘要：示例解題代碼注意，如果要在上提交解答，必須把接口和類(lèi)的代碼一并提交，這里并沒(méi)有在寫(xiě)類(lèi)中 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線(xiàn)段樹(shù)（SegmentTree） 一、什么是線(xiàn)段樹(shù) 1.最經(jīng)典的線(xiàn)段樹(shù)問(wèn)題：區(qū)間染色有一面墻，長(zhǎng)度為n，每次選擇一段墻進(jìn)行染色，m次操作后，我們可以看見(jiàn)多少種顏色？m次操作后，我們可以在[i, j]區(qū)間內(nèi)看見(jiàn)多少種顏色？showImg(https://segmentfau...

    waltr 評(píng)論0 收藏0

  • 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線(xiàn)段樹(shù)（SegmentTree）

    摘要：示例解題代碼注意，如果要在上提交解答，必須把接口和類(lèi)的代碼一并提交，這里并沒(méi)有在寫(xiě)類(lèi)中 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線(xiàn)段樹(shù)（SegmentTree） 一、什么是線(xiàn)段樹(shù) 1.最經(jīng)典的線(xiàn)段樹(shù)問(wèn)題：區(qū)間染色有一面墻，長(zhǎng)度為n，每次選擇一段墻進(jìn)行染色，m次操作后，我們可以看見(jiàn)多少種顏色？m次操作后，我們可以在[i, j]區(qū)間內(nèi)看見(jiàn)多少種顏色？showImg(https://segmentfau...

    shaonbean 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<