題目鏈接

滑動(dòng)窗口

class Solution { public:int equalSubstring(string s, string t, int maxCost) {int n = s.size();int cost = 0;int left = 0;int ans = 0;for (int i = 0; i < n; ++i) {cost += abs(s[i] - t[i]);while (cost > maxCost) {cost -= abs(s[left] - t[left]);++left;}ans = max(ans, i - left + 1);}return ans;} }; class Solution { public:int equalSubstring(string s, string t, int maxCost) {int n = s.size();int cost = 0;int left = 0;for (int i = 0; i < n; ++i) {cost += abs(s[i] - t[i]);if (cost > maxCost) { // 保證當(dāng)前為最長(zhǎng)值cost -= abs(s[left] - t[left]);++left;}}return n - left;} };

前綴和 + 二分

class Solution { public:int equalSubstring(string s, string t, int maxCost) {int n = s.size();vector<int> cost(n, 0);for (int i = 0; i < n; ++i) {cost[i] = (i ? cost[i-1] : 0) + abs(s[i] - t[i]);}int ans = 0;for (int i = 0; i < n; ++i) {int l = i, r = n - 1;while (l <= r) {int mid = l + (r - l) / 2;int tmp = cost[mid] - cost[i] + abs(s[i] - t[i]);if (tmp <= maxCost) {l = mid + 1;}else {r = mid - 1;}}ans = max(ans, r - i + 1);}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的滑动窗口/二分 - 尽可能使字符串相等的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。