欢迎来到小林的博客

【题目】：24. 两两交换链表中的节点 class Solution {public: ListNode* swapPairs(ListNode* head) { if(head == nullptr || head->next == nullptr) { return head; } ListNode* pre = new ListNode(0, head); // c、a、b（她们仨的相对顺序） ListNode *a = head, *b = head->next, *c = pre; while(b) {… b = temp->next; } return pre->next; }}; 时间复杂度: O(n) 空间复杂度: O(1)

【题目】：236. 二叉树的最近公共祖先 终止条件： 当root到叶节点终止 当root是p或q终止（因为要求的是公共祖先，如果遍历到p，就算q还在p的下边，他们的公共祖先还是p） 这也说明了：如果返回的是nullptr，说明p、q不在这棵树中 返回情况： left == nullptr && right == nullptr：说明root的左右子树都没有p、q，直接返回nullptr left != nullptr && right == nullptr：说明p、q在root的左子树中，那么只需要返回left（因为前面只要遇到p或q就会终止，所以此时left就是p、q中相对上边的节点） right != nullptr && left == nullptr：说明p、q在root的右子树中，那么只要返回right即可（原因同上） right != nullptr && left !=...

【题目】：189. 轮转数组 class Solution {public: void reverse(vector<int>& nums, int begin, int end) { for(int i = begin, j = end; i < j; ++i, --j) { swap(nums[i], nums[j]); } } void rotate(vector<int>& nums, int k) { int n = nums.size(); k = k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); }}; 时间复杂度: O(n) 空间复杂度:...

【题目】：160. 相交链表 class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* a = headA, *b = headB; while(a != b) { a = (a != NULL ? a->next : headB); b = (b != NULL ? b->next : headA); } return a; }}; 时间复杂度: O(a + b) 空间复杂度: O(1) 这题可以将headA遍历完后遍历headB，把headB遍历完后遍历headA，这样就相当于走了同样的距离。不管什么情况，都会退出循环，且都只会遍历（a+b）次，不会有死循环的情况。

【题目】：146. LRU 缓存 LRU：最近最少未使用，很少被请求的数据才会被淘汰掉 本质：让不经常访问的数据往下排，经常访问的数据往上排。这样会导致：冷门数据在最下边，热门数据在最上边。如果访问的数据缓存中没有且缓存已经满了：把最下边的数据淘汰掉，再把刚访问的数据放到上边（换页） 分析： 选用什么数据结构？ 数组：添加一个节点，所有节点都要往后移动，时间复杂度O(n) 链表：添加节点、删除节点只需要改变节点指向，时间复杂度O(1)。只需要改变指针的指向即可。由于不仅要直到节点的下一位，还需要直到节点的上一位，所以使用双向链表。 怎么找到链表的某个节点？ 正常查询链表的某个节点，需要逐个遍历链表元素，时间复杂度O(n)。那有没有办法优化到O(1)的时间复杂度呢？ hashMap的查询时间复杂度是O(1)，可以用hashMap来存储链表节点。 最后选择数据结构如下： 双向链表数据结构 class Node {public: int key; int value; Node *pre; Node *next; ...

【题目】：142. 环形链表 II 如图所示，如果有环，fast 和 slow必会相遇，此时fast走n圈，slow走一圈。由于： n = 1：a = c n > 1：a = c + (n - 1)(b + 1)所以可以进行两次遍历，第一次遍历找到相遇点；第二次遍历时，一个指针从相遇点开始遍历，一个指针从head处开始遍历，当这两个指针相遇时，就是到达题目所求节点。 class Solution {public: ListNode *detectCycle(ListNode *head) { ListNode *fast = head, *slow = head; while(true) { if(fast == nullptr || fast->next == nullptr) {// 不相遇 - 无环 return nullptr; } fast =...

【题目】：124. 二叉树中的最大路径和 这题有两个关键点： 更新res：res = max(l + r + root->val, res)，左子树最大链长 + 右子树最大链长 + 根节点的值其实也可以当成一条链 子树root的最大链长：max(max(l, r) + root->val, 0)，由于一个子树的链长只能取左子树的最大链长或右子树的最大链长，所以这里先max(l, r)，也别忘了+root->val，由于这个值可能比0还小，如果比0小那要你还有什么用？直接舍弃好了（0表示什么都不取） class Solution {public: int res = INT_MIN; int help(TreeNode* root) { if(root == nullptr) { return 0; } int l = help(root->left); // 左子树的最大链和 int r =...

【题目】：114. 二叉树展开为链表这题要将一个二叉树转成单链表，且展开后的单链表应该和二叉树的先序遍历相同。如果直接正向思考：能不能先序遍历，先处理当前节点（把当前遍历到的节点插入到单链表中），但是这样存在一个问题，此时当前节点的右孩子还没有被遍历到，这样会出现孩子丢失的情况。 考虑逆向思考：题目要求先序遍历（根左右）的结果，那能不能用后序遍历（左右根）呢？这样就不会出现孩子丢失的问题，因为当去更新当前的右指针时，已经遍历过他的右节点了。 但是如果是后序遍历的话，结点的顺序应该怎么处理呢？目前节点的顺序是和题目所求的节点顺序相反，因此可以考虑头插法。 class Solution {public: TreeNode* res = nullptr; void help(TreeNode* root) { if(root == nullptr) { return; } // 右 help(root->right); // 左 ...

【题目】：108. 将有序数组转换为二叉搜索树二叉搜索树的特征：左 < 根 < 右所以可以将数组最中间的数作为根节点，依次把根左边的数组和根右边的数组作为左右节点即可。 class Solution {public: TreeNode* help(vector<int> nums, int l, int r) { // [l, r) if(l == r) { return nullptr; } int mid = l + (r - l) / 2; TreeNode *node = new TreeNode(nums[mid]); node->left = help(nums, l, mid); // [l, mid) node->right = help(nums, mid + 1, r); // [mid + 1, r) return node; } ...

【题目】：102. 二叉树的层序遍历 class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { if(root == nullptr) { return {}; } queue<TreeNode*> q; vector<vector<int>> res; q.push(root); while(!q.empty()) { vector<int> tempVec; // 存储一整行的数据 int n = q.size(); for(int i = 0; i < n; ++i) { // 遍历q队列（此时q队列中存储一层的数据 -> 全部出队） ...