目录
- 链表
- 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;
}
};