每日一题 21-2
888. 公平的糖果棒交换
分类：数组
排序后二分
class Solution {
public:
int binarySearch(vector<int>& B, int t){
int l=0, r=B.size();
while(l<r){
int mid = (l+r) >> 1;
if(B[mid] > t){
r = mid;
}else if(B[mid] < t){
l = mid+1;
}else{
return mid;
}
}
return -1;
}
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
int sum1 = accumulate(A.begin(), A.end(), 0);
int sum2 = accumulate(B.begin(), B.end(), 0);
sort(B.begin(), B.end());
int avg = (sum1 + sum2) / 2 ;
for(int i=0; i<A.size(); i++){
// a[i] + sum2 - b[j] == avg 则交换后相等
int j = binarySearch(B, A[i]+sum2-avg);
if(j!=-1){
return {A[i], B[j]};
}
}
return {0, 0};
}
};/* 99% **/
2021/02/01
424. 替换后的最长重复字符
分类：滑动窗口
class Solution {
public:
int characterReplacement(string s, int k) {
int mostCharCnt = 0, left, right;
vector<int> cnt(26, 0); //用一个hash记录窗口内字符的出现次数
for(left=0, right=0; right<s.size(); right++){
int index = s[right]-'A';
mostCharCnt = max(mostCharCnt, ++cnt[index]); //记录窗口内单个字符出现的最多次数
if(right+1 - left > mostCharCnt+k){ //区间右移
cnt[s[left]-'A']--;
left++;
}
}
return s.size() - left; //因为区间不会收缩，所以遗留下来的区间长度就是最长那啥
}
};
2021/02/02
643. 子数组最大平均数 I
分类：滑动窗口
维护下窗口长度的子数组和就行
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
nums.push_back(0); //不会对结果产生影响，但是方便循环
int maxsum = -3e8, i=0, j=0, currentsum=0;
while(j < k) currentsum += nums[j++];
for(; j<nums.size(); j++, i++){
maxsum = max(maxsum, currentsum);
currentsum-=nums[i];
currentsum+=nums[j];
}
return maxsum*1.0/k;
}
};/* 84.9% **/
2021/02/04
1208. 尽可能使字符串相等
分类：滑动窗口
保证窗口不会收缩，留下的长度就是最大长度
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int i=0, j=0, mv=0;
vector<int> need2mv(s.size());
for(; j<s.size(); j++){
need2mv[j] = abs(s[j]-t[j]);
mv += need2mv[j];
if(mv > maxCost){
mv -= need2mv[i];
i++;
}
}
return s.size() - i;
}
};/* 98.6% **/
2021/02/05
1423. 可获得的最大点数
分类：前缀和
无论怎么选，最终结果都是前i个与后k-i个的和；可以通过逐步增加后k-i个的数量来遍历所有结果
class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int preSum = 0, postSum = 0;
for(int i=0; i<k; i++) preSum += cardPoints[i];
int ans = preSum;
for(int i=k-1, j=cardPoints.size()-1; i>-1; i--, j--){
preSum -= cardPoints[i];
postSum += cardPoints[j];
ans = max(ans, preSum+postSum);
}
return ans;
}
};/* 87.2% **/
class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int preSum = 0;
int n = cardPoints.size();
for(int i=0; i<k; i++) preSum += cardPoints[i];
int ans = preSum;
for(int i=k-1; i>-1; i--){
preSum = preSum - cardPoints[i] + cardPoints[n+i-k];
ans = max(ans, preSum);
}
return ans;
}
};/* 100% */
2021/02/06
665. 非递减数列
分类：数组
如果在i处出现了”下落“，可以进行的修改有
- 降低前一个数
- 提高这一个数
修改时优先降低前一个数并保持前面序列满足，因为这样不会对数组后面的部分产生影响。同理，只写出提高这一个数，对后续产生了影响的情况。
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
for(int i=1; i<nums.size(); i++){
if(nums[i-1] > nums[i]){
count+=1;
if(i> 1 && nums[i-2] > nums[i]){ //3 4 2 5
nums[i] = nums[i-1];
}
// 后续遍历已经不会涉及到对nums[i-1]的查看，假装完成了修改
// else{ //1 4 2 3
// nums[i-1] = nums[i];
// }
}
}
return count<2;
}
};
2021/02/07
978. 最长湍流子数组
分类：滑动窗口
不喜欢这种题
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int left = -1;
int i=0, j=1, ans=1;
for(; j<arr.size(); j++){
if(arr[j-1] < arr[j]){
if(left == 1) {
ans = max(ans, j-i);
i = j-1;
}
left = 1;
}else if(arr[j-1] > arr[j]){
if(left == 0){
ans = max(ans, j-i);
i = j-1;
}
left = 0;
}else{
ans = max(ans, j-i);
i = j;
left = -1;
}
}
return max(ans, j-i);
}
};/* 86.9% **/
2021/02/08
567. 字符串的排列
分类：滑动窗口
如果s2窗口内的每个字母的出现次数与s1完全符合，那么ok
特例：s1 > s2，必然不会出现子串
class Solution {
public:
bool chk(string& s1, vector<int>& s1Map, vector<int>& s2Map){
for(char& c : s1) if(s1Map[c-'a'] != s2Map[c-'a']) return false;
return true;
}
bool checkInclusion(string s1, string s2) {
if(s1.size() > s2.size()) return false;
vector<int> s1Map(26, 0), s2Map(26, 0);
int windowSize = s1.size(), i=0, j=0;
for(char& c : s1) s1Map[c-'a']+=1;
for(;j<windowSize; j++) s2Map[s2[j]-'a']+=1;
if(chk(s1, s1Map, s2Map)) return true;
while(j<s2.size()){
s2Map[s2[i++]-'a']-=1;
s2Map[s2[j++]-'a']+=1;
if(chk(s1, s1Map, s2Map)) return true;
}
return false;
}
};/* 91.8% **/
2021/02/10
703. 数据流中的第 K 大元素
分类：堆
维护一个从小到大，大小为k的优先队列，队列的第一个元素就是第k大元素。
可以用小顶堆实现，可以用STL实现
class KthLargest {
private:
priority_queue<int, vector<int>, greater<int>> q;
int size;
public:
KthLargest(int k, vector<int>& nums) {
size = k;
for(int &num : nums) q.push(num);
while(q.size() > size) q.pop();
}
int add(int val) {
q.push(val);
if(q.size() > size) q.pop();
return q.top();
}
};
2021/02/11
448. 找到所有数组中消失的数字
分类：数组，哈希？
将值转换为下标，下标对应的数值+=n（一个原数组不可能出现的值）
扫描一遍数组，数值没能大于n的下标即是没有出现的值（因为没有值被转换为这个下标）
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
for(int& num : nums) nums[(num-1)%n] += n;
vector<int> ans;
for(int i=0; i<n; i++) if(nums[i] <= n) ans.push_back(i+1);
return ans;
}
};
2021/02/13
485. 最大连续1的个数
分类：滑动窗口
这题挺标准的，记录一下维护区间起止和维护区间长度的两种写法
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int i=0, j=0, ans=0;
for(; j<nums.size(); j++){
if(nums[j] != 1) {
ans = max(ans, j-i);
i = j+1;
}
}
ans = max(ans, j-i);
return ans;
}
};
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int cnt=0, maxcnt=0, ans=0;
for(int i=0; i<nums.size(); i++){
if(nums[i] != 1) {
maxcnt = max(maxcnt, cnt);
cnt=0;
}else{
cnt++;
}
}
maxcnt = max(maxcnt, cnt);
return maxcnt;
}
};
2021/02/15
561. 数组拆分 I
分类：数组
每一对数字选一个最小的出来，能够形成的最大和。即排序后的奇数项（这个项在自己对中是最小的，却又比前一对中最大的大
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int sum = 0;
for(int i=0; i<nums.size(); i+=2) sum += nums[i];
return sum;
}
};
2021/02/16