LeetCodeCampsDay15二叉树part03
LeetCodeCampsDay15二叉树part03
涉及树的高度/深度求解,以及平衡二叉树的判断,完全二叉树求节点个数;
根节点到任意节点的路径/深度求解
平衡二叉树
https://leetcode.cn/problems/balanced-binary-tree/
给定一个二叉树,判断它是否是 平衡二叉树
示例 1:
12输入:root = [3,9,20,null,null,15,7]输出:true
示例 2:
12输入:root = [1,2,2,3,3,null,null,4,4]输出:false
示例 3:
12输入:root = []输出:true
提示:
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
后序递归思路
这里强调一波概念:
二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。
但leetcode中强调的深度和高度很明显是按照节点来计算的,如图:
如何判断一个树是不是平衡二叉树?—判断它的左树和右树的高度是否差大 ...
gitSwitchAccount
起因是本地git存在多个账号,提交时显示登录的是lthero-g,我需要切换回lthero-big
123lthero@LtherodeMac-mini HiFi-Mark % git pushremote: Permission to lthero-big/HiFi-Mark.git denied to Lthero-g.fatal: unable to access 'https://github.com/lthero-big/HiFi-Mark/': The requested URL returned error: 403
These should reflect the lthero-big account. If not, update them:
123git config user.name "lthero-big"git config user.email "email-associated-with-lthero-big"
Update Remote URL to Include lthero-big Cr ...
LeetCodeCampsDay14-二叉树part02
LeetCodeCampsDay14-二叉树part02
继续使用深度/广度遍历解决问题,包含迭代&递归的方法
翻转二叉树
https://leetcode.cn/problems/invert-binary-tree/
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 1:
12输入:root = [4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]
示例 2:
12输入:root = [2,1,3]输出:[2,3,1]
示例 3:
12输入:root = []输出:[]
提示:
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
递归思路
可以发现想要翻转它,其实就把每一个节点的左右孩子交换一下就可以了。
可以按“前序/中序/后序”的方法,将中间节点进行“调换”,然后用递归的方式去处理左、右子树
递归三步走:返回值与输入值;终止条件(传入node为空);单层递归的逻辑(调换node的左右子树,再执行递归处理左、右子树)
递归代码
前序递归
时间复杂度O(N)
空间复 ...
LeetCodeCampsDay13-二叉树part01
LeetCodeCampsDay13-二叉树part01
二叉树的遍历,前序/中序/后序/层序,以及迭代、递归等方法实现
二叉树的递归遍历
二叉树的递归遍历,或者说“所有的递归”都离不开三个因素
确定递归函数的input与output(参数与返回值)
终止条件
单层递归的逻辑
以中序遍历为例
确定递归函数的参数与返回值:
需要有“当前节点”,其次,需要将中序遍历的结果放在res数组中;可以不返回
def traversal(cur: TreeNode, res: List): ..... return
终止条件
当“当前节点”为空时,则终止
if not cur: return
单层递归的逻辑
先将"cur.val"添加到res中,再递归遍历"cur.left",最终递归遍历"cur.right"
res.append(cur.val) // 中
traversal(cur.left, res); // 左
traversal(cur.right, res); // 右
二叉 ...
LeetCodeCampsDay11-栈与队列part02
LeetCodeCampsDay11-栈与队列part02
使用栈与队列解决问题,栈适合深度搜索/深度遍历的问题;而队列适用于广度搜索/遍历
这里有个滑动窗口最大值的问题值得关注下
150. 逆波兰表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意:
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数(运算对象)都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
示例 1:
123输入:tokens = ["2","1","+","3","*"]输出:9解释:该算式转化为常见的中缀算术表达式为:((2 + ...
LeetCodeCampsDay10栈与队列part01
LeetCodeCampsDay10栈与队列part01
使用队列实现栈;
使用栈实现队列;
以及两个关于栈的题目
232. 用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明:
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
示例 1:
12345678910111213输入:[&quo ...
LeetCodeCampsDay9字符串part02
LeetCodeCampsDay9字符串part02
字符串反转/kmp算法/重复字符串的查找
151. 反转字符串中的单词
https://leetcode.cn/problems/reverse-words-in-a-string/
给你一个字符串 s ,请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
**注意:**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。
示例 1:
12输入:s = "the sky is blue"输出:"blue is sky the"
示例 2:
123输入:s = " hello world "输出:"world hello"解释:反转后的字符串中不能存在前导空格和尾随空格。
示例 3:
123输入:s = "a good ...
LeetCodeCampsDay8字符串01
LeetCodeCampsDay8字符串part01
双指针/字符串反转/python列表与字符串互换/python列表语法糖
344. 反转字符串
https://leetcode.cn/problems/reverse-string/
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
示例 1:
12输入:s = ["h","e","l","l","o"]输出:["o","l","l","e","h"]
示例 2:
12输入:s = ["H","a","n","n","a","h"]输出:["h",&qu ...
LeetCodeCampsDay7哈希表part02
LeetCodeCampsDay7哈希表part02
双指针/生产者消费者/HashTable
383. 赎金信
https://leetcode.cn/problems/ransom-note/
给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以,返回 true ;否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1:
12输入:ransomNote = "a", magazine = "b"输出:false
示例 2:
12输入:ransomNote = "aa", magazine = "ab"输出:false
示例 3:
12输入:ransomNote = "aa", magazine = "aab"输出:true
提示:
1 <= ransomNote.length, magazine.length ...
LeetCodeCampsDay6哈希表part01
LeetCodeCampsDay6哈希表part01
以及几题目主要利用hash table的“唯一性”思想解决题目
关键词:哈希表;快慢指针;双指针;用set/dict/当成hash表;
242. 有效的字母异位词
https://leetcode.cn/problems/valid-anagram/
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的 字母异位词。
示例 1:
12输入: s = "anagram", t = "nagaram"输出: true
示例 2:
12输入: s = "rat", t = "car"输出: false
提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
思路
使用hash table可解决
开辟一块26个int型的数组即可,比如对于字符串s,"a"出现一次 ...