题目链接：随机链表的复制给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。你的代码 只 接受原链表的头节点 head 作为传入参数。方法一：哈希表/* // 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: Node* copyRandomList(Node* head) { if (head == NULL) return NULL; unordered_map<Node*,Node*> map; Node* cur = head; while (cur != NULL) { map[cur] = new Node(cur->val); cur = cur->next; } cur = head; while (cur != NULL) { map[cur]->next = map[cur->next]; map[cur]->random = map[cur->random]; cur = cur->next; } return map[head]; } };方法二：拼接+拆分class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; // 1. 复制各节点，并构建拼接链表 while(cur != nullptr) { Node* tmp = new Node(cur->val); tmp->next = cur->next; cur->next = tmp; cur = tmp->next; } // 2. 构建各新节点的 random 指向 cur = head; while(cur != nullptr) { if(cur->random != nullptr) cur->next->random = cur->random->next; cur = cur->next->next; } // 3. 拆分两链表 cur = head->next; Node* pre = head, *res = head->next; while(cur->next != nullptr) { pre->next = pre->next->next; cur->next = cur->next->next; pre = pre->next; cur = cur->next; } pre->next = nullptr; // 单独处理原链表尾节点 return res; // 返回新链表头节点 } };
题目链接：LRU 缓存请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类：LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。方法一：双向链表class LRUCache { private: int capacity; list<pair<int, int>> cache_list; // pair 里面保存的是 key 和 value unordered_map<int, list<pair<int, int>>::iterator> key_to_iter; // key -> 链表节点迭代器 public: LRUCache(int capacity) : capacity(capacity) {} int get(int key) { auto umap_iter = key_to_iter.find(key); if (umap_iter == key_to_iter.end()) { // 没有这本书 return -1; } auto list_iter = umap_iter->second; // 有这本书 // 把这本书（list_iter）从书堆（cache_list）中抽出来，放到最上面（cache_list.begin()） cache_list.splice(cache_list.begin(), cache_list, list_iter); return list_iter->second; // 返回这本书的 value } void put(int key, int value) { auto umap_iter = key_to_iter.find(key); if (umap_iter != key_to_iter.end()) { // 有这本书 auto list_iter = umap_iter->second; list_iter->second = value; // 更新 value // 把这本书（list_iter）从书堆（cache_list）中抽出来，放到最上面（cache_list.begin()） cache_list.splice(cache_list.begin(), cache_list, list_iter); return; } // 新书，放到最上面（emplace_front） cache_list.emplace_front(key, value); key_to_iter[key] = cache_list.begin(); // 书太多了 if (key_to_iter.size() > capacity) { // 去掉最后一本书 key_to_iter.erase(cache_list.back().first); cache_list.pop_back(); } } };
题目链接：二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”方法一：递归/** * 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: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return NULL; if (root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left,p,q); TreeNode* right = lowestCommonAncestor(root->right,p,q); if (left && right) return root; return left ? left : right; } };方法二：栈/** * 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: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return NULL; unordered_map<TreeNode*,TreeNode*> parent; parent[root] = NULL; stack<TreeNode*> s; s.push(root); while (!parent.count(p) || !parent.count(q)) { TreeNode* cur = s.top(); s.pop(); if (cur->left) { parent[cur->left] = cur; s.push(cur->left); } if (cur->right) { parent[cur->right] = cur; s.push(cur->right); } } unordered_set<TreeNode*> se; while (p) { se.insert(p); p = parent[p]; } while (!se.count(q)) { q = parent[q]; } return q; } };
从前序与中序遍历序列构造二叉树
题目链接：从前序与中序遍历序列构造二叉树给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。方法一：递归/** * 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 { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (inorder.size() == 0) return nullptr; TreeNode* root = new TreeNode(preorder[0]); int mid = 0; while (mid < inorder.size() && inorder[mid] != preorder[0]) { mid++; } vector<int> leftIn(inorder.begin(), inorder.begin() + mid); vector<int> rightIn(inorder.begin() + mid + 1, inorder.end()); vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + mid); vector<int> rightPre(preorder.begin() + 1 + mid, preorder.end()); root->left = buildTree(leftPre,leftIn); root->right = buildTree(rightPre,rightIn); return root; } };
题目链接：二叉树展开为链表给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。方法一：递归/** * 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 { public: void flatten(TreeNode* root) { if (root == nullptr) return ; flatten(root->left); flatten(root->right); if (root->left != nullptr) { auto pre = root->left; while (pre->right != nullptr) pre = pre->right; pre->right = root->right; root->right = root->left; root->left = nullptr; } root = root->right; return ; } };
题目链接：实现 Trie (前缀树)Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。请你实现 Trie 类：Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。方法一：前缀树class Trie { public: bool isEnd; Trie* next[26]; Trie() { isEnd = false; memset(next, 0, sizeof(next)); } void insert(string word) { Trie* node = this; for (char c : word) { if (node->next[c-'a'] == NULL) { node->next[c-'a'] = new Trie(); } node = node->next[c-'a']; } node->isEnd = true; } bool search(string word) { Trie* node = this; for (char c : word) { node = node->next[c-'a']; if (node == NULL) { return false; } } return node->isEnd; } bool startsWith(string prefix) { Trie* node = this; for (char c : prefix) { node = node->next[c-'a']; if (node == NULL) { return false; } } return true; } }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */
题目链接：课程表你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。方法一：DFSclass Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<int> f(numCourses,0); vector<vector<int>> rel(numCourses,vector<int>{}); for (auto x : prerequisites) { f[x[0]]++; rel[x[1]].push_back(x[0]); } queue<int> q; for (int i = 0;i < numCourses;i++) { if (f[i] == 0) { q.push(i); } } int les = 0; while (q.size()) { les++; int fi = q.front(); q.pop(); for (auto x : rel[fi]) { f[x]--; if (f[x] == 0) { q.push(x); } } } return les == numCourses; } };
题目链接：编辑距离给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符方法一：二维数组+动态规划class Solution { public: int minDistance(string word1, string word2) { vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0)); for (int i = 0; i < dp.size(); i++) { dp[i][0] = i; } for (int j = 0; j < dp[0].size(); j++) { dp[0][j] = j; } for (int i = 1; i < dp.size(); i++) { for (int j = 1; j < dp[i].size(); j++) { // dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; // if (word1[i - 1] == word2[j - 1]) { // dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); // } dp[i][j] = word1[i-1] == word2[j-1] ? dp[i-1][j-1] : min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; } } return dp.back().back(); } };
题目链接：最长公共子序列给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。方法一：二维数组+动态规划class Solution { public: int f[1010][1010]; int longestCommonSubsequence(string text1, string text2) { int n = text1.size(); int m = text2.size(); for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { f[i+1][j+1] = text1[i] == text2[j] ? f[i][j] + 1 : max(f[i][j+1],f[i+1][j]); } } return f[n][m]; } };
题目链接：最长回文子串给你一个字符串 s，找到 s 中最长的 回文 子串。方法一：中心扩散string longestPalindrome(string s) { int n = s.size(); if (n == 0) return ""; int bestL = 0, bestLen = 1; for (int i = 0; i < n; ++i) { int l = i - 1, r = i + 1; // 吃掉与中心相同的连续字符（处理 "aaaa" 这类） while (l >= 0 && s[l] == s[i]) --l; while (r < n && s[r] == s[i]) ++r; // 再向两边扩展 while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; } int len = r - l - 1; int start = l + 1; if (len > bestLen) { bestLen = len; bestL = start; } } return s.substr(bestL, bestLen); }方法一优化string longestPalindrome(string s) { int n = s.size(); if (n == 0) return ""; int bestL = 0, bestLen = 1; for (int i = 0; i < n; ) { int l = i, r = i; while (r + 1 < n && s[r + 1] == s[i]) ++r; // 合并重复中心 i = r + 1; // 关键：跳到下一段 // 扩展 while (l - 1 >= 0 && r + 1 < n && s[l - 1] == s[r + 1]) { --l; ++r; } int len = r - l + 1; if (len > bestLen) { bestLen = len; bestL = l; } // 可选剪枝：如果剩余长度不足以超越 bestLen if ((n - i) * 2 + 1 <= bestLen) break; } return s.substr(bestL, bestLen); }