LeetCode刷题| Leetcode 45. 跳跃游戏，1190. 反转每对括号间的子串，781. 森林中的兔子，739. 每日温度

45. 跳跃游戏

题目链接： 45. 跳跃游戏 II - 力扣（LeetCode）

思路：这道题思路不难记，遍历数组每个位置，更新下一次的范围，当当前位置已经在当前范围之外时，步数一定得加一，当前范围更新成下一个范围。

难点在于边界条件。

1. 当数组只有一个元素时，步数默认为0，而不是1，因为已经站到了终点，无需走动。
2. step初始值为0，所以currentRange正好等于当前位置时，步数就要加1，更新当前位置。
3. 当更新过后的当前位置已经覆盖到终点后，就不用继续循环，直接返回步数。

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, i+nums[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. 不同回答的兔子颜色肯定不同
2. 求至少有多少只兔子，所以尽量让回答相同数量的兔子颜色相同，也就是让每个兔子和自己相同颜色的兔子都在回答的这些兔子里。
3. 如果回答同一个数量的兔子的数量超过这个数量+1，说明不全部为同一个颜色
4. 需要把这些兔子尽量分为最小的组。

e,g, 有5只兔子都说有2个兔子与自己颜色相同。“有两只兔子与自己颜色相同”说明和它同一个颜色的兔子数量只有3只，五只兔子至少得分为两组颜色，每组颜色至少有（2+1） = 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)/(value+1))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[i+1]:ans[i] = 1else:for j in range(i+1+ans[i+1], 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