05.数学
# 01.整数反转
# 1.1 题目描述
# 例1
输入:x = 123
输出:321
# 例2
输入:x = -123
输出:-321
1
2
3
4
5
6
7
2
3
4
5
6
7
# 1.2 python
以12345为例,先拿到5,再拿到4,之后是3,2,1
我们按这样的顺序就可以反向拼接处一个数字了,也就能达到 反转 的效果。
怎么拿末尾数字呢?好办,用取模运算就可以了
- 1、将12345 % 10 得到5,之后将12345 / 10
- 2、将1234 % 10 得到4,再将1234 / 10
- 3、将123 % 10 得到3,再将123 / 10
- 4、将12 % 10 得到2,再将12 / 10
- 5、将1 % 10 得到1,再将1 / 10
但是要注意32 位的有符号整数,则其数值范围为
[−2^31, 2^31 − 1]
- 假设有1147483649这个数字,它是小于最大的32位整数2147483647的
- 但是将这个数字反转过来后就变成了9463847411,这就比最大的32位整数还要大了
- 这样的数字是没法存到int里面的,所以肯定要返回0(溢出了)。
def reverse(x):
res = 0
x1 = abs(x)
while(x1!=0): # 3//10 = 0 {如果等于0,代表数字所有数全部遍历完成}
temp = x1%10 # 321 % 10 = 1 (取出数字个位数)
if res > 214748364 or (res==214748364 and temp>7):
return 0
if res<-214748364 or (res==-214748364 and temp<-8):
return 0
res = res*10 + temp
x1 = x1 // 10 # 321 // 10 = 32 (去除数字个位数)
return res if x >0 else - res
print( reverse(-321) ) # -123
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
- 不考虑32位系统边界问题的解法
def reverse(x):
res = 0
x1 = abs(x)
while(x1!=0): # 3 // 10 = 0 {如果等于0,代表数字所有数全部遍历完成}
temp = x1%10 # 321 % 10 = 1 (取出数字个位数)
res = res*10 + temp # 从右向左依次拼接
x1 = x1 // 10 # 321 // 10 = 32 (去除数字个位数)
return res if x >0 else - res
print( reverse(-321) ) # -123
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 1.3 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
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 的平方根
# 2.1 题目描述
实现
int sqrt(int x)
函数。计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
1
2
3
4
5
6
2
3
4
5
6
# 2.2 python
- 一个数的平方满足这个公式,
- 因此我们可以 进行二分查找,从而得到答案
def mySqrt(x):
l, r, ret = 0, x, -1 # l: 左边界, r: 右边界, ret:目标值
while l <= r:
mid = (l + r) // 2 # 每次都取中位数
if mid * mid <= x: # 如果中位数平方小于x,左指针向右移动一位
ret = mid
l = mid + 1
else: # 如果中位数平方大于x,右指针向左移动一位
ret = mid
r = mid - 1
return ret
print(mySqrt(8))
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 2.3 golang
package main
import (
"fmt"
)
func mySqrt(x int) int {
l, r := 0, x
ans := -1
for l <= r {
mid := l + (r - l) / 2
// 中间元素 mid 的平方与 x 的大小关系
if mid * mid <= x { // 如果小于 x 左指针向右移动一位
ans = mid
l = mid + 1
} else { // 如果大于 x 右指针向左移动一位
r = mid - 1
}
}
return ans
}
func main() {
x := 8
val := mySqrt(x)
fmt.Println(val) // 2
}
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
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 03.罗马数字转整数
# 3.1 题目说明
- 罗马数字包含以下七种字符:
I
,V
,X
,L
,C
,D
和M
。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
- 例如
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
1
2
3
2
3
# 3.2 解题思路
- 罗马数字由 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
2
3
4
5
6
7
8
9
10
11
12
# 04.无重复数字的三位数
- 有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?
#! /usr/bin/env python
# -*- coding: utf-8 -*-
#题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?
sum=0
for i in range(1,5,1):
for j in range(1,5,1):
for k in range(1,5,1):
if i!=j and i!=k and k!=j :
sum=sum+1
print i,j,k # 这里去重
print sum
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 05.十进制转任意进制
def f(n, x):
'''
:param n: n为待转换的十进制数
:param x: x为机制,取值为2-16
:return: 返回转换后的进制数
'''
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
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 06.找素数
# 6.1 普通方法找素数
#!/usr/bin/env python
# -*- coding:utf-8 -*-
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
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 6.2 求素数 时间复杂度最低方法
#!/usr/bin/env python
# -*- coding:utf-8 -*-
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
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 6.3 golang
package main
import "fmt"
func findPrimeNumber(num int) []int {
vals := []int{}
for i := 2; i <= num; i++ {
for j := 2; j < i; j++{
if i % j == 0 {
goto breakTag // 不执行append语句,直接跳到 breakTag标签部分
}
}
vals = append(vals, i)
breakTag: // 标签
}
return vals
}
func main() {
v := findPrimeNumber(20)
fmt.Println(v) // [2 3 5 7 11 13 17 19]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 07.三数之和
# 7.1 题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?
请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
1
2
2
# 7.2 解答思路
- 对数组进行排序
- 遍历排序后数组:
- 若 nums[i]>0:因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回结果。
- 对于重复元素:跳过,避免出现重复解
- 令左指针 L=i+1,右指针 R=n-1,当 L<R 时,执行循环:
- 当 nums[i]+nums[L]+nums[R]==0,执行循环
- 判断左界和右界是否和下一位置重复,去除重复解。
- 并同时将 L,R移到下一位置,寻找新的解
- 若和大于 0,说明 nums[R] 太大,R左移
- 若和小于 0,说明 nums[L] 太小,L右移
def threeSum(nums):
n=len(nums)
res=[]
if(not nums) or (n<3): # 数组为 null 或者数组长度小于 3,返回 []
return []
nums.sort() # 对数组进行排序
if(nums[0]>0): # 若 nums[0]>0:因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回[]
return []
for i in range(n): # 遍历排序后数组
if(i>0 and nums[i]==nums[i-1]): # 对于重复元素:跳过,避免出现重复解
continue
L=i+1
R=n-1
while(L<R): # 令左指针 L=i+1,右指针 R=n-1,当 L<R 时,执行循环
if(nums[i]+nums[L]+nums[R]==0):
res.append([nums[i],nums[L],nums[R]])
# 当 nums[i]+nums[L]+nums[R]==0,执行循环,判断左界和右界是否和下一位置重复,去除重复解
while(L<R and nums[L]==nums[L+1]):
L=L+1
while(L<R and nums[R]==nums[R-1]):
R=R-1
# 并同时将 L,R 移到下一位置,寻找新的解
L=L+1
R=R-1
elif(nums[i]+nums[L]+nums[R]>0): # 若和大于 0,说明 nums[R] 太大,R 左移
R=R-1
else: # 若和小于 0,说明 nums[L] 太小,L 右移
L=L+1
return res
nums = [-1,0,1,2,-1,-4]
print( threeSum(nums) ) # [[-1, -1, 2], [-1, 0, 1]]
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
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10