在排序的字符串中查找最长的重复字符

本文介绍了在排序的字符串中查找最长的重复字符的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想在排序的字符串中找到最长的重复字符。

class 程序 { 静态 字符串 input = aaaabbcddddddddddeeffffg; // 预期：d static void Main（ string [] args） { char [] c = input.ToCharArray（）; List< string> list = new List< string>（）; string temp = String .Empty; for （ int i = 1 ; i < c.Length - 1 ; i ++） { char curr = c [i]; char next = c [i + 1 ]; temp + = curr.ToString（）; if （curr！= next） { list.Add（temp）; temp = next.ToString（）; } } Console.WriteLine（list.OrderByDescending（n = > n.Length）。 （）[ 0 ]）; Console.WriteLine（ 按任意键......）; Console.ReadKey（）; } }

我的代码有两个缺陷。 1）它错过了最后一个字符。 2）它使用Linq并将块存储到列表中，因此可能效率不高。我希望有一种就地算法。 谢谢。

解决方案

数组为零 - 根据;从 i = 1 开始，你跳过一个元素。通过使用 c.Length - 1 ，您还可以跳过最后一个元素。您也不需要存储整个列表，只能存储最长的列表。使用 StringBuilder 比使用字符串连接更好。并且 temp = next.ToString（）; 行不应该存在，因为它会导致char被计数两次。

char [] c = input.ToCharArray（）; string longest = ; StringBuilder sb = new StringBuilder（）; for （ int i = 0 ; i < c.Length; i ++） { char curr = c [i]; char next = i！= c.Length - 1 ？ c [i + 1 ]：' \ 0' ; // 检查当前char是否是最后一个 sb.Append（curr）; if （curr！= next） { string temp = sb.ToString（）; if （temp.Length > longest.Length） { longest = temp; // 如果带有新字符的新字符串更长，则替换最长的字符串 } sb.Clear（）; // 清除StringBuilder } } Console.WriteLine（最长[ 0 ]）; Console.WriteLine（ 按任意键......）; Console.ReadKey（）;

上面的代码显示了如何使用 StringBuilder 没有LINQ。 为什么选择StringBuilder？看一下这篇文章： yoda.arachsys/csharp/stringbuilder.html [ ^ ]

引用：

当你在一个非平凡的循环中连接时，绝对使用StringBuilder - 如果你不确定的话，尤其是在编译时）你将通过循环进行多少次迭代。例如，一次读取一个文件，使用+ =运算符构建一个字符串可能会导致性能自杀。

这就是这种情况;我们不知道它会进行多少次迭代，因为这取决于输入。

我建​​议阅读这个帖子：计算一个字符 [ ^ ]。 我没有看到使用Linq的任何性能问题，除非字符串集是非常非常的很大。 这真的很快。以下查询在0.001秒内执行。

string input = aaaabbcddddddddddeeffffg; var qry =（ from c in 输入 group c by c into grp orderby grp.Count（）降序 选择 new { Character = grp.Key， Count = grp.Count（）} ）。取（ 1 ）; foreach （ var v in qry） { Console.WriteLine（ '{0}'计算{1}次，v.Character，v.Count）; }

结果：

'd'计算10次

这是一个只对字符进行计数并跟踪到目前为止看到的最长序列的解决方案。

class 计划 { 静态 string input = aaaabbcddddddddddeeffffg; // 预期：d static void Main（ string [] args） { var longest = FindLongestRepeat（输入）; Console.WriteLine（ Char {0} Count {1}，longest.Item1 ，longest.Item2）; Console.WriteLine（ 按任意键......）; Console.ReadKey（）; } 静态元组< char，int> FindLongestRepeat（ string str） { if （ string .IsNullOrEmpty（str）） return null ; char seqChar = str [ 0 ]; int seqCount = 1 ; char longChar = seqChar; int longCount = seqCount; for （ int i = 1 ; i < str.Length; i ++） { char c = str [i]; if （c！= seqChar） { seqChar = c; seqCount = 1 ; } else { ++ seqCount; if （c == longChar） { ++ longCount; } else if （seqCount > longCount） { longCount = seqCount; longChar = seqChar; } } } 返回 Tuple.Create（longChar，longCount）; } }

如果出现平局，则返回第一个。

I want to find the longest repeating character in a sorted string.

class Program { static string input = "aaaabbcddddddddddeeffffg"; // expected: "d" static void Main(string[] args) { char[] c = input.ToCharArray(); List<string> list = new List<string>(); string temp = String.Empty; for (int i = 1; i < c.Length - 1; i++) { char curr = c[i]; char next = c[i + 1]; temp += curr.ToString(); if (curr != next) { list.Add(temp); temp = next.ToString(); } } Console.WriteLine(list.OrderByDescending(n => n.Length).First()[0]); Console.WriteLine("Press any key..."); Console.ReadKey(); } }

My code has two flaws. 1) It missed the last char. 2) It used Linq and stored the blocks to a list, so it may not be efficient. I hope some kind of in-place algorithm. Thank you.

解决方案

Arrays are zero-based; by starting with i = 1 you skip one element. And by using c.Length - 1, you also skip the last element. You also don't need to store the whole list, you can store only the longest. It's also better to use StringBuilder than string concatenation. And the temp = next.ToString(); line shouldn't be there, because it causes a char to be counted twice.

char[] c = input.ToCharArray(); string longest = ""; StringBuilder sb = new StringBuilder(); for (int i = 0; i < c.Length; i++) { char curr = c[i]; char next = i != c.Length - 1 ? c[i + 1] : '\0'; // check whether the current char is the last sb.Append(curr); if (curr != next) { string temp = sb.ToString(); if (temp.Length > longest.Length) { longest = temp; // if the new string with the new chars is longer, replace the longest string } sb.Clear(); // clear the StringBuilder } } Console.WriteLine(longest[0]); Console.WriteLine("Press any key..."); Console.ReadKey();

The above code shows how you can do it with a StringBuilder and without LINQ. Why StringBuilder? Take a look at this article: yoda.arachsys/csharp/stringbuilder.html[^]

Quote:

Definitely use StringBuilder when you're concatenating in a non-trivial loop - especially if you don't know for sure (at compile time) how many iterations you'll make through the loop. For example, reading a file a character at a time, building up a string as you go using the += operator is potentially performance suicide.

That is the case here; we don't know how many iterations it'll make, because that depends on the input.

I'd suggest to read this thread: Counting A Character[^]. I do not see any performance issues by using Linq, unless the set of strings is very, very LARGE. It's really fast. Below query is executed in 0.001 sec.

string input = "aaaabbcddddddddddeeffffg"; var qry = (from c in input group c by c into grp orderby grp.Count() descending select new { Character = grp.Key, Count= grp.Count() }).Take(1); foreach(var v in qry) { Console.WriteLine("'{0}' is counted {1} time(s)",v.Character,v.Count); }

Result:

'd' is counted 10 time(s)

Here's a solution that just counts the characters and keeps track of the longest sequence seen so far.

class Program { static string input = "aaaabbcddddddddddeeffffg"; // expected: "d" static void Main(string[] args) { var longest = FindLongestRepeat(input); Console.WriteLine("Char {0} Count {1}", longest.Item1, longest.Item2); Console.WriteLine("Press any key..."); Console.ReadKey(); } static Tuple<char, int> FindLongestRepeat(string str) { if (string.IsNullOrEmpty(str)) return null; char seqChar = str[0]; int seqCount = 1; char longChar = seqChar; int longCount = seqCount; for (int i = 1; i < str.Length; i++) { char c = str[i]; if (c != seqChar) { seqChar = c; seqCount = 1; } else { ++seqCount; if (c == longChar) { ++longCount; } else if (seqCount > longCount) { longCount = seqCount; longChar = seqChar; } } } return Tuple.Create(longChar, longCount); } }

In case of a tie, it returns the first.