剑指offer牛客网练习20200131

剑指offer牛客网练习20200131"/>

剑指offer牛客网练习20200131

1.和为S的连续正数序列

想的方法有点复杂，看了评论区那个滑动窗口的哇瑟= =

# -*- coding:utf-8 -*-
class Solution:def FindContinuousSequence(self, tsum):# write code hereresult=[[]]sumr=0for i in range(1,tsum):sumr+=iresult[-1].append(i)print(result,sumr)while sumr>tsum:sumr-=result[-1].pop(0)if sumr==tsum and i!=tsum-1:result.append(result[-1][2:])sumr=sum(result[-1])print(result,sumr)if sum(result[-1])!=tsum:result.pop()return result

2.和为S的两个数字

# -*- coding:utf-8 -*-
class Solution:def FindNumbersWithSum(self, array, tsum):# write code herea=0b=0for i in array:for j in array:if i==j:continueif i+j==tsum:if a==0 or (a*b>i*j):a=ib=jif a!=0:return [a,b]else:return []

看了讨论区第一的思路后 ，array头和尾设一个指针，若两数和>tsum，则代表j-=1，若两数和<tsum,那么i肯定不是答案之一，i和j的距离越大，乘积就越小

# -*- coding:utf-8 -*-
class Solution:def FindNumbersWithSum(self, array, tsum):# write code herei=0j=len(array)-1result=[]while(i<j):temp=array[i]+array[j]print(i,j,array[i],array[j],temp)if temp>tsum:j-=1elif temp<tsum:i+=1else:if (result and result[0]*result[1]>array[i]*array[j]) or not result:result=[array[i],array[j]]i+=1j-=1return result

3.左旋转字符串

# -*- coding:utf-8 -*-
class Solution:def LeftRotateString(self, s, n):# write code hereif not s:return ""n=n%len(s)return s[n:]+s[:n]

4.反转单词顺序

# -*- coding:utf-8 -*-
class Solution:def ReverseSentence(self, s):# write code herel=s.split(" ")l=l[::-1]return ' '.join(l)

5.扑克牌顺子

主要注意：1.有没有五张牌 2.牌存在重复3.大小王能弥补间隔吗

class Solution:def IsContinuous(self, numbers):# write code herenumbers.sort()print(numbers)if len(numbers)<5:return Falsecount0=0leiji=0youyong=len(numbers)for i in range(0,len(numbers)-1):if numbers[i]==0:count0+=1youyong-=1else:if numbers[i]!=numbers[i+1]:leiji+=numbers[i+1]-numbers[i]-1else:youyong-=1print(count0,leiji,youyong)if count0>=leiji and youyong+count0>=5:return Trueelse:return False

6.孩子们的游戏（圆圈中最后剩下的数）

约瑟夫环问题

# -*- coding:utf-8 -*-
class Solution:def LastRemaining_Solution(self, n, m):# write code herel=list(range(0,n))result=-1temp=0while(l):print(l,temp,result,(temp+m-1)%len(l))t=(temp+m-1)%len(l)result=l.pop(t)temp=treturn result

7.求1+2+3+..+n

刚开始没注意不能使用乘除法= =

# -*- coding:utf-8 -*-
class Solution:def Sum_Solution(self, n):# write code heretemp=1+ncount=int(n/2)res=n%2return count*temp+res*(int(n/2)+1)

看了讨论区的我表示？？？？稍微了解了一下短路求值，bye

8.不用加减乘除做加法

。。。按照位运算写了一个超时了

# -*- coding:utf-8 -*-
class Solution:def Add(self, num1, num2):# write code herewhile(num2!=0):temp=num1^num2num2=(num1&num2)<<1num1=tempreturn num1

9.把字符转换为整数

看评论区有直接建立一个array表示【‘0’，‘’1】啥的，下标就可以是数字了

溢出的处理表示很懵逼

# -*- coding:utf-8 -*-
class Solution:def StrToInt(self, s):# write code hereresult=0flag=Truefu=Falsefor i in s:if flag:fu=(i=='-')if i>='0' and i<='9':t=ord(i)-ord('0')result=result*10+telse:if not flag:result=0breakflag=Falseif fu:result*=-1if result>=2147483648 or result<=-2147483649:return 0return result