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

ethernet 發布于2019-07-01 12:38 / 3471人閱讀

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

908. Smallest Range I 題目鏈接

908. Smallest Range I

題目分析

給定一個數組A和一個數字K，找到一個在-K和K之間的數字x并加到數組A中的每一個元素生成數組B，返回數組B中最大值和最小值之差最小的值。

思路

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

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

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

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

再遍歷每個元素。

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

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

第2個：3，-K<=-1<=K，3-1=2；

第3個：5，-K<=-3<=K，5-3=2；

第4個：4，-K<=-2<=K，4-2=2；

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

我們于是得到數組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);
    }
}

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

云服務器 GPU云服務器 Smallest 題解 oj題解 LeetCode

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

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

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

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

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

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

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

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

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

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

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

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

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