41.和为S的连续正数序列
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
思路：因为是连续的整数序列，故从1开始；对于一个子序列，如果该子序列的值小于给定的值，则应该加上下一个值，
如果大于该值，则去除序列中的第一个值，当序列中第一个值大于设定值的一半时，停止循环
class Solution:def findContinueSeq(self,sumA):a,b=1,2res=[]while a<=sumA//2:t=list(range(a,b+1))if sum(t)==sumA:res.append(t)a+=1b+=1elif sum(t)<sumA:b+=1else:a+=1return ress=Solution()r=s.findContinueSeq(100)
print(r)
42.和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的
和等于S，输出两个数的乘积最小的。
思路1：因为是一个增序的序列，因此可以从头部和尾部给定两个指针来控制，首先找出所有的数字对，然后给出
乘积最小的一对
思路2：还有一个理论说对于和相等的两个数，相互之间的差别越大，那么乘积越小，头部和尾部两个指针找到的
第一对即为乘积最小的合为S的两个数字
class Solution:def findPairsWithSum1(self,a,sumA):s=0e=len(a)-1res=[]while s<e:if a[s]+a[e]==sumA:res.append([a[s],a[e]])s+=1elif a[s]+a[e]<sumA:s+=1else:e-=1if len(res)==0:return []else:res=sorted(res,key=lambda x:x[0]*x[1],reverse=False)return res[0]def findPairsWithSum2(self,a,sumA):s=0e=len(a)-1while s<e:if a[s]+a[e]==sumA:return [a[s],a[e]]s+=1elif a[s]+a[e]<sumA:s+=1else:e-=1return []s=Solution()
a=[1,2,3,4,5,6,7,8,9,10,12]
r1=s.findPairsWithSum1(a,12)
r2=s.findPairsWithSum2(a,12)print(r1,r2)
43.左旋转字符串
对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。
例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
思路：python中的分片 即可直接实现a[bit:]+a[0:bit]
class Solution:def leftRotateStr(self,s,k):if len(s)<=0:return ''k=k%len(s)return s[k:]+s[0:k]s=Solution()
a="HJKasdfgxcvbm"
r1=s.leftRotateStr(a,3)
r2=s.leftRotateStr(a,26)
print(r1,r2)
44.翻转单词顺序列
例如，“student. a am I”翻转为“I am a student.”。
思路：按空格切分为数组，反转数组用空格连接
class Solution:def reverseSentence(self,s):words=s.split(" ")return " ".join(words[::-1])a="student. a am I"s=Solution()
r=s.reverseSentence(a)
print(r)
45.扑克牌顺子
一副扑克牌,里面有2个大王，2个小王，从中随机抽出5张牌，如果牌能组成顺子就输出true，否则就输出
false。为了方便起见，大小王是0，大小王可以当作任何数字。
思路：
1、将数组排序；
2、统计数组中0的个数，即判断大小王的个数；
3、判断非0数中是否存在对子，存在返回False；否则，统计数组中相邻数字之间的空缺总数gap;如果gap
小于0的个数；返回True，否则返回False
class Solution:def isContinue(self,a):if(len(a)<5):return Falsea.sort()num0=a.count(0)gap=0for i in range(num0,len(a)-1):#是否存在对子if a[i+1]==a[i]:return False#统计gapgap+=(a[i+1]-a[i]-1)if gap<=num0:return Truereturn Falses=Solution()
a1=[1,2,3,4,5]
a2=[2,4,0,0,8]
r1=s.isContinue(a1)
r2=s.isContinue(a2)
print(r1,r2)
46.孩子们的游戏（圆圈中最后剩下的数）
游戏是这样的：首先，让小朋友们围成一个大圈。然后，他随机指定一个数m，让编号为0的小朋友开始报数。
每次喊到m-1的那个小朋友要出列，不再回到圈中，从他的下一个小朋友开始，继续0...m-1报数....
这样下去....直到剩下最后一个小朋友获胜，获胜的小朋友编号多少？(注：小朋友的编号是从0到n-1)
思路：构造f[n]表示编号0，1...n-1的序列每次删除的第m个数；
第一个出局的人编号为m%n-1；下次起始位点k=m%n，剩余编号如下：
k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2
对应报数关系：
现在我们把他们的编号做一下映射，变为f'(n-1)的子问题：
k –> 0
k+1 –> 1
k+2 –> 2
…
…
k-2 –> n-2
k-1 –> n-1
映射后x的变化为x=(x-k)%n x为正常序列0，1...n-1
原始的x则可表示为x’=(x+k)%n
得到递推关系n=1;f[1]=0
n>1;f[n]=(f[n-1] +m)%n
class Solution:def lastRemain(self,n,m):if n<1 or m<1:return -1a=list(range(n))i=0while len(a)>1:i=(i+m-1)%len(a)a.pop(i)return a[0]s=Solution()
r=s.lastRemain(3,3)
print(r)
47.求1+2+3+...+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
思路：将加法问题转化为递归进行求解即可。
class Solution:def __init__(self):self.sumN=0def getSumN(self,n):if n<=0:return 0self.getSum(n)return self.sumNdef getSum(self,n):if n==0:return self.sumN+=nself.getSum(n-1)s=Solution()
r=s.getSumN(10)
print(r)
48.不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：
对数字做运算，除了加减乘除外，还有位运算，位运算是针对二进制的，二进制的运算有“三步走”策略：
1、不考虑进位对每一位相加，0加0、1加1的结果都是0，1加0、0加1的结果都是1；与异或运算相同
2、至于进位，只有1加1的时候产生进位。类似位与运算，1左移一位。
3、循环相加直到进位为0
class Solution:def add(self,n1,n2):while (n2):n1,n2=n1^n2,(n1&n2)<<1return n1 s=Solution()
r=s.add(8,3)
print(r)
49.把字符串转换成整数
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字
要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值
则返回0。
输入：+2147483647 ，输出：2147483647；输入：1a33，输出：0。
思路：1、判断符号：用flag标记符号，如果s[0]为-，flag=-1 s=s[1:]
2、反转s，循环累加s[i]*10**i；在循环过程中遇到非"0123456789"中的数，返回0
class Solution:def str_to_int(self,s):if s=='':return 0flag=1if s[0] in "+-":if s[0]=='-':flag=-1s=s[1:]s=reversed(s)r=0for i,c in enumerate(s):if c not in "0123456789":return 0else:r+=(ord(c)-ord("0"))*(10**i)r=r*flagif r>-2**32 and r<2**32-1:return rreturn 0s=Solution()
r=s.str_to_int("+123456756")
print(r)
50.数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几
个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入
长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路：hash表统计每个数字出现的次数；返回出现次数大于1的数
class Solution:def get_duplicated(self,a):res=[]for i in a:if a.count(i)>1:res.append(i)return list(set(res))s=Solution()
a=[1,2,3,4,2,6,7,4]
r=s.get_duplicated(a)
print(r)