數(shù)據(jù)結(jié)構(gòu)與算法——數(shù)學相關(guān)
2021-12-01 22:59:04

一、整數(shù)反轉(zhuǎn)

此題為leetcode??第7題??

思路：基本思路就是，初始化y = 0，進入while循環(huán)，令y = y * 10 + x % 10，并且x = // 10，當x != 0的時候繼續(xù)循環(huán)，最后返回y。這里需要注意幾點：（1）x是有符號整數(shù)，取余的時候要對x的絕對值取余，否則負數(shù)取余會有問題；（2）此題有范圍限制，循環(huán)的時候需要判斷一下y的范圍；（3）當x是負數(shù)的時候，返回的y注意也加上負號

class Solution:
    def reverse(self, x: int) -> int:
        x_, y = abs(x), 0   # 負數(shù)取余要注意，和正數(shù)不一樣
        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個數(shù)字

此題為leetcode??第400題??

思路：我們觀察發(fā)現(xiàn)：

[1, 9]區(qū)間里基數(shù)是1，長度為9，每個數(shù)有1位，一共有91位數(shù)字
[10, 99]區(qū)間里基數(shù)是10，長度為90，每個數(shù)有2位，一共有902位數(shù)字

[100, 999]區(qū)間里基數(shù)是100， 長度為900，每個數(shù)有3位，一共有900*3位數(shù)字

……

因此我們可以遍歷長度i (1 <= i <= 10)，先求得基數(shù) f i r s t n u m = 10 ? ? ( i ? 1 ) first_num = 10 ** (i - 1) firstn?um=10??(i?1)，然后判斷n是否在當前區(qū)間內(nèi)（ n < f i r s t n u m ? 9 ? i n < first_num * 9 * i n<firstn?um?9?i），在的話可以直接求得結(jié)果 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

三、自除數(shù)

此題為leetcode??第728題??

思路：遍歷數(shù)組里的數(shù)，依次判斷是否是自除數(shù)。判斷的時候，可以將數(shù)字轉(zhuǎn)為字符串，這樣如果中間有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