LeetCode刷题【链表,图论,回溯】

目录

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

回溯

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505752.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于知识图谱的个性化学习推荐系统的设计与实现(论文+源码)_kaic

摘 要 Abstract 1 绪 论 1.1 研究背景及意义 1.2 国内外现状研究 1.3 研究工作和论文结构 2 相关技术 2.1 HTML 语言 2.2 Python 语言 2.3 数据库技术 2.4 Django 框架 3 系统分析 3.1 需求概述 3.2 系统可行性分析 3.2.1 技术可行性 3.2.2 经济可行性 3.2.3 操作可行性 3.3 功…

网络基础二补充——json与http协议

五、市面上常用序列化和反序列化工具 ​ 常用的有&#xff1a;json、protobuf、xml三种方案&#xff1b; 5.1json的使用 1.安装jsoncpp库&#xff0c;是一个第三方的开发库文件&#xff1b; sudo yum install -y jsoncpp-devel2.使用json ​ 经常使用的头文件是json.h&…

Python之Opencv教程(2):图像边缘检测

1、什么是边缘检测 OpenCV中的边缘检测是一种常见的图像处理技术&#xff0c;用于检测图像中物体边缘的位置。常用的边缘检测算法包括Sobel算子、Scharr算子、Laplacian算子和Canny边缘检测算法等。下面将介绍使用OpenCV实现这些边缘检测算法的方法。 2、边缘检测的作用 边缘…

C语言---自定义类型:联合体和枚举

文章目录 前言1. 联合体类型的声明1.1 联合体类型的声明1.2 联合体的特点1.4 联合体大小的计算1.5 联合的一个练习 2.枚举2.1 枚举类型的声明2.2 枚举类型的优点 前言 上一篇我们学习了自定义类型—结构体&#xff0c;大家会发现&#xff0c;构建一个结构体时&#xff0c;有些…

程序数据模型由OS还是硬件架构决定?

文章目录 前言硬件架构的作用OS的作用编译器的角色OS的数据模型参考 前言 在文章 1>>32的结果是1还是0 中提到了数据模型 L P 64 LP64 LP64 &#xff0c;并提出这个数据模型主要是由 U n i x Unix Unix 以及类 U n i x Unix Unix 的操作系统使用居多&#xff0c;例如…

macOS Catalina for mac (macos 10.15系统)v10.15.7正式版

macOS Catalina是苹果公司专为麦金塔电脑推出的桌面操作系统&#xff0c;是macOS的第16个主要版本。它继承了苹果一贯的优雅与高效&#xff0c;不仅引入了分割视图和侧边栏&#xff0c;还带来了全新的音乐和播客应用&#xff0c;极大地提升了用户体验。在隐私保护和安全性方面&…

java学习总结以及考试总结

1.对象的this引用 this引用用于区分成员变量和局部变量&#xff0c;this引用的一定的指的是成员变量 所以说this语句的作用就是区分成员变量和局部变量&#xff08;如何呢&#xff09; package com.temo.test1;public class student{private String name;//成员变量private …

Optimizer神经网络中各种优化器介绍

1. SGD 1.1 batch-GD 每次更新使用全部的样本&#xff0c;注意会对所有的样本取均值&#xff0c;这样每次更新的速度慢。计算量大。 1.2 SGD 每次随机取一个样本。这样更新速度更快。SGD算法在于每次只去拟合一个训练样本&#xff0c;这使得在梯度下降过程中不需去用所有训…

OpenEuler华为欧拉系统安装教程及联网配置

OpenEuler简介 openEuler是一款开源操作系统。当前openEuler内核源于Linux&#xff0c;支持鲲鹏及其它多种处理器&#xff0c;能够充分释放计算芯片的潜能&#xff0c;是由全球开源贡献者构建的高效、稳定、安全的开源操作系统&#xff0c;适用于数据库、大数据、云计算、人工智…

【Laravel】07 快速套用一个网站模板

【Laravel】07 快速套用一个网站模板 1. 新增post表2.补充 &#xff1a;生成Model、Controller、迁移文件3. 使用php artisan tinker4. 网站模板下载 课程地址 1. 新增post表 在Model中创建Post (base) ➜ example-app php artisan make:model Post Model created successfu…

力扣 1035. 不相交的线

题目来源&#xff1a;https://leetcode.cn/problems/uncrossed-lines/description/ C题解&#xff1a;经过细细一推导&#xff0c;就发现跟力扣 1143. 最长公共子序列-CSDN博客 换汤不换药。 直线不能相交&#xff0c;说明元素顺序不能改变&#xff0c;求可以绘制的最大连线数…

相机显示储存卡未格式化怎么回事?怎么办

在摄影的学习和实践中&#xff0c;相机是我们记录美好瞬间的得力助手。然而&#xff0c;当相机突然提示储存卡未格式化时&#xff0c;这往往会让我们感到困惑和焦虑。本文将探讨相机显示储存卡未格式化的可能原因&#xff0c;并提供相应的解决方案。 图片来源于网络&#xff0c…

游戏引擎中的大气和云的渲染

一、大气 首先和光线追踪类似&#xff0c;大气渲染也有类似的渲染公式&#xff0c;在实际处理中也有类似 Blinn-Phong的拟合模型。关键参数是当前点到天顶的角度和到太阳的角度 二、大气散射理论 光和介质的接触&#xff1a; Absorption 吸收Out-scattering 散射Emission …

汇编语言第四版-王爽第1章 基础知识

前言 基础知识 &#xff08;1&#xff09;换成bit&#xff0c;1KB1024B&#xff0c;1Byte8bit&#xff1b;1KB1024*8bit&#xff0c;即2的13次方&#xff0c;宽度为13. &#xff08;2&#xff09;1个存储单元只能放1个字节&#xff0c;1KB1024B&#xff1b;编号从0到1023. &a…

web前端面试题----->VUE

Vue的数据双向绑定是通过Vue的响应式系统实现的。具体原理&#xff1a; 1. Vue会在初始化时对数据对象进行遍历&#xff0c;使用Object.defineProperty方法将每个属性转化为getter、setter。这样在访问或修改数据时&#xff0c;Vue能够监听到数据的变化。 2. 当数据发生变化时…

书生 浦语大模型全链路开源体系

通用大模型成为发展通用人工智能的重要途径 书生 浦语大模型的开源历程 书生 浦语 2.0体系&#xff0c;面向不同的使用需求&#xff0c;每个规格包含三个模型版本&#xff0c;&#xff08;7B、20B&#xff09;InternLM2-Base、InternLM2、InternLM2-Chat。 大模型是回归语言建…

python通过shapely 的 valid 判断aoi图形是否有效

测试aoi坐标&#xff1a; 116.527712,39.924304;116.527123,39.924353;116.52707,39.923985;116.527685,39.92397;116.527712,39.924304 如图所示是一个有效的坐标&#xff0c;使用python代码判断是否有效&#xff1a; 代码&#xff1a; from shapely.geometry import Polyg…

数字孪生|山海鲸可视化快速入门

哈喽,你好啊,我是雷工! 今天继续学习山海鲸可视化软件,以下为学习记录。 (一)新建项目 1.1、打开软件后,默认打开我的项目界面,初次打开需要注册,可以通过手机号快速注册。 点击“新建”按钮,新建一个项目。 1.2、根据项目需要选择一个快捷的项目模板,填写项目名称…

C语言 | Leetcode C语言题解之第1题两数之和

题目&#xff1a; 题解&#xff1a; int* twoSum(int* nums, int numsSize, int target, int* returnSize) {for (int i 0; i < numsSize; i) {for (int j i 1; j < numsSize; j) {if (nums[i] nums[j] target) {int* ret malloc(sizeof(int) * 2);ret[0] i, ret…

【Qt 学习笔记】Day1 | Qt 背景介绍

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Day1 | Qt 背景介绍 文章编号&#xff1a;Qt 学习笔记 / 01 文章目录…