字符串][模拟]leetcode1780:满足三条件之一需改变的最少字符数(medium)"/>
[字符串][模拟]leetcode1780:满足三条件之一需改变的最少字符数(medium)
题目:
题解:
- 按照题目的思路,进行枚举就行了。
代码如下:
class Solution {
public:// 让 A 中所有字符严格小于 B 中的所有字符int work(vector<int> cntA,vector<int> cntB){int res=INT_MAX;// 以字符i为边界,将A中A[i,'Z']的所有字符全部变成小于i的字符,将B中B['a',i-1]的所有字符变成大于i的字符// 边界不能取'a',因为这样A没有小于'a'的字符,无法转变;边界'z'是可以取到的for(int i=1;i<26;++i){int cnt=0;// 将A中A[i,'Z']的所有字符全部变成小于i的字符for(int j=i;j<26;++j)cnt+=cntA[j];// 将B中B['a',i-1]的所有字符变成大于i的字符for(int j=0;j<i;++j)cnt+=cntB[j];res=min(res,cnt);}return res;}int minCharacters(string a, string b) {// 统计 a b 中字符串的频率vector<int> cntA(26,0),cntB(26,0);for(auto c:a)cntA[c-'a']++;for(auto c:b)cntB[c-'a']++;int res=INT_MAX;int n=a.size(),m=b.size();// 计算条件3满足的情况:将字符串 a b,都变成字符c='a'+i// 那么需要改变的字符数=m+n-(cntA[c]+cntB[c]),因为字符c不要改变,只需要改变其他字符就行了for(int i=0;i<26;++i)res=min(res,m+n-(cntA[i]+cntB[i]));return min({res,work(cntA,cntB),work(cntB,cntA)});}
};
更多推荐
[字符串][模拟]leetcode1780:满足三条件之一需改变的最少字符数(medium)
发布评论