从最近对亚马逊的采访中，我发现了以下问题。我想不出一个有效的方法来解决它。
问题如下：
给定一个字符串数组，您需要在数组中字符串的所有可能排列中找到一个字符的最长运行序列。
输入：
ab
ba
aac
输出：
a,3
注意：从输入和输出集合来看，我认为各个字符串的排列是不用做的。
如果有人可以提供帮助，我将不胜感激。谢谢。
问问题
1859 次
6 回答
2
可爱的问题。如此多的极端案例。我猜这个面试问题的重点是看看你提出了多少极端案例。
我希望我没有错过任何一个。
字符序列可以通过两种方式解决这个问题：
1）它是一个内部字符序列（例如。adddddddddddddddddb）
2) 它是一个后缀、仅由该字符组成的整个字符串集合和一个前缀的连接。在这种情况下，任何字符串都不能使用超过一次，包括一个字符是同一字符串的后缀和前缀的情况。（为避免重复同质字符串，后缀和前缀必须严格；即不是整个字符串）。
案例 1 很简单。我们只需记住单个字符和序列长度，以及当前字符和序列长度。正如我们在字符串中读取的那样，如果当前字符/序列长度大于最大值，我们将替换最大值。我们不必担心它与案例 2 的计算冲突，因为它不会影响结果。
案例 2 的工作量更大。对于每个字符，我们需要保留一些数据。如果字母表很小，我们可以使用固定大小的数组，字母表中每个字符一个条目，或者我们可以使用字符哈希表。两者都是O(1)平均水平；由于我们要处理的字符数不能大于所有字符串中的字符总数，因此可以认为哈希表的大小要求为O(N). （实际上，它受字母大小的限制，所以就像固定大小的数组一样，存储需求在技术上是有限制的，O(1)但在 Unicode 的情况下，例如，常数相当大。）
现在，我们需要什么数据？只是重复单个字符的字符串很容易；我们需要这些字符串的总长度。因此，每次我们找到这样的字符串时，我们都可以将其长度添加到每个字符数据中条目的总长度成员中。
对于（严格的）后缀和前缀，我们似乎只需要为每个后缀和前缀维护一个最大长度。但是，如果我们遇到一个字符串，其前缀和后缀序列是相同的字符，并且这两个序列都比我们之前处理过的序列长，该怎么办？我们不能将字符串同时用作后缀和前缀。幸运的是，有一个简单的答案：我们保留三个值：maximum_prefix、maximum_suffix、maximum_sum。如果我们在读取一个单词后更新表格，结果发现同一个字符既是前缀又是后缀，我们将三个值更新如下：
maximum_sum = max(maximum_sum,
prefix_length + maximum_suffix,
suffix_length + maximum_prefix)
maximum_prefix = max(maximum_prefix, prefix_length)
maximum_suffix = max(maximum_suffix, suffix_length)
请注意，如果 prefix_length 或 suffix_length 为 0，则上述伪代码可以正常工作（如果有点浪费）。
因此，每个字符总共有四个值：homogenous_length, maximum_sum, maximum_prefix, maximum_suffix. 在扫描结束时，我们需要找到homogenous_length + maximum_sum最大的字符；我们可以通过简单地扫描字符表来做到这一点。
总处理时间是O(1)每个字符（对于初始扫描），即O(N)（其中N是问题中的字符总数，加上O(max(N, |A|))字符表的最终扫描（|A|是字母表的大小）；换句话说，O(N).空间要求如上所述。
于 2012-12-19T16:18:01.127 回答
0
#include <iostream>
using namespace std;
class alphabet
{
string str;
int chars[26];
public:
alphabet()
{
for(int i=0; i < 26 ; i++)
chars[i] = 0;
}
void initialize(string s)
{
str = s;
for(int pos=0 ; pos < s.length(); pos++)
chars[s[pos]-'a']++;
}
int getCount(int i)
{
return chars[i];
}
};
int main()
{
int n=3;
alphabet *arr = new alphabet[n];
arr[0].initialize("varun");
arr[1].initialize("ritl");
arr[2].initialize("hello");
int Max =0;
char MaxChar = ' ';
for(int i=0; i<n-1 ; i++)
{
for(int j=0; j<26; j++)
{
int m = arr[i].getCount(j)+ arr[i+1].getCount(j);
if(m > Max)
{
Max = m;
MaxChar = char('a' + j);
}
}
}
cout<<"Max Char = "<<MaxChar<<" "<<Max<<" times";
system("pause");
}
于 2013-04-20T17:49:19.293 回答
0
在一次采访中，我本可以想出解决这个问题的基本机制，但我无法在白板上写出完整的、无错误的解决方案。调试器拐杖。
无论如何，这是我在 C# 中的解决方案。
1.) 我定义了集合。
var set = new List<string>() { "ab", "ba", "aac" };
2.）我组装了一个通用方法来递归组装所有排列。
private static List<List<T>> GetPermutations<T>(List<T> values)
{
if (values.Count <= 1) return new List<List<T>>() { values };
var results = new List<List<T>>();
var perms = GetPermutations(values.Skip(1).ToList());
foreach (var perm in perms)
{
foreach (int i in Enumerable.Range(0, perm.Count + 1))
{
List<T> list = new List<T>();
list.AddRange(perm.Take(i));
list.Add(values[0]);
list.AddRange(perm.Skip(i));
results.Add(list);
}
}
return results;
}
3.) 我找到了集合的所有排列。
var perms = GetPermutations<string>(set);
4.) 我定义了一种在单个字符串中查找最长运行序列的方法。
private static string LongestRunningSequence(string s)
{
if (string.IsNullOrEmpty(s)) return null;
if (s.Length == 1) return s;
var seq = new Dictionary<char, int>();
char prev = s[0];
int counter = 0;
foreach (char cur in s)
{
if (cur == prev) // chars match
{
++counter; // increment counter
}
else // chars don't match
{
prev = cur; // store new char
counter = 1; // reset the counter
}
// store the higher number of characters in the sequence
if (!seq.ContainsKey(prev)) seq.Add(prev, counter);
else if (seq[prev] < counter) seq[cur] = counter;
}
char key = seq.Keys.First();
foreach (var kvp in seq)
{
if (kvp.Value > seq[key]) key = kvp.Key;
}
return string.Join("", Enumerable.Range(0, seq[key]).Select(e => key));
}
5.) 我定义了一个在字符串列表中找到最长运行序列的方法，利用了之前对单个字符串执行此操作的方法。
private static string LongestRunningSequence(List<string> strings)
{
string longest = String.Empty;
foreach (var str in strings)
{
var locallongest = LongestRunningSequence(str);
if (locallongest.Length > longest.Length) longest = locallongest;
}
return longest;
}
6.) 我将每个计算的排列表示为单个字符串的列表。
var strings = perms.Select(e => string.Join("", e)).ToList();
7.) 我将此列表传递给较早的方法，该方法在字符串列表中找到最长的运行序列。
LongestRunningSequence(strings); // returns aaa
于 2013-06-25T16:42:49.717 回答
0
第1步：需要维护4个长度为26的表--第一个跟踪字符串中最长前缀的长度--第二个跟踪字符串中最长后缀的长度--第三个跟踪完全由给定字符组成的字符串的总长度 --Fourth 跟踪中间最长的字符
第 2 步： -- 对 0 到 26 运行循环并添加 first[i]+second[i]+third[i] 并将它们存储在 sum[i] 中 --找到 sum[i] 和第四个表中的最大元素。--index 是字母（0 是 A），最大元素是长度
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int pre[26],su[26],single[26],middle[26],sum[26];
int getlength(char str[][10])
{
int i,j,n=3,counter=0,max=-1,index;
char c,p;
for(j=0;j<n;j++)
{
for(i=0;i<strlen(str[j]);i++)
{
if(i==0)
{
c=str[j][i];
counter++;
continue;
}
else if(i==strlen(str[j])-1&&c == str[j][i])
{
counter =0;
break;
}
else
{
if(c == str[j][i])
counter++;
else
break;
}
}
if(pre[toupper(c)-65]<counter)
pre[toupper(c)-65]=counter;
counter=0;
}
for(j=0;j<n;j++)
{
for(i=strlen(str[j])-1;i>=0;i--)
{
if(i==strlen(str[j])-1)
{
c=str[j][i];
counter++;
continue;
}
else if(i==0&&c == str[j][i])
{
counter =0;
break;
}
else
{
if(c == str[j][i])
counter++;
else
break;
}
}
if(su[toupper(c)-65]<counter)
su[toupper(c)-65]=counter;
counter=0;
}
for(j=0;j<n;j++)
{
for(i=strlen(str[j])-1;i>=0;i--)
{
if(i==strlen(str[j])-1)
{
c=str[j][i];
counter++;
continue;
}
else
{
if(c == str[j][i])
counter++;
else
{
counter=0;
break;
}
}
}
if(single[toupper(c)-65]<counter)
single[toupper(c)-65]=counter;
counter=0;
}
counter=0;
for(j=0;j<n;j++)
{
for(i=1;i<strlen(str[j])-1;i++)
{
if(i==1)
{
c=str[j][i];
counter++;
}
else
{
if(c == str[j][i])
{
counter++;
}
else
{
if(middle[toupper(c)-65]<counter)
middle[toupper(c)-65]=counter;
counter=1;
c=str[j][i];
}
}
}
counter=0;
}
for(i=0;i<26;i++)
{
sum[i]=pre[i]+su[i]+single[i];
if(sum[i]>max)
{
max=sum[i];
index=i;
}
}
for(i=0;i<26;i++)
{
if(middle[i]>max)
{
max=middle[i];
index=i;
}
}
printf("\n length %d index %d",max,index);
}
void main()
{
char arr[3][10]={"bbbb","dccccccar","vaa"};
getlength(arr);
}
于 2014-09-07T07:36:21.590 回答
0
您可以为此使用哈希图。最慢的算法是为每个字符串制作一个字符计数器的映射，然后找到最大值。
我也想知道更高级的算法
于 2012-12-19T11:55:27.757 回答
0
这是我天真的 Ruby 实现。我将尝试解释我是如何推理和实施它的。
在 Ruby 中，字符串不是可枚举的，因此 Ruby 不能像 Python 那样直接枚举它。这样str.chars.to_a就解决了。它将字符串转换为字符数组。
我的计划是计算一个字符在每个字符串中出现的次数。["ab", "ba", "ccc"]会变成[{"a"=>1, "b"=>1}, {"b"=>1, "a"=>1}, {"c"=>3}]. 然后我会添加每对连续的哈希/字典的出现次数。在此示例中，它将导致[{"a"=>2, "b"=>2}, {"b"=>1, "a"=>1, "c"=>3}]. 这个哈希数组中的最大值将代表最长的运行序列。
问题是一遍又一遍地包含相同字符的字符串会使这个算法失效。我对此的解决方案是检查这些类型的字符串，然后如果该字符串包含任何此类字符，则将它们与以下字符串连接。这是在方法中实现arr_of_chararr.each的max_running_sequence。
成对加法是用Hash#merge一个块来实现的，除了数组中只有一个元素的特殊情况。
最后我扫描哈希数组的最大值。
class Sequence_tester
def self.max_running_sequence(arr_of_chararr)
reduced = []
all_same_chars = []
arr_of_chararr.each do |str|
arr = str.chars.to_a
if arr.all? {|c| c == arr.first}
all_same_chars += arr
else
if !all_same_chars.empty?
if arr.any? {|c| c == all_same_chars.first}
arr += all_same_chars
else
reduced << count_char_occurrences(all_same_chars)
end
end
reduced << count_char_occurrences(arr)
all_same_chars.clear
end
end
if !all_same_chars.empty?
reduced << count_char_occurrences(all_same_chars)
end
max_seqs = reduced
if reduced.length > 1
max_seqs = reduced.each_cons(2).map do |pair|
pair.first.merge(pair.last) {|key, oldval, newval| oldval + newval}
end
end
longest_seq = max_seqs.map {|h| h.max_by {|kv| kv[1]} }.max_by {|a| a[1]}
end
def self.count_char_occurrences(arr)
arr.each_with_object(Hash.new(0)) {|o, h| h[o] += 1}
end
end
input = ["a", "b", "c"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["abc", "abb", "abc"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["ab", "ba", "ccc"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["ada", "dd", "dd", "eedd"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
输出：
a,1
b,3
c,3
d,7
于 2012-12-19T21:23:22.330 回答