-1

我如何编写一个方法，它接受一个参数。单个参数是一个字符串s，它只包含非零数字。

此函数应打印 s 的最长连续子串的长度，使得子串的长度为2*N位（字符串的最大长度为 49）并且最左边 N 位的和等于最右边的和N 位数。如果没有这样的字符串，你的函数应该打印 0

我是 C# 的学习者。我看到了这个谜题，没有做。

样本输入：123231，预期输出为 6

解释：

1 + 2 + 3 = 2 + 3 + 1. 最长子串的长度 = 6 其中第一半的总和 = 第二半

示例输入#2：986561517416921217551395112859219257312 输出为 36

static int myMethod(string s) {

 var input = "123231";
 bool expected = 
 new System.Text.RegularExpressions.Regex("^[1-9]+$").IsMatch(input);

 return 0;
}
4

2 回答 2

1

一个使用 LINQ 的解决方案，希望对您有所帮助。“诀窍”是您必须检查整个字符串的新版本，即第一个 int 的 lop 和最后一个 int。这个问题之前已经在 SO 上提出过，但是作为一个 c++ 问题。它在 C# 中看起来好多了:)

int GetSumString(string s)
{
  // Convert everything to int[], easier that way in .NET
  var numbersOrg = s.Select(t => int.Parse(t.ToString())).ToArray();

  // Its possible to optimize by using ienumerable and lazy evaluation i guess, but I'm lazy :)
  var queue = new Queue<int[]>();
  queue.Enqueue(numbersOrg);

  while (queue.Any())
  {
      var numbers = queue.Dequeue();   

      var firstHalf = numbers.Take(numbers.Length / 2).Sum();
      var secondHalf = numbers.Skip(numbers.Length / 2).Sum();
      // It must be of even length (% 2) and the sum of the first half must be equal to the last half.
      if (numbers.Length % 2 == 0 && firstHalf == secondHalf)
          return numbers.Length;

      // Console.WriteLine("tried: " + string.Join("", numbers) + " gave (" + firstHalf + "," + secondHalf + ")");
      // Only enqueue when we have something left in the array
      if (numbers.Length > 1)
      {
          queue.Enqueue(numbers.Take(numbers.Length - 1).ToArray());
          queue.Enqueue(numbers.Skip(1).ToArray());
      }
  }
  return 0;
}

解决方案就是以正确的顺序进行检查，即保证第一个“解决方案”是最长的解决方案。

于 2013-03-18T10:10:59.007 回答
0

只需遍历可能的组合。123231字符串示例：

1=2         -> fail
1+2=3+2     -> fail
1+2+3=2+3+1 -> len=6, longest so far
2=3         -> fail
2+3=2+3     -> len=4, not longer
3=2         -> fail
3+2=3+1     -> fail
2=3         -> fail
3=1         -> fail

像这样的东西：

int longest = 0;
for (int i = 0; i < str.Length; i++) {
  for (j = longest + 1; i + j * 2 <= str.Length; j++) {
    if (sum(str, i, j) == sum(str, i + j, j)) {
      longest = j;
    }
  }
}

int sum(string str, int offset, int len) {
  int s = 0;
  for (int i = 0; i < len; i++) s += (int)(str[offset + i] - '0');
  return s;
}
于 2013-03-18T09:51:06.897 回答