目录
- 问题1：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题2：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题3：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题4：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
问题1：
问题链接：
187. 重复的DNA序列
问题描述：
DNA序列 由一系列核苷酸组成，缩写为'A','C','G'和'T'.。*例如，"ACGAATTCCG" 是一个 DNA序列 。 在研究 DNA 时，识别 DNA 中的重复序列非常有用。 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为10的序列(子字符串)。你可以按 任意顺序 返回答案。实例：
示例1： 输入：s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC","CCCCCAAAAA"]示例2： 输入：s="AAAAAAAAAAAAA" 输出：["AAAAAAAAAA"]代码：
#1.利用哈希表#定义一个哈希表 cnt，用于存储所有长度为 10 的子字符串出现的次数。#遍历字符串 s 的所有长度为 10 的子字符串，对于当前子字符串 t，我们更新其在哈希表中对应的计数。如果 t 的计数为 2，我们就将它加入答案。#遍历结束后，返回答案数组即可。classSolution:deffindRepeatedDnaSequences(self,s:str)->List[str]:cnt=Counter()ans=[]foriinrange(len(s)-10+1):t=s[i:i+10]cnt[t]+=1ifcnt[t]==2:ans.append(t)returnans问题2：
问题链接：
188. 买卖股票的最佳时机 IV
问题描述：
给你一个整数数组 prices 和一个整数 k ，其中 prices[i]是某支给定的股票在第i天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。实例：
示例1： 输入：k=2,prices=[2,4,1]输出：2解释：在第1天(股票价格=2)的时候买入，在第2天(股票价格=4)的时候卖出，这笔交易所能获得利润=4-2=2。 示例2： 输入：k=2,prices=[3,2,6,5,0,3]输出：7解释：在第2天(股票价格=2)的时候买入，在第3天(股票价格=6)的时候卖出,这笔交易所能获得利润=6-2=4。 随后，在第5天(股票价格=0)的时候买入，在第6天(股票价格=3)的时候卖出,这笔交易所能获得利润=3-0=3。代码：
classSolution:defmaxProfit(self,k:int,prices:List[int])->int:f=[[-inf]*2for_inrange(k+2)]forjinrange(1,k+2):f[j][0]=0forpinprices:forjinrange(k+1,0,-1):f[j][0]=max(f[j][0],f[j][1]+p)f[j][1]=max(f[j][1],f[j-1][0]-p)returnf[-1][0]问题3：
问题链接：
189. 轮转数组
问题描述：
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。实例：
示例1:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,5]向右轮转3步:[5,6,7,1,2,3,4]示例2:输入：nums=[-1,-100,3,99],k=2输出：[3,99,-1,-100]解释:向右轮转1步:[99,-1,-100,3]向右轮转2步:[3,99,-1,-100]代码：
classSolution:defrotate(self,nums:List[int],k:int)->None:""" Do not return anything, modify nums in-place instead. """# 第一种:这种利用了一个新的数组，采用的deepcopy，不是简单的复制#时间复杂度O(n),空间复杂度O(n)n=len(nums)ans=deepcopy(nums)foriinrange(n):nums[(i+k)%n]=ans[i]浅拷贝和深拷贝的区别是：浅拷贝只是将原对象在内存中引用地址拷贝过来了。让新的对象指向这个地址。而深拷贝是将这个对象的所有内容遍历拷贝过来了，相当于跟原来没关系了，所以如果你这时候修改原来对象的值跟他没关系了，不会随之更改。classSolution:defrotate(self,nums:List[int],k:int)->None:""" Do not return anything, modify nums in-place instead. """#第二种：时间复杂度O(n),空间复杂度O(1)#把一个子数组反转两次，子数组的元素顺序不变。#注：请勿使用切片，会产生额外空间defreverse(i:int,j:int)->None:whilei<j:nums[i],nums[j]=nums[j],nums[i]i+=1j-=1n=len(nums)k%=n reverse(0,n-1)reverse(0,k-1)reverse(k,n-1)#一种思想的解法问题4：
问题链接：
190. 颠倒二进制位
问题描述：
颠倒给定的32位有符号整数的二进制位。实例：
示例1： 输入：n=43261596输出：964176192解释： 整数 二进制432615960000001010010100000111101001110096417619200111001011110000010100101000000示例2： 输入：n=2147483644输出：1073741822解释： 整数 二进制214748364401111111111111111111111111111100107374182200111111111111111111111111111110代码：
classSolution:defreverseBits(self,n:int)->int:#1.循环做法res=0foriinrange(32):#1.res每次右移一位#2.n&1进行与操作，选出最后一维。#3.随后进行或操作，除了0与0才是0，其他都是1res=(res<<1)|(n&1)n>>=1returnres
进阶必会：从“瞎聊”到“精准控制”)
