leetcode hot100 简单难度 day01-刷题
day01 leetcode hot100题单
1. 前言
对应资料
leetcode网站：https://leetcode.cn/
hot100题单：https://leetcode.cn/problem-list/2cktkvj/
说明
本人没有系统的刷过题目，临时抱佛脚，先从hot100开始刷，这是第一次刷。写博客，是强迫自己刷题。
- 从简单难度来时往后刷。
- 这是第一遍刷题，主要目的是通过，而不是追求效率。
- 语言采用的python
目录
文章目录
2. 简单 - 两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
思考
我知道用双重循环可以瞬间解决，但是我想用一个循环来解决这个问题。
我想到这种求和的问题，可以变为迭代右维护左这样的思路，我构建一个哈希表，存储左边的值，然后去迭代右边，如果遇到target-right的值存在于哈希表中，就直接返回结果。
- 采用哈希表是因为其查询时间复杂度O（1），非常快
- 其次，哈希表的key可以是当前元素值，value就是对应的索引，方便返回结果
代码实现
- 双重循环：正常通过
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
for i in range(length-1):
for j in range(i+1,length):
if nums[i] + nums[j] == target:
return [i,j]
- 迭代右，维护左：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hs = defaultdict(int)
for i,v in enumerate(nums):
# 判断元素是否存在
if target-v in hs:
return [i,hs[target-v]]
# 如果不存在，就存储当前元素
hs[v] = i
3. 简单 - 有效的括号
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思考
括号的匹配，有一个特点，就是最后出现的左括号，必须配对最先出来的右括号。这让我想到，后进先出，也就是栈这个数据结构。
这里用列表代替栈，可以这么做：
- 先入栈：不停压入元素，直至遇到了右边括号的元素
- 遇到右边的括号，就出栈，如果匹配，就继续，否则就不是有效字符串
- 当访问的元素为空了，说明就是有效字符串
实现
实现过程中的注意点：
- 发现特殊情况，就是只有一个括号的时候，上面的思路没有处理好，直接加上一个判断
- 字符串一来就是右括号，导致栈为空，一pop就报错，也加上一个判断
- 最后返回True的时候，必须判断栈是否为空，为空，才说明正常匹配完成
class Solution:
def isValid(self, s: str) -> bool:
# 特殊情况
if len(s) < 2:
return False
pair = {'[':']','{':'}','(':')'}
stack = []
for v in s:
# 如果元素是左括号，入栈
if v in pair:
stack.append(v)
# 如果是右括号，则出栈并匹配
else:
# 防止遇到一来就是右括号的情况，使得pop报错
if len(stack) == 0:
return False
p = stack.pop()
if pair[p] != v:
return False
return True if len(stack) == 0 else False
4. 简单 - 合并两个有序链表
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思考
我想用正常的合并思维去解决，比如：我现在有头节点h1、h2：
- 比较头结点h1、h2大小，如果h1>=h2，那么新链表的头节点就是h2，反之就是h1。然后传入下一个要合并的两个结点，以新头节点为h1为例，那么传入的就是h1.next和h2
- 重复上面的判断操作：如果一个链表为空，则直接传入剩下的所有链表；如果两个都为空了，直接结束
这么想来，就是一个递归问题：
- 边界条件：如果一个链表为空，则直接传入剩下的所有链表；如果两个都为空了，直接结束
- 递归：不停合并的过程
实现
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 边界条件
if list1 is None: return list2
if list2 is None: return list1
# 递归
if list1.val >= list2.val:
return ListNode(list2.val,self.mergeTwoLists(list1,list2.next))
else:
return ListNode(list1.val,self.mergeTwoLists(list1.next,list2))
没想到一次性成功了，看来梳理出算法流程，的确可以减少debug的时间。
5. 简单 - 爬楼梯
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思考
我想，如果第一次爬1，后面还有n-1阶台阶，这样没有办法去计数。应该用一个确定的数去计数。
- 于是，反过来。如果此时已经爬了n-1个台阶，那么只剩下1种方式。
- 如果此时还剩下n-2个台阶，有两种方式（1+1 、 2）
- 如果此时还剩下n-3个台阶，有三种方式（1+1+1、1+2、2+1），也就是f(n-2) + f(n-1)
此时就提取出计算公式了：f(n-3) = f(n-2)+f(n-1)，对于后续的，比如n-4，就是f(n-4)=f(n-3)+f(n-2)
实现
- 这个解法正确，但是遇到n=44的时候，超出时间限制了，说明需要优化一下
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n-2)+self.climbStairs(n-1)
- 我想了下，n=3的话，就是前两个相加，其实就是斐波拉契数列，可以转为迭代解法，就是标准的1 1 2 3 这样的写法：
class Solution:
def climbStairs(self, n: int) -> int:
# 初始的两个
a,b = 1,1
for i in range(2,n+1):
temp = a + b
a = b
b = temp
return b
6. 简单 - 二叉树的中序遍历
题目
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
思考
查阅网上资料知道，二叉树的遍历都是以当前结点为顺序来命名的，即中序遍历就是：左子树、当前结点-右子树这样的顺序。
树的遍历基本上都是递归的问题，所以来确定边界条件和递归问题：
- 边界条件：如果访问到None，说明访问完毕，返回None即可
- 递归：对于一棵树，先访问左子树，再访问当前结点，接着访问右子树即可；进入递归的思路：比如递归去访问左子树A，也是A的左子树、A、A的右子树
实现
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 一个列表保存结果
ans = []
# 一个递归函数
def dfs(node):
# 边界条件
if node is None:
return None
# 左、当前、右
dfs(node.left)
ans.append(node.val)
dfs(node.right)
dfs(root)
return ans
7. 简单 - 对称二叉树
题目
给你一个二叉树的根节点 root ， 检查它是否轴对称。
思考
我想了挺久，觉得可以把这颗树当成两棵树来做，这样就由一个树的复杂判断，变成两个树的对应判断。
那么，假设我需要实现一个判断两个树是否相同的方法：
- 判断传入的当前结点是否相等，相等就继续，如果不相等就是边界条件，结束
- 然后递归传入两者的左子树和右子树
如果实现了这个方法，就传入根节点的左右子树即可
实现
- 实现过程：发现少了一些边界条件，就是为空的情况没有判断
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
# 判断两棵树是否相同
def judge(left,right):
# 如果为空
if left is None and right is None:
return True
if (left is None and right) or (right is None and left):
return False
# 判断是否相等
if left.val != right.val:
return False
# 递归
return judge(left.left,right.right) and judge(left.right,right.left)
return judge(root.left,root.right)
8. 简单 - 二叉树的最大深度
题目
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思考
这道题，就是去遍历整颗树，只是需要记录长度，然后遇到叶子结点的时候需要判断一下大小，返回最大的即可，感觉挺简单的。
实现
- 实现的过程才发现自己最开始想歪了，总想要用一个变量去记录所有的长度，但是利用递归的特性，给函数一个深度变量，这样每个结点都有对应的深度
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
ans = 0
# 定义遍历函数
def dfs(node,depth):
nonlocal ans
if node is None:
return None
depth += 1
ans = max(ans,depth)
dfs(node.left,depth)
dfs(node.right,depth)
dfs(root,0)
return ans
9. 简单 - 买股票的最佳时机
题目
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
思考
去迭代右边，维护左的思路去做。
- 初始化最小值为第一个元素值
- 然后去迭代右边，当前利润，等于此时迭代的对象减去最小值即可
- 记得更新最小值
实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
mn = prices[0]
for v in prices:
ans = max(ans,v-mn)
mn = min(mn,v)
return ans
10. 简单 - 只出现一次的数字
题目
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
思考
先不考虑后面的要求，先完成这个道题再说。
构建一个哈希表和列表，去迭代整个数组，如果元素不存在于哈希表，添加，如果已经存在于这个哈希表，则删除这个key，然后把这个值存放到列表中，表示是重复的元素。这样最后剩下的字典就是不重复的元素：
实现
- 这个方法非常慢，基本上是最慢的方法了
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hs = defaultdict(int)
l = []
for v in nums:
if v in hs:
del hs[v]
l.append(v)
if v not in l:
hs[v] += 1
return list(hs.keys())[0]
- 顺带看了下灵神的题解，发现直接用的异或，唉，我咋没想到
11. 今日总结
- 一些必备的方法：
# 创建一个默认字典，值为int类型
hs = defaultdict(int)
- 一些必备的解题思维：
- 递归的写法和思考思路
- 去重复问题，可以考虑哈希表
- 两个数求和或者求差之类的问题，可以考虑迭代一边，然后用一个列表、哈希表等维护左边的值
更多推荐
15
0- 0
已为社区贡献6条内容
所有评论(0)