Leetcode PHP題解--D18 908. Smallest Range I

ethernet 發(fā)布于2019-07-01 12:38 / 3477人閱讀

摘要：再向上取整為。第個(gè)要向上方求到的靠攏，需要加。最大值和最小值之差為。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。

908. Smallest Range I 題目鏈接

908. Smallest Range I

題目分析

給定一個(gè)數(shù)組A和一個(gè)數(shù)字K，找到一個(gè)在-K和K之間的數(shù)字x并加到數(shù)組A中的每一個(gè)元素生成數(shù)組B，返回?cái)?shù)組B中最大值和最小值之差最小的值。

思路

根據(jù)題目，需要我們可以給數(shù)組A中的每一個(gè)元素添加-K<=x<=K中的任何一個(gè)整數(shù)，使新生成的數(shù)組B的最大值和最小值之差最小。

怎么使最大值和最小值之差最小呢？
最大值和最小值越接近中間值，最大值和最小值之差最小。

舉個(gè)例子：A = [-3, 1, 3, 5, 4, 6], K = 3

先求中間值：$mid = ceil((max($A)+min($A))/2)。(-3+6)/2再向上取整為2。

再遍歷每個(gè)元素。

第0個(gè)：-3要向上方求到的2靠攏，需要加2-(-3)=5。然而5>(K=3)。那么只能加K的最大值3了。-3+3=0；

第1個(gè)：1要向2靠攏，需要1，-K<=1<=K，1+1=2；

第2個(gè)：3，-K<=-1<=K，3-1=2；

第3個(gè)：5，-K<=-3<=K，5-3=2；

第4個(gè)：4，-K<=-2<=K，4-2=2；

第5個(gè)：6，-4<(-K=3)，取最小值-3，6-3=3。

我們于是得到數(shù)組B = [0,2,2,2,2,3]。最大值和最小值之差為3-0=3。

最終代碼

$K && $a>=$mid){
                $b[] = $a-$K;
            }
            else if($a-$mid<$K&&$a>=$mid){
                $b[] = $mid;
            }
            else if($mid-$a<$K && $a<$mid){
                $b[] =$mid;
            }
            else if($mid-$a>$K && $a<$mid){
                $b[] = $a+$K;
            }
        }
        return max($b)-min($b);
    }
}

若覺得本文章對你有用，歡迎用愛發(fā)電資助。

云服務(wù)器 GPU云服務(wù)器 Smallest 題解 oj題解 LeetCode

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/31131.html

相關(guān)文章

Leetcode PHP題解--D79 448. Find All Numbers…

摘要：題目鏈接題目分析給定一個(gè)到的數(shù)組，返回其中缺失的數(shù)字。思路用得出到的數(shù)字，再用和給定的數(shù)組計(jì)算差集。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D79 448. Find All Numbers Disappeared in an Array 題目鏈接 448. Find All Numbers Disappeared in an Array 題目分析給定一個(gè)1到n的數(shù)組，返回...

X1nFLY 2019-07-01 13:57 評論0 收藏0
Leetcode PHP題解--D71 788. Rotated Digits

摘要：題目鏈接題目分析當(dāng)一個(gè)數(shù)字度旋轉(zhuǎn)后，不等于原來的數(shù)字，那么我們稱它是一個(gè)好數(shù)字。和旋轉(zhuǎn)后為對方。思路用函數(shù)生成到給定數(shù)組之間的所有數(shù)組。對每一個(gè)數(shù)字，用和函數(shù)處理。對數(shù)字，轉(zhuǎn)換成。否則返回，排除當(dāng)前數(shù)字。 D71 788. Rotated Digits 題目鏈接 788. Rotated Digits 題目分析當(dāng)一個(gè)數(shù)字180度旋轉(zhuǎn)后，不等于原來的數(shù)字，那么我們稱它是一個(gè)好數(shù)字。例...

CntChen 2019-07-01 12:50 評論0 收藏0
Leetcode PHP題解--D10 942. DI String Match

摘要：題目鏈接題目分析給定一個(gè)只含和的字符串，返回一個(gè)數(shù)組。這個(gè)數(shù)組滿足以下條件當(dāng)為時(shí)，。當(dāng)遇到時(shí)，在數(shù)組的當(dāng)前下標(biāo)位置前插入當(dāng)前下標(biāo)。最終代碼個(gè)人認(rèn)為這題不是很好描述。有空會嘗試描述清楚這個(gè)問題。 942. DI String Match 題目鏈接 942. DI String Match 題目分析給定一個(gè)只含I和D的字符串S，返回一個(gè)數(shù)組。這個(gè)數(shù)組滿足以下條件：當(dāng)S[i]為I時(shí)...

yibinnn 2019-07-01 12:35 評論0 收藏0
Leetcode PHP題解--D52 496. Next Greater Element I

摘要：題目鏈接題目分析給定兩個(gè)數(shù)組，其內(nèi)元素不重復(fù)。數(shù)組是數(shù)組的子集，返回每個(gè)在數(shù)組中的元素在數(shù)組對應(yīng)位置以右最大的元素。思路只能逐個(gè)遍歷吧。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D52 496. Next Greater Element I 題目鏈接 496. Next Greater Element I 題目分析給定兩個(gè)數(shù)組，其內(nèi)元素不重復(fù)。數(shù)組1是數(shù)組2的子集，返回每個(gè)...

only_do 2019-07-01 12:44 評論0 收藏0
Leetcode PHP題解--D14 561. Array Partition I

摘要：題目鏈接題目分析本題給了一個(gè)數(shù)組，要求將數(shù)組分為個(gè)只有個(gè)元素的一對。因此，要使每組中最大的數(shù)字和最小的數(shù)組之差最小，這樣才能使損失最小。當(dāng)分為兩組時(shí)，每組取最小后，會得到。求和后為，比大。 561. Array Partition I 題目鏈接 561. Array Partition I 題目分析本題給了一個(gè)數(shù)組，要求將數(shù)組分為n個(gè)只有2個(gè)元素的一對。使得每對數(shù)字中最小的數(shù)加起...

stonezhu 2019-07-01 12:36 評論0 收藏0