IT评测·应用市场-qidao123.com

标题: 力扣9.27 [打印本页]
作者: 知者何南    时间: 2024-9-28 16:32
标题: 力扣9.27
2516. 每种字符至少取 K 个

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回必要的 最少 分钟数；如果无法取到，则返回 -1 。
数据范围


分析

本题有良好的二分性子，对于某一个                                   t                              t                  t，小于                                   t                              t                  t的分钟都无法满足，大于等于t的都可以满足，因此可以考虑二分答案
代码

  1. class Solution {
  2. public:
  3.     const static int N = 1e5 + 5;
  4.     int prea[N], preb[N], prec[N];
  5.     int lasta[N], lastb[N], lastc[N];
  6.     int n;
  7.     bool check(int t, int k) {
  8.         for(int i = 0; i <= t; i ++ ) {
  9.             int na = prea[i] + lasta[n - (t - i) + 1];
  10.             int nb = preb[i] + lastb[n - (t - i) + 1];
  11.             int nc = prec[i] + lastc[n - (t - i) + 1];
  12.             if(na >= k && nb >= k && nc >= k) return true;
  13.         }
  14.         return false;
  15.     }
  16.     int find(int l, int r, int k) {
  17.         while(l < r) {
  18.             int mid = (l + r) >> 1;
  19.             if(check(mid, k)) r = mid;
  20.             else l = mid + 1;
  21.         }
  22.         return l;
  23.     }
  24.     int takeCharacters(string s, int k) {
  25.         n = s.size();
  26.         for(int i = 1; i <= n; i ++ ) {
  27.             prea[i] = prea[i - 1] + (s[i  - 1] == 'a' ? 1 : 0);
  28.             preb[i] = preb[i - 1] + (s[i  - 1] == 'b' ? 1 : 0);
  29.             prec[i] = prec[i - 1] + (s[i  - 1] == 'c' ? 1 : 0);
  30.         }
  31.         for(int i = n; i >= 1; i -- ) {
  32.             lasta[i] = lasta[i + 1] + (s[i - 1] == 'a' ? 1 : 0);
  33.             lastb[i] = lastb[i + 1] + (s[i - 1] == 'b' ? 1 : 0);
  34.             lastc[i] = lastc[i + 1] + (s[i - 1] == 'c' ? 1 : 0);
  35.         }
  36.         if(prea[n] < k || preb[n] < k || prec[n] < k) return -1;
  37.         int l = 0, r = n;
  38.         int res = find(0, n, k);
  39.         return res;
  40.     }
  41. };
复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4