338. 计数问题，求一个更优算法解

明天会更好zj · 发表于 2024-4-21 09:02

PQ就是简单！

cnmlgb9998 · 发表于 2024-4-21 09:06

优化代码，第三种解法。效率提高了，减少了不必要的循环！！！！

时间的音符 · 发表于 2024-4-21 09:50

数据开小了,这题可以开到(1,100亿).

时间的音符 · 发表于 2024-4-21 09:53

原题开到1亿一是数据测试量够了,二是怕longlong溢出.

micch · 发表于 2024-4-21 10:57

sql的方法相当于调用强大的库
pq的函数看不懂，不知道是纯循环还是有算法。

无论是纯循环还是用函数或者库直接计算，本身没啥不好，只是算法题主要是练习不同方法的实现过程。比如DP数位可以解这个题，用算法写个库，直接调用就出结果了。但是这个库怎么写还没搞懂

perfect131 · 发表于 2024-4-21 15:10

蛮有规律的哎写出来咋这费劲呢

micch · 发表于 2024-4-21 15:30

找到这个规律后，解决0~abcdefg的时候，如果abcdefg不是9999999，怎么处理一下，然后就可以按位求和算出总数量。然后就可以算出abcdef~ghijklm这样的区间的数量。

规律搞懂了，然后就是如何转化为代码。

时间的音符 · 发表于 2024-4-21 16:27

Private Function solve(a, b)
Dim ret(0 To 9)
For i = 0 To 9
      ret(i) = countDigit(b, i) - countDigit(a - 1, i)
Next
solve = ret
End Function

Private Function countDigit(n, x)
ret = 0: vbase = 1
Do While vbase <= n
      a = n \ vbase
      b = n Mod vbase
      c = a Mod 10
      a = a \ 10
      If c > x Then
         ret = ret + (a + IIf(x = 0, 0, 1)) * vbase
      ElseIf c = x Then
         ret = ret + (a - IIf(x = 0, 1, 0)) * vbase + (b + 1)
      Else
         ret = ret + a * vbase
      End If
      vbase = vbase * 10
Loop
countDigit = ret
End Function

Public Sub main()
a = 1: b = 100004000
ret = solve(a, b)
End Sub

NBCBA123 · 发表于 2024-4-21 22:06

参与一下，字典+正则

NBCBA123 · 发表于 2024-4-21 22:07

Sub test()
t = Timer
Set dic = CreateObject("scripting.dictionary")
Set reg = CreateObject("vbscript.regexp")
reg.Global = True
reg.Pattern = "[0-9]"
b = 1: c = 990000000
d = c / 50000
For a = b To c Step d
k = k + 1
f = k * d
f = IIf(f > c, c, f)
For e = a To f
Set ks = reg.Execute(e)
For Each k In ks
k = k.Value
If Not dic.exists(k) Then
dic(k) = 1
Else
dic(k) = dic(k) + 1
End If
Next k
Next e
Next a
[a1].Resize(dic.Count, 2) = Application.Transpose(Array(dic.keys, dic.items))
Set dic = Nothing
MsgBox Timer - t
End Sub

复制代码

		自动登录	找回密码
密码			免费注册

[已解决] 338. 计数问题，求一个更优算法解

评分

评分

评分

评分

评分