专栏首页Don的成长史字符串长度最大乘积

字符串长度最大乘积

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/95098742

题目描述:

已知一个字符串数组words,要求寻找其中两个没有重复字符的字符串,使得这两个字符串的长度乘积最大,输出这个最大的乘积。如:

words=["abcd","wxyh","defgh"], 其中不包含重复字符的两个字符串是"abcd"和"wxyh",则输出16

words=["a","aa","aaa","aaaa"], 找不到满足要求的两个字符串,则输出0

输入描述:

Input:

["a","ab","abc","cd","bcd","abcd"]

输出描述:

Output:

4

输入样例1:

["a","ab","abc","cd","bcd","abcd"]

输出样例1:

4

说明:

Input中,不包含相同字符的有两对

"ab"和"cd"

"a"和"bcd"

所以字符串长度乘积的最大值是4

解题思路:

快手校招题。无脑暴力破解。先根据引号来分割单词(暂且称引号中的字符串为单词吧)并将它们放入vector中。自定义函数fun用于判断俩个字符串中有无重复字符,若有重复字符则返回0,否则返回这俩个字符串的长度乘积,这部分我是用set来实现的。好起来啦,ans初始化为0,然后开始双层for循环无脑比较,不停地更新最大值ans,最后输出ans即可。

AC代码:

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

int fun(string s1,string s2)    //判断俩个字符串中有无重复字符,若有重复字符则返回0,否则返回这俩个字符串的长度乘积
{
    set<char> s;
    for(auto it : s1)
    {
        if(s.count(it) == 0)
        {
            s.insert(it);
        }
        else
        {
            return 0;
        }
    }
    for(auto it : s2)
    {
        if(s.count(it) == 0)
        {
            s.insert(it);
        }
        else
        {
            return 0;
        }
    }
    int ans = s1.length()*s2.length();
    return ans;
}

int main()
{
    string str;
    getline(cin,str);
    vector<string> v;
    //分割字符串得到单词
    for(int i = 0; i < str.length(); i++)
    {
        if(str[i] == '"')
        {
            string word = "";
            i++;
            while(str[i] != '"')
            {
                word += str[i];
                i++;
            }
            //cout << word << endl;
            v.push_back(word);
        }
    }
    //暴力破解
    int ans = 0;   //输出结果,最大值
    for(int i = 0; i < v.size(); i++)
    {
        for(int j = i+1; j < v.size(); j++)
        {
            ans = max(ans,fun(v[i],v[j]));
        }
    }
    cout << ans << endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【PAT乙级】单身狗

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【GPLT】L2-008 最长对称子串

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 小易的字典

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • Leetcode 169 多数元素

    给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    glm233
  • Good Bye 2018 A. New Year and the Christmas Ornament(水题)

    题目链接:http://codeforces.com/contest/1091/problem/A

    Ch_Zaqdt
  • 大数据计算的基石——MapReduce

    Google File System提供了大数据存储的方案,这也为后来HDFS提供了理论依据,但是在大数据存储之上的大数据计算则不得不提到MapReduce。

    实时计算
  • 什么是窄带物联网(NB-IoT)?

    随着数十亿设备在不久的将来上线,我们将需要能够支持它们的无线网络。窄带物联网(NB-IoT)是否是解决方案?

    用户4122690
  • Linux ftp服务器(3):匿名登录

    实名登录有弊端,除了需要知道密码外,登录后可以任意目录切换,可以看到服务器里的很多内容,存在安全隐患。 ftp +服务器IP 用户名:anonymous ...

    Y大宽
  • 一个占据SAP BSP应用占据存储空间的小工具

    Today one of my colleague asks me whether there is some tool which can allow us ...

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券