算法闭关修炼百题计划(六)

塔塔开(滑稽

  • 1.删除排序链表中的重复元素
  • 2.删除排序链表中的重复元素II
  • 3.字典序的第k小数字
  • 4.下一个排列
  • 5.排序链表
  • 6.随机链表的复制
  • 7.数据流的中位数

1.删除排序链表中的重复元素

使每个元素就出现一次

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (!head) return nullptr;ListNode* cur = head;while (cur && cur->next) {if (cur->val == cur->next->val) {// Skip over duplicate nodesListNode* temp = cur->next;cur->next = cur->next->next;delete temp; // Free memory if needed} else {// Move to the next distinct nodecur = cur->next;}}return head;}
};

2.删除排序链表中的重复元素II

重复的全删了,一个也不留

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* cur = dummy;while(cur && cur->next && cur->next->next){//先把这个值存下来int num = cur->next->val;if(cur->next->next->val == num){//可能不止2个while(cur->next && cur->next->val == num){cur->next = cur->next->next;}}else cur = cur->next;}return dummy->next;}
};

以上两题放在一起是故意的,学一学这个这个写法

3.字典序的第k小数字

给定整数 n 和 k,返回 [1, n] 中字典序第 k 小的数字。

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。

字节考频top10
字典序答,什么是字典序?
简而言之,就是根据数字的前缀进行排序,比如 10 < 9,因为 10 的前缀是 1,比 9 小。再比如 112 < 12,因为 112 的前缀 11 小于 12。这样排序下来,会跟平常的升序排序会有非常大的不同。先给你一个直观的感受,一个数乘 10,或者加 1,哪个大?可能你会吃惊,后者会更大。
在这里插入图片描述

class Solution {
public:int findKthNumber(int n, int k) {int curr = 1; // 从字典序第一个数字1开始k--;          // 减1是因为我们已经在第一个位置(数字1)while (k > 0) {int steps = calculateSteps(n, curr, curr + 1);if (steps <= k) {// k在当前前缀范围之外,跳到下一个前缀curr += 1;k -= steps;} else {// k在当前前缀范围之内,向下移动到更小的前缀curr *= 10;k -= 1;}}return curr;}private:int calculateSteps(int n, long curr, long next) {int steps = 0;while (curr <= n) {steps += std::min((long)n + 1, next) - curr;curr *= 10;next *= 10;}return steps;}
};

findKthNumber:找到字典序第 k 小的数字。

从 curr = 1 开始,每次根据剩余的 k 确定是向下移动还是进入下一个数字前缀。
当 k == 0 时,curr 就是第 k 小的数字。
calculateSteps:计算以 curr 为前缀的子树节点数量。

curr 和 next 分别代表当前前缀和下一个前缀的起始数字,通过扩大 10 倍逐层计算包含的节点数。

4.下一个排列

整数数组的下一个排列是指其整数的下一个字典序更大的排列
arr = [1,2,3]的下一个排列是[1,3,2]。

给你一个整数数组 nums ,找出 nums 的下一个排列。
必须 原地 修改,只允许使用额外常数空间。

现在给一个序列5 2 4 3 1,找下一个字典序排列,可以按照以下步骤:
在这里插入图片描述

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();int i = n - 2;// Step 1: Find the first decreasing element from the endwhile (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// Step 2: If we found a valid i, find the next largest element to swap withif (i >= 0) {int j = n - 1;while (nums[j] <= nums[i]) {j--;}swap(nums[i], nums[j]);}// Step 3: Reverse the decreasing sequence to get the smallest lexicographical orderreverse(nums.begin() + i + 1, nums.end());}
};

step3中,笃定了nums[i]的右侧一定是降序的,所以总结reverse成升序,为什么这么笃定呢?
因为我们一开始找i,找的就是逆序数,找到了i,就意味着i的右侧都是顺序数,也就是降序
现在交换了nums[i]和一个比nums[i]大的最小数,右侧排序仍然是降序的,不会有任何改变!

5.排序链表

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

要对链表进行排序,可以使用归并排序,因为归并排序在链表上非常高效,且可以在O(nlogn)时间复杂度内完成
归并排序的思路是将链表递归拆成两半,对每一半进行排序,然后将它们合并。具体步骤如下:

  1. 使用快慢指针找到链表的中间节点,以便将链表分成两半。
  2. 递归对左右两半分别进行排序。
  3. 使用合并两个有序链表的方法将两半合并成一个有序链表。
class Solution {
public:ListNode* sortList(ListNode* head) {// Base case: If the list is empty or has only one node, it's already sortedif(!head || !head->next) return head;// Step 1: Use fast and slow pointers to find the middle of the listListNode* fast = head;ListNode* slow = head;ListNode* pre = nullptr;while(fast && fast->next){pre = slow;slow = slow->next;fast = fast->next->next;}// Cut the list into two halvespre->next = nullptr;// Step 2: Recursively sort each halfListNode* left = sortList(head);ListNode* right = sortList(slow);// Step 3: Merge the sorted halvesreturn merge(left, right);}ListNode* merge(ListNode* l1, ListNode* l2){ListNode* dummy = new ListNode(0);ListNode* tail = dummy;while(l1 && l2){if(l1->val < l2->val){tail->next = l1;l1 = l1->next;}else{tail->next = l2;l2 = l2->next;}tail = tail->next;}// If there are remaining elements in either list, append themif(l1){tail->next = l1;}else{tail->next = l2;}return dummy->next;}
};

6.随机链表的复制

在这里插入图片描述
在这里插入图片描述

题意解读:
创建一个新链表 链表的所有东西 val next random都要与原链表完全相同 但是node的地址不能和原链表相同 也就是进行深拷贝 类似c++类中有指针 要自定义拷贝构造函数

分析:
要复制一个带有随机指针的链表,可以分成几个步骤来完成。这里采用一种O(n)的时间复杂度和O(1)的空间复杂度的方法。这个方法的核心是将链表的节点复制一份并插入到原链表中,然后调整随机指针,最后将原链表和复制的链表分离。

思路:
第一步:在原链表中插入新节点
遍历原链表的每个节点,对每个节点创建一个新节点,并将新节点插入到原节点的后面。如果原链表是A->B->C,插入新节点后变成A->A’->B->B’->C->C’。
第二步:设置新节点的随机指针
遍历链表,对每个新节点设置其random指针。由于新节点在原节点的后面,因此node->next->random应该指向node->random->next(如果 node->random 不为空的话)。
上一句解释:
在这里插入图片描述
举例:
假设原链表node1->node2->node3
node1->random = node3
node2->random = node1
node3->random = node2

通过第一步,我们应该将复制的节点node1’,node2’,node3’加上去,结果如下
node1->node1’->node2->node2’->node3->node3’
现在我们需要更改random指针,比如node1’,我们需要他的random指针指向node3’而不是node3
所以更改random指针这一步是node->next->random = node->random->next!!!
第三步:将原链表和复制链表分离
再次遍历链表,将新节点从原链表中分离出来形成新的链表

在这个问题中,深拷贝的知识点是指创建一个完全独立的复制链表,其中每个节点都是原链表中节点的独立副本。具体来说,原链表中的每个节点不仅要复制他的值和next指针,还要复制他的random指针(指向链表中的任意节点或空指针)。而且,复制链表中的节点不能引用到原链表中的节点,必须是完全独立的。

独立的新节点:深拷贝会创建新的节点对象,而不是直接引用原节点对象。这意味着复制链表中的每个节点在内存中是独立的,与原链表中的节点没有共享部分。即使原链表被修改,复制链表的内容也不会受到影响。

复制复杂结构:对于一个有复杂指针结构(例如 random 指针)的数据结构,深拷贝要求复制每一个指针引用关系。在这个链表中,除了复制 next 指针,还要确保 random 指针也复制到新链表中相应位置。

避免浅拷贝问题:浅拷贝只会简单复制原链表节点的指针,使新链表中的节点指向原链表中的节点。这会导致原链表和复制链表共享相同的节点对象,若修改一个链表中的节点,另一个链表也会受到影响。在这个题目中,我们需要完全独立的复制链表,避免这样的副作用。

class Solution {
public:Node* copyRandomList(Node* head) {if (!head) return nullptr;// Step 1: 创建新节点并插入到原节点后面Node* curr = head;while (curr) {Node* newNode = new Node(curr->val);newNode->next = curr->next;curr->next = newNode;curr = newNode->next;}// Step 2: 设置新节点的 random 指针curr = head;while (curr) {if (curr->random) {curr->next->random = curr->random->next;}curr = curr->next->next;}// Step 3: 将原链表和复制链表分离,注意!!不要破坏原链表!!curr = head;Node* newHead = head->next;Node* copy = newHead;while (curr) {curr->next = curr->next->next;if (copy->next) {copy->next = copy->next->next;}curr = curr->next;copy = copy->next;}return newHead;}
};

7.数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

第一个数组是操作顺序,第二个数组是操作对应的数字

本题的核心思路是使用两个堆,也就是两个优先队列
小的倒三角就是个大顶堆,梯形就是个小顶堆,中位数可以通过它们的堆顶元素算出来:
在这里插入图片描述
addNum(int num)函数,当添加一个数时,首先判断该数应当放入哪个堆(大根堆或小根堆)。根据当前堆的大小,调整堆的平衡,确保两个堆的元素数目差不超过1。

findMedian()如果两个堆的大小相等,返回两个堆顶元素的平均值,如果堆的大小不等,直接返回大根堆的堆顶元素,因为它代表了数据流的中位数

class MedianFinder {
private:priority_queue<int> maxHeap; // 大根堆,用于存储较小的一半priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆,用于存储较大的一半public:/** Initialize your data structure here. */MedianFinder() {}/** Adds a number into the data structure. */void addNum(int num) {// 保证maxHeap存储较小部分,minHeap存储较大部分if (maxHeap.empty() || num <= maxHeap.top()) {maxHeap.push(num);  // 如果num小于等于maxHeap的堆顶,加入maxHeap} else {minHeap.push(num);  // 否则加入minHeap}// 平衡两个堆,使得maxHeap和minHeap的大小差不超过1if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}/** Returns the median of current data stream */double findMedian() {if (maxHeap.size() == minHeap.size()) {return (maxHeap.top() + minHeap.top()) / 2.0; // 两个堆大小相等,取两个堆顶的平均值} else {return maxHeap.top(); // 如果maxHeap多一个元素,返回maxHeap的堆顶元素}}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

实习冲刺第二十天

543.二叉树的直径 给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1&#xff1a; 输入&#xff1a;root …

搜索引擎算法解析提升搜索效率的关键要素

内容概要 搜索引擎算法是指一系列计算机程序和规则&#xff0c;用于决定如何抓取、索引和提供网页信息。了解这些算法的核心概念对于提高我们的搜索效率至关重要。本文将详细分析搜索引擎的工作原理和主要算法类型&#xff0c;以及它们如何影响搜索结果的准确性和用户体验。 …

Brave127编译指南 Windows篇:配置Git(四)

1. 概述 在Brave浏览器的开发过程中&#xff0c;Git作为核心版本控制工具扮演着不可或缺的角色。作为当今最广泛使用的分布式版本控制系统&#xff0c;Git为开发者提供了强大的源码管理能力。通过Git&#xff0c;您可以轻松追踪代码变更、管理不同版本&#xff0c;并与其他开发…

使用React和Vite构建一个AirBnb Experiences克隆网站

这一篇文章中&#xff0c;我会教你如何做一个AirBnb Experiences的克隆网站。主要涵盖React中Props的使用。 克隆网站最终呈现的效果&#xff1a; 1. 使用vite构建基础框架 npm create vitelatestcd airbnb-project npm install npm run dev2. 构建网站的3个部分 网站从上…

LC68----222. 完全二叉树的节点个数(java版)---树

1. 题目描述 完全二叉树的节点个数 给你一棵 完全二叉树 的根节点 root &#xff0c;求出该树的节点个数。 完全二叉树 的定义如下&#xff1a;在完全二叉树中&#xff0c;除了最底层节点可能没填满外&#xff0c;其余每层节点数都达到最大值&#xff0c;并且最下面一层的节点…

206面试题(71~80)

208道Java面试题 文章目录 **208道Java面试题** **71. 如何避免 SQL 注入&#xff1f;****72. 什么是 XSS 攻击&#xff0c;如何避免&#xff1f;****73. 什么是 CSRF 攻击&#xff0c;如何避免&#xff1f;****74. throw 和 throws 的区别&#xff1f;****75. final、finally、…

快速安装mysql5.7.44

参考文档&#xff1a; Windows系统上安装MySQL 5.7步骤&#xff08;实测可行&#xff09;_mysql5.7 windows-CSDN博客 MySQL 5.7压缩包安装图文教程(超详细)_Mysql_脚本之家 关键点&#xff1a; 参数文件内容参考&#xff1a; ALTER USER rootlocalhost IDENTIFIED WITH mys…

大数据新视界 -- 大数据大厂之 Impala 性能提升:高级执行计划优化实战案例(下)(18/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

数字经济新时代,高校数字经济专业人才培养如何与产业对接?

一、数字经济发展及人才需求 &#xff08;一&#xff09;数字经济蓬勃发展 数字经济已成为驱动中国经济实现发展的新引擎&#xff0c;据中国信通院数据&#xff0c;2023年&#xff0c;我国数字经济规模达到53.9万亿元&#xff0c;数字经济占GDP比重达到42.8&#xff05;&#x…

【SpringBoot】21 @Async异步任务线程池的隔离

Git仓库 https://gitee.com/Lin_DH/system 介绍 线程池隔离&#xff1a;指一种通过为每个服务提供独立的线程池来隔离服务之间的资源和执行环境的做法。 为什么需要线程池隔离&#xff1f; 资源隔离&#xff0c;每个服务都有独立的线程池&#xff0c;可以避免由于某个服务的…

Python进行GRPC和Dubbo协议的高级测试

在微服务架构日益流行的今天&#xff0c;分布式系统的复杂性不断增加。GRPC 和 Dubbo 协议作为当今互联网行业中常见的高性能通信协议&#xff0c;已经成为服务之间交互的核心。然而&#xff0c;随着服务调用层次的不断增加&#xff0c;如何有效地测试这两种协议&#xff0c;确…

【启明智显分享】5G CPE为什么适合应用在连锁店中?

连锁门店需要5G CPE来满足其日益增长的网络需求&#xff0c;提升整体运营效率和竞争力。那么为什么5G CPE适合连锁店应用呢&#xff0c;小编为此做了整理&#xff0c;主要是基于以下几个方面的原因&#xff1a; 一、高效稳定的网络连接 1、高速数据传输&#xff1a; 5G CPE能…

私域运营流程框架

蝴蝶模型的作用主要体现在以下几点&#xff1a; 1. 提供清晰的运营思路&#xff1a;使运营人员能够全面、系统地规划和执行私域运营策略&#xff0c;避免盲目和混乱。 2. 实现精准营销&#xff1a;通过分层分类&#xff0c;能够针对不同用户群体制定个性化的营销策略&#xff0…

Python中的面向对象编程,类,对象,封装,继承,多态

一、面向对象编程 1.面向过程和面向对象 面向过程和面向对象都是一种编程方式&#xff0c;只不过再设计上有区别。 面向过程 C语言 细分成每一个过程 优点&#xff1a;简单直观、性能高效、代码简洁。 缺点&#xff1a;不易维护、不易扩展、代码重用性低。 面向对象 p…

【MongoDB】MongoDB的集群,部署架构,OptLog,集群优化等详解

文章目录 一、引入复制集的原因二、复制集成员&#xff08;一&#xff09;基本成员&#xff08;二&#xff09;主节点&#xff08;Primary&#xff09;细化成员 三、复制集常见部署架构&#xff08;一&#xff09;基础三节点&#xff08;二&#xff09;跨数据中心 四、复制集保…

万字长文串烧LLM大模型技术原理

导读 导读对Llama 3大型语言模型技术的一次全面概述&#xff0c;涵盖了预训练、后训练及推理阶段的关键技术&#xff0c;包括数据处理、量化方法&#xff08;如INT8和FP8量化&#xff09;、以及如何通过微调提升模型效率和准确性等方面的内容。 0 开始之前 本文从Llama 3报告…

网络工程师--端口隔离技术

端口隔离基本原理&#xff1a; 同一VLAN隔离组内的用户不能进行二次通信 不同隔离组内的用户可正常通信 未划分VLAN隔离的用户也可与VLAN隔离组内的用户正常通信 VLAN隔离组分为两种模式&#xff1a; 二层隔离三层互通 二三层均隔离 命令&#xff1a; 进入要加入隔离组的…

基于SSM花卉商城设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…

智慧选矿流程可视化平台

通过图扑可视化搭建的智慧选矿平台为选矿过程提供直观监控与优化方案。实现对生产效率、资源消耗和设备状态的动态分析&#xff0c;优化管理流程&#xff0c;提高矿业生产的智能化水平和决策精准度。

Java程序员从阿里、京东、美团面试回来,这些面试题你会吗?

最近有很多朋友去目前主流的大型互联网公司面试&#xff08;阿里巴巴、京东、美团、滴滴&#xff09;&#xff0c;面试回来之后会发给我一些面试题。有些朋友轻松过关&#xff0c;拿到offer&#xff0c;但是有一些是来询问我答案的。 其实本来真的没打算写这篇文章&#xff0c…