225. 用队列实现栈

用队列实现栈emmmm
好难，感觉要长脑子了
用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1
也就是说，在出栈的时候把物理中的队列底部，也就是逻辑上的栈顶元素外的所有数暂存入第二个队列里

class MyStack {
public:queue que1;queue que2; // 辅助队列，用来备份/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que1.size();size--;while (size--) { // 将que1 导入que2，但要留下最后一个元素que2.push(que1.front());que1.pop();//队列的pop没有返回值}int result = que1.front(); // 留下的最后一个元素就是要返回的值que1.pop();que1 = que2;            // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}/** Get the top element. */int top() {return que1.back();//back()直接引用队列容器中最新的元素}/** Returns whether the stack is empty. */bool empty() {return que1.empty();}
};

其实一个队列就可以，也就是把队列1的元素挨个pop再push进去

int pop() {int size = que.size();size--;while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部que.push(que.front());que.pop();}int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了que.pop();return result;}

看到了一个O(1)时间的代码
先放在这里

class MyStack {typedef int Item;
private:enum {S_SIZE = 5};class Node {public:Item item;Node *next;Node(const Item &i, const MyStack &s) : item(i), next(s.ptop) {};};const int stSize;int size;Node *ptop;
public:MyStack(int s = S_SIZE) : stSize(s), ptop(nullptr), size(0) {}~MyStack() {Node *temp;while (ptop != NULL)    // while queue is not yet empty{temp = ptop;        // save address of front itemptop = ptop->next; // reset pointer to next itemdelete temp;         // delete former front}}void push(int x) {if (size == stSize) {return;}Node *node = new Node(x, *this);size++;//链表头部指向这个最新入栈的元素ptop = node;}int pop() {if (empty()) {return 0;}size--;Item item = ptop->item;Node *temp = ptop;ptop = ptop->next;delete temp;return item;}int top() {return ptop->item;}bool empty() {return size == 0;}
};

226. 翻转二叉树

最开始感觉和101对称二叉树很像，但是其实比101感觉还简单，我自己有点想复杂了
递归三部曲
（1）确定递归函数的参数和返回值
参数是当前节点的子节点。
不需要返回值，但是可以直接用题目的函数。

TreeNode* invertTree(TreeNode* root)  

（2）确定终止条件
如果节点为空，返回

if(root==nullptr)return root;

（3）确定单层递归的逻辑
交换左右节点
进入左子树右子树

swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);

228. 汇总区间

细节有很多需要注意到，我细节处理得不好，所以代码写得很冗余
而且有一个测试用例是
[-2147483648,-2147483647,2147483647]
如果用nums[i]-nums[i-1]==1判断是否是临近的数字的话，2147483647-（-2147483647）会溢出
所以要用nums[i]==nums[i-1]+1判断
然后边缘部分，因为要判断后一个减前一个，所以我边缘增加了很多条件，使得代码大大加长

class Solution {
public:vector summaryRanges(vector& nums) {vector ret;if(nums.empty())return ret;if(nums.size()==1){ret.push_back(to_string(nums[0]));return ret;}int left,right;left=nums[0];right=nums[0];for(int i=1;istring cur;if(nums[i]==nums[i-1]+1&&i!=nums.size()-1)continue;if(nums[i]==nums[i-1]+1&&i==nums.size()-1){cur=to_string(left)+"->"+to_string(nums[i]);ret.push_back(cur);continue;}right=nums[i-1];if(right!=left)cur=to_string(left)+"->"+to_string(right);elsecur=to_string(right);ret.push_back(cur);left=nums[i];if(i==nums.size()-1){cur=to_string(nums[i]);ret.push_back(cur);}}return ret;}
};

题解里这样写就简洁很多

class Solution {
public:vector summaryRanges(vector& nums) {vector ret;int i = 0;int n = nums.size();while (i < n) {int low = i;i++;while (i < n && nums[i] == nums[i - 1] + 1) {i++;}int high = i - 1;string temp = to_string(nums[low]);if (low < high) {temp.append("->");temp.append(to_string(nums[high]));}ret.push_back(move(temp));}return ret;}
};