bugku——cookies（cookies欺骗）
2025/12/17 1:30:49
目录
- 问题1：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题2：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题3：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题4：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题5：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题6：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题7：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
问题1：
问题链接：
162. 寻找峰值
问题描述：
峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1]=nums[n]=-∞ 。 你必须实现时间复杂度为O(log n)的算法来解决此问题。实例：
示例1： 输入：nums=[1,2,3,1]输出：2解释：3是峰值元素，你的函数应该返回其索引2。 示例2： 输入：nums=[1,2,1,3,5,6,4]输出：1或5解释：你的函数可以返回索引1，其峰值元素为2； 或者返回索引5， 其峰值元素为6。代码：
classSolution:deffindPeakElement(self,nums:List[int])->int:#1.使用二分left,right=-1,len(nums)-1whileleft+1<right:mid=(left+right)//2ifnums[mid]>nums[mid+1]:#下坡，峰顶位置在mid左边right=midelse:left=midreturnrightclassSolution:deffindPeakElement(self,nums:List[int])->int:#1.使用二分left,right=-1,len(nums)-1whileleft+1<right:mid=(left+right)//2ifnums[mid]>nums[mid+1]:#下坡，峰顶位置在mid左边right=midelse:left=midreturnright问题2：
问题链接：
164. 最大间距
问题描述：
给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于2，则返回0。 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。实例：
示例1:输入:nums=[3,6,9,1]输出:3解释:排序后的数组是[1,3,6,9],其中相邻元素(3,6)和(6,9)之间都存在最大差值3。 示例2:输入:nums=[10]输出:0解释:数组元素个数小于2，因此返回0。代码：
桶排序
classSolution:defmaximumGap(self,nums:List[int])->int:#2.桶排序m=min(nums)M=max(nums)ifM-m<=1:returnM-m n=len(nums)ans=d=(M-m+n-2)//(n-1)# 答案至少是 dbuckets=[[inf,-inf]for_inrange((M-m)//d+1)]forxinnums:b=buckets[(x-m)//d]b[0]=min(b[0],x)# 维护桶内元素的最小值和最大值b[1]=max(b[1],x)pre_max=infformn,mxinbuckets:ifmn!=inf:# 非空桶# 桶内最小值，减去上一个非空桶的最大值ans=max(ans,mn-pre_max)pre_max=mxreturnansclassSolution:defmaximumGap(self,nums:List[int])->int:#1.不是用桶排序ifnotnumsorlen(nums)<=1:return0nums.sort(reverse=True)returnmax(nums[i]-nums[i+1]foriinrange(len(nums)-1))问题3：
问题链接：
165. 比较版本号
问题描述：
给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点'.'分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。 比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为0。 返回规则如下： 如果 version1<version2 返回-1， 如果 version1>version2 返回1， 除此之外返回0。实例：
示例1： 输入：version1="1.2",version2="1.10" 输出：-1解释： version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2<10，所以 version1<version2。 示例2： 输入：version1="1.01",version2="1.001" 输出：0解释： 忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。 示例3： 输入：version1="1.0",version2="1.0.0.0" 输出：0解释： version1 有更少的修订号，每个缺失的修订号按 "0" 处理。代码：
classSolution:defcompareVersion(self,version1:str,version2:str)->int:#2.双指针做法m,n=len(version1),len(version2)i=j=0whilei<morj<n:a=b=0whilei<mandversion1[i]!='.':a=a*10+int(version1[i])i+=1whilej<nandversion2[j]!='.':b=b*10+int(version2[j])j+=1ifa!=b:return-1ifa<belse1i,j=i+1,j+1return0classSolution:defcompareVersion(self,version1:str,version2:str)->int:#1.库函数做法a=map(int,version1.split('.'))b=map(int,version2.split('.'))forver1,ver2inzip_longest(a,b,fillvalue=0):ifver1!=ver2:return-1ifver1<ver2else1return0问题4：
问题链接：
166. 分数到小数
问题描述：
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。 如果小数部分为循环小数，则将循环的部分括在括号内。 如果存在多个答案，只需返回 任意一个 。 对于所有给定的输入，保证 答案字符串的长度小于104。 注意，如果分数可以表示为有限长度的字符串，则 必须 返回它。实例：
示例1： 输入：numerator=1,denominator=2输出："0.5" 示例2： 输入：numerator=2,denominator=1输出："2" 示例3： 输入：numerator=4,denominator=333输出："0.(012)"代码：
classSolution:deffractionToDecimal(self,numerator:int,denominator:int)->str:sign='-'ifnumerator*denominator<0else''numerator=abs(numerator)# 保证下面的计算过程不产生负数denominator=abs(denominator)# 计算整数部分 q 和初始余数 rq,r=divmod(numerator,denominator)ifr==0:# 没有小数部分returnsign+str(q)ans=[sign+str(q)+'.']r_to_pos={r:1}# 初始余数对应小数点后第一位whiler:# 计算小数点后的数字 q，更新 rq,r=divmod(r*10,denominator)ans.append(str(q))ifrinr_to_pos:# 有循环节pos=r_to_pos[r]# 循环节的开始位置returnf"{''.join(ans[:pos])}({''.join(ans[pos:])})"r_to_pos[r]=len(ans)# 记录余数对应位置return''.join(ans)# 有限小数问题5：
问题链接：
167. 两数之和 II - 输入有序数组
问题描述：
给你一个下标从1开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1]和 numbers[index2]，则1<=index1<index2<=numbers.length 。 以长度为2的整数数组[index1,index2]的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。实例：
示例1： 输入：numbers=[2,7,11,15],target=9输出：[1,2]解释：2与7之和等于目标数9。因此 index1=1,index2=2。返回[1,2]。 示例2： 输入：numbers=[2,3,4],target=6输出：[1,3]解释：2与4之和等于目标数6。因此 index1=1,index2=3。返回[1,3]。 示例3： 输入：numbers=[-1,0],target=-1输出：[1,2]解释：-1与0之和等于目标数-1。因此 index1=1,index2=2。返回[1,2]。代码：
classSolution:deftwoSum(self,numbers:List[int],target:int)->List[int]:n=len(numbers)left,right=0,n-1whileleft<right:count=numbers[left]+numbers[right]ifcount==target:return[left+1,right+1]elifcount<target:left+=1else:right-=1return[]问题6：
问题链接：
168. Excel 表列名称
问题描述：
给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。 例如： A->1B->2C->3...Z->26AA->27AB->28...实例：
示例1： 输入：columnNumber=1输出："A" 示例2： 输入：columnNumber=28输出："AB" 示例3： 输入：columnNumber=701输出："ZY" 示例4： 输入：columnNumber=2147483647输出："FXSHRXW"代码：
classSolution:defconvertToTitle(self,n:int)->str:ans=[]whilen:n-=1ans.append(chr(n%26+ord('A')))n//=26return''.join(ans[::-1])问题7：
问题链接：
169. 多数元素
问题描述：
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。实例：
示例1： 输入：nums=[3,2,3]输出：3示例2： 输入：nums=[2,2,1,1,1,2,2]输出：2代码：
classSolution:defmajorityElement(self,nums:List[int])->int:#第一种做法#nums.sort()#return nums[len(nums)//2]#第二种做法:mode通常用于统计数据集中出现频率最高的元素#return mode(nums)#第三种解法：哈希表#dict_1={}#for item in nums:# if item not in dict_1:# dict_1[item]=0# else:# dict_1[item]+=1#return max(dict_1,key=dict_1.get) # 返回出现次数最多的元素#第三种解法：摩尔投票#推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。votes=0#初始化：票数统计votes=0,众数xfornuminnums:ifvotes==0:x=num#当票数 votes 等于 0 ，则假设当前数字 num 是众数。votes+=1ifnum==xelse-1#当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 。returnx