一道看似简单的找重题难倒了7年开发经验的老程序员和99.9%程序员
本帖最后由 futureflsl 于 2019-11-11 11:12 编辑题目如下：
请用任意一门编程语言实现如下函数：
输入三个数字文本（文本长度可能不同也可能相同），找出三个数字文本中相同的数字最长组合，且组合后的文本顺序必须在原文本中保持位置不变且长度必须>=2，如果有多个相同长度的组合文本输出一个即可。不满足条件输出为空。例如有以下三个文本
（1）输入132,123,112233则输出为13或者12都可以
（2）输入1523,123,112233则输出为123
（3）输入172853,8516623,053122883则输出为123
（4）输入123,132,321则输出为空
（5）输入123,132,3212则输出为12
（6）输入64532,8366252183,5266435412则输出为652
（7）输入132,123,112233则输出为12或者13，不能是123因为第一个132中3和2顺序必须保持前后关系，也不能是132因为后面都是2在前3在后
我试了很多方法均告失败，确实很难！目前还没方法解决
没看懂？解释一下就是找出3个文本中数字相同的，并且数字在原来文本位置和组合后的文本保持一致，比如123和132，组合输出为12或者13，其中1和2在原来2个文本中1在前2在后，组合后也要保持这种位置前后关系 这个题好难啊，不会 第五个第六个的输出不是很理解，第五个看最后一个数字，1在3212的第一个2的后面，你输出12是不是不对，第六个也类似 我看都看不懂{:301_1005:} 给个思路，以第五题为例：123,132,3212
A=123
B=132
C=3212均视为字符串，而非数字
设置长度L>=2，开始计数：
当L=2时，
A={12,23,13}
B={13,12,32}
C={32,21,12,31,22}
用A,B,C的L=2的字符碰撞，可得出 12 or 13
当L=L+1=3时，
A={123}
B={132}
C={321,212,312}
用A,B,C的L=2的字符碰撞，可得出 NULL
当结果=NULL时，上一步L=2的结果为最终解输出，若仍为NULL则循环直至L=2也为NULL时则输出无解。 来自OIer的回复：
LCS水题，dp求解，不会请戳:
http://huzpsb.cf/build/index.php/archives/9/ 题都读不懂 第一个为什么不是123 题目都看不懂...... ```
static IEnumerable<string> FindSub(string str, int len)
{
if (str == null || str.Length < len)
{
yield break;
}
if (len == 1)
{
foreach (var c in str)
{
yield return c.ToString();
}
yield break;
}
if (len == str.Length)
{
yield return str;
yield break;
}
for (int i = 0; i <= str.Length - len; i++)
{
var c = str;
foreach (var sub in FindSub(str.Substring(i + 1), len - 1))
{
yield return c + sub;
}
}
}
static bool Contains(string find, string str)
{
if (find == null || str == null || find.Length == 0 || str.Length == 0)
{
return false;
}
if (find.Length > str.Length)
{
return false;
}
int cur = 0;
for (int i = 0; i < find.Length; i++)
{
var index = str.IndexOf(find, cur);
if (index < 0)
{
return false;
}
cur = index + 1;
}
return true;
}
static string[] FindMax(string[] array)
{
var result = new List<string>();
if (array == null) { return result.ToArray(); }
array = array.Where(e => e != null && e.Length >= 2).OrderBy(e => e.Length).ToArray();
if (array.Length < 2) { return result.ToArray(); }
var item = array;
for (int newLen = item.Length; newLen >= 2; newLen--)
{
foreach (var sub in FindSub(item, newLen))
{
var match = true;
for (var index = 1; index < array.Length; index++)
{
if (!Contains(sub, array))
{
match = false;
break;
}
}
if (match)
{
result.Add(sub);
}
}
if (result.Count > 0)
{
return result.ToArray();
}
}
return result.ToArray();
}
public static void Main(string[] args)
{
var items = @"[
[""132"",""123"",""112233""],
[""1523"",""123"",""112233""],
[""172853"",""8516623"",""053122883""],
[""123"",""132"",""321""],
[""123"",""132"",""3212""],
[""64532"",""8366252183"",""5266435412""],
[""132"",""123"",""112233""]
]";
var arrays = JsonConvert.DeserializeObject<string[][]>(items);
foreach (var array in arrays)
{
Console.WriteLine($"{string.Join(",", array)} => {string.Join(",", FindMax(array))}");
}
Console.ReadLine();
}
```
页:
[1]