leetcode刷题(二)
1、栈
逆波兰表达式求值
根据逆波兰表示法,求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2:
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6
示例 3:
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
class Solution(object):
def evalRPN(self, tokens):
"""
用到栈(先进后出的数据结构)
遍历表达式:
碰到数字则入栈
碰到运算符则连续从栈中取出2个元素, 使用该运算符运算然后将结果入栈
最后栈中剩余一个数字, 就是结果.
"""
result = []
for i in tokens:
if i not in ('+', '-', '*', '/'):
result.append(int(i))
else:
num1 = result.pop()
num2 = result.pop()
if i == '+':
result.append(num2 + num1)
elif i == '-':
result.append(num2 - num1)
elif i == '*':
result.append(num2 * num1)
else:
result.append(int(num2 * 1.0 / num1))
return result[0]
2、队列
最近的请求次数
写一个 RecentCounter 类来计算最近的请求。
它只有一个方法:ping(int t),其中 t 代表以毫秒为单位的某个时间。
返回从 3000 毫秒前到现在的 ping 数。
任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内,包括当前(指 t 时刻)的 ping。
保证每次对 ping 的调用都使用比之前更大的 t 值。
示例:
输入:inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
输出:[null,1,2,3,3]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-recent-calls
class RecentCounter(object): def __init__(self):
self.nums = []
self.size = 0 def ping(self, t):
"""
:type t: int
:rtype: int
"""
self.nums.append(t)
self.size += 1
while self.size and self.nums[0] < t - 3000 :
del self.nums[0]
self.size -= 1
return self.size
3、动态规划
砖墙
你的面前有一堵方形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少,并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。
示例:
输入: [[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
输出: 2
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/brick-wall
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return -1
m, n = len(grid), len(grid[0])
f = [[0]*n for _ in range(m)]
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if i != m-1 and j != n-1:
f[i][j] = min(f[i][j + 1], f[i + 1][j]) + grid[i][j]
elif i == m-1 and j != n-1:
f[i][j] = f[i][j + 1] + grid[i][j]
elif i != m - 1 and j == n - 1:
f[i][j] = f[i + 1][j] + grid[i][j]
else:
f[i][j] = grid[i][j]
return f[0][0]
4、贪心算法
跳跃游戏
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game
方法一:DFS
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
def dfs(index, nums, sets, n):
if index in sets:
return False
if index >= n - 1:
return True
for j in range(min(nums[index], n - index - 1), 0, -1):
if dfs(index + j, nums, sets, n):
return True sets.add(index)
return False return dfs(0, nums, set(), len(nums))
方法二:贪心
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums:
return False last = 0
n = len(nums)
for i, step in enumerate(nums):
if i <= last <= i + step:
last = i + step
if last >= n - 1:
return True
return False
最新文章
- iOS/OS X线程安全的基础知识
- ubuntu14.04 boost动态库找不到 libboost_system.so.1.58.0
- ASP连接数据库登录按钮
- Windows调试学习笔记:(二)WinDBG调试.NET程序示例
- HtmlAgilityPack教程
- 【POJ】【2891】Strange Way to Express Integers
- 使用JSP处理用户注册和登陆
- Spring + JdbcTemplate + JdbcDaoSupport examples
- 【ZZ】大数据架构师基础:hadoop家族,Cloudera系列产品介绍
- 第一次知道Winform的窗体之间传值怎么写,分享给小白~
- matlab——sparse函数和full函数(稀疏矩阵和非稀疏矩阵转换)
- [jobdu]调整数组顺序使奇数位于偶数前面
- Hadoop学习之HBase
- Java调用IDL出错处理
- gevent-websocket初识
- linux局域网内挂载其它操作系统目录
- DJango 基础 (1)
- Node.js初探
- 遍历FTP目录及下载
- JS学习笔记(6)--音乐播放器
热门文章
- 用友开发者中心全新升级,YonBuilder移动开发入门指南
- ZROI3
- win32com操作word API精讲 第六集 Range(四)对齐和缩进
- GIT安装步骤记录以及Git 常用命令,忽略文件,推送本地代码到仓库示例以及报错解决
- .Net6 使用 Ocelot + Consul 看这篇就够了
- 字节输出流的续写和换行-字节输入流_inputS Stream类
- MRS_MounRiver安装与驱动相关问题汇总
- 亲测有效! TG Pro 实时温度工具 V2.7.6 for mac 破解版
- 【TS】泛型以及多个泛型参数
- 生物制剂时代的SpA研究正站在十字路口_Appel,Sieper2009