-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathMath.py
443 lines (419 loc) · 12.3 KB
/
Math.py
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
# -*- coding: utf-8 -*-
"""
-------------------------------------------------
File Name: Math
Description :
Author : amilyxy
date: 2019/9/4
-------------------------------------------------
"""
'''
7. Reverse Integer: 整数反转
describe: 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
'''
class Solution:
def reverse(self, x: int) -> int:
# # 方法一 56ms
neg = 0
if x < 0:
neg = 1
x = abs(x)
strx = str(x)
out = 0
for i in range(len(strx)):
out += pow(10, i)*int(strx[i])
# 说明x是正数
if (neg == 0) & (out < (pow(2, 31)-1)):
return out
if (neg == 1) & (out < pow(2, 31)):
return -out
return 0
# 方法二
neg = 0
out = 0
if x < 0:
neg = 1
x = abs(x)
while True:
out = out * 10 + x % 10
if x // 10 == 0:
break
x = x // 10
if (neg == 0) & (out < (pow(2, 31) - 1)):
return out
if (neg == 1) & (out < pow(2, 31)):
return -out
return 0
'''
165. Compare Version Numbers: 比较版本号
describe: 比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1
如果 version1 < version2 返回 -1
除此之外返回 0。
'''
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
list1 = version1.split('.')
list2 = version2.split('.')
L1 = len(list1)
L2 = len(list2)
L = max(L1, L2)
if L1 < L2:
list1.extend(['0'] * (L2 - L1))
elif L1 > L2:
list2.extend(['0'] * (L1 - L2))
# 评论方法 -d很关键
# d = L1 - L2
# list1, list2 = list1 + [0] * d, list2 + [0] * -d
for i in range(L):
if (int(list1[i]) > int(list2[i])):
return 1
elif (int(list1[i]) < int(list2[i])):
return -1
return 0
'''
66. Plus One: 加一
describe: 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
'''
class Solution:
def plusOne(self, digits: list[int]) -> list[int]:
# 方法一 56ms
L = len(digits)
out = []
num = 0
for i in range(L):
num += pow(10, i)*digits[L-1-i]
num += 1
while True:
out.append(num%10)
num = num//10
if num == 0:
return out[::-1]
# 方法二 52ms
L = len(digits)
for i in range(L - 1, -1, -1):
temp = digits[i] + 1
digits[i] = temp % 10
if temp >= 10:
if i == 0:
digits.insert(0, temp // 10)
break
else:
break
return digits
'''
8. String to Integer (atoi) 字符串转换整数
'''
# 感觉真的是笨方法hhhh
class Solution:
def myAtoi(self, str: str) -> int:
res, i, neg = 0, 0, 0
strin = str.lstrip()
n = len(strin)
nums = set(['0','1','2','3','4','5','6','7','8','9'])
if n == 0:
return res
if strin[0] == '-' or strin[0] == '+':
i = 1
if strin[0] == '-':
neg = 1
while i<n and strin[i] in nums:
res = res*10 + int(strin[i])
i+=1
if neg:
res = -res
if res>pow(2,31)-1:
res = pow(2,31)-1
if res<-pow(2, 31):
res = -pow(2, 31)
return res
# 看到题目的第一眼我就觉得可以用正则,但是我不会用py的正则,答案肯定有人用呀
import re
class Solution:
def myAtoi(self, s: str) -> int:
return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
'''
258. Add Digits 各位相加
好吧,看答案大家好像都是用%9去做的 == 是我naive
'''
class Solution:
def addDigits(self, num: int) -> int:
res = 0
while num:
res += num%10
num //=10
if not num and res>=10:
num = res
res = 0
return res
# 方法二: 巧了嘿! 昨天正好学习了eval() 今天就能用上
def addDigits(self, num: int) -> int:
while len(str(num))>1:
num = eval('+'.join(list(str(num))))
return num
# 题解方法三 %9
def addDigits(self, num: int) -> int:
if num > 9:
num = num % 9
if num == 0:
return 9
return num
'''
67. Add Binary 二进制求和
题意还是按原始的方法做吧! 感觉方法还是蛮多的比如异或 不写了~
'''
class Solution:
# 真的是最原始的加减法hhh
def addBinary(self, a: str, b: str) -> str:
na = len(a)
nb = len(b)
if na > nb:
b = '0'*(na-nb) + b
else:
a = '0'*(nb-na) + a
add = 0
n =len(a)
res = ''
for i in range(n-1, -1, -1):
temp = int(a[i]) + int(b[i]) + add
res = str(temp%2) + res
add = 0 if temp<2 else 1
if add == 1:
res = '1' + res
return res
# 方法二: python的骚操作
def addBinary(self, a: str, b: str) -> str:
res = bin(int(a, 2) + int(b, 2))
return res[2:]
'''
263.丑数
desc: 判断一个数是否为丑数,包括递归和非递归做法
'''
# 递归方法 @powcai
class Solution:
def isUgly(self, num: int) -> bool:
if num == 0: return False
if num == 1:return True
if num % 2 == 0: return self.isUgly(num // 2)
if num % 3 == 0: return self.isUgly(num // 3)
if num % 5 == 0: return self.isUgly(num // 5)
return False
# 迭代方法:
class Solution:
def isUgly(self, num: int) -> bool:
if num ==0: return False
for i in 2, 3, 5:
while num % i == 0:
num //= i
return num == 1
'''
264.丑数II
在此之前有个类似题型:263.丑数,判断一个数是不是丑数,这个很简单
'''
class Solution:
def nthUglyNumber(self, n: int) -> int:
res = [1]
dic = {}
for i in [2,3,5]:
dic[i] = 0
for i in range(n-1):
tmp = min([res[dic[i]]*i for i in dic])
for i in dic:
if tmp == res[dic[i]]*i:
dic[i] = dic[i]+1
res.append(tmp)
# print(res)
return res[-1]
'''
313.超级丑数
也就是把264题中[2,3,5]替换成primes,其他不变
'''
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
res = [1]
dic = {}
for i in primes:
dic[i] = 0
for i in range(n-1):
tmp = min([res[dic[i]]*i for i in dic])
for i in dic:
if tmp == res[dic[i]]*i:
dic[i] = dic[i]+1
res.append(tmp)
# print(res)
return res[-1]
'''
204.计数质数
方法一:采用厄拉多塞筛法
'''
import math
class Solution:
def countPrimes(self, n: int) -> int:
res = 0
tmp = [1]*n
for i in range(2, n):
if tmp[i]: res+=1
j = i
while j*i<n:
tmp[j*i]=0
j+=1
return res
# 改进方法
import math
class Solution:
def countPrimes(self, n: int) -> int:
if n<=1: return 0
res = [0, 0]+[1]*(n-2)
for i in range(2, int(math.sqrt(n))+1):
if res[i]:
k = i
while k*i<n:
res[k*i] = 0
k+=1
return sum(res)
'''
172.阶乘后的0
'''
class Solution:
def trailingZeroes(self, n: int) -> int:
if n<5: return 0
res = 0
while n>0:
n //= 5
res += n
return res
'''
1.两数之和
'''
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(nums)):
dist = target-nums[i]
if dist in dic:
return [dic[dist], i]
dic[nums[i]] = i
'''
15.三数之和
desc:双指针
'''
# 题解方法 @吴彦祖
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if n<3: return []
res = []
nums.sort()
for i in range(n):
if nums[i]>0:
return res
if i>0 and nums[i]==nums[i-1]:
continue
l, m, r = i, i+1, n-1
while m<r:
if nums[l]+nums[m]+nums[r]==0:
res.append([nums[l], nums[m], nums[r]])
while m<r and nums[m]==nums[m+1]:
m+=1
while m<r and nums[r]==nums[r-1]:
r-=1
m+=1
r-=1
elif nums[l]+nums[m]+nums[r]>0:
r-=1
else:
m+=1
return res
'''
18.四数之和
desc:①类似LC40 组合总和,用组合的方式解决(会超时),考虑进行剪枝
'''
# 回溯法
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res = []
self.dfs(0, res, [], target, nums)
return res
def dfs(self, i, res, tmp, target, nums):
if len(tmp) == 4 and sum(tmp)==target:
res.append(tmp)
if len(tmp)<4:
for j in range(i, len(nums)):
# 剪枝一
if sum(tmp)+(4-len(tmp))*(nums[-1])<target:
break
# 剪枝二
if sum(tmp)+(4-len(tmp))*(nums[j])>target:
break
# 去重
if j>i and nums[j]==nums[j-1]:
continue
self.dfs(j+1, res, tmp+[nums[j]], target, nums)
# 双指针 类似三数之和,固定两个l和midl然后遍历寻找midr和r
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
if n<4: return []
nums.sort()
if nums[-1]*4<target or nums[0]*4>target:
return []
res = []
for l in range(n-3):
if l>0 and nums[l]==nums[l-1]:
continue
if nums[l]*4>target:
return res
for ml in range(l+1, n-2):
if ml>l+1 and nums[ml]==nums[ml-1]:
continue
mr, r = ml+1, n-1
if nums[l]+nums[ml]+nums[mr]*2>target:
break
if nums[l]+nums[ml]+nums[r]*2<target:
continue
while mr<r:
tmp = [nums[l],nums[ml],nums[mr],nums[r]]
if sum(tmp)==target:
res.append(tmp)
while mr<r and nums[mr]==nums[mr+1]:
mr+=1
while mr<r and nums[r]==nums[r-1]:
r-=1
mr+=1
r-=1
elif sum(tmp)<target:
mr+=1
else:
r-=1
return res
'''
1363.形成三的最大倍数
'''
class Solution:
def largestMultipleOfThree(self, digits: List[int]) -> str:
cnt, mod = [0] * 10, [0] * 3
sumi = 0
for i in digits:
cnt[i] += 1
mod[i % 3] += 1
sumi += i
remove_mod, rest = 0, 0
if sumi % 3 == 1:
remove_mod, rest = (1, 1) if mod[1] >= 1 else (2, 2)
elif sumi % 3 == 2:
remove_mod, rest = (2, 1) if mod[2] >= 1 else (1, 2)
ans = ""
for i in range(0, 10):
if cnt[i] and rest and i % 3 == remove_mod:
rest -= 1
cnt[i] -= 1
if rest == 0:
ans += (str(i) * cnt[i])
else:
ans += (str(i) * cnt[i])
if len(ans) > 0 and ans[-1] == "0":
ans = "0"
return ans[::-1]