資訊專欄INFORMATION COLUMN
摘要：這道題目是篩選出數(shù)組中的最小值，存入新數(shù)組。因此，聯(lián)想到和系列的題目，對(duì)于的處理，使用線段樹(shù)是非常有效的方法。之前我們創(chuàng)建的線段樹(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), 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.
ExampleFor array [1,2,7,8,5], and queries [(1,2),(0,4),(2,4)], return [2,1,5]
ChallengeO(logN) time for each query
Note這道題目是篩選出Interval數(shù)組中的最小值，存入新數(shù)組。因此，聯(lián)想到Segment Tree Build和Segment Tree Query系列的題目，對(duì)于Interval的處理，使用線段樹(shù)是非常有效的方法。之前我們創(chuàng)建的線段樹(shù)，有max和count兩個(gè)properties。參照max這個(gè)參數(shù)，可以考慮在這道題增加一個(gè)min的參數(shù)，代表每個(gè)結(jié)點(diǎn)的最小值。
詳細(xì)思路見(jiàn)code。
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;
}
//創(chuàng)建新的樹(shù)結(jié)構(gòu)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;
}
}
//創(chuàng)建新的MinTreeNode
public MinTreeNode buildTree(int[] A, int start, int end) {
if (start > end) return null;
//下面四行語(yǔ)句是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);
//下面三行語(yǔ)句設(shè)置每個(gè)結(jié)點(diǎn)的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;
}
//最底層條件結(jié)構(gòu)
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));
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66195.html
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 ...
摘要：題目是要查詢到這個(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 ar...
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...
摘要：很簡(jiǎn)單的題目，不過(guò)要達(dá)到的時(shí)間，只能用前綴和的方法來(lái)做。法前綴和法推薦 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...
摘要：第一種方法是很早之前寫的，先對(duì)三角形兩條斜邊賦值，和分別等于兩條斜邊上一個(gè)點(diǎn)的和與當(dāng)前點(diǎn)的和。然后套用動(dòng)規(guī)公式進(jìn)行橫縱坐標(biāo)的循環(huán)計(jì)算所有點(diǎn)的，再遍歷最后一行的，找到最小值即可。 Problem Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen...
閱讀 2041·2021-11-19 11:37
閱讀 730·2021-11-11 16:54
閱讀 1180·2021-11-02 14:44
閱讀 3080·2021-09-02 15:40
閱讀 2384·2019-08-30 15:44
閱讀 971·2019-08-29 11:17
閱讀 1074·2019-08-26 14:06
閱讀 1568·2019-08-26 13:47
