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;}
};