2026-11-23:解码值之和。用go语言,给定一个整数列表 nums。列表中的每个整数都携带两个正整数 x 和 y 的信息。对于任意一个元素,先取它的个位数字作为切分长度,再把该元素去掉个位后得到的整数记作 d。然后,把 d 的十进制表示按这个切分长度分成左右两段:左边一段作为 x,右边剩余部分作为 y。题目保证 d 的十进制位数大于切分长度,因此 x 和 y 都至少有一位数字。该元素的解码结果就是把 x 的十进制表示和 y 的十进制表示依次连接后得到的整数。要求计算列表中所有元素解码结果的总和,并对 1000000007 取余。除法只取整数部分。
1 <= nums.length <= 100000。
100 < nums[i] < 1000000000000000。
1 <= widthi <= 9。
1 <= xi, yi < 1000000000。
用于构成 xi 和 yi 的数字序列均不包含前导零。
保证 nums 中的每个元素都是有效的编码整数。
输入: nums = [2522,2101]。
输出: 1649。
解释:
对于 2522,有 width = 2、d = 252、x = 25、y = 2。
2522 的解码值为 252 = 625。
对于 2101,有 width = 1、d = 210、x = 2、y = 10。
2101 的解码值为 210 = 1024。
所有解码值之和为 625 + 1024 = 1649。
题目来自力扣4039。
逐元素处理步骤(对数组中每一个 nums[i])
输入是一个 int64 类型的编码数字 X(比如 2522):
1.分离切分(10^{宽度}) width 和 d
• width = X % 10:取个位数字,就是切分(10^{宽度});题目保证 width 在 1~9;
• d = X / 10:整数除法,去掉个位,得到 d;
2.计算
width 范围只有1~9,所以 最大是 ;
3.拆分得到 x 和 y
• x = d / pow10:整数除法,d 除以 的商;
• y = d % pow10:d 除以 的余数;
4.计算解码值
mod 固定为 1000000007;这里使用**快速幂(二进制快速幂)**算法求幂取模:
• 快速幂原理:把指数 y 拆成二进制,逐个看二进制位;
• 初始结果 res=1;底数是 x;
• 循环:指数不断折半(除以2);如果当前最低位是1,就把 res 和当前底数相乘再取模;
• 底数自身平方,再取模;直到指数变成0;
• 循环结束得到的值就是 ,也就是这个元素的解码值;
5.累加到总和 ans
ans 持续累加每个元素算出的解码值;
全部元素处理完成后的收尾步骤
所有数字遍历完毕之后,把总和 ans 对 1000000007 再取一次模,输出结果。
样例累加:625 + 1024 = 1649,1649 < 1e9+7,最终输出1649。
补充:你贴出的原始代码里有一处写错了:pow10 := int(math.Pow10(lengthD - x%10)) 是错误写法,属于代码bug;正确逻辑上面描述的是:pow10 = ,width = X%10,不需要算d的长度。业务逻辑本身是上面这套流程。时间复杂度分析
设数组长度为 , 。
对于每一个元素:
• width ∈ [1,9],计算 是常数时间 ;
• 拆分 x、y 是一次除法+取模, ;
• 快速幂:y 是 ,width最多是9,所以 ;快速幂循环次数等于 y 的二进制位数,最多约30次,是常数 。
所以单个元素耗时 ((\boldsymbol{O(1)}));
整体时间复杂度: 。
额外空间复杂度
算法只使用有限几个临时变量:width、d、pow10、x、y、快速幂内部的res、循环变量;没有开辟随n增长的数组、切片等空间。
额外空间复杂度: 。
说明:输入nums本身是输入空间,不计入额外空间复杂度。Go完整代码如下:
package main
import (
"fmt"
"math"
)
const mod = 1_000_000_007
func pow(x, n int)int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
func sumDecoded(nums []int64) (ans int) {
for _, X := range nums {
x := int(X)
d := x / 10
// 计算 d 的十进制长度
lengthD := 0
for v := d; v > 0; v /= 10 {
lengthD++
}
pow10 := int(math.Pow10(lengthD - x%10))
// 根据 pow10 求出 x = d/pow10 和 y = d%pow10
ans += pow(d/pow10, d%pow10)
}
return ans % mod
}func main() {
nums := []int64{2522, 2101}
result := sumDecoded(nums)
fmt.Println(result)
}
Python完整代码如下:
# -*-coding:utf-8-*-
MOD = 1_000_000_007
def pow_mod(x, n):
res = 1
x %= MOD
while n > 0:
if n & 1:
res = res * x % MOD
x = x * x % MOD
n >>= 1
return res
def sumDecoded(nums):
ans = 0
for X in nums:
x = int(X)
d = x // 10
lengthD = 0
v = d
while v > 0:
lengthD += 1
v //= 10
pow10 = 10 ** (lengthD - x % 10)
left = d // pow10
right = d % pow10
ans += pow_mod(left, right)
return ans % MOD
def main():
nums = [2522, 2101]
result = sumDecoded(nums)
print(result)if __name__ == "__main__":
main()
C++完整代码如下:
using namespace std;
const int mod = 1'000'000'007;
// 快速幂取模
long long modPow(long long x, long long n) {
long long res = 1;
x %= mod;
while (n > 0) {
if (n & 1) {
res = res * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return res;
}
int sumDecoded(const vector & nums) {
long long ans = 0;
for (long long X : nums) {
long long d = X / 10;
// 计算 d 的十进制长度
int lengthD = 0;
for (long long v = d; v > 0; v /= 10) {
lengthD++;
}
// 切分长度 = 个位数字
int width = (int)(X % 10);
int cut = lengthD - width;
// 等价于 math.Pow10(cut)
long long pow10 = 1;
for (int i = 0; i < cut; i++) {
pow10 *= 10;
}
long long left = d / pow10;
long long right = d % pow10;
ans = (ans + modPow(left, right)) % mod;
}
return (int)(ans % mod);
}int main() {
vector nums = {2522, 2101};
int result = sumDecoded(nums);
cout << result << endl;
return 0;
}
芯谷ai:xinguhub.com/sign-up?aff=txk5
我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.