字符串长度最大乘积
字符串长度最大乘积
http://www.nowcoder.com/questionTerminal/480caa5ffd164ac8b71caaa6d0f4e6db
题目难度：二星
考察点：字符串、模拟
方法：模拟
1.分析：
根据题意，我们可以对这n个字符串进行枚举，即判断字符串两两是否有重复的字符，如果没有就计算两个字符串的长度乘积，将n^2个字符串的长度乘积求出来，然后比较输出最大值即可。有几个小坑点：
(1). 处理输入问题，因为这个题的输入是比较恶心的，所以我们需要专门的处理一下输入，即输入的是一个字符串，然后将""之内的字符串全部提取出来，保存在一个vector数组中，具体可以详见代码。
(2). 判断s1,s2两个字符串是否有重复字符，那么我们可以首先定义一个标志数组ok[26] ，然后对s1进行遍历，ok[s1[i]-'a'] = true;， 然后在对s2进行遍历，如果在s2中找到有相同字符即ok[s2[i]-'a'] = true;的话直接return 0，否则继续往下进行遍历，直到s2的字符全部遍历完毕，发现没有相同字符，return s1和s2的字符串长度之积。
举个例子： 有两个字符串s1 = "abc", s2 = "dea"
在对s1遍历完毕之后，那么在ok数组中的表示就是ok[0] = ok[1] = ok[2] = true，其余的都是false，然后在对s2进行遍历：
当遍历到第一个字符d时，发现ok['d'-'a'=3] = false，那么继续往下遍历，
当遍历到第一个字符d时，发现ok['d'-'a'=3] = false，那么继续往下遍历，
当遍历到第二个字符d时，发现ok['e'-'a'=4] = false，那么继续往下遍历，
当遍历到最后一个字符d时，发现ok['a'-'a'=0] = true，那么有相同字符，直接return 0。
(1). 输入字符串s
(2). 将字符串s进行处理，得到一个包含所有字符串的vector<string> a;
(3). 按照上述算法进行遍历，即i从1-n, j从1-n，得到两个字符串s[i]和s[j]的字符串长度之积，如果有相同字符，长度之积为0.，并比较最大值。
(4). 输出最大的字符串长度之积结果为ans。
2.复杂度分析：
时间复杂度：O(n^2)空间复杂度：O(26)
3.代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
vector<string> get_vector(string s) {
int i = 0, n = s.size();
vector<string> ans;
while(i < n) {
if(i<n && s[i++]=='"') {
string tmp = "";
while(i<n && s[i]!='"') tmp += s[i++];
ans.push_back(tmp);
i++;
}
}
return ans;
}
bool ok[26];
int get_ans(string s1, string s2) {
memset(ok, false, sizeof ok);
for(int i=0; i<s1.size(); i++) ok[s1[i]-'a'] = true;
for(int i=0; i<s2.size(); i++) if(ok[s2[i]-'a']) return 0;
return s1.size() * s2.size();
}
int main() {
string s; cin>>s;
vector<string> a = get_vector(s);
int ans = 0;
for(int i=0; i<a.size(); i++) {
for(int j=0; j<a.size(); j++) {
ans = max(ans, get_ans(a[i], a[j]));
}
}
cout<<ans<<endl;
return 0;
}
查看4道真题和解析
