数据结构与算法——数学相关
2021-12-01 22:59:04

一、整数反转

此题为leetcode​​第7题​​

思路：基本思路就是，初始化y = 0，进入while循环，令y = y * 10 + x % 10，并且x = // 10，当x != 0的时候继续循环，最后返回y。这里需要注意几点：（1）x是有符号整数，取余的时候要对x的绝对值取余，否则负数取余会有问题；（2）此题有范围限制，循环的时候需要判断一下y的范围；（3）当x是负数的时候，返回的y注意也加上负号

class Solution:
    def reverse(self, x: int) -> int:
        x_, y = abs(x), 0   # 负数取余要注意，和正数不一样
        if x < 0:
            bound = 2**31
        else:
            bound = 2**31 - 1

        while x_ != 0:
            y = y * 10 + x_ % 10
            x_ = x_ // 10
            if y > bound:
                return 0
        if x >= 0:
            return y
        else:
            return -y

二、第N个数字

此题为leetcode​​第400题​​

思路：我们观察发现：

[1, 9]区间里基数是1，长度为9，每个数有1位，一共有91位数字
[10, 99]区间里基数是10，长度为90，每个数有2位，一共有902位数字

[100, 999]区间里基数是100， 长度为900，每个数有3位，一共有900*3位数字

……

因此我们可以遍历长度i (1 <= i <= 10)，先求得基数 f i r s t n u m = 10 ∗ ∗ ( i − 1 ) first_num = 10 ** (i - 1) firstn​um=10∗∗(i−1)，然后判断n是否在当前区间内（ n < f i r s t n u m ∗ 9 ∗ i n < first_num * 9 * i n<firstn​um∗9∗i），在的话可以直接求得结果 i n t ( s t r ( f i r s t _ n u m + n / / i ) [ n % i ] ) int(str(first\_num + n // i)[n \% i]) int(str(first_num+n//i)[n%i])。如果不在的话，n减去 f i r s t _ n u m ∗ 9 ∗ i first\_num * 9 * i first_num∗9∗i

class Solution:
    def findNthDigit(self, n: int) -> int:
        n -= 1
        for i in range(1, 10):
            first_num = 10 ** (i - 1)
            if n < 9 * first_num * i:
                return int(str(first_num + n // i)[n % i])
            n -= 9 * first_num * i

三、自除数

此题为leetcode​​第728题​​

思路：遍历数组里的数，依次判断是否是自除数。判断的时候，可以将数字转为字符串，这样如果中间有0的话可以将其提出来，会方便一些。

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        def self_divide(num):
            for d in str(num):
                if d != '0' and num % int(d) == 0:
                    continue
                else:
                    return False
            return True

        res = []
        for num in range(left, right + 1):
            if self_divide(num):    
                res.append(num)
        return res