剑指offer牛客网练习20200131

谁践踏了优雅 2023-07-03 02:38 13阅读 0赞

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

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

# -*- coding:utf-8 -*-
    class Solution:
        def FindContinuousSequence(self, tsum):
            # write code here
            result=[[]]
            sumr=0
            for i in range(1,tsum):
                sumr+=i
                result[-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 here
            a=0
            b=0
            for i in array:
                for j in array:
                    if i==j:
                        continue
                    if i+j==tsum:
                        if a==0 or (a*b>i*j):
                            a=i
                            b=j
            if 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 here
            i=0
            j=len(array)-1
            result=[]
            
            while(i<j):
                temp=array[i]+array[j]
                print(i,j,array[i],array[j],temp)
                if temp>tsum:
                    j-=1
                elif temp<tsum:
                    i+=1
                else:
                    if (result and result[0]*result[1]>array[i]*array[j]) or not result:
                        result=[array[i],array[j]]
                    i+=1
                    j-=1
            return result

3.左旋转字符串

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

4.反转单词顺序

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

5.扑克牌顺子

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

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

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

约瑟夫环问题

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

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

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

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

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

8.不用加减乘除做加法

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

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

9.把字符转换为整数

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

溢出的处理表示很懵逼

# -*- coding:utf-8 -*-
    class Solution:
        def StrToInt(self, s):
            # write code here
            result=0
            flag=True
            fu=False
            for i in s:
                if flag:
                    fu=(i=='-')
                if i>='0' and i<='9':
                    t=ord(i)-ord('0')
                    result=result*10+t
                else:
                    if not flag:
                        result=0
                        break
                flag=False
            if fu:
                result*=-1
            if result>=2147483648 or result<=-2147483649:
                return 0
            return result