首页 > 编程语言 >数据结构与算法(LeetCode) 第二节 链表结构、栈、队列、递归行为、哈希表和有序表

数据结构与算法(LeetCode) 第二节 链表结构、栈、队列、递归行为、哈希表和有序表

时间：2023-10-28 15:11:23浏览次数：31  
标签：head cur int value public 链表 哈希 next LeetCode

一、链表结构

1.单向链表节点结构
public class Node{
	public int value;
    public Node next;
    public Node(int data){
        value=data;
    }
}
2.双向链表节点结构
public class DoubleNode{
    public int value;
    public DoubleNode last;
    public DoubleNode next;
    public DoubleNode(int data){
		value=data;
    }
}
3.单向链表与双向链表最简单的练习
3.1单向链表与双链表如何反转
//单向链表反转
public static Node reverseLinkedList(Node head){
   Node pre =null;
   Node next = null;
    while(head !=null){
		next=head.next;
        head.next=pre;
        pre=head;
        head=next;
    } 
    //返回新的头结点
    return pre;
}
//双向链表反转
public static DoubleNode reverseDoubleList(DoubleNode head){
	DoubleNode pre=null;
    DoubleNode next=null;
    while(head!=null){
		next=head.next;
        head.next=pre;
        head.last=next;
        pre=head;
        head=next;
    }
    //返回头结点
    return pre;
}
3.2把给定值删除
//删除一个单链表中值为num的节点
public static Node removeValue(Node head,int num){
    //判断头部节点需要删多少个
    //如在3-3-3-3-2-2-1链表中，删掉值为3的节点，则需要删掉4个头部节点
	while(head !=null){
    	if(head.value !=num){
         	break;
         }
         head=head.next;
    }
    //head来到第一个不需要删除的位置
    Node pre=head;
    Node cur=head;
    
    while(cur != null){
        //注意：java中会自动释放无法找到的节点，不需要手动释放
        if(cur.value == num){
            pre.next =cur.next;
        }else{
            pre=cur;
        }
        cur= cur.next;
    }
    retuen pre;
}

二、栈和队列

1.逻辑概念

栈：数据先进后出

队列：数据先进先出

2.栈和队列的实际实现

双向链表实现

数组实现

1.使用双向链表实现栈和队列

(1)使用双向链表模拟栈与队列的进出操作

public static class DoubleEndsQueue<T>{
	public Node<T> head;//头指针
    public Node<T> tail;//尾指针
    //如果从头部开始加节点采用以下方法
    public void addFormHead(T value){
        Node<T> cur=new Node<T>(value);
        if(head==null){
            head=cur;
            tail=cur;
        }else{
			cur.next=head;
            head.last=cur;
            head=cur;
        }
    }
    //如果从尾部开始加节点采用以下方式
    public void addFromBottom(T value){
		Node<T> cur =new Node<T>(value);
        if(head ==null){
			head=cur;
            tail=cur;
        }else{
            cur.last=tail;
            tail.next=cur;
            tail=cur;
        }
    }
     //从头部弹出节点
    public T popFromHead(){
        if(head==null){
            return null;
        }
        Node<T> cur=head;
        if(head==tail){//如果链表中只有一个节点
            head=null;
            tail=null;
        }else{
            head=head.next;
            cur.next=null;
            head.last=null;
        }
        return cur.value;
    }
    //从尾部弹出节点
    public T popFromBottom(){
        if(head==null){
            return null;
        }
        Node<T> cur=tail;
        if(head==tail){//如果链表中只有一个节点
            head=null;
            tail=null;
        }else{
            tail=tail.last;
            tail.next=null;
            cur.last=null;
        }
        return cur.value;
    }

}

(2)双向链表创建栈

public static class MyStack<T{
	private DoubleEndsQueue<T> queue;
    public MyStack(){
		queue=new DoubleEndsQueue<T>();
    }
    //从头部插入从头部弹出，实现先进后出
    //往栈中插入数据
    public void push(T value){
        queue.addFromHead(value);
    }
    //将数据弹出栈
    public T pop(){
		return queue.popFromHead();
    }
    //判断是否为空
    public boolean isEmpty(){
        return queue.isEmpty();
    }
}

(3)双向链表创建队列

public static class MyQueue<T{
	private DoubleEndsQueue<T> queue;
    public MyStack(){
		queue=new DoubleEndsQueue<T>();
    }
    //从头部插入从尾部弹出，实现先进先出
    //往栈中插入数据
    public void push(T value){
        queue.addFromHead(value);
    }
    //将数据弹出栈
    public T pop(){
		return queue.popFromBottom();
    }
    //判断是否为空
    public boolean isEmpty(){
        return queue.isEmpty();
    }
}

2.使用数组实现栈和队列

提示：只考虑固定大小数组

(1)数组实现队列：实现环形数组

public static class MyQueue{
	private int[] arr;
    private int pushi;//记录插入数据的位置
    private int polli;//记录弹出数据的位置
    private int size;//记录队列中的数据个数
    private final int limit;//数组大小
    //初始化数组
    publish MyQueue(int limit){
		arr=new int[limit];
        pushi = 0;
        polli=0;
        size=0;
        this.limit=limit;
    }
	//进队列
    public void push(int value){
        if(size==limit){
			throw new RuntimeException("队列已满，不可再入队")
        }
        size++;
        arr[pushi]=value;
        pushi=nextIndex(pushi);
    }
    //出队列
    public int pop(){
        if(size==0){
			throw new RuntimeException("栈为空");
        }
        size--;
        int ans=arr[polli];
        polli=nextIndex(polli);
        return ans;
    }
    //判断是否为空
    public boolean isEmpty(){
        return size==0;
    }
    //如果现在的下标是i，返回下一个位置，
    private int nextIndex(int i){
        //判断i是否到了数组的最后一个位置，如果是，从0开始
        return i<limit-1 ? i+1:0;
    }

}

(2)数组实现栈

public static class MyStack{
	private int[] arr;
    private int size;//记录栈的数据大小
	private final int limit;//数组大小
    //初始化数组
    publish MyQueue(int limit){
		arr=new int[limit];
        size=0;
        this.limit=limit;
    }
    //进栈
    public void push(int value){
        if(size==limit){
			throw new RuntimeException("队列已满，不可再入队")
        }else{
             size++;
             arr[size]=value;
        }
    }
     //出栈
    public int pop(){
        if(size==0){
			throw new RuntimeException("栈为空");
        }
        size--;
        int ans=arr[size];
        return ans;
    }
	 //判断是否为空
    public boolean isEmpty(){
        return size==0;
    }
}

3.栈和队列的常见面试题

（1）实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能

​ 1) pop、push、getMin操作的时间复杂度都是O(1)。
​ 2）设计的栈类型可以使用现成的栈结构。

实现思路：准备两个栈，一个栈为正常的数据栈Data，一个栈Min来存放最小值，每次插入一个新数据newNum，Data正常插入，插入Min中是每次要与栈顶比较大小

public static class MyStack2{
    //创建两个栈
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    
    public MyStack2(){
        this.stackData=new Stack<Integer>();
        this.stackMin=new Stack<Integer>();
    }
    
    public void push(int newNum){
        //往stackMin中放数据时，需要将数据与Min栈顶的数据进行比较，
        // 以确保Min插入的每一个数据都是最新的最小值
        if(this.stackMin,isEnpty()){
            this.stackMin.push(newNum);
        }else if(newNum<this.getmin()){
            this.stackMin.push(newNum);
        }else{
            int newMin =this.stackMin.peek();
            this.stackMin.push(newMin);
        }
        this.stackData.push(newNum);
    }
    public int pop(){
        if(this.stackData.isEmpty()){
			throw new RuntimeException("栈为空");
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }
    public int getmin(){
        if (this.stackMin.isEmpty()){
            throw new RuntimeException("栈为空");
        }
        //返回栈栈顶数据
        return this.stackMin.peek();
    }
    
}

三、递归

判断递归的复杂度

Master公式
形如 T(N)= a * T(N/b)+O(N^d)(其中的a、b、d都是常数)的递归函数，可以直接通过Master公式来确定时间复杂度

如果log(b,a)< d，复杂度为O(N^d)

如果log(b,a) > d,复杂度为O(N^log(b,a))

如果log(b,a) == d，复杂度为O(N^d * logN)

四、哈希表与有序表

1.哈希表（HashMap）

1)哈希表在使用层面上可以理解为一种集合结构

2)如果只有key，没有伴随数据value，可以使用HashSet结构

3)如果既有key，又有伴随数据value，可以使用HashMap结构

4)有无伴随数据，是HashMap和HashSet唯一的区别,实际结构是一回事

5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为o(1)，但是常数时间比较大

6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小

7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节

2.有序表（TreeMap）

1)有序表在使用层面上可以理解为一种集合结构。

2)如果只有key，没有伴随数据value，可以使用set结构

3)如果既有key，又有伴随数据value，可以使用map结构

4)有无伴随数据是set与map的唯一区别，底层的实际结构是一回事。

5)有序表和哈希表的区别是，有序表把key按顺序组织起来，而哈希表完全不组织。

6)只要是有序表，他的常见操作的时间复杂度都是O(logN)

标签：head,cur,int,value,public,链表,哈希,next,LeetCode
From： https://www.cnblogs.com/jiaxh/p/17794096.html

相关文章

  • 数据结构与算法(LeetCode)第一节：认识复杂度，对数器，二分法与异或运算
    一、认识复杂度1.评估算法优劣的核心指标：时间复杂度：当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉，记为O（去掉系数的高阶项）；​ 时间复杂度是衡量算法流程的复杂度的一种指标，该指标只与数据量有关，与过程之外的优化无关常见的时间复杂度（从好到坏）O......
  • 面试必刷TOP101：15、删除有序链表中重复的元素-I
    题目题解importjava.util.*;publicclassSolution{publicListNodedeleteDuplicates(ListNodehead){//空链表if(head==null)returnnull;//遍历指针ListNodecur=head;//指针当前和下一位不为空......
  • LeetCode 11. 盛最多水的容器
    盛水最多的容器题目链接11.盛最多水的容器给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。**说明：**你不能倾斜容器。示例1：......
  • LeetCode 202. 快乐数
    快乐数题目链接202.快乐数编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1。如果这个过程结果为1，那么这个数就是快乐数。如果n......
  • Leetcode 1089. 复写零
    复写零题目链接1089.复写零给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。示例1：输入：arr=[1,0,2,3,0,4,5,0]输出：[1,0,0,......
  • LeetCode 611. 有效三角形的个数
    有效三角形的个数题目链接611.有效三角形的个数给定一个包含非负整数的数组nums，返回其中可以组成三角形三条边的三元组个数。示例1:输入:nums=[2,2,3,4]输出:3解释:有效的组合是:2,3,4(使用第一个2)2,3,4(使用第二个2)2,2,3示例2:输入:nums=[4,2,3,4]输出:......
  • Leetcode 283. 移动零
    移动零题目链接283.移动零给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。示例1:输入:nums=[0,1,0,3,12]输出:[1,3,12,0,0]示例2:输入:nums=[0]输出:[0]题目解释这道题目......
  • day 3 链表 203.移除链表元素、707.设计链表、206.反转链表
    203.移除链表元素题目链接：203.移除链表元素视频教程文字教程虚拟头节点虚拟头节点的目的：消除头节点的特殊性痛点：删除头节点和删除其他节点的操作是不一样的，导致写代码时需要分两种情况考虑因为其他链表都是通过前一个节点删除的而头节点没有前一个节点，只需将头节点向......
  • LeetCode 2: Add Two Numbers
    https://leetcode.cn/problems/add-two-numbers/description/FinallyIjoinedaforeigncompany'sChinabranchtolearnEnglishandstartanewjourney.PS:FromnowformeseemsMoreleisurely,elegant,high-tech,andalittlewise(inleadership)compa......
  • 字符串中的BKDRHash哈希函数
    字符串中的BKDRHash哈希函数在计算机科学中，哈希函数是一种将任意长度的输入（也称为“消息”）通过散列算法转换成固定长度的输出，该输出就是哈希值。哈希函数的一个重要特性是，对于相同的输入，无论何时执行哈希函数，它都应该产生相同的输出。然而，对于不同的输入，即使它们只有微小的差别，哈......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99