《剑指offer》-算法篇-数学

题目

代码实现

数值的整数次方

题目描述：给定一个double类型的浮点数base和int类型的整数exponent，求base的exponent次方。保证base和exponent不同时为0。

思路：判断exponent的奇偶性。相比于直接按照循环次数，相乘exponent次，采用res*=res的方式可以实现O(logn)次的相乘。

# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
res=base
flag=1
if exponent<0:
exponent*=-1
flag=-1
elif exponent==0:
return 1
while True:
if exponent%2==1:
if exponent==1:
res*=base
break
res*=res
exponent=exponent//2
else:
if exponent==1:
res=res
break
res*=res
exponent=exponent//2
return res if flag==1 else 1/res

整数中1出现的次数（整数的范围为1～n）

题目描述：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

思路：逐个找到数字所包含的1的个数。

# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
"""
方法1：参考
https://www.nowcoder.com/profile/4321749/codeBookDetail?submissionId=12566515
的讲解
res = 0
i = 1 # 个位开始
while n // i != 0:
high = n//(i*10) # 高位数
current = (n//i) % 10 # 第i位数
low = n – (n//i) * i # 低位数
if current == 0:
res += high * i
elif current == 1:
res += high * i + low + 1
else:
res += (high+1) * i
i *= 10
return res
"""
"""
#方法2
#以1~13为例：
res=0
tmp=n
base=1
while tmp:
last=tmp%10
tmp=tmp/10
#加上两位数中的双11的这一种情况
res+=tmp*base
#加上两位数的其它情况
if last==1:
res+=n%base+1
#加上个位的"1"这一种情况
elif last>1:
res+=base
base*=10
return res
"""
counts = 0
if n < 1: return 0
for i in range(1, n+1):
num = i
while num>0:
if num%10 ==1:
counts = counts + 1
num = num/10
return counts

丑数

题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路：保证相乘的数中只有2、3、5，而且是按照由小到大的顺序一次得到丑数，列表中的最后一个数值就是第N个丑数。

# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index <= 1: return index
#第一个丑数是1
res = [1] * index
i2, i3, i5 = 0, 0, 0
#找到第2个到第index个丑数
#在for的每一次循环中肯定可以找到一个丑数，且是由小到大最小的一个
for i in range(1, index):
res[i] = min(res[i2]*2, min(res[i3]*3, res[i5]*5))
if res[i] == res[i2]*2: i2 += 1
if res[i] == res[i3]*3: i3 += 1
if res[i] == res[i5]*5: i5 += 1
return res[-1]

和为S的连续正数序列

题目描述：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!要求：输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。 思路：滑动窗口实现，注意题中是连续的正数序列，如果是负数的话就不适合了（因为中间会删除掉最小的述，但是对于有负数的情况，删除负数之后会更大而非更小）

# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
res = []
windows = []
sum = 0
for t in range(1, tsum):
windows.append(t)
sum += t
#增加大的数值，删除小的数值，得到连续的正数序列
while sum > tsum:
sum -= windows.pop(0)
if sum == tsum:
res.append(windows[:])
return res

和为S的两个数字

题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路：和直接找到和为S的两个数字（在Leetcode中就有这样的题目，对应于其中的第1道题）不同，这里还增加了限制条件：乘积最小。

# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if not array: return []
lp = 0
rp = len(array) – 1
res = [array[-1]] * 2
#找到满足两数之和等于tmp的数组的下标lp和rp，在多组中找到乘积最小的那组
#如果没有找到的话，返回[]
while lp < rp:
tmp = array[lp] + array[rp]
if tmp > tsum:
rp -= 1
elif tmp < tsum:
lp += 1
else:
if array[lp] * array[rp] < res[0] * res[1]:
res[0], res[1] = array[lp], array[rp]
lp += 1
rp -= 1
return res if res[0] + res[1] == tsum else []

构建乘积数组

题目描述：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]。不能使用除法。

思路：先完成A[0]*A[1]*…*A[i-1]这一部分，再完成A[i+1]*…*A[n-1]这一部分。

# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
B = [1] * len(A)
temp = 1
#先得出B[n-2]=A[0]*A[1]*…*A[n-3]
for i in range(1, len(A)):
temp *= A[i-1]
B[i] *= temp
temp = 1
#再求出B[n-2]=A[0]*A[1]*…*A[n-3]×A[n-1]
#for循环要从n-2开始，使得数组B刚好没有下标是n-2的元素
for i in range(len(A)-2, -1, -1):
temp *= A[i+1]
B[i] *= temp
return B

数据流中的中位数

题目描述：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路：边读入数据边排序，注意奇偶情况下的结果的差异。

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.sortedList = []
def Insert(self, num):
# write code here
n = len(self.sortedList)
self.sortedList.append(num)
#由小到大排序
while n != 0:
if self.sortedList[n] < self.sortedList[n-1]:
self.sortedList[n], self.sortedList[n-1] = self.sortedList[n-1], self.sortedList[n]
else:
break
n -= 1
if n == 0:
self.sortedList[n] = num

def GetMedian(self, x):
# write code here
n = len(self.sortedList)
#奇偶判断
if n % 2 == 0:
return (self.sortedList[n//2]+self.sortedList[n//2-1]) / 2.0
else:
return self.sortedList[n//2]

扑克牌顺子

题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

思路：首先，确定“大小王”的个数。然后，排除组成的牌中有相同的大小的牌的情况。最后，看纯数字牌之间要组成"连续值"所需要的“大小王”的张数，小于等于之前统计得到的“大小王”的个数则说明可以组成“顺子”。

# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if not numbers: return 0
numbers.sort()
cnt = 0
jokers = 0
pre = None
for i in range(len(numbers)):
#得到大小王的个数
if numbers[i] == 0:
jokers += 1
else:
#赋给pre一个初值
if pre is None:
pre = numbers[i]
else:
#有重复数字的话，肯定不是顺子
if pre == numbers[i]: return 0
#累加找到要保证是连续数字，则数字之间相隔的缺失数字的个数
cnt += numbers[i] – pre – 1
pre = numbers[i]
cnt -= jokers
#cnt <= 0表示大小王的个数是足够补上缺失数字的个数的
return cnt <= 0

结尾

亲爱的读者朋友：感谢您在繁忙中驻足阅读本期内容！您的到来是对我们最大的支持❤️

正如古语所言："当局者迷，旁观者清"。您独到的见解与客观评价，恰似一盏明灯💡，能帮助我们照亮内容盲区，让未来的创作更加贴近您的需求。

若此文给您带来启发或收获，不妨通过以下方式为彼此搭建一座桥梁： ✨ 点击右上角【点赞】图标，让好内容被更多人看见 ✨ 滑动屏幕【收藏】本篇，便于随时查阅回味 ✨ 在评论区留下您的真知灼见，让我们共同碰撞思维的火花

我始终秉持匠心精神，以键盘为犁铧深耕知识沃土💻，用每一次敲击传递专业价值，不断优化内容呈现形式，力求为您打造沉浸式的阅读盛宴📚。

有任何疑问或建议？评论区就是我们的连心桥！您的每一条留言我都将认真研读，并在24小时内回复解答📝。

愿我们携手同行，在知识的雨林中茁壮成长🌳，共享思想绽放的甘甜果实。下期相遇时，期待看到您智慧的评论与闪亮的点赞身影✨！

万分感谢🙏🙏您的点赞👍👍、收藏⭐🌟、评论💬🗯️、关注❤️💚～

自我介绍：一线互联网大厂资深算法研发（工作6年+），4年以上招聘面试官经验（一二面面试官，面试候选人400+），深谙岗位专业知识、技能雷达图，已累计辅导15+求职者顺利入职大中型互联网公司。熟练掌握大模型、NLP、搜索、推荐、数据挖掘算法和优化，提供面试辅导、专业知识入门到进阶辅导等定制化需求等服务，助力您顺利完成学习和求职之旅（有需要者可私信联系） 

友友们，自己的知乎账号为“快乐星球”，定期更新技术文章，敬请关注！