本系列为剑指offer刷题笔记，刷题平台为牛客网。
本文主要是其他相关题目题解总结。
[TOC]
11.二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路
思路1：
从右往左逐位判断
思路2：
为了避免死循环，我们可以不右移输入的数据n。首先把n和1做与运算，判断n的最低位是不是为1，接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1.。。这样反复左移，每次都能判断n的其中一位是不是1.注意flag要设定范围。循环次数等于二进制的位数。
思路3：（最优）
如果一个整数不为0，那么这个整数至少有一位是1，如果我们把整数减1，那么原来处在整数最右边的1就会变为0, 原来在1后面的所有0都会变为1（如果最右边的1后面还有0的话）。其余所有位将不受影响。
举个例子：一个二进制数1100，从右边起第三位是处于最右边的1，减去1后，第三位变为0，他后面的两个0变为1了，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果就是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0.如1100&1011 = 1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0，那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
在python中，由于负数使用补码表示的，对于负数，最高位为1，而负数在计算机中是以补码存在的，往右移，符号位不变，符号位往右移，最终可能会出现全1的情况，导致死循环。与oxffffffff想与，就可以消去负数的影响。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# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
# 思路1
# if n < 0:
# n = n & 0xffffffff
# count = 0
# while n:
# if n%2 == 1:
# count += 1
# n = n >> 1
# return count
# 思路2
# flag = 1
# count = 0
# while flag and flag <= 0xffffffff:
# if n & flag:
# count += 1
# flag = flag << 1
# return count
# 思路3
if n < 0:
n = n & 0xffffffff
count = 0
while n:
count += 1
n = (n-1)&n
return count
if __name__ == '__main__':
result = Solution().NumberOf1(42)
print(result)
12 数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解题思路
二分求幂，递归。
- 如果n=0，返回1；
- 如果n为负数，相当于求(1.0/x)^(-n)。
- 如果n为正奇数，相当于求 x (x^2)^(n//2)；
- 如果n为正偶数，相当于求 (x^2)^(n//2)。
1 | # -*- coding:utf-8 -*- |
python中等于没有误差，因此可以写出如下代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
if base == 0.0:
return 0
flag = 0
if exponent < 0:
flag = 1
exponent = -exponent
res = 1
for i in range(exponent):
res *= base
if flag:
res = 1.0/res
return res
if __name__ == '__main__':
result = Solution().Power(2,-3)
print(result)
19 顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解题思路
从左往右，再从上往下，再从右往左，最后从下往上遍历.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# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
rows = len(matrix)
cols = len(matrix[0])
left, right = 0, cols-1
top, bottom = 0, rows-1
res = []
while left <= right and top <= bottom:
for i in range(left, right+1):
res.append(matrix[top][i])
for i in range(top+1,bottom+1):
res.append(matrix[i][right])
if top != bottom:
for i in range(right-1,left-1,-1):
res.append(matrix[bottom][i])
if left != right:
for i in range(bottom-1,top,-1):
res.append(matrix[i][left])
left += 1
right -= 1
top += 1
bottom -= 1
return res
if __name__ == '__main__':
result = Solution().printMatrix([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]])
print(result)
29 最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
解题思路
思路1：
使用冒泡排序，找出最小的k个数返回，时间复杂度O(n^2)。
思路2：
另一种O(nlogk)的算法是基于堆排序的，特别适合处理海量数据。
我们可以先创建一个大小为k的数据容器来存储最小的k个数字，接下来我们每次从输入的n个整数中的n个整数中读入一个数。如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中；如果容器已经有k个数字了，也就是容器满了，此时我们不能再插入新的数字而只能替换已有的数字。找出这已有的k个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，于是我们可以抛弃这个整数。
因此当容器满了之后，我们要做3件事情：一是在k个整数中找到最大数；二是有可能在这个容器中删除最大数；三是有可能要插入一个新的数字。如果用一个二叉树来实现这个数据容器，那么我们在O(logk)时间内实现这三步操作。因此对于n个输入数字而言，总的时间效率就是O(nlogk)。
1 | # -*- coding:utf-8 -*- |
31 整数中1出现的次数（从1到n整数中1出现的次数）
题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
解题思路
思路1
从1到n遍历。对每一个数字，每次通过对10求余数判断整数的个位数字是不是1，大于10的除以10之后再判断，我们对每个数字都要做求余和除法运算以求出该数字中1出现的次数。如果输入数字n，n有O(logn)位，我们需要判断每一位是不是1，那么时间复杂度为O(n*logn)。
思路2
考虑将n的十进制的每一位单独拿出讨论，每一位的值记为weight。
1) 个位
从1到n，每增加1，weight就会加1，当weight加到9时，再加1又会回到0重新开始。那么weight从0-9的这种周期会出现多少次呢？这取决于n的高位是多少，看图：
以534为例，在从1增长到n的过程中，534的个位从0-9变化了53次，记为round。每一轮变化中，1在个位出现一次，所以一共出现了53次。
再来看weight的值。weight为4，大于0，说明第54轮变化是从0-4，1又出现了1次。我们记1出现的次数为count，所以：
count = round+1 = 53 + 1 = 54
如果此时weight为0（n=530），说明第54轮到0就停止了，那么：
count = round = 53
2) 十位
对于10位来说，其0-9周期的出现次数与个位的统计方式是相同的，见图：
不同点在于：从1到n，每增加10，十位的weight才会增加1，所以，一轮0-9周期内，1会出现10次。即round*10。
再来看weight的值。当此时weight为3，大于1，说明第6轮出现了10次1，则：
count = round10+10 = 510+10 = 60
如果此时weight的值等于0（n=504），说明第6轮到0就停止了，所以：
count = round10+10 = 510 = 50
如果此时weight的值等于1（n=514），那么第6轮中1出现了多少次呢？很明显，这与个位数的值有关，个位数为k，第6轮中1就出现了k+1次(0-k)。我们记个位数为former，则：
count = round10+former +1= 510+4 +1= 55
3) 更高位
更高位的计算方式其实与十位是一致的，不再阐述。
4) 总结
将n的各个位分为两类：个位与其它位。
对个位来说：
若个位大于0，1出现的次数为round1+1
若个位等于0，1出现的次数为round1
对其它位来说，记每一位的权值为base，位值为weight，该位之前的数是former，举例如图：
则：
- 若weight为0，则1出现次数为round*base
- 若weight为1，则1出现次数为round*base+former+1
- 若weight大于1，则1出现次数为rount*base+base
比如：
- 534 = （个位1出现次数）+（十位1出现次数）+（百位1出现次数）=（531+1）+（510+10）+（0*100+100）= 214
- 530 = （531）+（510+10）+（0*100+100） = 213
- 504 = （501+1）+（510）+（0*100+100） = 201
- 514 = （511+1）+（510+4+1）+（0*100+100） = 207
- 10 = (11)+(010+0+1) = 2
来自 https://blog.csdn.net/yi_afly/article/details/52012593
1 | # -*- coding:utf-8 -*- |
33 丑数
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路
思路：用空间换时间
创建一个数组，里面的数字是排好序的丑数，每个丑数都是前面的丑数乘以2,3,或5得到的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index <= 0:
return 0
t2, t3, t5 = 0, 0, 0
res = [1]
for i in range(1, index):
res.append(min(res[t2]*2, res[t3]*3, res[t5]*5))
if res[-1] == res[t2]*2:
t2 += 1
if res[-1] == res[t3]*3:
t3 += 1
if res[-1] == res[t5]*5:
t5 += 1
return res[-1]
41 和为S的连续正数序列
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
解题思路
设定两个指针，一个指向第一个数，一个指向最后一个数，在此之前需要设定第一个数和最后一个数的值，由于是正数序列，所以可以把第一个数设为1，最后一个数设为2（因为是要求是连续正数序列，最后不可能和第一个数重合）。下一步就是不断改变第一个数和最后一个数的值。
如果第一个数到最后一个数的和正好是要求的和，那么把所有的数都添加到一个序列中。
如果大于要求的和，这说明从第一个数到最后一个数之间的范围太大，因此减小范围，需要把第一个数的值加1，此时当前和变为减去原来的第一个数的值。
如果小于要求的和，说明范围太小，因此把最后一个数加1，此时当前和变为加上最后一个数的值。
这样不断修改第一个和最后一个数的值，就能确定所有连续正数序列的和等于S的序列了。
连续序列和公式:sum = (a+b)(b-a+1)/2
1 | # -*- coding:utf-8 -*- |
42 和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
解题思路
对于一个数组，我们可以定义两个指针，一个从左往右遍历（l），另一个从右往左遍历（r）。首先，我们比较第一个数字和最后一个数字的和curSum与给定数字tsum，
如果curSum == tsum，那么这两个数字就是我们要找的数字，直接输出，这里已经保证了乘积的最小。
如果curSum > tsum，我们需要减小输入值，r向左移动一位。
如果curSum < tsum，我们需要加大输入值，l向右移动一位。
如果没有找到，输出[]。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if len(array)<=1:
return []
left, right = 0, len(array)-1
while left < right:
if array[left]+array[right]==tsum:
return [array[left],array[right]]
elif array[left]+array[right] > tsum:
right -= 1
else:
left += 1
return []
if __name__ == '__main__':
result = Solution().FindNumbersWithSum([1,2,3,4,6],5)
print(result)
45 扑克牌顺子
题目描述
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。
解题思路
满足一下信息才认为是顺子：
输入数据个数为5
输入数据都在0-13之间
没有相同的数字
最大值与最小值之差不大于5
注意为什么是numbers[big]-numbers[small]-1，因为0是用来填补空缺的，如果空缺是1则不用填补，这个做法我们看出不等于1的空缺有多少。
1 | # -*- coding:utf-8 -*- |
46 孩子们的游戏（圆圈中最后剩下的数）
题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
解题思路
第一个被删除的数字是(m-1)%n，记为k，那么删除k之后的数字为0,1,…,k-1,k+1,…,n-1，并且下一个开始计数的数字是k+1。即有以下关系
k+1—>0
k+2—>1
n-1 —> n-k-2
0 — > n-k-1
k-1 —> n-2
总结：设置变化前有n个元素，出现小孩序号为k，那么k=(m-1)%n，设置剩余小孩调整前原始序号为x，那么调整后为f(x)=(x-k-1)%n，将k值代入有:f(x) = x0 = (x-(m-1)%n - 1)%n = (x-m)%n 所以已知x0新序号推原序号为x=(x0+m)%n
1
2
3
4
5
6
7
8
9
10
11
12
13# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n < 1 or m < 1:
return -1
last = 0
for i in range(2, n + 1):
last = (last + m) % i
return last
if __name__ == '__main__':
result = Solution().LastRemaining_Solution(6,4)
print (result)
47 求1+2+3+…+n
题目描述
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
解题思路
思路1：递归
思路2：与逻辑的短路特性做递归停止条件1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here
#思路1
#if n == 1:
# return 1
#return self.Sum_Solution(n-1)+n
# 思路2
return n>0 and n + self.Sum_Solution(n-1)
if __name__ == '__main__':
result = Solution().Sum_Solution(10)
print(result)
48 不用加减乘除的加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
解题思路
首先看十进制是如何做的： 5+7=12，
可以使用三步走：
第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。 同样我们可以
三步走的方式计算二进制值相加： 5-101，7-111
第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步：重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
Python需要处理负数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
unit = (num1^num2)& 0xFFFFFFFF
carry = ((num1&num2)<<1) & 0xFFFFFFFF
while carry:
temp1 = unit
temp2 = carry
unit = (temp1^temp2) & 0xFFFFFFFF
carry = ((temp1&temp2)<<1) & 0xFFFFFFFF
return unit if unit<=0x7FFFFFFF else ~(unit^0xFFFFFFFF)
if __name__ == '__main__':
result = Solution().Add(-12,-104)
print (result)
54 字符流中第一个不重复的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。
解题思路
这道题还是很简单的。将字节流保存起来，通过哈希表统计字符流中每个字符出现的次数，顺便将字符流保存在string中，然后再遍历string，从哈希表中找到第一个出现一次的字符。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# -*- coding:utf-8 -*-
class Solution:
# 返回对应char
def FirstAppearingOnce(self):
# write code here
for i in self.word:
if self.charCount[i] == 1:
return i
return '#'
def Insert(self, char):
# write code here
self.word += char
if char not in self.charCount:
self.charCount[char] = 1
else:
self.charCount[char] += 1
def __init__(self):
self.word = ''
self.charCount = {}
if __name__ == '__main__':
word = 'google'
S = Solution()
for c in word:
S.Insert(c)
result = S.FirstAppearingOnce()
print(result)
63 数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路
初始化一个数组，读入数据后，排序，直接计算1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.numbers = []
def Insert(self, num):
# write code here
self.numbers.append(num)
def GetMedian(self):
# write code here
self.numbers.sort()
if len(self.numbers) % 2 == 1:
return self.numbers[len(self.numbers)//2]
else:
return (self.numbers[len(self.numbers)//2]+self.numbers[len(self.numbers)//2-1])/2.0
if __name__ == '__main__':
numbers = [1,2,3,4]
S = Solution()
for i in numbers:
S.Insert(i)
result = S.GetMedian()
print(result)
64 滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
解题思路
1 | # -*- coding:utf-8 -*- |
