3.11 美团前端笔试 两道编程题AC解法

1、单拎一段重复字符的子串出来，发现规律，只要隔一个字符修改一下，次数是 floor(len / 2)，遍历累加即可，记得最后一段出循环也要计算

#include<bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  int l = 0;
  int ans = 0;
  for(int i = 1; i < s.length(); ++i) {
    if(s[i] == s[i-1])
      continue;
    else {
      int len = i - l;
      ans += len / 2;
      l = i;
    }
  }
  ans += (s.length() - l) / 2;
  cout << ans << endl;
  return 0;
} 

2、区间计数，要把区间端点存储成 [下标，左or右] 的形式，比如 [5, 0] 表示一个区间左端点在位置5，[6, 1] 表示一个区间的右端点在位置6。由此用一个数组记录每个区间端点按下标升序排序，如果下标相同就左端点排在前面。然后遍历每个区间端点，如果碰到左端点，重叠数++，碰到右端点就--；如果发现是最大重叠数就标记下位置，出了这个区间就结算以下覆盖长度；如果最大重叠数有更新，记得清空覆盖长度。

#include<bits/stdc++.h>
using namespace std;

int n, t;
int main() {
  cin >> n;
  vector<pair<int, int> > vec;
  for(int i = 0; i < n; ++i) {
    cin >> t;
    vec.push_back({t, 0});
  }
  for(int i = 0; i < n; ++i) {
    cin >> t;
    vec.push_back({t, 1});
  }
  sort(vec.begin(), vec.end());
  // depth 是当前区间深度，maxDep是最大的深度，cnt是最大深度覆盖的长度和，l是当前最大深度覆盖区间的左端点
  int depth = 0, maxDep = 0, cnt = 0, l = 0;
  for(int i = 0; i < vec.size(); ++i) {
    if(vec[i].second == 0) {	//	碰到左端点，深度+1
      depth++;
      if(depth > maxDep) {	//	找到了新的最深区间
      	cnt = 0; 
        maxDep = depth;
        l = vec[i].first;
      } else if(depth == maxDep) {
        l = vec[i].first;	//	第二次碰到最深区间，也记录左端点
      }
    } else {	//	碰到右端点，深度-1
      if(depth == maxDep) {
        cnt += vec[i].first - l + 1;
      }
      depth--;
    }
  }
  cout << maxDep << ' ' << cnt << endl;
  return 0;
}
/*
3
2 1 5
6 3 7
*/