5.6k 字 5 分钟

# 找树左下角的值 题目链接🔗 # 迭代 层序遍历找最后一行第一个值。 class Solution {public: int findBottomLeftValue(TreeNode* root) { queue<TreeNode*> que; if (root != nullptr) que.push(root); int result = 0; while (!que.empty()) { int size = que.size(); for (int i = 0; i < size; i++)...
4.6k 字 4 分钟

# 完全二叉树的节点个数 题目链接🔗 # 普通二叉树思路 # 递归 class Solution {public: int countNodes(TreeNode* root) { if (root == nullptr) return 0; return 1 + countNodes(root->left) + countNodes(root->right); }};# 迭代 class Solution {public: int countNodes(TreeNode* root)...
6k 字 5 分钟

# 翻转二叉树 题目链接🔗 想要翻转二叉树，只需要交换每个节点的左右子节点即可。 这道题目使用层序遍历、前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！ # 递归法 以前序遍历递归： class Solution {public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return root; swap(root->left, root->right); // 中 invertTree(root->left);...
6.1k 字 6 分钟

# 二叉树理论基础 # 二叉树种类 # 满二叉树 满二叉树：只有读为 0 的节点和度为 2 的节点，并且度为 0 的节点都在同一层上。 这棵二叉树为满二叉树，也可以说深度为kkk，有2k−12^k-12k−1 个节点的二叉树。 # 完全二叉树 完全二叉树：除了最底层可能没填满外，其余每层节点数都达到最大值，并且最下一层节点都集中在该层最左边的若干位置。若最底层为第 h 层 (h 从 1 开始)，则该层包含1−2h−11 - 2^{h - 1}1−2h−1 个节点。 #...
4.2k 字 4 分钟

# 删除字符串中所有相邻重复项 题目链接🔗 用栈来存放遍历过的元素，当遍历当前这个元素的时候，去看栈顶是不是与当前这个元素相同。 如果相同就弹出栈顶元素并遍历字符串的下一个元素，如果不同就将元素压入栈中。 注意栈里的元素在弹出时是倒序的。 class Solution {public: string removeDuplicates(string s) { stack<char> result; for(int i = 0; i < s.size(); i++) { if(!result.empty()...
3.3k 字 3 分钟

# 栈与队列理论基础 队列是先进先出，栈是先进后出。 栈提供 push 和 pop 等接口，所有元素必须符合先进后出的规则，所以栈不提供走访功能和迭代器。 栈以底层容器来完成所有工作，对外统一接口，底层容器是可插拔的。 因此在 STL 中栈汪汪不被归为容器 (container)，而被归为容器适配器 (container adapter)。 栈的底层实现可以是 vector ， deque ， list 等数组和链表的底层实现。 常用的 SGI STL 如果没有指定底层实现，默认是以 deque 为底层数据结构。 deque...
3.1k 字 3 分钟

# 题目列表 移除元素 反转字符串 替换数字 翻转字符串里的单词 翻转链表 删除链表的倒数第N个节点 链表相交 环形链表II # 三数之和 题目链接🔗 用这个 nums 数组举例。首先数组排序，然后有一层 for 循环， i 从下标 0 的地方开始，同时定一个下标 left 定义在 i+1 的位置上，定义下标 right 在数组结尾的位置上。 依然还是在数组中找到 abc 使得a+b+c=0a + b +c =0a+b+c=0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right] 。 接下来移动 left 和 right...
4.6k 字 4 分钟

# 右旋字符串 题目链接🔗 不申请额外空间，只在本串操作。 右旋：将字符串后面 n 个字符右移到前面。这样字符串分成了两个部分。 右移 n 位，就是将第二段放在前面，第一段放在后面，先不考虑里面字符的顺序，整体倒叙就行了。 此时第一段和第二段顺序符合结果，但里面字符顺序被倒序，更正回来。 // 版本一#include<iostream>#include<algorithm>using namespace std;int main() { int n; string s; cin >> n; cin >>...
2k 字 2 分钟

# 反转字符串 题目链接🔗 要求原地修改，可以定义两个指针，一个在字符串前面，一个在字符串后面，同时向中间移动并交换两元素。 class Solution {public: void reverseString(vector<char>& s) { int i = 0, j = s.size() - 1; while(i < j) { swap(s[i++], s[j--]); } }};或者使用 reverse 库函数。 #...
1.9k 字 2 分钟

# 四数相加 II 题目链接🔗 本题是四个独立的数组，不用考虑四个重复的元素相加等于 0 的情况。 本题解题步骤： 定义一个 unordered_map ， key : value 为 a+b : a+b出现的次数 : 遍历 A 和 B，统计 a+b 及其出现的次数，放入 map 中； 遍历 C 和 D，查询 map 中是否有 0-(a+b) ，如果有则算入次数 class Solution {public: int fourSumCount(vector<int>& nums1,...