java – 数字的子串的总和

发布时间：2020-12-15 05:19:24 所属栏目：Java 来源：网络整理

导读：找到数字子串总和的最佳解决方案是什么？例如,Sum(123)= 1 2 3 12 23 123 = 164. 我认为这是O(n ^ 2).因为 sum = 0for i in number: // O(n) sum += startwith(i) // O(n)return sum 有什么最佳方案？什么是最好的方法？这是我的解决方案,但O(n ^ 2)： pub

找到数字子串总和的最佳解决方案是什么？

例如,Sum(123)= 1 2 3 12 23 123 = 164.

我认为这是O(n ^ 2).因为

sum = 0
for i in number: // O(n)
    sum += startwith(i) // O(n)
return sum

有什么最佳方案？什么是最好的方法？

这是我的解决方案,但O(n ^ 2)：

public static int sumOfSubstring(int i) {
  int sum = 0;

  String s = Integer.toString(i);

  for (int j = 0,bound = s.length(); j < bound; j++) {
   for (int k = j; k < bound; k++) {
    String subString = s.subSequence(j,k + 1).toString();
    sum += Integer.valueOf(subString);
   }
  }

  return sum;
 }

解决方法

观察：

>对于数字XY,您有11X 2Y.
>对于数字XYZ,你有111X 22Y 3Z.
>对于WXYZ,你有1111W 222X 33Y 4Z.

这是我的C#实现,尽管移植到Java应该是微不足道的：

static long SumSubtring(String s)
{
    long sum = 0,mult = 1;
    for (int i = s.Length; i > 0; i--,mult = mult * 10 + 1)
        sum += (s[i - 1] - '0') * mult * i;
    return sum;
}

注意它实际上是O(n).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!