Jayce's Blog

PROBLEM剑指 Offer 36. 二叉搜索树与双向链表 难度 中等 MY ANSWER递归遍历树的节点，改变节点左子树的最右儿子、右子树的最左儿子的指针构建双向链表。 /*// Definition for a Node.class Node {public: int val; Node* left; Node* right; Node() {} Node(int _val) { val = _val; left = NULL; right = NULL; } Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; }};*/class Solution {public: void changer(Node* node) { ...

PROBLEM剑指 Offer 35. 复杂链表的复制 难度 中等 MY ANSWER使用哈希表储存原链表节点与新链表节点的对应关系，根据表来构造新链表。时间复杂度空间复杂度都为O(n)。 /*// Definition for a Node.class Node {public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; }};*/class Solution {public: unordered_map<Node*, Node*> table; Node* copyRandomList(Node* head) { if(!head) { return nullptr; } Node* tmp = h ...

PROBLEM剑指 Offer 34. 二叉树中和为某一值的路径 难度 中等 MY ANSWERdfs遍历树，将合适的路径seq加入到res。时间复杂度为O(n)，空间复杂度O(n)。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution { ...

PROBLEM剑指 Offer 32 - III. 从上到下打印二叉树 III 难度 中等 MY ANSWER使用双端队列deque进行bfs，奇数层正序遍历deque，偶数层倒序遍历deque。时间复杂度O(n)，空间复杂度O(n)。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { deque<TreeNode*> bfs; vector<vector<int>> re ...

PROBLEM剑指 Offer 33. 二叉搜索树的后序遍历序列 难度 中等 MY ANSWER后序遍历序列最后一个元素为根节点，由二叉搜索树性质可得，序列以第一个比根节点值大的元素为界，左边全部小于根节点值，右边全部大于根节点值，可以通过检查是否符合该情况来判断能否满足二叉搜索树的定义。递归对数组进行遍历，先遍历整个树判断是否符合上述条件，然后是左子树、右子树如此递归。时间复杂度为O(n^2)，空间复杂度O(n)。 class Solution {public: vector<int> p; bool judge(int left, int right){ // cout<<left<<right<<endl; if(left >= right - 1) { return true; } int sign = p[right]; int mid = right; for(i ...

PROBLEM剑指 Offer 31. 栈的压入、弹出序列 难度 中等 MY ANSWER使用栈进行模拟，时间复杂度为O(n)，空间复杂度为O(n)。 class Solution {public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { int pushp = 0, popp = 0; stack<int> s; while(pushp < pushed.size() || popp < popped.size()) { if(s.empty() || pushed.size() && popped[popp] != s.top()) { while(pushp < pushed.size()) { s.push ...

PROBLEM剑指 Offer 26. 树的子结构 难度 中等 MY ANSWER使用bfs遍历A，找到与B头节点值相等的节点，调用judge，分别使用bfs遍历进行比较。若有一次judge调用返回true，则说明A包含B。M为A节点数，N为B节点数，时间复杂度O(MN)，空间复杂度O(M)。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool judge(TreeNode* A, TreeNode* B) { queue<TreeNode*> m; queue<TreeNode*> n; ...

PROBLEM剑指 Offer 22. 链表中倒数第k个节点 难度 简单 MY ANSWER首先遍历一次得出链表长度，然后再遍历一次返回链表。时间复杂度O(n)，空间复杂度O(1)。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* getKthFromEnd(ListNode* head, int k) { int cnt = 0; ListNode* tmp = head; while(tmp) { tmp = tmp->next; cnt++; } tmp = h ...

PROBLEM剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 难度 简单 MY ANSWER顺序遍历，偶数存入偶数数组，奇数存入奇数数组，返回组合后的数组。时间复杂度O(n)，空间复杂度O(n)。 class Solution {public: vector<int> exchange(vector<int>& nums) { vector<int> even; vector<int> odd; for(int i = 0; i < nums.size(); i++) { if(nums[i] & 1) { odd.push_back(nums[i]); } else { even.push_back(nums[i]); }
...

PROBLEM剑指 Offer 30. 包含min函数的栈 难度 简单 MY ANSWER两个栈，一个存放数据，一个存放前者对应的元素为栈顶时的最小值。 class MinStack {public: /** initialize your data structure here. */ stack<int> s; stack<int> m; MinStack() { } void push(int x) { s.push(x); if(m.empty()) { m.push(x); return; } if(x < m.top()) { m.push(x); } else { m.push(m.top()); } } ...