第四题比较难，看题解用并查集做比较简单，但是我觉得难度在想到用并查集，可能是最近做题少所以想不到吧。
1 替换所有的问号
class Solution {
public:
string modifyString(string s) {
int n=s.size();
int last='a';
int cnt=1;
for(int i=0;i<n;i++){
if(s[i]=='?'){
s[i]=(last+1-'a')%26+'a';
if(i!=0){
while(s[i]==s[i-1])
s[i]=(s[i]+1-'a')%26+'a';
}
if(i!=n-1){
while(s[i]==s[i+1])
s[i]=(s[i]+1-'a')%26+'a';
}
last=s[i];
}
else
continue;
}
return s;
}
};
2 数的平方等于两数乘积的方法数
2.1 stl
class Solution {
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
map<long long,int> ma;
for (int i=0;i<nums1.size();i++){
for (int j=i+1;j<nums1.size();j++){
ma[1LL*nums1[i]*nums1[j]]++;
}
}
int res=0;
for (int i=0;i<nums2.size();i++){
res+=ma[1LL*nums2[i]*nums2[i]];
}
ma.clear();
for (int i=0;i<nums2.size();i++){
for (int j=i+1;j<nums2.size();j++){
ma[1LL*nums2[i]*nums2[j]]++;
}
}
for (int i=0;i<nums1.size();i++){
res+=ma[1LL*nums1[i]*nums1[i]];
}
return res;
}
};
2.2 粗暴一点
class Solution {
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
int ans=0;
if(nums1.size()<2&&nums2.size()<2){
return 0;
}
vector<long long>q1;
vector<long long>q2;
vector<long long>ch1;
vector<long long>ch2;
for(int i=0;i<nums1.size();i++){
q1.push_back((long long)nums1[i]*(long long)nums1[i]);
}
for(int i=0;i<nums2.size();i++){
q2.push_back((long long)nums2[i]*(long long)nums2[i]);
}
for(int i=0;i<nums1.size();i++)
for(int j=i+1;j<nums1.size();j++)
{
ch1.push_back((long long)nums1[i]*(long long)nums1[j]);
}
for(int i=0;i<nums2.size();i++)
for(int j=i+1;j<nums2.size();j++)
{
ch2.push_back((long long)nums2[i]*(long long)nums2[j]);
}
sort(q1.begin(),q1.end());
sort(q2.begin(),q2.end());
sort(ch1.begin(),ch1.end());
sort(ch2.begin(),ch2.end());
int i=0,j=0;
int cnt1=0,cnt2=0;
while(i<q1.size()&&j<ch2.size()){
if(q1[i]==ch2[j]){
cnt1++,cnt2++;
while(i+1<q1.size()&&q1[i+1]==q1[i])
{
cnt1++,i++;
}
while(j+1<ch2.size()&&ch2[j+1]==ch2[j])
{
cnt2++,j++;
}
i++,j++;
ans=ans+cnt1*cnt2;
cnt1=0,cnt2=0;
}
else if(q1[i]<ch2[j])
{
cnt1=0,cnt2=0;
i++;
}
else{
j++;
cnt1=0,cnt2=0;
}
}
i=0,j=0;
cnt1=0,cnt2=0;
while(i<q2.size()&&j<ch1.size()){
if(q2[i]==ch1[j]){
cnt1++,cnt2++;
while(i+1<q2.size()&&q2[i+1]==q2[i])
{
cnt1++,i++;
}
while(j+1<ch1.size()&&ch1[j+1]==ch1[j])
{
cnt2++,j++;
}
i++,j++;
ans=ans+cnt1*cnt2;
cnt1=0,cnt2=0;
}
else if(q2[i]<ch1[j])
{
i++;
}
else
j++;
}
return ans;
}
};
3 避免重复字母的最小删除成本
class Solution {
public:
int minCost(string s, vector<int>& cost) {
int temp=cost[0];
int ans=0;
for(int i=1;i<s.size();i++){
if(s[i]==s[i-1]){
if(temp>cost[i])
ans+=cost[i];
else
{
ans+=temp;
temp=cost[i];
}
}
else
temp=cost[i];
}
return ans;
}
};
4 保证图可完全遍历
并查集。
先跑一边公共边，统计保留边数量nums，再分别跑各自边剩下的数量numa，numb。去掉的边是有相同父亲的边。
当nums+numsb=n-1，说明恰好遍历。否则不能遍历
// 参考 wyj20154348 的题解
class Solution {
public:
int fa[100010];
int tempfa[100010];
int tfind(int x){
if (fa[x]==x) return x;
return fa[x]=tfind(fa[x]);
}
vector<vector<int>> edge[4];
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
for (int i=0;i<=n;i++) fa[i]=i;
for (int i=0;i<edges.size();i++){
edge[edges[i][0]].push_back(edges[i]);
}
int ans=0;
int numa=0,numb=0;
int num=0;
for (int i=0;i<edge[3].size();i++){
int rootu=tfind(edge[3][i][1]);
int rootv=tfind(edge[3][i][2]);
if (rootu==rootv){
ans++;
continue;
}
num++;
fa[rootu]=rootv;
}
numa=numb=num;
for (int i=0;i<=n;i++) tempfa[i]=fa[i];
for (int i=0;i<edge[2].size();i++){
int rootu=tfind(edge[2][i][1]);
int rootv=tfind(edge[2][i][2]);
if (rootu==rootv){
ans++;
continue;
}
numb++;
fa[rootu]=rootv;
}
for (int i=0;i<=n;i++) fa[i]=tempfa[i];
for (int i=0;i<edge[1].size();i++){
int rootu=tfind(edge[1][i][1]);
int rootv=tfind(edge[1][i][2]);
if (rootu==rootv){
ans++;
continue;
}
numa++;
fa[rootu]=rootv;
}
if (numa!=(n-1)||(numb!=n-1)) return -1;
return ans;
}
};