vlambda博客
学习文章列表

【每日编程-449期】Leetcode.910.最小差值II



910.最小差值II




给定一个整数数组 A,对于每个整数 A[i],我们可以选择 x = -K 或是 x = K,并将 x 加到 A[i] 中。
在此过程之后,我们得到一些数组 B。
返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

样例一:

输入:A = [1], K = 0
输出:0
解释:B = [1]

样例二:

输入:A = [0,10], K = 2
输出:6
解释:B = [2,8]

样例三:

输入:A = [1,3,6], K = 3

输出:3解释:B = [4,6,3]


解决方法:

(1)算法的基本思想:

想法


如 最小差值 I 问题的解决方法,较小的 A[i] 将增加,较大的 A[i] 将变小。


算法


我们可以对上述想法形式化表述:如果 A[i] < A[j],我们不必考虑当 A[i] 增大时 A[j] 会减小。这是因为区间 (A[i] + K, A[j] - K) 是 (A[i] - K, A[j] + K) 的子集(这里,当 a > b 时 (a, b) 表示 (b, a) )。


这意味着对于 (up, down) 的选择一定不会差于 (down, up)。我们可以证明其中一个区间是另一个的子集,通过证明 A[i] + K 和 A[j] - K 是在 A[i] - K 和 A[j] + K 之间。


对于有序的 A,设 A[i] 是最大的需要增长的 i,那么 A[0] + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K 就是计算结果的唯一值。


作者:LeetCode

链接:https://leetcode-cn.com/problems/smallest-range-ii/solution/zui-xiao-chai-zhi-ii-by-leetcode/

来源:力扣(LeetCode)

(2)代码实现:

  
    
    
  
class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        int N = A.size();
        sort(A.begin(),A.end());
        int ans = A[N-1]- A[0];

        for (int i = 0; i < A.size() - 1; ++i) {
            int a = A[i], b = A[i+1];
            int high = max(A[N-1] - K, a + K);
            int low = min(A[0] + K, b - K);
            ans = min(ans, high - low);
        }

        return ans;
    }
};

明日预告:Leetcode.1002.查找常用字符
给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。


你可以按任意顺序返回答案。

样例一:

输入:["bella","label","roller"]
输出:["e","l","l"]

样例二:

输入:["cool","lock","cook"]
输出:["c","o"]
提示:
  1. 1 <= A.length <= 100

  2. 1 <= A[i].length <= 100

  3. A[i][j] 是小写字母


class Solution {
public:
    vector<string> commonChars(vector<string>& A) {

    }
};