24.日常算法

1. 数组中两元素的最大乘积

题目来源
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。

示例 1：
输入：nums = [3,4,5,2]
输出：12
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1) * (nums[2]-1) = (4-1) * (5-1) = 3 * 4 = 12 。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int i = nums.size() - 1;
        int j = i - 1;
        return (nums[i]-1)*(nums[j]-1);
    }
};

2. 替换后的最长重复字符

题目来源
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

示例 1：
输入：s = “ABAB”, k = 2
输出：4
解释：用两个’A’替换为两个’B’,反之亦然。

class Solution {
public:
    int characterReplacement(string s, int k) {
        int ret = 0;
        int left = 0, right = 0;
        int hash[26] = {0};
        int max_count = 0;
        while (right < s.size()){
            hash[s[right] - 'A']++;
            max_count = max(max_count, hash[s[right] - 'A']);
            // 不满足窗口大小中最多重复字母数+k < 窗口大小
            while (max_count + k < right - left + 1){
                hash[s[left] - 'A']--;
                ++left;
            }
            ret = max(ret, right - left + 1);
            ++right;
        }
        return ret;
    }
};