【Java算法题】剑指offer_01数据结构

前言

刷题链接：
https://www.nowcoder.com/exam/oj/ta?page=2&tpId=13&type=265

1. 链表

JZ24 反转链表

[图片]

思路：基本操作，如下所示。
[图片]
[图片]

[图片]

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;

        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

JZ6 从尾到头打印链表

[图片]

思路：

  1. 反转链表
  2. 添加元素至数组
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
        ArrayList<Integer> arr = new ArrayList<Integer>();

        // 1. 链表不为空，则反转链表
        if(listNode!=null){
            listNode = ReverseList(listNode);
            // 2. 添加元素到ArrayList
            ListNode cur = listNode;
            while(cur!=null){
                arr.add(cur.val);
                cur = cur.next;
            }
            return arr;
        }
        return arr; // 空链表返回空ArrayList
    }
    public ListNode ReverseList(ListNode head){ //反转链表
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = cur.next;

        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

JZ25 合并两个排序的链表

[图片]

[图片]

思路：看代码很清楚，利用新的lsit存排序后的链表，小的先存。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode list = new ListNode(0);
        ListNode l = list;
        if(list1 == null || list2 == null){
            return list1 != null?list1:list2;
        }
        while(list1!=null && list2!=null){
            if(list1.val<=list2.val){
                l.next = list1;
                list1=list1.next;
            }else{
                l.next = list2;
                list2=list2.next;
            }
            l=l.next;
        }
        if(list1!=null){
            l.next = list1; 
        }
        if(list2!=null){
            l.next = list2;
        }
        return list.next;
    }
}

JZ52 两个链表的第一个公共节点

[图片]

[图片]

思路：Y字形链表，以相同的速度遍历两条链表最终总会相遇。（注意：当遍历链表1结束，将指针指向链表2的头。）

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1=pHead1, p2=pHead2;
        while(p1!=p2){
            p1 = (p1==null)?pHead2:p1.next;
            p2 = (p2==null)?pHead1:p2.next;
        }
        return p1;
    }
}

JZ23 链表中环的入口结点

[图片]

[图片]

思路：
快慢指针，快指针走两步，慢指针走一步。
[图片]

  1. 判断是否有环；
  2. 有环则将slow指针指向头，fast从相遇点出发，二者将在入环点相遇。
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){ //判断有没有环
                break;
            }
        }
        if(fast.next==null || fast.next.next==null){ //无环返回null
            return null;
        }
        slow = pHead;
        while (slow != fast) { //找到环入口
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

JZ22 链表中倒数最后k个结点

[图片]

[图片]

思路：快慢指针，先让一个指针走k步，后面同步一个个走，快指针走到末尾的时慢指针刚好指向末尾第k个节点。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead == null){
            return null;
        }
        ListNode slow = pHead;
        ListNode fast = pHead;

        while(k-->0){
            if(fast == null)
                return null;
            fast = fast.next; //先走k步
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        
        return slow;
    }
}

JZ35 复杂链表的复制

[图片]

[图片]

思路：参考这篇博客 https://blog.csdn.net/qq_43676757/article/details/106253305

使用常规方法一，将步骤分成三个：

  1. 复制节点
    [图片]

  2. 复制random节点给已拷贝节点
    [图片]

  3. 拆分链表
    [图片]

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null)
            return null;
        
        RandomListNode cur = pHead;
        //遍历原始链表，复制
        while(cur!=null){
            //拷贝节点
            RandomListNode temp = new RandomListNode(cur.label);
            //添加新节点到原始链表当前节点后面
            temp.next=cur.next;
            cur.next=temp;
            cur=temp.next;
        }

        //连接新链表的random节点
        cur = pHead;//回到头节点
        RandomListNode temp = pHead.next;
        while(cur!=null){
            if(cur.random==null){
                temp.random=null;
            }else{
                temp.random = cur.random.next; //新链表的random为cur的random下一个
            }
            cur = cur.next.next;
            if(temp.next!=null){
                temp=temp.next.next;
            }
        }

        //拆分链表
        cur = pHead;
        RandomListNode res = pHead.next;
        temp = res;
        while(cur!=null){
            cur.next=cur.next.next;
            cur=cur.next;
            if(temp.next!=null){
                temp.next = temp.next.next;
            }
            temp = temp.next;
        }
        return res;
    }
}

JZ76 删除链表中重复的结点

[图片]

[图片]

思路：需要前一个节点、当前节点和下一节点的信息。在表头添加一个节点作为pre，当前节点和下一节点相同的时候，当前指针往下移动；当数值不同的时才退出循环，将pre.next指向下一个节点。

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        // 链表为空或者只有一个节点
        if(pHead == null || pHead.next==null){
            return pHead;
        }

        ListNode res = new ListNode(-1); //表头加一个节点
        res.next = pHead;
        ListNode pre = res;
        ListNode cur = pHead;
        
        while(cur!=null && cur.next!=null){
            if(cur.val == cur.next.val){ //相邻的节点值相同
                int tmp = cur.val;
                while(cur.next!=null && cur.next.val==tmp){
                    cur = cur.next; //跳过相同的节点    
                }
                //退出循环时，cur指向最后一个重复值
                cur = cur.next;
                pre.next = cur;
            }else{
                pre=cur;
                cur=cur.next;
            }
        }
        return res.next;
    }
}

JZ18 删除链表的节点

[图片]

思路：直观的想法就是记录下前一个节点，当搜索到匹配的数值，将前一个节点的next直接指向当前节点的下一个节点，达到删除当前节点的目的。特殊情况是表头节点满足条件！

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    public ListNode deleteNode (ListNode head, int val) {
        // write code here
        //1. 空则返回null
        if(head == null){ 
            return null;
        }
        ListNode pre = head; //pre记录当前节点前一个节点
        ListNode cur = head.next;
        //2.第一个元素就满足val，删除第一个元素
        if(pre!=null&&pre.val==val){
            pre=pre.next;
            return pre;
        }
        //3.第二个元素开始匹配
        while(cur!=null){
            if(cur.val==val){
                pre.next = cur.next;
                cur.next = null;
                break;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return head;
    }
}

更简洁的代码（来源牛客网题解）：在单链表前再加一个节点( ListNode res = new ListNode(0); res.next = head; )，返回的时候记得去掉。

import java.util.*;
public class Solution {
    public ListNode deleteNode (ListNode head, int val) {
        //加入一个头节点
        ListNode res = new ListNode(0);
        res.next = head;
        //前序节点
        ListNode pre = res;
        //当前节点
        ListNode cur = head;
        //遍历链表
        while(cur != null){
            //找到目标节点
            if(cur.val == val){
                //断开连接
                pre.next = cur.next;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        //返回去掉头节点
        return res.next;
    }
}

2. 树

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

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

相关文章

ad18学习笔记一

ad18学习笔记一

如何自学altium designer如何自学altium designer&#xff1f; - 知乎如何自学altium designer 这里面有ad官方推荐的b站的视频&#xff1a;可以直接去b站关注ad官方账号 AltiumChina&#xff0c;它本身就发布了很多实用教程。 在知乎的这个界面也有Altium Designer Ver18_官…
阅读更多...
c++ 11标准模板（STL） std::set(六）

c++ 11标准模板（STL） std::set(六）

定义于头文件 <set> template< class Key, class Compare std::less<Key>, class Allocator std::allocator<Key> > class set;(1)namespace pmr { template <class Key, class Compare std::less<Key>> using se…
阅读更多...
如何使用SCQA模型提高表达能力

如何使用SCQA模型提高表达能力

SCQA架构是“结构化表达”工具。 一、什么是“SCQA架构”&#xff1f;‍ S&#xff08;Situation&#xff09;情景——由熟悉的情境或事实引入 C&#xff08;Complication&#xff09;冲突——指出实际面临的困境或冲突 Q&#xff08;Question&#xff09;疑问——你如何分析…
阅读更多...
文本三剑客正则表达式3

文本三剑客正则表达式3

文章目录 文本三剑客&正则表达式31 awk工作原理2 awk的基本格式及其内置变量2.1 基本格式2.2 内置变量2.3 示例2.3.1 直接打印所有内容2.3.2 取每一行的第一列2.3.3 打印行号&#xff0c;及所有内容2.3.4 打印第三行2.3.5 打印2-4行2.3.6 打印第2行和第4行2.3.7 用正则表达…
阅读更多...
基于harbor安装私有镜像仓库

基于harbor安装私有镜像仓库

目录 Harbor介绍 Harbor安装 下载完成后&#xff0c;在压缩包解压到/usr/local目录下&#xff1a; 修改Harbor配置文件 推送本地镜像到harbor上 1、给本地镜像打一个标签 2、 设置docker的daemon.json 3、重启docker 4、使用docker登录harbor 5、把本地的镜像push到harbor…
阅读更多...
银豆信息张雪灿：钻石级合作伙伴的增长秘诀

银豆信息张雪灿：钻石级合作伙伴的增长秘诀

编者按&#xff1a; 杭州银豆信息技术有限公司&#xff08;简称“银豆”&#xff09;&#xff0c;是一家专注于云计算服务的高科技企业&#xff0c;目前已为2000家企业级客户提供了专业的行业解决方案, 与人民网、光大银行、长安汽车金融、vivo金融、浙江省农科院、淄博市大数…
阅读更多...
MediaPipe虹膜检测：实时虹膜跟踪和深度估计

MediaPipe虹膜检测：实时虹膜跟踪和深度估计

包括计算摄影（例如，人像模式和闪光反射）和增强现实效果（例如，虚拟化身）在内的大量实际应用都依赖于通过跟踪虹膜来估计眼睛位置。一旦获得了准确的光圈跟踪，我们就可以确定从相机到用户的公制距离，而无需使用专用的深度传感器。反过来，这可以改善各种用例，从计算摄影…
阅读更多...
机器学习之SVM分类器介绍——核函数、SVM分类器的使用

机器学习之SVM分类器介绍——核函数、SVM分类器的使用

系类文章目录 机器学习算法——KD树算法介绍以及案例介绍 机器学习的一些常见算法介绍【线性回归&#xff0c;岭回归&#xff0c;套索回归&#xff0c;弹性网络】 文章目录 一、SVM支持向量机介绍 1.1、SVM介绍 1.2、几种核函数简介 a、sigmoid核函数 b、非线性SVM与核函…
阅读更多...
从内网护卫到零信任尖兵：腾讯iOA炼成记

从内网护卫到零信任尖兵：腾讯iOA炼成记

腾讯既是企业产品的服务商又是使用者&#xff0c;很多产品最原始的出发点最早只是为了解决腾讯自身某一个需求&#xff0c;经过不断地发展完善和业务场景锤炼&#xff0c;最终进化成一个成熟的企服产品。本系列文章讲述的是这样一组Made in Tencent故事&#xff0c;这是系列的第…
阅读更多...
Word批量更改图片环绕方式与=尺寸大小

Word批量更改图片环绕方式与=尺寸大小

前提&#xff1a;一份Word文档里面有100张图片&#xff0c;有大有小&#xff0c;需要将100张图片更改为统一大小&#xff0c;宽度与高度均为5厘米&#xff0c;同时环绕方式也需要改成四周型。 默认Word图片的默认环绕方式为嵌入型&#xff0c;需要统一更改为四周型&#xff0c;…
阅读更多...
linux 安装 maven 3.8 版本

linux 安装 maven 3.8 版本

文章目录 1&#xff1a;maven 仓库官网 2、下载安装包 3、使用&#xff1a;Xftp 上传到你想放的目录 4、解压文件 ​编辑 5、配置环境变量 ​编辑 6、刷新 /etc/profile 文件 7、查看maven 版本 1&#xff1a;maven 仓库官网 Maven – Download Apache Mavenhttps://mave…
阅读更多...
Java 基础进阶篇（十五）：IO 流总结（全网最全面）

Java 基础进阶篇（十五）：IO 流总结（全网最全面）

文章目录 前置内容&#xff1a;字符集一、IO 流概述二、字节流2.1 文件字节输入流 FileInputStream2.1.1 案例&#xff1a;每次读取一个字节2.1.2 案例&#xff1a;每次读取一个字节数组2.1.3 案例&#xff1a;读取文件的全部字节 2.2 文件字节输出流 FileOutputStream2.3 文件…
阅读更多...
使用Docker Dockerfile构建php LNMP集成开发环境，并运行Thinkphp5

使用Docker Dockerfile构建php LNMP集成开发环境，并运行Thinkphp5

宿主机环境 系统&#xff1a;MAC、Windows10 Docker版本&#xff1a;Docker version 23.0.5 Docker Desktop:Dockerdesktop官方地址 前言 这篇主要介绍如何在Mac、Windows10使用docker搭建LNMP集成开发环境。下面我会写Dockerfile编译安装Nginxphp基础环境。mysql、redis基…
阅读更多...
pynvme操作流程

pynvme操作流程

如下操作pynvme运行在fedora上&#xff0c;在其他操作系统尚未做尝试。 步骤一&#xff1a;检查本地windows是否安装ssh 检查方式&#xff1a;windows本地打开windows powershell&#xff0c;输入ssh&#xff0c;若打印usage &#xff1a;ssh等一些信息&#xff0c;则已安装s…
阅读更多...
8.防火墙

8.防火墙

文章目录 防火墙iptables防火墙介绍基础操作高级操作通用匹配隐含匹配端口匹配&#xff1a;--sport 源端口、--dport 目的端口 TCP标志位匹配&#xff1a;--tcp-flags TCP标志位ICMP类型匹配&#xff1a;--icmp-type ICMP类型 显式匹配多端口匹配IP范围匹配&#xff1a;-m ipra…
阅读更多...
基于αβ剪枝算法的五子棋

基于αβ剪枝算法的五子棋

访问【WRITE-BUG数字空间】_[内附完整源码和文档] 五子棋是世界智力运动会竞技项目之一&#xff0c;是一种两人对弈的纯策略型棋类游戏&#xff0c;是世界智力运动会竞技项目之一&#xff0c;通常双方分别使用黑白两色的棋子&#xff0c;下在棋盘直线与横线的交叉点上&#xf…
阅读更多...
记录：自回归 模型在记忆 全随机序列 的潜变量 统计量爆炸现象

记录：自回归 模型在记忆 全随机序列 的潜变量 统计量爆炸现象

只是一个记录 8层12头512维度的 GPT 模型&#xff0c;使用它来记忆 10000 条 512长度 的无序序列&#xff0c;vocab_size 为100。 模型要自回归生成这些序列&#xff0c;不可能依赖局部推理&#xff0c;必须依赖全局视野&#xff0c;即记住前面的序列。 然后统计 最后一个no…
阅读更多...
EasyRecovery16电脑硬盘数据恢复软件功能讲解

EasyRecovery16电脑硬盘数据恢复软件功能讲解

硬盘是很常见的存储数据的设备&#xff0c;硬盘中很多重要的数据一旦丢失会很麻烦&#xff0c;不过现在有硬盘数据恢复软件可以自行在家恢复数据。今天的文章就带大家来看看硬盘恢复数据的软件EasyRecovery。 EasyRecovery 是一款专业的数据恢复软件&#xff0c;支持恢复不同存…
阅读更多...
nginx实现正向代理

nginx实现正向代理

1.下载nginx nginx: download 选择自己需要的版版本下载下来 2.解压文件修改ngixn.conf配置文件 events { worker_connections 1024; } http { include mime.types; default_type application/octet-stream; sendfile on; keepalive_timeout…
阅读更多...
VSAN 7 安装部署指南（一）

VSAN 7 安装部署指南（一）

本文使用三台服务器安装ESXI 7.0 &#xff0c;并在其中一台ESXI中安装vCenter 7.0。本环境中最终在VMware Workstation虚拟机中做的嵌套虚拟化。每台虚拟机配置两块网卡&#xff0c;一块网卡桥接&#xff0c;一块NAT。三块硬盘&#xff0c;一块100GB作为系统盘&#xff0c;一块…
阅读更多...
最新文章

Copyright @ 2022~2023