数据结构 双端队列 C++一端受限的队列无法解决反向输出问题，那就双端嘛。思路同层次遍历一样，用r来记录当前层最后一个入队节点，时间复杂度为O(n)，n为树的节点数；空间复杂度为O(n)。 vector<vector<int> > Print(TreeNode* pRoot) { TreeNode* r = pRoot; //层次遍历，记录当前层最后一个入队节点 deque<TreeNode*> q;//双端队列 vector<vector<int>> ans; if(p...

C++递归 字符拼接将字符串中的空格替换成 %20 ，考虑到移动元素消耗的时间会比较多，于是想到了递归拼接，核心思路是遍历string，碰到空格就进入下一层递归。string内每个元素被访问一次，所以时间复杂度为O(n)，空间复杂度上因为运用了递归，所以主要是一个递归栈的空间占用，取决于空格的数量，最坏情况下可以达到O(n)级。本解法并不高效，但是很懒。 string replaceSpace(string s) { // write code here for(int i=0;i<s.length();i++){ if(s[i]=...

1

除了同归于尽法、map法和排序法以外，还可以有另一个方法，核心思想是顺序遍历数组，对当前下标之后的数字进行内循环统计出现次数。首先创建数组arr，赋初值1，长度等于数组的size，其记录的是数字出现次数，外循环数组，内循环 i 之后的数字，碰到相等数字则对首次出现位置上arr值+1，并且对相等数所对应arr上的值赋值为-1。内外循环均跳过arr[]=-1。在最好情况下即第一个数字就是答案，查找长度为n（或者n/2+1)，时间复杂度为O(n)；最坏情况下前一半的数字都不是答案且均不相同，此时代码的时间复杂度达到O(n²)，总体来说效率较低，属于新手答案。具体代码如下 class So...