1281. 整数的各位积和之差

诸神缄默不语-个人CSDN博文目录
力扣刷题笔记

1. 简单粗暴的遍历

Python版：

class Solution:def subtractProductAndSum(self, n: int) -> int:he=0ji=1while n>=1:last_number=n%10he+=last_numberji*=last_numbern=n//10  #就是n=int(n/10)的意思return ji-he

Java版：

class Solution {public int subtractProductAndSum(int n) {int he=0;int ji=1;while(n>=1){int last_number=n%10;he+=last_number;ji*=last_number;n/=10;  //我一开始写成了n=(int)(n/10);  Java的话不需要做这个转换}return ji-he;}
}

时间复杂度：$O(\log n)$
空间复杂度：$O(1)$

参考ChatGPT的回答，解释一下时间复杂度：

这个函数的目的是计算给定数字 $n$ 的各个数字的乘积与和的差值。在这个过程中，你会遍历整个数字的每一位。

时间复杂度是 $O(\log n)$ 的原因是你每次迭代都会通过 $n=n//10$ 将数字的位数减少一位。因此，你将执行与数字 $n$ 的位数相同的迭代次数。

现在，让我们理解为什么数字 $n$ 最多有 $\log n$ 位。

给定一个 $k$ 位的数字$n$，最大值为 $10^k-1$，最小值为$10^{k-1}$：

$$10^{k-1}\le n<10^k$$

取两边的对数，你得到：

$$k-1\le {\log }_{10}n<k$$

所以 $k$就是数字 $n$ 的位数，它的上界是${\log }_{10}n+1$。
因此，遍历数字 $n$ 的每一位需要 $O(\log n)$ 的时间。

2. 其实也是遍历，但是用Python内置函数只用写一行

class Solution:def subtractProductAndSum(self, n: int) -> int:return eval('*'.join(str(n))) - eval('+'.join(str(n)))