不做大哥好多年
xiaonaiqiang
2021-06-19
目录

41.数学

# 01.整数反转

# 例1
输入：x = 123
输出：321

# 例2
输入：x = -123
输出：-321
1
2
3
4
5
6
7

# 1、python

class Solution:
    def reverse(self, x):
        res = 0
        max_, min_ = 2 ** 31 - 1, -2 ** 31    # 32 位整数的最大值和最小值
        x1 = abs(x)
        while x1 != 0:                        # 3//10 = 0 {如果等于0，代表数字所有数全部遍历完成}
            digit = x1 % 10                   # 321 % 10 = 1 (取出数字个位数)

            # 因为我们要判断的是 res * 10 + digit 是否溢出，所以这里需要 (max_ - digit) // 10
            if res > (max_ - digit) // 10 or res < (min_ - digit) // 10:
                return 0
            res = res * 10 + digit
            x1 = x1 // 10                     # 321 // 10 = 32 （去除数字个位数）
        return res if x > 0 else - res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

  • # 2、golang

package main

import (
	"fmt"
	"math"
)

func reverse(x int) (rev int) {
	for x != 0 {
		// 判断超出int型的正负边界问题
		if rev < math.MinInt32/10 || rev > math.MaxInt32/10 {
			return 0
		}
		digit := x % 10        // 321 % 10 = 1 (取出数字个位数)
		x /= 10                // 321 // 10 = 32 （去除数字个位数）
		rev = rev*10 + digit   // 将各位加入新数中
	}
	return
}

func main() {
	x := -123
	val := reverse(x)
	fmt.Println(val)   // -321
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 02.x 的平方根

  • 69.x 的平方根 (opens new window)

  • 实现 int sqrt(int x) 函数

  • 计算并返回 x 的平方根，其中 x 是非负整数

  • 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去

# 1、python

  • 一个数的平方满足这个公式，

  • 如果 mid * mid 小于 x，移动左边界

  • 如果 mid * mid 大于 x，移动右边界

  • 当二分查找结束时，right 会指向平方根的整数部分

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x

        left, right = 2, x // 2  # 只需要从 2 到 x//2 之间搜索

        while left <= right:
            mid = left + (right - left) // 2
            num = mid * mid

            if num == x:
                return mid  # 完全平方根
            elif num < x:
                left = mid + 1  # 搜索右半部分
            else:
                right = mid - 1  # 搜索左半部分

        return right  # 此时 right 是最接近平方根的整数部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

  • # 2、golang

func mySqrt(x int) int {
	if x < 2 {
		return x
	}
	
	left, right := 2, x/2  // 初始化搜索范围

	for left <= right {
		mid := left + (right - left) / 2
		num := mid * mid

		if num == x {
			return mid  // 找到完全平方根
		} else if num < x {
			left = mid + 1  // 搜索右半部分
		} else {
			right = mid - 1  // 搜索左半部分
		}
	}

	return right  // 此时 right 是最接近平方根的整数部分
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 03.罗马数字转整数

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
1
2
3
4
5
6
7
8
  • 例如
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
1
2
3

# 1、python

  • 罗马数字由 I,V,X,L,C,D,M 构成；
  • 当小值在大值的左边，则减小值，如 IV=5-1=4；
  • 当小值在大值的右边，则加小值，如 VI=5+1=6；
  • 由上可知，右值永远为正，因此最后一位必然为正
  • 一言蔽之，把一个小值放在大值的左边，就是做减法，否则为加法
def romanToInt(s):
    map = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
    output = 0
    for i in range(len(s) - 1):
        if map[s[i]] >= map[s[i+1]]:
            output += map[s[i]]
        else:
            output -= map[s[i]]
    output += map[s[-1]]
    return output

print( romanToInt('VI') )  # 6
1
2
3
4
5
6
7
8
9
10
11
12

# 04.十进制转任意进制

def f(n, x):
	a = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F']
	ret = ''
	while True:
		s = n // x    # 商
		y = n % x     # 余数
		ret = a[y] + ret
		if s == 0:
			break
		n = s
	return ret

s = f(26, 16)
print(s)  # 1A
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 05.找素数

  • 素数除了1和他本身没有其他因数

# 1、python

  • 1）普通方法找素数
    • 遍历从 2 到 sqrt(n) 之间所有数字，如果存在能够整除的，证明不是素数
import math

def func(n):
    l = []
    for i in range(2, n+1):
        for j in range(2, int(math.sqrt(i))+1):
            if i%j == 0:           # 如果出现整除说明有因子
                break              # 跳出最外层for循环判断下一个
        else:                      # 如果第二层循环结束还没有跳出的话
            l.append(i)            # 说明是素数，加到列表里
    return l

print func(20)  # [2, 3, 5, 7, 11, 13, 17, 19]
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 2）求素数 时间复杂度最低方法
import math
def func(n):
    l = [2,3,5]
    for i in range(6, n+1):
        for j in l:
            if j <= ( math.sqrt(i) + 1 ) and i%j == 0:
                break                #跳出最外层for循环判断下一个
        else:                        #如果第二层循环结束还没有跳出的话
            l.append(i)              #说明是素数，加到列表里
    return l

print func(10)     # [2, 3, 5, 7]
'''
说明：判断100是否是质素只需要对比4次
1、不需要循环[1,2,3,4,5,6,7,8,9,10]依次与100取余
2、只需要循环[2, 3, 5, 7] 依次与100取余即可
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 06.字符串相加

"1234" "123" ==> "1357"
1

# 1、python

class Solution:
    def addStrings(self, num1, num2):
        res = ""
        i, j, carry = len(num1) - 1, len(num2) - 1, 0   # 设定 i，j 两指针分别指向 num1，num2 尾部, 两数相加进位为0
        while i >= 0 or j >= 0:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10                      # 进位
            res = str(tmp % 10) + res              # 取余就是当前位的值，并加入字符串右面
            i, j = i - 1, j - 1                    # 指针向右移动一位
        if carry:                                  # 如果循环结束还存在井位，在头部添加进位 1
            res = '1' + res
        return res

print(Solution().addStrings("1234", "123") )  # "1357"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 07.字符串相乘

  • 字符串相乘 (opens new window)

  • 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式

  • **注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数

输入: num1 = "123", num2 = "456"
输出: "56088"
1
2

# 1、python

  • 乘积最大长度 len(num1)+len(num2)，所以初始化数组 res 来保存结果

  • 从 num1 的最后一位开始，依次与 num2 的每一位相乘，并将结果累加到 res 数组的适当位置

  • 在累加的过程中，如果某一位置的值超过 10，要将其进位到前一位

  • 将 res 数组中非零的数字转为字符串，去掉前导零，得到最终结果

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        res = [0] * (len(num1) + len(num2))          # 初始化结果数组长度
        
        # 从num1最后一位开始，依次与num2的每一位相乘，并将结果累加到res数组的适当位置
        for i in range(len(num1) - 1, -1, -1):       # 倒序遍历 range(2, -1, -1)=[2, 1, 0]
            for j in range(len(num2) - 1, -1, -1):
                tmp = int(num1[i]) * int(num2[j])    # 计算当前位的乘积
                p1, p2 = i + j, i + j + 1            # p1当前乘积位置，p2进位位置
                total = tmp + res[p2]                # 乘积 + 上次进位
                res[p2] = total % 10                 # 更新低位的值
                res[p1] += total // 10               # 处理高位的进位
                
        s = ''.join(map(str, res))                   # 将结果数组转换为字符串，并去除前导零
        return s.lstrip('0')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 08.整数拆分

  • 343.整数拆分 (opens new window)
  • 给定一个正整数 n ，将其拆分为 k 个正整数 的和（ k >= 2 ），并使这些整数的乘积最大化
  • 返回 你可以获得的最大乘积
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
1
2
3
4
5
6
7

# 1、python

  • 状态定义：dp[i] 表示将整数 i 拆分成至少两个正整数后，能够获得的最大乘积

  • 状态转移方程：

    • tmp = max(i - j, dp[i - j]) 获取i-j 如何才能最大，历史最大乘积 or 本身
    • dp[i] = max(dp[i], j * tmp) j是固定的 乘积 i-j 最大值即可获取新的最大值

  • 初始状态：dp 数组初始化为 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]，表示初始时没有计算任何值

class Solution:
    def integerBreak(self, n):
        dp = [0] * (n + 1)                # dp[i] 表示将整数i拆分成至少两个正整数后，能够获得的最大乘积
        for i in range(2, n + 1):         # 从 2 开始，因为 1 不能拆分
            for j in range(1, i):         # 尝试将 i 拆分为 j 和 (i - j)
                tmp = max(i - j, dp[i - j])           # j是固定的 (i-j) 可以是历史中最大值 也可以是 i-j本身
                dp[i] = max(dp[i], j * tmp)
        return dp[n]

print( Solution().integerBreak(10) )  # [0, 0, 1, 2, 4, 6, 9, 12, 18, 27, 36]
1
2
3
4
5
6
7
8
9
10

# 09.丑数 II

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列
1
2
3

# 1、python

  • 根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）
  • 设置三个指针 i2, i3, i5，初始值均为 0，分别表示当前丑数数组中应该乘以 2、3 和 5 的位置
  • 通过比较 dp[i2] * 2, dp[i3] * 3 和 dp[i5] * 5 的最小值，将其作为下一个丑数加入 dp 数组中
  • 如果某个指针的计算值等于当前丑数，则对应指针自增1，表示这个指针要移动到下一个丑数位置
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0] * n
        dp[0] = 1                                 # 第一个丑数是 1
        i2 = i3 = i5 = 0                          # 当前丑数数组中应该乘以 2、3 和 5 的位置

        for i in range(1, n):
            # 下一个丑数是 2*dp[i2], 3*dp[i3], 5*dp[i5] 中的最小值
            next_ = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
            dp[i] = next_

            # 如果某个指针的计算值等于当前丑数，则对应指针自增1，表示这个指针要移动到下一个丑数位置
            if next_ == dp[i2] * 2:
                i2 += 1
            if next_ == dp[i3] * 3:
                i3 += 1
            if next_ == dp[i5] * 5:
                i5 += 1

        return dp[-1]  # 返回第 n 个丑数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
上次更新: 2024/9/12 08:22:36
31.树
61.矩阵

← 61.矩阵→

最近更新
01
04.数组双指针排序_子数组
03-25
02
08.动态规划
03-25
03
06.回溯算法
03-25
更多文章>
Theme by Vdoing | Copyright © 2019-2025 逍遥子 技术博客 京ICP备2021005373号