国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Interval Minimum Number

taowen / 545人閱讀

摘要:這道題目是篩選出數組中的最小值,存入新數組。因此,聯想到和系列的題目,對于的處理,使用線段樹是非常有效的方法。之前我們創建的線段樹,有和兩個。參照這個參數,可以考慮在這道題增加一個的參數,代表每個結點的最小值。

Problem

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(1,2),(0,4),(2,4)], return [2,1,5]

Challenge

O(logN) time for each query

Note

這道題目是篩選出Interval數組中的最小值,存入新數組。因此,聯想到Segment Tree Build和Segment Tree Query系列的題目,對于Interval的處理,使用線段樹是非常有效的方法。之前我們創建的線段樹,有maxcount兩個properties。參照max這個參數,可以考慮在這道題增加一個min的參數,代表每個結點的最小值。
詳細思路見code。

Solution
public class Solution {
    public ArrayList intervalMinNumber(int[] A, 
                                                ArrayList queries) {
        ArrayList res = new ArrayList();
        if (A == null || queries == null) return res;
        MinTreeNode root = buildTree(A, 0, A.length-1);
        for (Interval i: queries) {
            res.add(getMin(root, i.start, i.end));
        }
        return res;
    }
    //創建新的樹結構MinTreeNode
    public class MinTreeNode {
        int start, end, min;
        MinTreeNode left, right;
        public MinTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public MinTreeNode(int start, int end, int min) {
            this(start, end);
            this.min = min;
        }
    }
    //創建新的MinTreeNode
    public MinTreeNode buildTree(int[] A, int start, int end) {
        if (start > end) return null;
        //下面四行語句是recursion的主體
        if (start == end) return new MinTreeNode(start, start, A[start]);
        MinTreeNode root = new MinTreeNode(start, end);
        root.left = buildTree(A, start, (start+end)/2);
        root.right = buildTree(A, (start+end)/2+1, end);
        //下面三行語句設置每個結點的min值
        if (root.left == null) root.min = root.right.min;
        else if (root.right == null) root.min = root.left.min;
        else root.min = Math.min(root.left.min, root.right.min);
        return root;
    }
    //獲得最小值min的子程序
    public int getMin(MinTreeNode root, int start, int end) {
        //空集和越界情況
        if (root == null || root.end < start || root.start > end) {
            return Integer.MAX_VALUE;
        }
        //最底層條件結構
        if (root.start == root.end || (start <= root.start && end >= root.end)) {
            return root.min;
        }
        //遞歸
        return Math.min(getMin(root.left, start, end), getMin(root.right, start, end));
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66195.html

相關文章

  • [LintCode] Minimum Adjustment Cost [Undone]

    Problem Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target. If the array before adjustment is A, the array after ...

    Aomine 評論0 收藏0
  • [LintCode] Segment Tree Query I & Segment Tree

    摘要:題目是要查詢到這個區間內某一點的。值是從最底層的子節點值里取最大值。因此,不用太復雜,遞歸就可以了。與所不同的是,對所給區間內的元素個數求和,而非篩選。這樣就會出現的情況,視作本身處理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

    vibiu 評論0 收藏0
  • [LintCode/LeetCode] Integer Replacement

    Problem Given a positive integer n and you can do operations as follow: 1.If n is even, replace n with n/2.2.If n is odd, you can replace n with either n + 1 or n - 1. What is the minimum number of re...

    fyber 評論0 收藏0
  • [LintCode] Interval Sum

    摘要:很簡單的題目,不過要達到的時間,只能用前綴和的方法來做。法前綴和法推薦 Problem Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each...

    kelvinlee 評論0 收藏0
  • [LintCode/LeetCode] Triangle

    摘要:第一種方法是很早之前寫的,先對三角形兩條斜邊賦值,和分別等于兩條斜邊上一個點的和與當前點的和。然后套用動規公式進行橫縱坐標的循環計算所有點的,再遍歷最后一行的,找到最小值即可。 Problem Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen...

    劉德剛 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<