当前位置: 首页 > news >正文

数据结构和算法基础(一)

文章目录

    • 链表反转
    • 链表合并
    • 删除链表倒数第 n 个结点
    • 找链表的中间结点
    • 链表中环的检测
    • 排序算法
    • 递归

趁空闲时间刷一遍极客时间上王争的《数据结构与算法之美》课程,个人觉得写的很好,每章节由浅入深且从基础到引入设计类问题,如果写过很多代码想要进行架构设计转型时再回头看这些基础知识还蛮有趣的,以下纪录下随着课程走的部分实现代码和思考;
内容主要是笔记和代码,注:手写一遍代码是有必要的;

链表反转

单链表反转

class ListNode {  int val;  ListNode next;  ListNode(int val) {  this.val = val;  this.next = null;  }  
public ListNode reverseList(ListNode head) {  ListNode prev = null;  ListNode curr = head;  while (curr != null) {  ListNode nextTemp = curr.next;  // 临时保存下一个节点  curr.next = prev;               // 反转当前节点的指针  prev = curr;                    // 将前一个节点移动到当前节点  curr = nextTemp;                // 将当前节点移动到下一个节点  }  return prev;  // prev 最后会指向新的头节点  }  
}

链表合并

两个有序的链表合并,用到了哨兵dummy这个指针记录

class ListNode {  int val;  ListNode next;  ListNode(int val) {  this.val = val;  this.next = null;  }  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  // 创建一个哨兵节点,方便处理边界情况  ListNode dummy = new ListNode(0);  ListNode curr = dummy;  // 使用两个指针分别遍历两个链表  while (l1 != null && l2 != null) {  if (l1.val <= l2.val) {  curr.next = l1;  l1 = l1.next;  } else {  curr.next = l2;  l2 = l2.next;  }  curr = curr.next;  }  // 处理剩余节点(只能有一个链表还有剩余节点)  if (l1 != null) {  curr.next = l1;  } else {  curr.next = l2;  }  }
}

删除链表倒数第 n 个结点

使用快慢指针,快慢指针在解很多链表题目中都有体现

class ListNode {  int val;  ListNode next;    ListNode(int val) {  this.val = val;  this.next = null;  }  public ListNode removeNthFromEnd(ListNode head, int n) {  // 创建一个哨兵节点,简化头节点被删除的情况  ListNode dummy = new ListNode(0);  dummy.next = head;// 初始化快慢指针  ListNode fast = dummy;  ListNode slow = dummy;  // 先将快指针向前移动 n+1 步  for (int i = 0; i <= n; i++) {  fast = fast.next;  }    // 然后同时移动快慢指针,直到快指针到达链表末尾  while (fast != null) {  fast = fast.next;  slow = slow.next;  }    // 此时慢指针指向的节点的下一个节点就是要删除的节点  slow.next = slow.next.next;    // 返回头节点(注意是哨兵节点的下一个节点)  return dummy.next;  }    
}

找链表的中间结点

使用快慢指针来实现,快指针每次移动2步,而慢指针每次移动1步。当快指针到达链表末尾时,慢指针将恰好位于链表的中间。

class ListNode {  int val;  ListNode next;  ListNode(int val) {  this.val = val;  this.next = null;  }  public ListNode findMiddle(ListNode head) {  // 初始化快慢指针  ListNode slow = head;  ListNode fast = head;  // 快指针每次移动两步,慢指针每次移动一步  while (fast != null && fast.next != null) {  slow = slow.next;  // 慢指针移动一步  fast = fast.next.next;  // 快指针移动两步  }  // 当快指针到达链表末尾时,慢指针指向中间节点  return slow;  } 
}

链表中环的检测

快慢指针进行遍历,如果快慢指针不相遇说明没有环

class ListNode {  int val;  ListNode next;ListNode(int val) {  this.val = val;  this.next = null;  }  public boolean hasCycle(ListNode head) {  if (head == null || head.next == null) {  // 如果链表为空或只有一个节点,则不可能有环  return false;  }   ListNode slow = head;  ListNode fast = head;// 快慢指针开始移动,直到它们相遇或快指针到达链表末尾  while (fast != null && fast.next != null) {  slow = slow.next;          // 慢指针每次移动一步  fast = fast.next.next;     // 快指针每次移动两步  // 如果快慢指针相遇,说明链表中存在环  if (slow == fast) {  return true;  }  }// 快指针到达链表末尾,说明链表中没有环  return false;  }  
}

排序算法

常用的冒泡、选择、插入、归并、快速算法,手写很重要,写出来会发现即使是一个小的改动对于程序的消耗来说都有所差别;
关于排序的算法还可以参照:https://mp.weixin.qq.com/s/HQg3BzzQfJXcWyltsgOfCQ
在要求高效的很多基础框架代码中都是用了快速排序(递归思路)

// 冒泡排序  
void bubbleSort(int[] arr) {  int n = arr.length;  for (int i = 0; i < n - 1; i++) {  for (int j = 0; j < n - i - 1; j++) {  if (arr[j] > arr[j + 1]) {  // 交换arr[j]和arr[j + 1]  int temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = temp;  }  }  }  
}  // 选择排序  
void selectionSort(int[] arr) {  int n = arr.length;  for (int i = 0; i < n - 1; i++) {  int minIdx = i;  for (int j = i + 1; j < n; j++) {  if (arr[j] < arr[minIdx]) {  minIdx = j;  }  }  // 交换arr[i]和arr[minIdx]  int temp = arr[minIdx];  arr[minIdx] = arr[i];  arr[i] = temp;  }  
}  // 插入排序  
void insertionSort(int[] arr) {  int n = arr.length;  for (int i = 1; i < n; i++) {  int key = arr[i];  int j = i - 1;  // 将arr[i]插入到已排序部分arr[0..i-1]  while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  j = j - 1;  }  arr[j + 1] = key;  }  
} 
// 归并排序  
void mergeSort(int[] arr, int left, int right) {  if (left < right) {  int mid = left + (right - left) / 2;  // 递归排序两个子数组  mergeSort(arr, left, mid);  mergeSort(arr, mid + 1, right);  // 合并两个已排序的子数组  merge(arr, left, mid, right);  }  
}  
void merge(int[] arr, int left, int mid, int right) {  int n1 = mid - left + 1;  int n2 = right - mid;  int[] L = new int[n1];  int[] R = new int[n2];  for (int i = 0; i < n1; i++) L[i] = arr[left + i];  for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];  int i = 0, j = 0;  int k = left;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  } else {  arr[k] = R[j];  j++;  }  k++;  }  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  
}    
// 快速排序  
void quickSort(int[] arr, int low, int high) {  if (low < high) {  int pi = partition(arr, low, high);  // 递归排序两个子数组  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  
}  
int partition(int[] arr, int low, int high) {  int pivot = arr[high];  int i = (low - 1);  for (int j = low; j < high; j++) {  if (arr[j] < pivot) {  i++;  // 交换arr[i]和arr[j]  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  }  // 交换arr[i + 1]和arr[high] (或pivot)  int temp = arr[i + 1];  arr[i + 1] = arr[high];  arr[high] = temp;  return i + 1;  
}

递归

递归是一种分治的思维,不适合人类大脑但天然是计算机的处理方式,人类大脑总是想把事情的步骤想的很清晰,12345每一步骤做什么,但是计算机不是这样的;
递归也存在堆栈溢出和重复计算的问题,专栏中也给了对应的方式,重复计算可以通过缓存来解决;

// 上楼梯问题中可以适当增加缓存来消除重复计算
public int f(int n) {if (n == 1) return 1;if (n == 2) return 2;// hasSolvedList 可以理解成一个 Map,key 是 n,value 是 f(n)if (hasSolvedList.containsKey(n)) {return hasSovledList.get(n);}int ret = f(n-1) + f(n-2);hasSovledList.put(n, ret);return ret;
}

相关文章:

数据结构和算法基础(一)

文章目录 链表反转链表合并删除链表倒数第 n 个结点找链表的中间结点链表中环的检测排序算法递归 趁空闲时间刷一遍极客时间上王争的《数据结构与算法之美》课程&#xff0c;个人觉得写的很好&#xff0c;每章节由浅入深且从基础到引入设计类问题&#xff0c;如果写过很多代码想…...

【超长好文】网络安全从业者面试指南

文章为笔者偶然看到的github项目《网络安全面试指南》&#xff0c;作者FeeiCN&#xff0c;读完内容深感作者的用心&#xff0c;尽管一些观点因为时间原因与当下行情存在差异&#xff0c;但仍旧值得大家参考&#xff0c;希望能给大家在这行业寒冬带来一些启发&#xff0c;愿正在…...

基于大数据的高校新生数据可视化分析系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…...

【cache】浅析四种常用的缓存淘汰算法 FIFO/LRU/LFU/W-TinyLFU

本文浅析淘汰策略与工作中结合使用、选取&#xff0c;并非针对算法本身如何实现的 文章目录 FIFOLFULRUW-TinyLFU实践与优化监控与调整 FIFO first input first output &#xff0c; 先进先出&#xff0c;即最早存入的元素最先取出&#xff0c; 典型数据结构代表&#xff1a;…...

STM32的DMA技术介绍

DMA&#xff08;Direct Memory Access&#xff0c;直接内存访问&#xff09; 是一种允许外设直接与系统内存进行数据传输&#xff0c;而无需经过CPU的技术。在STM32微控制器中&#xff0c;DMA技术极大地提高了数据传输效率&#xff0c;降低了CPU的负担&#xff0c;从而提升系统…...

C++11 多线程编程-小白零基础到手撕线程池

提示&#xff1a;文章 文章目录 前言一、背景二、 2.1 2.2 总结 前言 前期疑问&#xff1a; 本文目标&#xff1a; 一、背景 来源于b站视频 C11 多线程编程-小白零基础到手撕线程池 学习来源&#xff1a;https://www.bilibili.com/video/BV1d841117SH/?p2&spm_id_f…...

智源研究院与百度达成战略合作 共建AI产研协同生态

2024年9月24日&#xff0c;北京智源人工智能研究院&#xff08;简称“智源研究院”&#xff09;与北京百度网讯科技有限公司&#xff08;简称“百度”&#xff09;正式签署战略合作协议&#xff0c;双方将充分发挥互补优势&#xff0c;在大模型等领域展开深度合作&#xff0c;共…...

Flask-SQLAlchemy:在Flask应用中优雅地操作数据库

在Python的Web开发领域&#xff0c;Flask是一个备受欢迎的轻量级Web框架&#xff0c;它以简洁、灵活而著称。而当我们需要在Flask应用中与数据库进行交互时&#xff0c;Flask-SQLAlchemy就成为了一个强大而便捷的工具。它将Flask的简洁性与SQLAlchemy的强大数据库抽象能力完美结…...

智能巡检机器人 数据库

智能巡检机器人AI智能识别。无需人工。只需后台监控结果即可&#xff01;...

Spring AOP异步操作实现

在Spring框架中&#xff0c;AOP&#xff08;面向切面编程&#xff09;提供了一种非常灵活的方式来增强应用程序的功能。异步操作是现代应用程序中常见的需求&#xff0c;尤其是在处理耗时任务时&#xff0c;它可以帮助我们提高应用程序的响应性和吞吐量。Spring提供了一种简单的…...

【2006.07】UMLS工具——MetaMap原理深度解析

文献&#xff1a;《MetaMap: Mapping Text to the UMLS Metathesaurus》2006 年 7 月 14 日 https://lhncbc.nlm.nih.gov/ii/information/Papers/metamap06.pdf MetaMap&#xff1a;将文本映射到 UMLS 元数据库 总结 解决的问题 自动概念映射问题&#xff1a;解决如何将文本…...

ros2 colcon build 构建后,install中的local_setup.bash 和setup.bash有什么区别

功能概述 在 ROS2 中&#xff0c;colcon build是用于构建软件包的工具。构建完成后会生成install文件夹&#xff0c;其中的setup.bash和local_setup.bash文件都与环境设置相关&#xff0c;但存在一些区别。setup.bash 作用范围 setup.bash文件用于设置整个工作空间的环境变量。…...

Thymeleaf基础语法

Thymeleaf 是一种用于 Web 和非 Web 环境的现代服务器端 Java 模板引擎。它能够处理 HTML、XML、JavaScript、CSS 甚至纯文本。以下是 Thymeleaf 的一些基础语法&#xff1a; 1. 变量表达式 <!-- 显示变量的值 --> <p th:text"${name}">Default Name&l…...

spring cloud alibaba学习路线

以下是一条学习Spring Cloud Alibaba的路线&#xff1a; 一、基础前置知识 1. Java基础 熟练掌握Java语言特性&#xff0c;包括面向对象编程、集合框架、多线程等知识。 2. Spring和Spring Boot基础深入理解Spring框架&#xff0c;如依赖注入&#xff08;DI&#xff09;、控…...

基于 Seq2Seq 的中英文翻译项目(pytorch)

项目简介 本项目旨在使用 PyTorch 构建一个基于 Seq2Seq(编码器-解码器架构)的中英文翻译模型。我们将使用双语句子对的数据进行训练,最终实现一个能够将英文句子翻译为中文的模型。项目的主要步骤包括: 数据预处理:从数据集中提取英文和中文句子,并进行初步清洗和保存。…...

部标主动安全(ADAS+DMS)对接说明

1.前言 上一篇介绍了部标&#xff08;JT/T1078&#xff09;流媒体对接说明&#xff0c;这里说一下如何对接主动安全附件服务器。 流媒体的对接主要牵扯到4个方面&#xff1a; &#xff08;1&#xff09;平台端&#xff1a;业务端系统&#xff0c;包含前端呈现界面。 &#x…...

C++ STL(1)迭代器

文章目录 一、迭代器详解1、迭代器的定义与功能2、迭代器类型3、示例4、迭代器失效4.1、vector 迭代器失效分析4.2、list 迭代器失效分析4.3、set 与 map 迭代器失效分析 5、总结 前言&#xff1a; 在C标准模板库&#xff08;STL&#xff09;中&#xff0c;迭代器是一个核心概念…...

uview表单校验不生效问题

最近几次使用发现有时候会不生效&#xff0c;具体还没排查出来什么原因&#xff0c;先记录一下解决使用方法 <u--formlabelPosition"top"labelWidth"auto":model"form":rules"rules"ref"uForm" ><view class"…...

前端开发设计模式——单例模式

目录 一、单例模式的定义和特点&#xff1a; 1.定义&#xff1a; 2.特点&#xff1a; 二、单例模式的实现方式&#xff1a; 1.立即执行函数结合闭包实现&#xff1a; 2.ES6类实现&#xff1a; 三、单例模式的应用场景 1.全局状态管理&#xff1a; 2.日志记录器&#xff1a; …...

行情叠加量化,占据市场先机!

A股久违的3000点&#xff0c;最近都没有更新&#xff0c;现在终于对我们的市场又来点信息。相信在座的朋友这几天都是喜笑颜开&#xff0c;对A股又充满信心。当前行情好起来了&#xff0c;很多朋友又开始重回市场&#xff0c;研究股票学习量化&#xff0c;今天我们给大家重温下…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...