2024.9.2 Python,用栈写每日温度,等差数列划分,子串所有可能性,等差数列划分,深度优先搜索解决累加数

本文主要是介绍2024.9.2 Python,用栈写每日温度,等差数列划分,子串所有可能性,等差数列划分,深度优先搜索解决累加数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.每日温度

给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
***方法一:***暴力法,其中前向暴力法比较好想,但是还是比较麻烦的,可以考虑后向遍历,这样后向的经验就可以为前向服务,大概逻辑是,右边的数字如果比当前数字大,那就是1,如果比你小或者和你相等,那就找他指向的那个数字,不断循环直到找到比他大的那个数

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n=len(temperatures)res=[0]*nfor i in range(n-1,-1,-1):if i==n-1:continuetmp=1while temperatures[i+tmp]<=temperatures[i]:if i+tmp==n-1:          #写这一条的目的是为了让找不到更大的值的有一个归宿res[i]=0breakelse:if res[i+tmp]==0:tmp+=1else:tmp+=res[i+tmp]if temperatures[i+tmp]>temperatures[i]:res[i]=tmpreturn res

这个是我写的代码,我的条件写的有点复杂,但是我也不知道怎么优化,我的逻辑基本上就是按照上面的思路进行编写的,同时对很多异常情况进行了额外的处理,也就是堆屎山,chat根据我的思路进行了一些优化:

from typing import Listclass Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)res = [0] * n        for i in range(n - 2, -1, -1):  # 从倒数第二个元素开始遍历tmp = 1while i + tmp < n and temperatures[i + tmp] <= temperatures[i]:if res[i + tmp] == 0:  # 如果后面没有比当前温度高的tmp = 0breaktmp += res[i + tmp]  # 否则跳到下一个更高温度的位置if tmp > 0:			#可以不加这个判断没有意义res[i] = tmpreturn res

chat的代码的逻辑确实会好一些,他的逻辑是这样的:
1.首先保证i+tmp在n内,如果后面的值小于等于当前值,那么就进入循环找下一个更大的值
2.特例,如果在下一个的最大的值已经是0的情况下,说明这种情况下tmp等于0
3.如果右边有更大的那就res[i+tmp]更新为现在的tmp
4.跑完循环以后出来,把tmp附给res就好了。这里的判断完全不需要的
方法二:用栈来写

from typing import Listclass Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)res = [0] * nstack = []for i in range(n - 1, -1, -1):while stack and temperatures[stack[-1]] <= temperatures[i]: #判断当前值和盘子里的最小值stack.pop() 				#如果大就扔盘子找下一个,直到找到他合适的位置if stack:													res[i] = stack[-1] - i									#盘子里还有就作差值算数字stack.append(i)									#当前值一定入盘子,因为一定能给他在栈里找到一个合适的位置存放return res

代码逻辑:
1.当i为n-1的时候,栈写进n-1
2.到n-2的时候,最后一个温度和当前温度比较,之后的温度小就进循环pop掉最后一个温度,然后res[i]=0,如果最后一个温度比他大,那么就不pop了,res[i]=1
3.之后的逻辑就是,进来一个数就先和栈里最小的先比较,如果比不上,那就结算,如果比最小的大,那就找栈里下一个,他的目标是把这个栈严格写成一个从大到小的顺序,如果当前数更大的,就把比这个数小的所有的盘子全部pop出去,下一次判断就以当前数为模板
具体的逻辑看我的注释,我是看明白了,但是这个代码也是那种,自己写很难写出来的逻辑,只能说看看热闹。如果有任何人有问题可以评论区留言,我将详细解答。

2.等差数列划分

如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。
例如,[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1:
输入:nums = [1,2,3,4]
输出:3
解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2:
输入:nums = [1]
输出:0
***方法一:***暴力法

class Solution:def numberOfArithmeticSlices(self, nums: List[int]) -> int:res=[]for left in range(0,len(nums)-2):right=left+2while right<len(nums):if self.check(nums[left:right+1]):res.append(nums[left:right+1])#注意这里的加一,加一是为了取到rightelse:breakreturn res def check(self,nums)->bool:if all(nums[i+1]-nums[i]==nums[i+2]-nums[i+1] for i in range(0,len(nums)-2)):return Trueelse:return False

方法二差分 + 计数

from typing import Listclass Solution:def numberOfArithmeticSlices(self, nums: List[int]) -> int:n = len(nums)if n == 1:return 0d, t = nums[0] - nums[1], 0  # 初始化公差d,以及等差数列的计数器tans = 0  # 最终结果,存储等差数列的数量# 从第3个元素开始遍历,因为等差数列至少有三个元素for i in range(2, n):if nums[i - 1] - nums[i] == d:  # 当前差值和之前差值d相等t += 1  # 当前元素与前两个元素构成新的等差数列,t增加else:d = nums[i - 1] - nums[i]  # 差值不相等,更新差值dt = 0  # t归零,因为无法继续形成等差数列ans += t  # 每次都将t的值加到最终结果中return ans

这个代码最巧的地方在于t+=1这里,我看这个代码的时候我心想这玩意加一有什么意义呢,每次发现一个新的元素,他要多好多子串呢,这咋能数的过来,但是其实很简单,比如三个元素的等差变四个元素的等差的时候就多了两种可能,四个元素变五个元素的时候就多了三种可能,是有规律的,所以这样遍历下来是合适的,只能说又是一个自己想是想不出来的题。还是暴力法来的直接。

3.累加数

累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 ‘0’-‘9’ 的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true ;否则,返回 false 。
说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1:
输入:“112358”
输出:true
解释:累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:
输入:“199100199”
输出:true
解释:累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
这个题我建议与上次那个ip地址配合食用,非常的好,详细请看我在9.1日写的文章

from typing import Listclass Solution:def isAdditiveNumber(self, num: str) -> bool:# 将seg_count用来表示段数seg_count = len(num)  # 使用整个字符串长度来作为循环的控制def dfs(segId: int, segStart: int, segments: List[int]):# 如果找到了所有段并且遍历完了字符串if segId >= 3 and segStart == len(num):if self.check(segments[:segId]):return Truereturn False# 如果已经遍历完了字符串但是还没有足够的段if segStart == len(num):return False# 由于不能有前导零,如果当前数字为 0if num[segStart] == "0":segments[segId] = 0return dfs(segId + 1, segStart + 1, segments)addr = 0for segEnd in range(segStart, len(num)):addr = addr * 10 + int(num[segEnd])segments[segId] = addrif dfs(segId + 1, segEnd + 1, segments):return Truereturn Falsesegments = [0] * seg_countreturn dfs(0, 0, segments)def check(self, nums: List[int]) -> bool:# 检查每两个数相加是否等于第三个数return all(nums[i] + nums[i + 1] == nums[i + 2] for i in range(len(nums) - 2))

这个代码是我根据昨天的代码修改而来的代码,这个代码的思路主要是dfs去遍历每种段,只要有一个是True,那就是True。看了下官方答案,这个题也是暴力法,我的方法未必不是好的,因为长度最多也就35个,所以这个题就是得用暴力法。

这篇关于2024.9.2 Python,用栈写每日温度,等差数列划分,子串所有可能性,等差数列划分,深度优先搜索解决累加数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1132251

相关文章

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在