链表
31. K个一组翻转链表
题目不难理解 主要是怎么写出清晰易懂的代码 可以先分成K组 再排序
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummyHead = new ListNode();dummyHead->next = head;// 首先查看需要翻转几次int count = 0;ListNode* cur = head;while (cur) {cur = cur->next;count++;}int n = count / k; // 根据题目数据范围 n大于等于1ListNode* prevGroupEnd = dummyHead; // 上一组翻转后的链表的尾部while (n--) { // 找到当前翻转组的头部ListNode* curhead = prevGroupEnd->next;ListNode* nexthead = curhead;for (int i = 0; i < k; i++) {nexthead = nexthead->next;}// 翻转当前的 k 个节点ListNode* prev = nexthead;ListNode* curr = curhead;while (curr != nexthead) {ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}// 更新prevGroupEnd与当前翻转后的头尾连接prevGroupEnd->next = prev;// 更新prevGroupEnd为当前翻转组的尾部prevGroupEnd = curhead;}return dummyHead->next;}
};
32. 复制带随机指针的链表
哈希表遍历两次搞定
class Solution {
public:Node* copyRandomList(Node* head) {Node* cur = head;unordered_map<Node* , Node*> unmap;while (cur) {if (unmap.count(cur) == 0) {unmap[cur] = new Node(cur->val);}cur = cur->next;}cur = head;while(cur) {if (cur->random == NULL) {unmap[cur]->random = NULL;}else {unmap[cur]->random = unmap[cur->random];}if (cur->next != NULL) {unmap[cur]->next = unmap[cur->next];}else {unmap[cur]->next = NULL;}cur = cur->next;}return unmap[head];}
};
33. 链表排序
要找的是快慢指针的左中点 要快指针先移动一格
class Solution {
public:ListNode* mergesort(ListNode* left, ListNode* right) {if (!left) return right;if (!right) return left;ListNode* dummyHead = new ListNode();ListNode* cur = dummyHead;// 合并两个有序链表while (left && right) {if (left->val < right->val) {cur->next = left;left = left->next;} else {cur->next = right;right = right->next;}cur = cur->next;}if (left) cur->next = left;if (right) cur->next = right;ListNode* result = dummyHead->next;delete dummyHead;return result;}ListNode* sortList(ListNode* head) {if (!head || !head->next) return head;// 使用快慢指针找到链表的中点ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// 断开链表ListNode* second = slow->next;slow->next = nullptr; // 断开链表// 递归排序两部分链表ListNode* first = head;first = sortList(first);second = sortList(second);// 合并排序后的链表return mergesort(first, second);}
};34. 合并K个升序链表
每两个之间两两合并即可
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr) {return list2;} if (list2 == nullptr) {return list1;}ListNode* Head = nullptr;if (list1->val < list2->val) {Head = list1;list1 = list1->next;}else {Head = list2;list2 = list2->next;}ListNode* ans = Head;while (list1 && list2) {ListNode* tmp = nullptr;if (list1->val < list2->val) {tmp = list1;list1 = list1->next;}else {tmp = list2;list2 = list2->next;}Head->next = tmp;Head = Head->next;}while(list1) {Head->next = list1;break;}while(list2) {Head->next = list2;break;}return ans;}ListNode* mergeKLists(vector<ListNode*>& lists) {int n = lists.size();if(n == 0) {return nullptr;}if (n == 1) {return lists[0];}ListNode* ans = lists[0];for (int i = 1; i < n; i++) {ans = mergeTwoLists(ans , lists[i]);}return ans;}
};
35. LRU缓存
哈希表和双向链表的结合 弄明白这两点就很容易做了
struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};class LRUCache {
private:unordered_map<int, DLinkedNode*> cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;public:LRUCache(int _capacity): capacity(_capacity), size(0) {// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) {return -1;}// 如果 key 存在，先通过哈希表定位，再移到头部DLinkedNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {if (!cache.count(key)) {// 如果 key 不存在，创建一个新的节点DLinkedNode* node = new DLinkedNode(key, value);// 添加进哈希表cache[key] = node;// 添加至双向链表的头部addToHead(node);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode* removed = removeTail();// 删除哈希表中对应的项cache.erase(removed->key);// 防止内存泄漏delete removed;--size;}}else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部DLinkedNode* node = cache[key];node->value = value;moveToHead(node);}}void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;}void moveToHead(DLinkedNode* node) {removeNode(node);addToHead(node);}DLinkedNode* removeTail() {DLinkedNode* node = tail->prev;removeNode(node);return node;}
};
二叉树
36. 中序遍历
class Solution {
public:vector<int> _inorderTraversal(TreeNode* root , vector<int>& ans) {if (root == nullptr) {return {};}_inorderTraversal(root->left , ans);ans.push_back(root->val);_inorderTraversal(root->right , ans);return ans;}vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;return _inorderTraversal(root , ans);}
};
37. 二叉树的最大高度
class Solution {
public:int maxDepth(TreeNode* root) {if (root == nullptr) {return 0;}int h1 = maxDepth(root->left);int h2 = maxDepth(root->right);return max(h1 , h2) + 1; }
};
38. 翻转二叉树
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == nullptr) {return nullptr;}auto* left = invertTree(root->left);auto* right = invertTree(root->right);root->left = right;root->right = left;return root;}
};
39. 对称二叉树
class Solution {
public:bool Check(TreeNode* p, TreeNode* q) {if (!q && !p) {return true;}if (!q || !p) {return false;} // 节点值相等，继续递归检查左右子树return p->val == q->val && Check(p->left, q->right) && Check(p->right, q->left);}bool isSymmetric(TreeNode* root) {if (root == nullptr) {return true;}return Check(root->left, root->right);}
};40. 二叉树的直径
struct info {int dis; // 当前节点的直径int depth; // 当前节点的深度info(int _dis, int _depth) {dis = _dis;depth = _depth;}
};class Solution {
public:info* _diameterOfBinaryTree(TreeNode* root) {if (root == nullptr) {return new info(0, 0); // 空节点的直径为0，深度为0}info* left = _diameterOfBinaryTree(root->left);info* right = _diameterOfBinaryTree(root->right);// 当前节点的直径是左右子树深度之和int diameter = left->depth + right->depth;// 当前节点的深度是左右子树深度的最大值 + 1int depth = std::max(left->depth, right->depth) + 1;// 返回当前节点的直径和深度return new info(std::max(diameter, std::max(left->dis, right->dis)), depth);}int diameterOfBinaryTree(TreeNode* root) {return _diameterOfBinaryTree(root)->dis;}
};
