法1：辅助栈 同时用两个指针i, j分别指向两个序列的头部, 每次我们先将i所指向的元素压入栈中, 然后i向后移动一步, 之后再检查当前栈顶, 若对应上了弹出序列中j所指向的元素, 则弹出元素, j向后移动, 再继续检查, 直到栈空或栈顶元素和j所指元素不等为止 class Solution { public: stack<int> s1; …
剑指offer67题-No21.栈的压入弹出序列
剑指offer67题-No20.包含min函数的栈
法1：双栈 再开一个栈，记录单调递减序列，关键是push操作，维护两个栈，每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈；若是较大，则第二个栈的栈顶元素再次入栈。于是，每次访问最小值即访问第二个栈的栈顶。 #include <stack> class Solution { public: stack<int> …
剑指offer67题-No19.顺时针打印矩阵
边界模拟 模拟四个边界情况，并不断收缩。 vector<int> printMatrix(vector<vector<int> > matrix) { if(matrix.size() == 0) return {}; if(matrix.size() == 1) return matrix.front(); int l = 0;…
剑指offer67题-No18.二叉树镜像
递归 class Solution { public: TreeNode* Mirror(TreeNode* pRoot) { //空树返回 if(pRoot == NULL) return NULL; //先递归子树 TreeNode* left = Mirror(pRoot->left); TreeNode* right = Mirror(pR…
剑指offer67题-No17.树的子结构
树的题目，一般用递归来写 双重递归 class Solution { public: bool isSubtree(TreeNode* p1, TreeNode* p2) { if (p2 == nullptr) return true; // 树 B 已匹配完 if (p1 == nullptr) return false; // 树 A 已空但…
剑指offer67题-No16.合并两个有序链表
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。 方法1：新链表合并，抄自牛客题解。比较直观。 class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { auto vhead=new ListNode(-1); //设置一个哨兵指针 ListN…
剑指offer67题-No15.反转链表
反转链表的三种方法--面试必考（图例超详细解析，小白一看就会！！！）-CSDN博客 要求：空间复杂度 O(1) ，时间复杂度 O(n) 。 方法1：就地逆置，三指针迭代分不太清头插法和就地逆置的区别，感觉没啥区别。三个指针temp、cur、newCur； ListNode* ReverseList(ListNode* head) { if(head…
剑指offer67题-No6.旋转数组中的最小数字
二分法。 二分法的本质、模板、例题 - 知乎 二分法的关键是找出目标点的性质。 观察题目中，旋转数组的性质，能发现最小的数字一定是小于等于最右端点的。即找出某区间的最左值，用二分法的右区间模板。 class Solution { public: int minArray(vector<int> &numbers) { int pivo…