目录
- 链表
- 138. 随机链表的复制
- 148. 排序链表
- 146. LRU 缓存
- 图论
- 200. 岛屿数量
- 994. 腐烂的橘子
- 207. 课程表
- 回溯
链表
138. 随机链表的复制
给你一个长度为 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 作为传入参数。
class Solution {
public:unordered_map<Node*, Node*> cachedNode;Node* copyRandomList(Node* head) {if(head == NULL){return NULL;}if(!cachedNode.count(head)){Node* temp = new Node(head->val);cachedNode[head] = temp;temp->next = copyRandomList(head->next);temp->random = copyRandomList(head->random);}return cachedNode[head];}
};
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
class Solution {
public:ListNode* merge(ListNode* head1, ListNode* head2){ListNode* dummyHead = new ListNode(0);ListNode* temp = dummyHead;ListNode* temp1 = head1;ListNode* temp2 = head2;while(temp1 != nullptr && temp2 != nullptr){if(temp1->val <= temp2->val){temp->next = temp1;temp1 = temp1->next;}else{temp->next = temp2;temp2 = temp2->next;}temp = temp->next;}if(temp1 != nullptr){temp->next = temp1;}else if(temp2 != nullptr){temp->next = temp2;}return dummyHead->next;}ListNode* sortList(ListNode* head, ListNode* tail){if(head == nullptr){return head;}if(head->next == tail){head->next = nullptr;return head;}ListNode* slow = head, *fast = head;while(fast != tail){slow = slow->next;fast = fast->next;if(fast != tail){fast = fast->next;}}ListNode* mid = slow;return merge(sortList(head, mid), sortList(mid, tail));}ListNode* sortList(ListNode* head) {return sortList(head, nullptr);}
};
146. 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) 的平均时间复杂度运行。
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)){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;}
};
图论
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
方法：深度优先搜索
class Solution {
public:void dfs(vector<vector<char>>& grid, int r, int c){int nr = grid.size();int nc = grid[0].size();grid[r][c] = '0';if(r - 1 >= 0 && grid[r-1][c] == '1'){dfs(grid, r - 1, c);}if(r + 1 < nr && grid[r+1][c] == '1'){dfs(grid, r + 1, c);}if(c - 1 >= 0 && grid[r][c-1] == '1'){dfs(grid, r, c - 1);}if(c + 1 < nc && grid[r][c+1] == '1'){dfs(grid, r, c + 1);}}int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if(!nr){return 0;}int nc = grid[0].size();int num_islands = 0;for(int r = 0; r < nr; r++){for(int c = 0; c < nc; c++){if(grid[r][c] == '1'){num_islands++;dfs(grid, r, c);}}}return num_islands;}
};
994. 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
方法：多源广度优先搜索
class Solution {int cnt;int dis[10][10];int dir_x[4] = {0, 1, 0, -1};int dir_y[4] = {1, 0, -1, 0};
public:int orangesRotting(vector<vector<int>>& grid) {queue<pair<int, int>> Q;memset(dis,-1, sizeof(dis));cnt = 0;int n = (int)grid.size(), m = (int)grid[0].size(), ans = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(grid[i][j] == 2){Q.push(make_pair(i, j));dis[i][j] = 0;}else if(grid[i][j] == 1){cnt += 1;}}}while(!Q.empty()){pair<int, int> x = Q.front(); Q.pop();for(int i = 0; i < 4; i++){int tx = x.first + dir_x[i];int ty = x.second + dir_y[i];if(tx < 0 || tx >= n || ty < 0 || ty >= m || ~dis[tx][ty] || !grid[tx][ty]){continue;}dis[tx][ty] = dis[x.first][x.second] + 1;Q.push(make_pair(tx, ty));if(grid[tx][ty] == 1){cnt -= 1;ans = dis[tx][ty];if(!cnt){break;}}}}return cnt ? -1 : ans; }
};
207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
class Solution {
private:vector<vector<int>> edges;vector<int> visited;bool valid = true;
public:void dfs(int u){visited[u] = 1;for(int v : edges[u]){if(visited[v] == 0){dfs(v);if(!valid){return;}}else if(visited[v] == 1){valid = false;return;}}visited[u] = 2;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for(const auto& info: prerequisites){edges[info[1]].push_back(info[0]);}for(int i = 0; i < numCourses && valid; i++){if(!visited[i]){dfs(i);}}return valid;}
};
