方法一：
class Solution:
def GetNumberOfK(self , nums: List[int], k: int) -> int:
#从两边开始找，找到之后记录当前位置
left = 0
right = len(nums) - 1
if k not in nums:
return 0
start = len(nums) - 1
end = 0
while left <= right:
if nums[left] < k:
left += 1
if nums[left] == k:
start = min(left,start)
left += 1
if nums[right] > k :
right -= 1
if nums[right] == k:
end = max(right,end)
right -= 1
return end - start + 1
方法二：
class Solution:
def divice(self,nums,k):
left = 0
right = len(nums) - 1
while left <= right:
mid = (right + left)//2
if nums[mid] < k:
left = mid + 1
elif nums[mid] > k:
right = mid - 1
return left
def GetNumberOfK(self , nums: List[int], k: int) -> int:
#二分法查找k+0.5和k-0.5的位置，中间部分就是k
return self.divice(nums,k+0.5) - self.divice(nums,k-0.5)
#线性搜索：首先从数组左下角搜索，如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。查找到target,返回true; 如果越界，返回false;
class Solution:
def Find(self , target: int, array: List[List[int]]) -> bool:
if len(array) == 0:
return False
row = len(array)
col = len(array[0])
c,r = 0,row - 1 #从左下角开始搜索
while c < col and r >= 0:
temp = array[r][c]
if temp < target:#往右移动
c += 1
if temp > target: #往上移动
r -= 1
if temp == target:
return True
return False
# 旋转之后，前半段和后半段都是升序，所以要确定最小值在后半段
#二分法，如果mid比right大，那mid在前半段中，让left = mid+1;如果mid比right小，mid在后半段，让right=mid,如果等无法判断是前半段还是后半段，right-=1，缩小判断范围。
class Solution:
def minNumberInRotateArray(self , nums: List[int]) -> int:
left = 0
right = len(nums) - 1
if len(nums) == 0:
return 0
while left < right:
mid = (right+left)//2
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
elif nums[mid] == nums[right]:
right -= 1
return nums[left]
全排列，递归回溯，每次将递归的层数和字符串下传，在[h，size-1]中的元素互换，然后递归，递归回来恢复现场
class Solution:
def Permutation(self , s: str) -> List[str]:
ans = []
s = list(s)
def dfs(h,string):
if h == len(s) - 1:
nonlocal ans
ans.append(''.join(s))
return
for i in range(h,len(s)):
s[i],s[h] = s[h],s[i]
dfs(h+1,s)
s[i],s[h] = s[h],s[i] #恢复现场
dfs(0,s)
ans = list(set(ans)) #因为没有在递归的时候拦住相等的元素重排列， 所以最后要去重
return ans
class Solution:
def findNthDigit(self , n: int) -> int:
#1~9 9*1=9个数字
#10~99 9*10*2=180个数字
#100~999 9*100*3=2700个数字
weishu = 1 #当前数字一共有多少位
start = 1 #当前数字起始区间的一个数字是多少
Sum = 9 #该区间一共多少个数字
while n > Sum:
n -= Sum
weishu += 1
start *= 10
Sum = 9*weishu*start
num = start+(n-1)//weishu #确定是哪个数字
index = (n-1)%weishu #确定数字在哪一位
return int(str(num)[index])
class Solution:
def add(self, a: int, b: int) -> int:
#要考虑负数的情况，python是用补码存储
x = 0xffffffff
a,b = a & x,b & x #获取补码
while b != 0:
a,b = a ^ b, (a & b)<<1 & x #可能超32位的也要补码
return a if a <= 0x7fffffff else ~(a^x) #按位取反后将整个数字取反
class Solution:
def NumberOf1(self , n: int) -> int:
#考虑移位运算，每次移动一位;遍历二进制的32位，通过移位0-31次实现
#将移位后的1与数字进行位与运算，结果为1就记录一次。
res = 0
for i in range(32):
if n & (1 << i) != 0:
res += 1
return res
用递归来累加
class Solution:
def Sum_Solution(self, n):
if n == 1:
return 1
return self.Sum_Solution(n-1)+n
方法一：使用哈希表，遍历数组，如果数组中的元素在key中，就删除掉这个元素。如果不在key中，就将其值置为1.最后排序一下哈希表，输出key。
class Solution:
def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:
#第一种，使用哈希表
dict_data = {}
for i in nums:
if i not in dict_data:
dict_data[i] = 1
else:
dict_data.pop(i)
res = [i for i in sorted(dict_data.keys())]
return res
#第二种，位运算
class Solution:
def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:
#先将全部进行异或运算，得到的是两个不同的数的异或结果
temp = 0
for i in nums:
temp ^= i
#分组，每组求出一个异或结果；从最低位开始找到这两个数不同的那个二进制1
mask = 1
while temp & mask == 0:
mask = mask << 1
#根据mask的分组结果，将两组数据进行异或
a = 0
b = 0
for i in nums:
if i & mask == 0:
a ^= i
else:
b ^= i
return [a,b] if a < b else [b,a]
class Solution:
def Power(self , base: float, exponent: int) -> float:
#如果两个通时是0就判错返回
if base == 0 and exponent == 0:
return False
#特别处理负次幂
if exponent < 0:
base = 1/base
exponent = -exponent
#根据幂指数累乘
res = 1
for i in range(exponent):
res *= base
return res
class Solution:
def printMatrix(self, matrix):
#顺时针就是先向右移动，到底后向下，然后向左，再向上。设置四个边界，每次遍历之后就更新边界，遇到边界后退出。
res = []
if len(matrix) == 0:
return []
left,right,down,up = 0, len(matrix[0]) - 1, len(matrix) - 1, 0
#直到边界重合
while left <= right and up <= down:
#先从左到右
for i in range(left,right+1):
res.append(matrix[up][i])
up += 1 #重置行数
if up > down: #重置之后要判断当前是否已经没有剩余行了
break
#从上到下
for i in range(up,down+1):
res.append(matrix[i][right])
right -= 1 #重置列
if right < left: #重置之后查看当前是否已经没有剩余列了
break
#从右往左
for i in range(right,left-1,-1):
res.append(matrix[down][i])
down -= 1 #重置行
#从下往上
for i in range(down,up-1,-1):
res.append(matrix[i][left])
left += 1 #重置列
return res
给数组排序， 然后计算0的个数，找到第一个不是0的数，计算两两之间的差值；如果出现了两个相同的不为0的数，就一定不是顺子；0的个数大于累加和就是顺子。
class Solution:
def IsContinuous(self , numbers: List[int]) -> bool:
#将数组排序，计算0的个数，超过4就返回FALSE，找到第一个不为0的数，计算两两差值，累加和0比较。
num_0 = 0
sum_0 = 0
numbers = sorted(numbers)
for i in range(len(numbers)-1):
if numbers[i] == 0:
num_0 += 1
else:
sum_0 += numbers[i+1] - numbers[i] - 1 if numbers[i+1] > numbers[i] else 1000 #保证sum_0在不是顺子的时候大于num_0.
if num_0 > 4:
return False
else:
if num_0 >= sum_0:
return True
else:
return False
class Solution:
def StrToInt(self , s: str) -> int:
#首先去掉字符串的首位空格，然后判断数字的符号位，然后开始遍历字符串，遇到非数字就跳过，最后做范围判断
#去空格
s = s.strip()
#长度判断
if len(s) == 0:
return 0
#确定符号位后去掉符号位
sign = -1 if s[0] == '-' else 1
s = s[1:] if s[0] == '+' or s[0] == '-' else s
#拼接res，如果去掉符号位后是空，那最后也能返回0，首字符是0不影响结果
res = ['0']
for i in range(len(s)):
j = i
while j < len(s) and '0' <= s[j] <= '9':
res.append(s[j])
j += 1
break #出循环之后就直接break
# 确定边界值
MAX = 2**31 - 1
MIN = -2**31
#计算整数，并根据边界值输出
ans = sign*int(''.join(res))
if MIN <= ans <= MAX:
return ans
if ans < MIN:
return MIN
if ans > MAX:
return MAX
class Solution:
#判断是否是整数（带符号）
def isInt(self,num):
if len(num) == 0 or (len(num) == 1 and num[0] in ['+','-']):
return False
ans = [i for i in num if not '0' <= i <= '9']
return len(ans) == 0 or (len(ans) == 1 and num[0] in ['+','-'])
#判断是否是小数（带符号）
def isFloat(self,num):
if len(num) == 0 or '.' not in num :
return False
#去掉符号位
num = num[1:] if num[0] in ['+','-'] else num
#获得小数点的下标
ind = num.index('.')
#判断是否是小数
a = self.isInt(num[:ind]) #前半段可以是带符号整数
b = self.isInt(num[ind+1:]) and '+' not in num[ind+1:] and '-' not in num[ind+1:] #后半段不可以带符号
if len(num[:ind]) == 0 : return b #如果前半段为空，后边必须成立
elif len(num[ind+1:]) == 0 : return a #如果后半段是空，前面必须成立
else: return a and b #都不空的时候，都得成立
#判断字符串
def isNumeric(self , s ):
#去空格
s = s.strip()
#判断长度
if len(s) == 0:
return False
#分类判断
for i in range(len(s)):
if '0' <= s[i] <= '9':
continue #数字就跳过
elif s[i] in ['e','E']: #遇到e之后，判断两段
a = self.isFloat(s[:i]) or self.isInt(s[:i]) #前半段整数或小数
b = self.isInt(s[i+1:]) #后半段必须整数
return a and b
elif s[i] == '.': #遇到.
if 'e' in s or 'E' in s: #如果有e，就先跳过
continue
else: #否则判断是否是小数
return self.isFloat(s)
elif s[i] in ['+','-']: #遇到符号位如果是最开始或者e后面，跳过
if i == 0 or s[i-1] in ['e','E']:
continue
else: #否则就是错误的
return False
else: #遇到其他字符直接报错
return False
return '0' <= s[-1] <= '9' #出循环后要保证最后跳过的是数字
文章来源地址https://www.toymoban.com/news/detail-634894.html
文章来源：https://www.toymoban.com/news/detail-634894.html
到了这里，关于《剑指offer》（5）搜索算法、位运算、模拟的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
