dedecms 做微网站,自己做门户网站,网站建设是前端的吗,做网站到哪里做45. 跳跃游戏
题目链接#xff1a; 45. 跳跃游戏 II - 力扣#xff08;LeetCode#xff09;
思路#xff1a;这道题思路不难记#xff0c;遍历数组每个位置#xff0c;更新下一次的范围#xff0c;当当前位置已经在当前范围之外时#xff0c;步数一定得加一#xff…45. 跳跃游戏
题目链接 45. 跳跃游戏 II - 力扣LeetCode
思路这道题思路不难记遍历数组每个位置更新下一次的范围当当前位置已经在当前范围之外时步数一定得加一当前范围更新成下一个范围。
难点在于边界条件。
当数组只有一个元素时步数默认为0而不是1因为已经站到了终点无需走动。step初始值为0所以currentRange正好等于当前位置时步数就要加1更新当前位置。当更新过后的当前位置已经覆盖到终点后就不用继续循环直接返回步数。
class Solution(object):def jump(self, nums):if len(nums) 1:return 0step 0currentRange, nextRange 0, 0for i in range(len(nums)):nextRange max(nextRange, inums[i])if currentRange i:step 1currentRange nextRangeif currentRange len(nums) - 1:breakreturn step
1190. 反转每对括号间的子串
题目链接1190. 反转每对括号间的子串 - 力扣LeetCode
思路字符串的反转要先想到栈的应用。栈“先进后出”的特点可以实现反转的效果。以括号为分割点逐一反转。
class Solution(object):def reverseParentheses(self, s):stack []for c in s:if c ! ):stack.append(c)else:cur []while stack and stack[-1] ! (:cur.append(stack.pop())if stack and stack[-1] (:stack.pop()stack curreturn .join(stack)781. 森林中的兔子
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路
不同回答的兔子颜色肯定不同求至少有多少只兔子所以尽量让回答相同数量的兔子颜色相同也就是让每个兔子和自己相同颜色的兔子都在回答的这些兔子里。如果回答同一个数量的兔子的数量超过这个数量1说明不全部为同一个颜色需要把这些兔子尽量分为最小的组。
e,g, 有5只兔子都说有2个兔子与自己颜色相同。“有两只兔子与自己颜色相同”说明和它同一个颜色的兔子数量只有3只五只兔子至少得分为两组颜色每组颜色至少有21 3只兔子所以至少有2*3 6只兔子
class Solution(object):def numRabbits(self, answers):num dict()ans 0for answer in answers:if answer not in num:num[answer] 1else:num[answer] num.get(answer) 1for value, num in num.items():if value 1 num:ans value 1else:if num%(value 1) 0:ans numelse:ans (int(num/(value 1))1)*(value 1)k ceil(float(num)/(value1))ans k*(value 1)return int(ans)
739. 每日温度
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路先对暴力算法做了优化从后往前遍历如果当前温度比它后一天的小天数则为1如果大那么就从比它后一天大的天数开始查找。但仍然超时
class Solution(object):def dailyTemperatures(self, temperatures):ans [0] * len(temperatures) for i in range(len(temperatures)-2, -1, -1):if temperatures[i] max(temperatures):passif temperatures[i] temperatures[i1]:ans[i] 1else:for j in range(i1ans[i1], len(temperatures)): if temperatures[j] temperatures[i]:ans[i] j-ibreakreturn ans然后根据力扣的题解发现可以用单调栈更高效地解决。
把没有找到比自己更高温度的天气下标记录在栈里循环每一个元素的下标和值如果当前温度高于前几天的温度那么就在对应温度的下标上记录天数把那些天从栈中弹出再把当前温度的下标记在栈里来被之后几天的温度查找。
class Solution:def dailyTemperatures(self, temperatures):stack, ans [], [0] * len(temperatures)for i, num in enumerate(temperatures): # 根据stack中的下标找到对应的温度while stack and temperatures[stack[-1]] num: index stack.pop() # 把栈里面找到更高温度的元素下标pop掉ans[index] i - indexstack.append(i) # 用栈保存元素下标下标return ans
