文章目录

    • 递归
      • TestRecursiveListRemoveNode
      • TestRecursiveListRemoveNode2
    • 循环
      • TestWhileLoopListRemoveNode
      • TestWhileLoopListRemoveNode2

递归

关键理解这几点:
1、求解基本问题
2、将原问题拆分为小问题,直至基本问题(难点)
3、借助设定的递归函数的语义,解决原问题
(在将原问题拆分成小问题时,可以借助设定的递归函数的语义,把设定的递归函数当作1个已实现的子函数,然后在递归函数中将原问题拆解成小问题,最终解决原问题)

TestRecursiveListRemoveNode

递归的技巧就是:你得先定义这个递归方法的目标功能,然后在递归的实现方法中可以使用这个递归方法,接着组织自己的逻辑,接着找出边界条件,还需要在递归方法实现中调用定义的递归方法,来驱动下一步的执行!!!

  • 实现功能:使用 递归的方式 删除单向链表中指定值的节点
  • 递归的方式将单向链表内容,使用字符串的形式输出

/*** 删除单向链表中指定值的节点*/
public class TestRecursiveListRemoveNode {/*** 单向链表节点*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 组织链表结构// 这里不循环到list.size(),可以减少判断for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}// 2种输出指定头节点的链表的方法// 方法1:把结果值传入,然后不断递归(递归方法无返回值)// 方法2:把控递归方法的含义,在递归方法中处理边界,并使用已定义的递归方法(递归方法有返回值)System.out.println(printAllList1(listNode0));System.out.println(printAllList2(listNode0));// 递归的缺陷:当元素越多的情况下,方法调用栈的深度就深,甚至栈内存溢出ListNode listNode = removeElement(listNode1, 6); // (递归方法有返回值)System.out.println(printAllList1(listNode));System.out.println(printAllList2(listNode));/*输出:6->6->1->2->6->3->4->6->5->6->6->76->6->1->2->6->3->4->6->5->6->6->71->2->3->4->5->71->2->3->4->5->7*/}// 递归的技巧就是:你得先定义这个递归方法的目标功能,然后在递归的实现方法中可以使用这个递归方法,//               接着组织自己的逻辑,接着找出边界条件,还需要在递归方法实现中调用定义的递归方法,来驱动下一步的执行!!!// 先定义当前这个方法的目标功能就是:传入1个链表的头节点,返回1个链表的头节点,并且这个链表头节点的后续节点中都不包含指定的值private static ListNode removeElement(ListNode head, int val) {// (递归的技巧就是:在实现递归的时候,递归方法的下面都是要假设传入的head有可能是第一次传入的,也有可能是后面的递归调用传入的,要有这个意识!!!)// 如果head是null, 则直接返回,因为没有处理的必要了if (head == null) {return null;}// 如果头节点的值就是指定的值,那么去除掉这个头节点,把头节点的下一个节点作为新的头节点,// 将新的头节点传入给定义的递归方法,根据定义的递归方法本来含义,其实只要把新的头节点传给这个递归方法就解决了if (head.val == val) {ListNode next = head.next;return removeElement(next, val);}// 至此,说明head头节点不是指定的值// 拿到头节点的下1个节点ListNode next = head.next;// 如果头节点的下1个节点不是空节点if (next != null) {// 如果头节点的下1个节点的值就是目标值,那就让头节点指向下1个节点的下1个节点,// 不过在这里,头节点的下1个节点的下1个节点,仍然需要经过递归方法的处理,所以这里又调用了一遍if (next.val == val) {head.next = removeElement(next.next, val);next.next = null;} else {// 如果头节点的下1个节点的值不是目标值,那就继续调用递归方法正常处理头节点的下1个节点的下1个节点next.next = removeElement(next.next, val);}}// 如果头节点的下1个节点就是空节点,那就直接返回头节点就行了// 如果头节点的下1个节点不是空节点,那经过上面的处理后,这里也直接返回头节点就行了return head;}private static String printAllList2(ListNode head) {// 如果头节点是空的,那就返回空字符串if (head == null) {return "";}// 传过来的头节点必定不为空// 拿到头节点的下1个节点ListNode next = head.next;// 如果头节点的下1个节点为空,那就直接返回这个头节点了if (next == null) {return String.valueOf(head.val);} else {// 如果头节点的下1个节点不为空,那就需要拼接上后面节点对应的结果了,由于当前递归方法的定义就是输出指定节点的链表,所以这里直接调用递归的方法了!return head.val + "->" + printAllList2(next);}}private static String printAllList1(ListNode listNode) {// 先构造结果StringBuilder sb = new StringBuilder();// 递归处理结果(此处,递归方法无返回值)printAllList1(listNode, sb, 0);// 递归处理完成后,返回结果return sb.toString();}// 该递归方法定义是:根据传入的指定节点,将这个节点及这个节点之后的所有节点都处理到sb上,形成 ->{节点值} 的形式private static void printAllList1(ListNode listNode, StringBuilder sb, int count) {// (递归的技巧就是:在实现递归的时候,递归方法的下面都是要假设传入的head有可能是第一次传入的,也有可能是后面的递归调用传入的,要有这个意识!!!)// 传入的节点为空,则不需要处理if (listNode == null) {return;}// 当count为0时,是第一次进入,因此前面不需要->if (count != 0) {sb.append("->");}// 标识是否第一次进入递归方法count++;// 将值设置的sb上sb.append(listNode.val);// 如果listNode还有下1个节点, 则继续处理下1个节点,// 由于我们已经定义的递归方法,正好就是将 这个节点及这个节点之后的所有节点都处理到sb上,形成 ->{节点值} 的形式,// 因此这里又调用了递归方法if (listNode.next != null) {printAllList1(listNode.next, sb, count);}}}

TestRecursiveListRemoveNode2

比上面更简洁。

关键理解这几点:
1、求解基本问题
2、将原问题拆分为小问题,直至基本问题(难点)
3、借助设定的递归函数的语义,解决原问题

public class TestRecursiveListRemoveNode2{/*** 单向链表节点*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = getListNode();System.out.println(printAllList(listNode0));ListNode handledListNode = removeElements(listNode0, 6);System.out.println(printAllList(handledListNode));}public static ListNode removeElements(ListNode head, int val) {if (head != null) {if (head.val == val) {// 由于头节点是给定的值,所以抛弃头节点,此时,这里,借助 定义的递归函数的宏观语义,只需要处理head.next即可返回return removeElements(head.next, val);} else {// 由于头节点不是给定的值,所以对头节点的下1个节点处理,此时,这里 借助定义的递归函数的宏观语义,只需要处理head.next即可返回head.next = removeElements(head.next, val);return head;}}return null;/*// 与上面相同, 但这里更能体现出,在解决原问题的时候,是如何借助设定的递归方法,将原问题拆分成基础问题的if (head == null) {return null;}ListNode res = removeElements(head.next, val);if (head.val == val) {return res;} else {head.next = res;return head;}*//*// 这整的有点高级了,意思和上面是相同的if (head == null) {return null;}head.next = removeElements(head.next, val);return head.val == val ? head.next : head;*/}private static String printAllList(ListNode head) {// 如果头节点是空的,那就返回空字符串if (head == null) {return "";}// 传过来的头节点必定不为空// 拿到头节点的下1个节点ListNode next = head.next;// 如果头节点的下1个节点为空,那就直接返回这个头节点了if (next == null) {return String.valueOf(head.val);} else {// 如果头节点的下1个节点不为空,那就需要拼接上后面节点对应的结果了,由于当前递归方法的定义就是输出指定节点的链表,所以这里直接调用递归的方法了!return head.val + "->" + printAllList(next);}}private static ListNode getListNode() {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 组织链表结构// 这里不循环到list.size(),可以减少判断for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}return listNode0;}}

循环

TestWhileLoopListRemoveNode

  • 实现功能:使用 循环的方式 删除单向链表中指定值的节点
  • 循环的方式将单向链表内容,使用字符串的形式输出
/*** 删除单向链表中指定值的节点*/
public class TestWhileLoopListRemoveNode {/*** 单向链表节点*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 组织链表结构// 这里不循环到list.size(),可以减少判断for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}// 使用循环(规避了递归可能引起的栈内存溢出的问题)System.out.println(printAllList(listNode0));// 使用循环(规避了递归可能引起的栈内存溢出的问题)ListNode node = removeElements(listNode0, 6);System.out.println(printAllList(node));}private static ListNode removeElements(ListNode head, int val) {// 去除可能存在的相连多个指定值的头节点while (head != null && head.val == val) {ListNode next = head.next;head.next = null;head = next; // head向后推移1位,继续循环}if (head == null) {return null;}// 将head值保存到prev,以开启循环处理(循环处理的技巧)ListNode prev = head;while (prev.next != null) {// 拿到prev的下1个节点 nextListNode next = prev.next;if (next.val == val) { // 此处可借助循环移除多个连续相连的指定值的节点prev.next = next.next; // prev指向的下1个节点时,跳过指定值的节点,而指向下1个节点next.next = null;// 此处也继续循环(并且注意此时prev值未变,继续处理prev的下1个节点)} else {// 当prev的next不为指定值的节点时,prev向后推移1位,以继续循环prev = prev.next;}}return head;}private static String printAllList(ListNode head) {if (head == null) {return "";}StringBuilder sb = new StringBuilder();sb.append(head.val);// 将head值保存到prev,以开启循环处理(循环处理的技巧)ListNode prev = head;while (prev.next != null) {sb.append("->" + prev.next.val);prev = prev.next;}return sb.toString();}}

TestWhileLoopListRemoveNode2

  • 实现功能:使用 循环的方式 删除单向链表中指定值的节点(添加虚拟头节点,统一化操作(简化代码))
  • 循环的方式将单向链表内容,使用字符串的形式输出
/*** 删除单向链表中指定值的节点(添加虚拟头节点)*/
public class TestWhileLoopListRemoveNode2 {/*** 单向链表节点*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 组织链表结构// 这里不循环到list.size(),可以减少判断for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}// 使用循环(规避了递归可能引起的栈内存溢出的问题)System.out.println(printAllList(listNode0));// 使用循环(规避了递归可能引起的栈内存溢出的问题)// (添加虚拟头节点技巧)ListNode node = removeElements(listNode0, 6);System.out.println(printAllList(node));}private static ListNode removeElements(ListNode head, int val) {// 添加1个虚拟头节点,来去除对head为空的情况的判断,从而简化代码ListNode dummyNode = new ListNode(null);dummyNode.next = head;// 将head值保存到prev,以开启循环处理(循环处理的技巧)ListNode prev = dummyNode;while (prev.next != null) {// 拿到prev的下1个节点 nextListNode next = prev.next;if (next.val == val) { // 此处可借助循环移除多个连续相连的指定值的节点prev.next = next.next; // 跳过指定值的节点next.next = null;// 此处也继续循环(并且注意此时prev值未变)} else {// 当prev的next不为指定值的节点时,prev向后推移1位,以继续循环prev = prev.next;}}// 返回时,也是返回虚拟头节点的下一个节点return dummyNode.next;}private static String printAllList(ListNode head) {if (head == null) {return "";}StringBuilder sb = new StringBuilder();sb.append(head.val);ListNode prev = head;while (prev.next != null) {sb.append("->" + prev.next.val);prev = prev.next;}return sb.toString();}}

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

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

3D魔方游戏

# 3D魔方游戏 这是一个基于Three.js的3D魔方游戏&#xff0c;支持2到6阶魔方的模拟操作。 ## 功能特点 - 支持2到6阶魔方 - 真实的3D渲染效果 - 鼠标操作控制 - 随机打乱功能 - 提示功能 - 重置功能 ### 安装依赖 bash npm install ### 启动游戏 bash npm start 然…

下载安装 com0com

下载 在 sourceforge 网站下载安装器&#xff1a;下载链接 安装完成后可以在设备管理器中看到默认创建的一对虚拟串口 使用串口调试助手收发 使用串口调试助手分别打开。如下图所示&#xff0c;在端口选择的下拉列表中可以看到刚才在设备管理器中看到的 COM3 和 COM5 分…

C++ 应用软件开发从入门到实战详解

目录 1、引言 2、IDE 开发环境介绍 2.1、Visual Studio 2.2、Qt Creator 3、 C语言特性 3.1、熟悉泛型编程 3.2、了解C/C异常处理 3.3、熟练使用STL容器 3.4、熟悉C11新特性 4、Windows 平台的编程技术与调试技能 4.1、需要掌握的若干编程技术和基础知识 4.2、需…

Python爬虫实战:研究slug相关技术

1. 引言 1.1 研究背景与意义 随着互联网技术的快速发展,网络上的信息量呈爆炸式增长。如何从海量的非结构化数据中提取有价值的信息,成为当前数据科学领域的重要研究方向。网络爬虫作为一种自动化数据采集工具,可以高效地获取网页内容,为数据分析提供丰富的数据来源。 Sl…

人工智能-基础篇-18-什么是RAG(检索增强生成:知识库+向量化技术+大语言模型LLM整合的技术框架)

RAG&#xff08;Retrieval-Augmented Generation&#xff0c;检索增强生成&#xff09;是一种结合外部知识检索与大语言模型&#xff08;LLM&#xff09;生成能力的技术框架&#xff0c;旨在提升生成式AI在问答、内容创作等任务中的准确性、实时性和领域适应性。 1、核心概念 …

CppCon 2018 学习:What do you mean “thread-safe“

什么是“线程安全”&#xff1f; “线程安全”指的是一个函数、方法或代码块能够在多个线程同时执行时&#xff0c;不会出现意外的交互或破坏共享数据&#xff0c;能够安全地运行。 POSIX 对线程安全的定义很清楚&#xff1a; “一个线程安全的函数可以在多个线程中被安全地并…

热方程初边值问题解法

已知公式&#xff1a; u ( x , t ) ∫ − ∞ ∞ G ( x , y , t ) g ( y ) d y . u(x,t)\int_{-\infty}^{\infty}G(x,y,t)g(y)dy. u(x,t)∫−∞∞​G(x,y,t)g(y)dy. &#xff08;1&#xff09; 其中 G ( x , y , t ) 1 2 k π t e − ( x − y ) 2 4 k t G(x,y,t)\frac{1}{2…

怎样理解:source ~/.bash_profile

场景复现 $ source ~/.bash_profileAnalysis 分析 一句话概括 source ~/.bash_profile “在 当前 终端会话里&#xff0c;立刻执行并加载 ~/.bash_profile 中的所有命令&#xff0c;让其中定义的环境变量、函数、alias 等即时生效&#xff0c;而无需重新登录或开新 Shell。…

搜索问答技术概述:基于知识图谱与MRC的创新应用

目录 一、问答系统应用分析 二、搜索问答技术与系统 &#xff08;一&#xff09;需求和信息分析 问答需求类型 多样的数据源 文本组织形态 &#xff08;二&#xff09;主要问答技术介绍 发展和成熟度分析 重点问答技术基础&#xff1a;KBQA和DeepQA KBQA&#xff08;…

TCP数据的发送和接收

本篇文章结合实验对 TCP 数据传输中的重传机制、滑动窗口以及拥塞控制做简要的分析学习。 重传 实验环境 这里使用两台腾讯云服务器&#xff1a;vm-1&#xff08;172.19.0.3&#xff09;和vm-2&#xff08;172.19.0.6&#xff09;。 超时重传 首先 vm-1 作为服务端启动 nc…

python 保存二维数组到本地

Python中保存二维数组有多种方法&#xff0c;以下是常用的几种方式&#xff1a;1. 使用NumPy&#xff08;推荐&#xff09;import numpy as np# 创建二维数组 arr np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])# 保存为.npy文件&#xff08;NumPy专用格式&#xff09; np.save…

LIN总线通讯中从节点波特率同步原理

波特率同步原理&#xff1a;从节点如何通过0x55校准时钟&#xff1f; 一、同步场的核心作用&#xff1a;统一“时间标尺” 在LIN总线中&#xff0c;主节点与从节点各自拥有独立的时钟源&#xff08;如MCU内部RC振荡器&#xff09;&#xff0c;但由于制造工艺差异&#xff0c;…

【Unity笔记02】订阅事件-自动开门

流程 当玩家移动到触发区域的时候&#xff0c;门自动打开 事件系统 using System; using System.Collections; using System.Collections.Generic; using UnityEngine;public class EventSystem : MonoBehaviour {public static EventSystem Instance { get; private set; }…

控制台字符动画

旋转的立方体 #include <cstdint> #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <cstdlib> #include <ctime> #include <thread> using namespace std;float angleX .0f; float a…

基于 PyTorch 的猫狗图像分类实战

基于 PyTorch 的猫狗图像分类实战 项目背景简介 深度学习框架 PyTorch 因其动态计算图和灵活易用性&#xff0c;被广泛应用于图像分类等计算机视觉任务。在入门计算机视觉领域时&#xff0c;常常以手写数字识别&#xff08;MNIST&#xff09;作为 “Hello World”&#xff0c…

SwiftUI 7(iOS 26 / iPadOS 26)中玻璃化标签页的全新玩法

&#x1f378; Liquid Glass 登场&#xff1a;界面设计焕然一新 WWDC25 可谓惊喜连连&#xff0c;其中最引人瞩目的变革之一&#xff0c;莫过于苹果推出的全新跨平台设计语言 —— Liquid Glass&#xff08;液态玻璃&#xff09;。这一设计风格涵盖了从按钮到导航栏&#xff0…

PDF处理控件Spire.PDF教程:在Java中读取PDF,提取文本、图片和表格

在数据驱动的现代开发中&#xff0c;高效处理 PDF 文档已成为 Java 开发者不可或缺的核心能力。无论是处理各类发票扫描件、业务分析报告&#xff0c;还是包含丰富图表的技术文档&#xff0c;掌握 Java 版的 PDF 解析技术都将大幅提升数据处理效率&#xff0c;充分释放文档中的…

跨平台游戏引擎 Axmol-2.7.0 发布

Axmol 2.7.0 版本是一个以错误修复和功能改进为主的次要LTS长期支持版本 &#x1f64f;感谢所有贡献者及财务赞助者&#xff1a;scorewarrior、peterkharitonov、duong、thienphuoc、bingsoo、asnagni、paulocoutinhox 重大变更 Android Studio 最低版本要求升级至 2025.1.1…

XML 笔记

<image src"hue.gif" width"100" height"auto" align"left"/> <br/> 换行 在 XML 中&#xff0c;<![CDATA[ 和 ]]> 用于定义一个 CDATA 节&#xff08;Character Data Section&#xff09;。CDATA 节是用于将一段…

Python实现优雅的目录结构打印工具

Python实现优雅的目录结构打印工具 在软件开发、系统管理和日常工作中&#xff0c;我们经常需要查看和分析目录结构。 工具功能概述 这个DirectoryPrinter类提供了以下功能&#xff1a; 递归打印目录结构可配置是否显示隐藏文件可设置最大递归深度自定义缩进和文件/文件夹符…