当前位置：首页 > news >正文

网站企业建设方案电工培训

news 2025/8/17 15:09:23

网站企业建设方案,电工培训,为什么运行wordpress,武汉市网络商城设计公司53. 最大子序和第二次做这个题,我对这个题完全一点印象都没有,所以怎么办呢?当然是再想一遍白思路1:可以看到,找到具有最大和的连续子数组--也就是说如果你从右往左找最大的,那么一定是绕不过每一个数的(除非不选)如:[-2,1,-3,4,-1,2,1,-5,4]从右往左看:[2,4,3,6,2,3,1,-1,…

53. 最大子序和

'''第二次做这个题,我对这个题完全一点印象都没有,所以怎么办呢?当然是再想一遍白
''''''思路1:可以看到,找到具有最大和的连续子数组--也就是说如果你从右往左找最大的,那么一定是绕不过每一个数的(除非不选)如:[-2,1,-3,4,-1,2,1,-5,4]从右往左看:[2,4,3,6,2,3,1,-1,4]就是如果你想要过去这个位置,就一定要看一下后面能不能变大,就是说后面的该位置的最大值是不是正数是不是我能走下去的依据
'''
#这个代码的本质是动态规划
#还有一种分治的写法,不过感觉挺难,先放着
def fun1(nums):max=nums[len(nums)-1]for i in reversed(range(len(nums)-1)):if nums[i+1]>0:nums[i]=nums[i]+nums[i+1]if nums[i]>max:max=nums[i]return max
fun1([-2,1,-3,4,-1,2,1,-5,4])

'''首先我是一个专业的小偷,那我要怎么偷,才可以偷的最多?因为两间相邻的房屋,不能在一晚上同时被偷,所以我要好好指定策略--能偷的时候一定要偷(基本素养问题哈哈哈)--那么既然我见人就偷,不就只有两种情况了第一次偷,或者第一次不偷?''''''方法一:既然见人就偷,才有美好明天(金额最大),那么只能分为两种情况,第一次偷和第一次不偷就直接一次遍历结束掉试了一下,有个问题,我没有考虑到,就是如果一群穷人中有一个富人,那么我见到穷人就偷,富人不就偷不到了?这样的话亏的反而更多
'''
def fun1(nums):s=0l=1sum_s=0sum_l=0while s<len(nums) or l<len(nums):if s<len(nums):sum_s+=nums[s]if l<len(nums):sum_l+=nums[l]s+=2l+=2return max(sum_s,sum_l)
print(fun1([2,1,1,2]))'''像这种最优解问题,动态规划是非常有效的首先能偷就偷是一定的,在这个房子里面偷了,有赚的,不偷毛都没有max(f(i))=f(i)+max(f(i+2<i))
'''def fun2(nums):if len(nums)==1:return nums[0]n=len(nums)ls=[0]*nls[n-1]=nums[n-1]ls[n-2]=nums[n-2]max_=max(ls[n-1],ls[n-2])for i in reversed(range(len(nums)-2)):ls[i]=nums[i]+max(ls[i+2::])if max_<ls[i]:max_=ls[i]return max_
print(fun2([2,1,1,2]))'''这里其实可以再化简一下,每次还额外的查找max(ls[i+2::])其实不需要,那个变量或者列表记录就好
'''

====================================================================================================================================================================================================================================
384. 打乱数组
这里有个名字听起来很高级的算法,但其实逻辑很简单
就是迭代的过程中,减少了列表的修改所需时间
就是无论如何,把剩下没有抽取的"签"放在一起,等我抽就行了,已经抽了的
签在也看不到就好了

'''这是是一类设计题目:我现在需要设计一个类:其中包含:--一个初始化函数--一个返回初始状态函数--一个返回随机打乱数组函数
''''''这类题目我做的并不多,所以可能会出现问题我就先试试random的随机打乱不用试了,他需要返回随机打乱所有的可能结果那么random本身属于伪随机,根本做不到
''''''昨天,因为没有什么思路,看了一下答案的解析,发现了他是进行抽签抽签(无放回)中每一个签被抽到的概率是等可能的,1/n所以就可以把所有情况随机出来
'''
import random
class Solution:def __init__(self, nums):self.nums=numsself.arr=nums.copy()def reset(self):self.nums=self.arr.copy()return self.numsdef shuffle(self):#返回打乱后的数组shuzhu=self.nums.copy()for i in range(len(self.nums)):#总共抽取的次数self.nums[i]=shuzhu.pop(random.randint(0,len(shuzhu)-1))return self.numsnums=[[0,-12893,128384]]
ls=list(nums)
ls[0][1]=10
print(nums)#Fisher-Yates 洗牌算法
#这种算法,是很像暴力枚举算法的,但是避免掉了每次迭代过程中,修改列表的时间
'''基本思想:--就像抽签一样,每次抽一个,已经被抽取过的不能抽了--那么我就需要对已经抽取过的进行删除--上面的删除是真删除,对列表进行了修改--但其实有更好的方法:假设有一数组:[0,-3,-4,9,5,1],当前位置为cur,抽取元素下标为:index,此时cur还没动等于0第一次(0,len):数组中每个元素都能取,假设取index=3,与当前位置交换变为:[9,-3,-4,0,5,1],cur+1第二次(1,len):.......不断的迭代这就相当于不放回的抽取
'''import random
class Solution1:def __init__(self, nums):self.nums=numsself.arr=nums.copy()def reset(self):self.nums=self.arr.copy()return self.numsdef shuffle(self):le=len(self.nums)-1for i in range(len(self.nums)):#总共抽取的次数index=random.randint(i,le)self.nums[i],self.nums[index]=self.nums[index],self.nums[i]return self.nums

'''这个题目怎么说?刚学数据结构的应该就会写增长一下自信心最小栈:肯定也是一个栈,只不过会有一个返回最小元素的函数
''''''push(x) —— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin() —— 检索栈中的最小元素。如果在别的语言中写,你可能会遇见栈的空间不够用的情况这时候需要重新开空间但是在python中,他写的好,你不够用的时候会自动帮你开
'''
class MinStack:def __init__(self):self.min=float('inf')#设置成正无穷,这样一定会改变self.nums=[]def push(self, val: int) -> None:self.nums.append(val)if self.min>val:self.min=valdef pop(self) -> None:val=self.nums.pop()#删除栈顶元素if val==self.min:#需要再次找到栈中的最小元素#self.min=min(self.nums),栈可能会空,需要判断一下if self.nums==[]:self.min=float('inf')else:self.min = min(self.nums)def top(self) -> int:return self.nums[len(self.nums)-1]def getMin(self) -> int:return self.min'''上面的写法是取巧了,正常的方式应该是牺牲空间来达到记录最小元素的情况,这里不需要进行排序而是利用栈的性质:如果在元素a入栈时,b,c,d已经在栈中,那么可想而知,a不出栈,b,c,d也是不可能出栈的那么使用另外一个栈(辅助栈),每次入栈的都是最小值,每次主栈要出栈时,辅助栈也出
'''
class MinStack1:def __init__(self):self.stack=[float('inf')]self.nums=[]def push(self, val: int) -> None:self.nums.append(val)self.stack.append(min(val,self.stack[-1]))def pop(self) -> None:self.nums.pop()#删除栈顶元素self.stack.pop()def top(self) -> int:return self.nums[-1]def getMin(self) -> int:return self.stack[-1]'''看到一个解放,不使用额外的空间,也没有用顺序查找采用了,栈中记录当前元素与最小值的差,并随时对最小值进行更改
'''class MinStack2:def __init__(self):self.min=float('inf')self.nums=[]def push(self, val: int) -> None:diff=val-self.min#当前入栈元素,与最小值的差self.nums.append(diff)if diff<0:self.min=valdef pop(self) -> None:diff=self.nums.pop()#删除栈顶元素#这里我需要判断一下,最小值是否发生改变if diff<0:top=self.min#说明刚才入栈的时候,他比最小值小,所以变成了最小值,所以需要对最小值进行更改self.min=self.min-diffelse:top=self.min+diffreturn topdef top(self) -> int:if self.nums[-1]<0:return self.minelse:return self.min+self.nums[-1]def getMin(self) -> int:return self.min

'''?????这也太看不起我了,这题目?????卧槽,我看了一下,这个题解下面的文章离谱?这个,写不出来,写出来要十几分钟?妈的没赶上好时代
'''def fun1(n):s_ls=[]for i in range(1,n+1):if i%15==0:s_ls.append('FizzBuzz')elif i%3==0:s_ls.append('Fizz')elif i%5==0:s_ls.append('Buzz')else:s_ls.append(str(i))return s_ls

====================================================================================================================================================================================================================================
204. 计数质数
这里面有两种算法埃式筛和线性筛
都是很不错的寻找质数的算法,并且线性筛还可以用在别处

'''题目要求:统计所有小于非负整数 n 的质数的数量。质数:除了1和他本身外,不能被其他数整除1不是质数
''''''方法一:不管3,7二十一先暴力,看能不能把题解出来
'''
def fun1(n):su = 0  # 进行统计for i in range(2, n):for j in range(2, i):if i % j == 0:breakelse:su += 1return su
#哈哈哈,不出以外,超时了'''现在我们来想一想,如何化简我的循环是从2开始,那么除2以外还有  偶数 可能是质数吗,不可能有吧?,那么可以省一半的循环
'''
def fun2(n):su = 0  # 进行统计if n >= 3:su += 1for i in range(2, n):if i % 2 != 0:for j in range(2, i):if i % j == 0:breakelse:su += 1return su'''超出时间限制'''
'''我们可以看到,如果一个数x是质数,那么他的2x,3x,4x......都不会是质数如果一个数x不是质数,那么它本身,他的2x,3x,4x....都不会是质数基本思路:我需要进行几个记录,不然后面的数还是要走一遍那么就需要开空间
'''def fun3(n):su = 0  # 进行统计ls = [0] * n  # 开空间进行记录for i in range(2, n):if ls[i] == 0:  # i是当前数,i的整数被不可能为质数beishu = 2x = beishu * iwhile x < n:ls[x] = 1beishu += 1x = beishu * ifor j in range(2, i):  # 判断当前数是不是质数if i % j == 0:breakelse:su += 1return su'''超出时间限制
''''''这里是还可以继续化简的:原因在于当前数的n倍可能已经被走过了
'''
def fun4(n):su = 0  # 进行统计ls = [0] * n  # 开空间进行记录for i in range(2, n):if ls[i] == 0:  # i是当前数,i的整数被不可能为质数x = i* iwhile x < n:ls[x] = 1x = x+ifor j in range(2, i):  # 判断当前数是不是质数if i % j == 0:breakelse:su += 1return su'''我看了下答案,发现他直接没有通过循环判断是不是质数而是列表对应数等于0时直接加为什么?
'''
'''吐了,提交通过了,我们来想一下为什么埃氏筛
'''
import time
start=time.time()
def fun5(n):su = 0  # 进行统计ls = [0] * n  # 开空间进行记录for i in range(2, n):if ls[i] == 0:  # i是当前数,i的整数被不可能为质数su+=1       #我觉得这是看规律可以得到的,未排除的数就是可以直接加的#当然,更数学的是这个样子#当前数(i)列表的下标对应元素为0,也就是说,i不是2~~i-1中任意一个的倍数#即i无法整除2~~i-1中的任意一个,所以i是质数#对就是这样x = i* i    #这样可以避免重复记录#为什么?#当前数为2,会把所有2的倍数筛选出来#当前数为3,会把所有3的倍数筛选出来#....#这样基本不会出现重复问题#而如果采用倍数问题2*i,3*i,4*i....#每一次都会经过2的倍数,3的倍数,4的倍数...#这样的话,会有大量重复记录while x < n:ls[x] = 1x = x+ireturn su'''线性筛:优化方向:每个合数只被标记一次因为,前面的基本思路:--标记过程不再仅当x为质数时才进行,而是对每个整数x,都进行--对于整数x,不再标记其所有的倍数 x*x, x*(x+1) .....而是只标记,质数集合中的数,与x相乘的数即:x*质数1,x*质数2,x*质数3......并且在x%质数i==0时停止*****因为这里的x不一定为质数如果是质数,会在超出范围后停止核心点:如果x%质数i==0,那么对于合数y=x*质数i+1他一定会在遍历到(x//质数i)*质数i+1这个数时被标记这里x是可以整除质数i,所以(x//质数i)*质数i+1最后一定会乘以质数i的可以得到y保证每一个合数,只能被其最小质因数得到个人理解:合数会有多个质因子
'''def fun6(n):ls=[0]*nzhishu=[]for i in range(2,n):if ls[i]==0:#这个和前面是一样的,i位置的2--i-1都不能整除他zhishu.append(i)for j in zhishu:#代码在leetcode里面运行不通过,我发现是因为,她会每次执行这个循环#然后会导致,多次循环,但什么都不干if i*j<n:ls[i*j]=1if i%j==0:#结束掉循环,因为y=i*j+1(这个是指位置+1),而这在后面一定会遇到(y),所以不会重复breakreturn len(zhishu)def fun7(n):ls=[0]*nzhishu=[]for i in range(2,n):if ls[i]==0:#这个和前面是一样的,i位置的2--i-1都不能整除他zhishu.append(i)for j in zhishu:if i*j<n:ls[i*j]=1else:breakif i%j==0:#结束掉循环,因为y=i*j+1(这个是指位置+1),而这在后面一定会遇到(y),所以不会重复breakreturn len(zhishu)print(fun6(10))
print(time.time()-start)

'''这种题目,或者说数学问题,基本上都是先暴力,然后再看可不可以优化思路基本不存在数学公式解决问题,哈哈哈如果能解决,一般也不会让你写代码
''''''方法一:直接暴力,先剔除小于等于0的数
'''def fun1(n):if n<=0:return Falsewhile n>=3:if n%3!=0:return Falsen=n//3if n==1:return Trueelse:return False

'''这个题目我做过,s中仅仅包含字符(I,V,X,L,C,D,M)I可以放在V和X,来表示4和9X可以放在L和C,来表示40和90C可以放在D和M,来表示400和900然后这个题目说,s 是一个有效的罗马数字,所以不会出现I在L的左边的情况
'''def fun1(s):#可以用双指针,i和i+1比较,#如果[i]小于[i+1]可以用[i+1]-[i]然后加上去#如果[i]大一些就不需要了dic={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}su=0i=0while i<len(s)-1:z=dic[s[i]]z1=dic[s[i+1]]if z<z1:su=su-zi+=1else:su+=zi+=1su+=dic[s[-1]]return suprint(fun1('IV'))

'''位1的个数:这个题目给我的第一感觉,是依靠补码,反码,等来计算第二感觉是转化成字符串的循环
''''''方法一:直接暴力,转化成字符串循环就好,反正常数级别
'''
def fun1(n):su=0n=str(n)for i in n:su+=eval(i)return su
print(fun1(0b00000000000000000000000000001011))

'''这个题目就是直接快慢指针写就好了
'''class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
def fun1(head):#从head的下一个,第二个节点开始if head==None or head.next==None:return head#直接返回了s=head.nextq=head.nextwhile q.next and q.next.next:s=s.nextq=q.next.nextreturn s

'''这个题目的要求是,你不能只换值,你要换的是链表(如果真的在笔试,就直接换值就好了)但现在,我需要学习所以,就改变列表的结构
''''''这种链表题目,没别的,就是修改指针,就好了对于s处于头部时s.next=q.nextq.next=s对于s不处于头部是s.next=q.nextq.next=spre.next=q#这里pre是s的上一位,如果不走这一步,那么q.next是s,pre.next也是s'''
def fun1(head):#已通过if head==None or head.next==None:return head#这是第一次转换,因为与其他不一样就单独拿出来了s=headq=head.nexts.next=q.nextq.next=shead=qwhile s.next.next and s.next:q = s.next.nexts = s.nexts.next=q.nextq.next=spre.next=qpre=sreturn head

'''分隔链表:--这个题目要求分隔中的每一部分都是连续的片段,不然可以直接一次循环,直接结束--所以可以第一次先遍历一遍链表,并进行计数得到n--n//k得链表被分成了多少份--n%k得余数,这个余数会分配给第一个链表分段到后面得,直到没有
'''def fun1(head,k):ls = []pre = headjishu = 0while pre:jishu += 1pre = pre.nextzhengshu = jishu // kyushu = jishu % kfor i in range(k):  # 分k段cur = headshuzhi = 0if (yushu > 0):while shuzhi < zhengshu:cur = cur.nextshuzhi += 1yushu -= 1ls.append(head)head = cur.nextcur.next = Noneelse:if head == None:ls.append(None)else:while shuzhi < zhengshu - 1:cur = cur.nextshuzhi += 1ls.append(head)head = cur.nextcur.next = Nonereturn ls

'''哈哈哈,啥东西都喜欢搞个回文
''''''这个题目的思路很简单:循环+栈第一遍的时候循环记录第二遍的时候开始比对没办法,只有头节点
'''def fun1(head):stack=[]node=headwhile node:stack.append(node.val)#这里保存值就行了,因为最后比的就是这个node=node.next#这里不想再出栈了,直接双指针(左右指针)left=0right=len(stack)-1while left<right:if stack[left]!=stack[right]:#左右不相等return Falseleft+=1right-=1return True'''哈哈哈,题目问我能不能用o(n)的时间复杂度和o(1)的空间复杂度我写上一个写法的时候突然想到,转换--第一次的循环是不可避免的,这是由于链表的性质导致--那么想一下我第一次的循环干什么?记录呗,一定是需要记录的,没毛病吧?那么用栈可以记录用字符串是不是也可以?那么字符串是不是可以转整数(他只有数字)?--字符串记录,转整数--然后变成了判断该数是不是回文数的问题没毛病吧,常数级别的空间吧?
'''def fun2(head):st=''while head:st+=str(head.str)head=head.next#我可以转换成数字,然后开始判断是不是回文数,但是偷个懒吧shuzhi=eval(st)left=0right=len(st)-1while left<right:if st[left] != st[right]:# 左右不相等return Falseleft += 1right -= 1return True'''果然这种操作还有经典的快慢指针quick=quick.next.nextslow=slow.next一个一次走两个,一个一次走一个,那么可以看到quick到了尾部,slow刚好到达中部这样将slow和quick之间的链表进行链表反转,继续比较,这样什么空间都没有开哈哈哈,流弊(因为上面其实有部分空间开了,只不过数据后面不用了,一切都只是假象哈哈哈)
'''

'''方法一:直接暴力cur为当前数然后不断从右向左遍历,找到[i]==[cur]然后开始同时动,不满足回退直到cur==i时结束,cur+1
'''def fun1(s):#提交通过,离谱len_=len(s)if len_==1:return s#s中至少有两个元素begin=0max_=1for cur in range(len_):#注意是否存在溢出情况for j in range(cur+1,len_):#注意是否存在溢出情况if j-cur+1>max_ and huiwen(cur,j,s):max_=j-cur+1begin=curprint(s[begin:begin+max_:])def huiwen(left,right,s):while left<right:if s[left]!=s[right]:return Falseleft+=1right-=1return Truedef fun2(s):#运行超时,最后一个测试用例没通过len_=len(s)max_=''for cur in range(len_):i=len_-1chongx=curhuitui=iwhile cur<i:if s[cur]!=s[i]:i=huitui-1huitui=icur=chongxelse:i-=1cur+=1if len(max_)<=len(s[chongx:huitui+1:]):max_=s[chongx:huitui+1:]print(max_)def fun3(s):#中心扩散方法,一共有n个中心,每个中心o(n)的时间复杂度len_ = len(s)# 不知道有没有边界条件if len_ == 1:return sbegin = 0max_ = 1for i in range(0, len_ - 1):jhw_begin, jhw_max = jhw(i, s)ohw_begin, ohw_max = ohw(i, i + 1, s)cur_max = max(ohw_max, jhw_max)if jhw_max < ohw_max:if max_ < ohw_max:begin = ohw_beginmax_ = ohw_maxelse:if max_ < jhw_max:begin = jhw_beginmax_ = jhw_maxreturn s[begin:begin + max_:]def jhw(zhongxing,s):len_=len(s)left=zhongxing-1right=zhongxing+1while left>=0 and right<len_:if s[left]!=s[right]:return left+1,right-left-1#因为这里[left]!=[right]所以left和right是不可取的left-=1right+=1return left+1,right-left-1def ohw(left,right,s):len_=len(s)while left>=0 and right<=len_:if s[left]!=s[right]:return left+1,right-left-1left-=1right+=1return left+1,right-left-1