23.日常算法

1. 最小绝对差

题目来源
给你个整数数组 arr，其中每个元素都 不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

每对元素对 [a,b] 如下：
a , b 均为数组 arr 中的元素
a < b
b - a 等于 arr 中任意两个元素的最小绝对差

示例 1：
输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int target = arr[1] - arr[0];
        vector<vector<int>> ret;
        int n = arr.size();
        for (int i = 1; i < n; i++){
            if (arr[i] - arr[i - 1] < target){
                target = arr[i] - arr[i - 1];
                ret.clear();
                ret.push_back({arr[i - 1], arr[i]});
            }else if (arr[i] - arr[i - 1] == target){
                ret.push_back({arr[i - 1], arr[i]});
            }
        }
        return ret;
    }
};

2. 至少有 K 个重复字符的最长子串

题目来源
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
如果不存在这样的子字符串，则返回 0。

示例 1：
输入：s = “aaabb”, k = 3
输出：3
解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。

class Solution {
public:
    int longestSubstring(string s, int k) {
        vector<int> hash(26);
        for (auto & x : s) ++hash[x - 'a'];
        for (int i = 0; i < s.size(); i++){
            if (hash[s[i] - 'a'] < k){
                int l = longestSubstring(s.substr(0, i), k);
                int r = longestSubstring(s.substr(i + 1), k);
                return max(l, r);
            }
        }
        return s.size();
    }
};