Photinia

1、654最大二叉树 我的思路：和从前序、中序、后序重构二叉树的框架一样。应该重构二叉树都是一个框架。 代码随想录 123456789101112131415161718192021222324252627class Solution {public: TreeNode* traverse(vector<int>& nums, int start, int end){ if(start > end){ return nullptr; } //find max int maxval = nums[start]; int idx = start; for(int i = start+1;i<=end;i++){ if(nums[i] > maxval){ maxval = nums[i]; idx = ...

1、110平衡二叉树 给定一个二叉树，判断它是否是平衡二叉树。 平衡二叉树：指该树所有节点的左右子树的高度相差不超过1。 我的思路：这道题和最大深度不同，最大深度只需要递归返回最大深度，但是这里有两个信息需要返回，一个是返回节点高度来供父节点处理，二是当前节点不满足平衡就返回false。我把高度作为参数，返回值为是否平衡。 代码随想录：看了代码随想录，由于高度始终为正，所以可以把-1作为否平衡，>0作为平衡。这样就只需要一个返回值，也就是当前节点的高度。 12345678910111213141516171819202122232425262728293031323334353637383940// 我的思路class Solution {public: bool traverse(TreeNode* root,int &hig){ if(root == nullptr){ hig = 0; return true; } int higl = ...

理论基础 二叉树的种类： 满二叉树：二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。（例如大顶堆和小顶堆就是这种数据结构） 二叉搜索树：二叉搜索树是一个有序树，左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。 平衡二叉树：左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn。 遍历框架 递归遍历（DFS） 12345678910void traverse(TreeNode* root) { if (root == nullptr) { return; } // 前序位置 traverse(root->left); // 中序位置 traverse(roo ...

栈与队列理论基础 栈和队列是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（底层容器可替换）。 所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。 我们常用的SGI STL（gcc所使用的stl库）默认是以deque为缺省情况下栈的底层结构。 123std::stack<int> third; // 默认dequestd::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列 1、232用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 b ...

1、344反转字符串 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 左右双指针 我的思路： 这道题很常规的问题，直接左右双指针。 12345678910111213class Solution {public: void reverseString(vector<char>& s) { int left = 0,right = s.size()-1; while(left<right){ auto temp = s[right]; s[right] = s[left]; s[left] = temp; left++; right--; } }}; 2、541反转字符串II 给定一个字符串 s 和一个整 ...

哈希表理论基础 什么时候用哈希法？ 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。 Hash表 数组就是一张哈希表。我们通过Hash函数把键映射成一个整数值，然后通过取模操作映射到哈希表的索引上。 但是可能出现多个键都映射到同一个索引上，这个现象叫哈希碰撞。解决这个问题有两个方案，一个是拉链法，一个是线性探测法。 常见的三种Hash结构 数组 set（集合） map（映射） 数组就没啥可说的了。在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示： 集合 实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率 std::set 红黑树 有序 否 否 O(log n) O(log n) std::multiset 红黑树 有序 是 否 O(log n) O(log n) std::unordered_set 哈希表 无序 否 否 O(1) O(1) std::unordered_set底层实现为哈希表，std::set 和std::multiset 的 ...