算法笔记—链表、队列和栈

链表、队列和栈

  • 1. 链表
    • 1.1 单链表反转
    • 1.2 双链表反转
    • 1.3 合并两个有序链表
    • 1.4 链表相加
    • 1.5 划分链表
  • 2. 队列和栈
    • 2.1 循环队列
    • 2.2 栈实现队列
    • 2.3 队列实现栈
    • 2.4 最小栈
    • 2.2 双端队列

1. 链表

1.1 单链表反转

  • 力扣 反转链表
	// 反转单链表
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;	// next指向head.next指的位置
            head.next = pre;	// head.next指向pre指向的位置
            pre = head;			// pre指向head指向的位置
            head = next;		// head指向next指向的位置
        }
        return pre;
    }

	// 单链表节点定义
	public static class ListNode {
		public int val;
		public ListNode next;
		public ListNode(int val) {
			this.val = val;
		}
		public ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

1.2 双链表反转

	// 反转双链表
	public static DoubleListNode reverseDoubleList(DoubleListNode head) {
		DoubleListNode pre = null;
		DoubleListNode next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			head.last = next;// 同时修改last指针即可
			pre = head;
			head = next;
		}
		return pre;
	}

	// 双链表节点
	public static class DoubleListNode {
		public int value;
		public DoubleListNode last;
		public DoubleListNode next;
		public DoubleListNode(int v) {
			value = v;
		}
	}

1.3 合并两个有序链表

  • 力扣链接
	// 合并两个有序链表
	public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
		//谁小谁做头
        ListNode head = head1.val <= head2.val ? head1 : head2; 
        ListNode cur1 = head.next;
        // 另一个链表的头结点
        ListNode cur2 = head == head1 ? head2 : head1; 
        // 已挂好(处理好)节点的前一个
        ListNode pre = head; 

        // 只要都没完 谁小谁挂在pre之后
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        // 若有一个链表结束 另一个剩余的挂在pre之后
        pre.next = cur1 != null ? cur1 : cur2; //剩余部分
        return head;
    }

1.4 链表相加

力扣 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

  • 请你将两个数相加，并以相同形式返回一个表示和的链表。
  • 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    在这里插入图片描述
	// 链表两数相加 没有复用老链表
    public ListNode addTwoNumbers(ListNode h1, ListNode h2) {
        ListNode ans = null, cur = null; // 初始化新链表
        int carry = 0; // 进位数 加法的进位只能为 0 或者 1
        for (int sum, val; // 声明变量
             h1 != null || h2 != null; // 循环条件
             h1 = h1 == null ? null : h1.next, // 每一轮h1的跳转
             h2 = h2 == null ? null : h2.next  // 每一轮h2的跳转
        ) {
        
            sum = (h1 == null ? 0 : h1.val)
                    + (h2 == null ? 0 : h2.val)
                    + carry; // 上一轮的进位
            
            // 组建新链表
            val = sum % 10; // 个位
            carry = sum / 10; // 进位
            if (ans == null) {
                ans = new ListNode(val);
                cur = ans;
            } else {
                cur.next = new ListNode(val);
                cur = cur.next;
            }
        }
        // 判断最后一位有无进位  若有则挂 1 节点
        if (carry == 1) {
            cur.next = new ListNode(1);
        }
        return ans;
    }

1.5 划分链表

力扣 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

  • 你应当 保留 两个分区中每个节点的初始相对位置。
	public static ListNode partition(ListNode head, int x) {
        ListNode leftHead = null, leftTail = null;
        ListNode rightHead = null, rightTail = null;
        ListNode next = null;

        // 终止条件
        while (head != null) {
            next = head.next; //记录一下下一位置 因为要断链
            head.next = null;
            // 小于范围
            if (head.val < x) {
                // set head
                if (leftHead == null) {
                    leftHead = head;
                } else {
                    leftTail.next = head;
                }
                // set tail
                leftTail = head;
            // 大于范围
            } else {
                if (rightHead == null) {
                    rightHead = head;
                } else {
                    rightTail.next = head;
                }
                rightTail = head;
            }
            head = next; // 处理下一节点
        }
        // 默认返回左头 这里对左头进行判断
        // 如果没有小于的 直接返回右头结点
        if (leftHead == null){
            return rightHead;
        }
        leftTail.next = rightHead;
        return leftHead;
    }
	// 单链表节点
    public static class ListNode {
        public int val;
        public Video_012.ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    	public ListNode(int val, Video_012.ListNode next) {
        	this.val = val;
        	this.next = next;
        }
    }

2. 队列和栈

2.1 循环队列

力扣 设计循环队列

class MyCircularQueue {
    public int[] queue;
    public int l, r, size, limit;

    // 同时在队列里的数字个数，不要超过k
    public MyCircularQueue(int k) {
        queue = new int[k];
        l = r = size = 0;
        limit = k;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        } else {
            queue[r] = value;
            // r++, 结束了，跳回0
            r = r == limit - 1 ? 0 : (r + 1);
            size++;
            return true;
        }
    }
    
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        } else {
            // l++, 结束了，跳回0
            l = l == limit - 1 ? 0 : (l + 1);
            size--;
            return true;
        }
    }
    
    public int Front() {
        if (isEmpty()) {
            return -1;
        } else {
            return queue[l];
        }
    }
    
    public int Rear() {
        if (isEmpty()) {
            return -1;
        } else {
            int last = r == 0 ? (limit - 1) : (r - 1);
            return queue[last];
        }
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == limit;
    }
}

2.2 栈实现队列

力扣

class MyQueue {

    public Stack<Integer> in;

    public Stack<Integer> out;

    public MyQueue() {
        in = new Stack<Integer>();
        out = new Stack<Integer>();
    }

    // 倒数据
    // 从in栈，把数据倒入out栈
    // 1) out空了，才能倒数据
    // 2) 如果倒数据，in必须倒完
    private void inToOut() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.pop());
            }
        }
    }

    public void push(int x) {
        in.push(x);
        inToOut();
    }

    public int pop() {
        inToOut();
        return out.pop();
    }

    public int peek() {
        inToOut();
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

2.3 队列实现栈

力扣

class MyStack {

    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<Integer>();
    }

    // O(n)
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

2.4 最小栈

力扣

class MinStack {
    public final int MAXN = 8001;
    public int[] data;
    public int[] min;
    int size;

    public MinStack() {
        data = new int[MAXN];
        min = new int[MAXN];
        size = 0;
    }

    public void push(int val) {
        data[size] = val;
        if (size == 0 || val <= min[size - 1]) {
            min[size] = val;
        } else {
            min[size] = min[size - 1];
        }
        size++;
    }

    public void pop() {
        size--;
    }

    public int top() {
        return data[size - 1];
    }

    public int getMin() {
        return min[size - 1];
    }
}

2.2 双端队列

力扣 设计循环双端队列

	// 双向链表实现
	// 常数操作慢，但是leetcode数据量太小了，所以看不出劣势
	class MyCircularDeque {

		public Deque<Integer> deque = new LinkedList<>();
		public int size;
		public int limit;

		public MyCircularDeque1(int k) {
			size = 0;
			limit = k;
		}

		public boolean insertFront(int value) {
			if (isFull()) {
				return false;
			} else {
				deque.offerFirst(value);
				size++;
				return true;
			}
		}

		public boolean insertLast(int value) {
			if (isFull()) {
				return false;
			} else {
				deque.offerLast(value);
				size++;
				return true;
			}
		}

		public boolean deleteFront() {
			if (isEmpty()) {
				return false;
			} else {
				size--;
				deque.pollFirst();
				return true;
			}
		}

		public boolean deleteLast() {
			if (isEmpty()) {
				return false;
			} else {
				size--;
				deque.pollLast();
				return true;
			}
		}

		public int getFront() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque.peekFirst();
			}
		}

		public int getRear() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque.peekLast();
			}
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean isFull() {
			return size == limit;
		}

	}

	// 用数组实现，常数操作快
	// 但是leetcode数据量太小了，看不出优势
	class MyCircularDeque {
		public int[] deque;
		public int l, r, size, limit;
		
		public MyCircularDeque2(int k) {
			deque = new int[k];
			l = r = size = 0;
			limit = k;
		}

		public boolean insertFront(int value) {
			if (isFull()) {
				return false;
			} else {
				if (isEmpty()) {
					l = r = 0;
					deque[0] = value;
				} else {
					l = l == 0 ? (limit - 1) : (l - 1);
					deque[l] = value;
				}
				size++;
				return true;
			}
		}

		public boolean insertLast(int value) {
			if (isFull()) {
				return false;
			} else {
				if (isEmpty()) {
					l = r = 0;
					deque[0] = value;
				} else {
					r = r == limit - 1 ? 0 : (r + 1);
					deque[r] = value;
				}
				size++;
				return true;
			}
		}

		public boolean deleteFront() {
			if (isEmpty()) {
				return false;
			} else {
				l = (l == limit - 1) ? 0 : (l + 1);
				size--;
				return true;
			}
		}

		public boolean deleteLast() {
			if (isEmpty()) {
				return false;
			} else {
				r = r == 0 ? (limit - 1) : (r - 1);
				size--;
				return true;
			}
		}

		public int getFront() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque[l];
			}
		}

		public int getRear() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque[r];
			}
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean isFull() {
			return size == limit;
		}
	}

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

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

相关文章

三、Shell 环境

三、Shell 环境

一、Linux 系统分类 在 Linux 中&#xff0c;常见的 Shell 有以下几种&#xff1a; Bourne Shell&#xff08;sh&#xff09;&#xff1a;最早的 Shell&#xff0c;由 Stephen Bourne 开发。它是大多数其他 Shell 的基础。Bourne Again Shell&#xff08;bash&#xff09;&am…
阅读更多...
螺旋矩阵算法(leetcode第59题)

螺旋矩阵算法(leetcode第59题)

题目描述&#xff1a; 给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。示例 1&#xff1a;输入&#xff1a;n 3 输出&#xff1a;[[1,2,3],[8,9,4],[7,6,5]] 示例 2&#xff1a;输入&#…
阅读更多...
SQL Server 远程连接服务器数据库

SQL Server 远程连接服务器数据库

本文解决sql server的远程连接问题。需要开启防火墙&#xff0c;开启端口&#xff0c;并处理权限不足的报错: 【use 某数据库】The server principal "[server]" is not able to access the database "[database]" under the current security context. 【…
阅读更多...
[C/C++]——内存管理

[C/C++]——内存管理

学习C/C的内存管理 前言&#xff1a;一、C/C的内存分布二、C语言中动态内存管理方式三、C中动态内存管理方式3.1、new/delete操作符3.1.2、new/delete操作内置类型3.1.3、new/delete操作自定义类型 3.2、认识operator new和operator delete函数3.3、了解new和delete的实现原理3…
阅读更多...
json.loads和eval 速度对比

json.loads和eval 速度对比

json.loads和eval 速度对比 代码1结果图代码2参考地址 代码1 import json import time import pandas as pddata_sets pd.read_pickle("val_token_id.pandas_pickle") data_sets[str(i) for i in data_sets] starttime.time() [json.loads(i) for i in data_sets] …
阅读更多...
FlieZilla服务器配置与数据访问、传输

FlieZilla服务器配置与数据访问、传输

概述 手机apk当初服务器&#xff0c;PC端访问手机端的数据&#xff0c;再没有数据线的情况下&#xff0c;非常方便。希望各位同仁搞起来&#xff0c;在此做个笔录。 安装包下载链接&#xff1a;https://download.csdn.net/download/qq_36075612/88577274 一、下载安装包&…
阅读更多...
2023-12-08 队列与栈

2023-12-08 队列与栈

栈与队列一 232. 用栈实现队列 思路&#xff1a;对于使用栈实现队列的话&#xff0c;必须使用两个共同来维护使得每次都能先进先出&#xff01; class MyQueue:def __init__(self):# 需要建立两个list来维护出栈以及进栈self.stack_in []self.stack_out []def push(self, x…
阅读更多...
“ABCD“[(int)qrand() % 4]作用

“ABCD“[(int)qrand() % 4]作用

ABCD[(int)qrand() % 4] 作用 具体来说&#xff1a; qrand() 是一个函数&#xff0c;通常在C中用于生成一个随机整数。% 4 会取 qrand() 生成的随机数除以4的余数。因为4只有四个不同的余数&#xff08;0, 1, 2, 3&#xff09;&#xff0c;所以这实际上会生成一个0到3之间的随…
阅读更多...
1.4 Postman的安装

1.4 Postman的安装

hello大家好&#xff0c;本小节我们来安装一下Postman&#xff0c;好为我们后续的测试工作做准备。 首先&#xff0c;打开Postman的官网Postman API Platform 然后根据同学们自己电脑的操作系统来下载对应的Postman安装包。我这里拿windows来举例。我们点击windows的图标 会跳…
阅读更多...
STM32G030C8T6：使用外部晶振配置LED灯闪烁

STM32G030C8T6：使用外部晶振配置LED灯闪烁

本专栏记录STM32开发各个功能的详细过程&#xff0c;方便自己后续查看&#xff0c;当然也供正在入门STM32单片机的兄弟们参考&#xff1b; 本小节的目标是&#xff0c;使用STM32G030C8T6单片机&#xff0c;通过STM32CubeMX软件&#xff0c;配置并使用外部8MHz晶振&#xff0c;实…
阅读更多...
孩子还是有一颗网安梦——Bandit通关教程：Level 10 → Level 11

孩子还是有一颗网安梦——Bandit通关教程：Level 10 → Level 11

&#x1f575;️‍♂️ 专栏《解密游戏-Bandit》 &#x1f310; 游戏官网&#xff1a; Bandit游戏 &#x1f3ae; 游戏简介&#xff1a; Bandit游戏专为网络安全初学者设计&#xff0c;通过一系列级别挑战玩家&#xff0c;从Level0开始&#xff0c;逐步学习基础命令行和安全概念…
阅读更多...
3、ollvm移植

3、ollvm移植

github: https://github.com/obfuscator-llvm/obfuscator/tree/llvm-4.0 先复制 include Obfuscation: /home/nowind/llvm/ollvm/obfuscator/include/llvm/Transforms/Obfuscation /home/nowind/llvm/llvm-project-9.0.1/llvm/include/llvm/Transforms/Obfuscation lib Ob…
阅读更多...
13.字符串长度【2023.12.5】

13.字符串长度【2023.12.5】

1.问题描述 获取字符串长度是编程过程中常用的操作之一。编写一个程序&#xff0c;输入一个字符串&#xff0c;然后输出字符串的长度。 2.解决思路 输入一个字符串。程序将输入的字符串的长度输出。使用内置函数len()获取字符串的长度 3.代码实现 strinput("请输入一…
阅读更多...
C语言实现简易版扫雷游戏

C语言实现简易版扫雷游戏

由于前面所讲知识点有限&#xff0c;无法实现扫雷游戏的全部功能&#xff0c;本期为各位呈现的是相对简单且易于编写的扫雷游戏。 第一步 设计游戏可玩多次的循环框架 这里在之前猜数字游戏时使用的循环框架一致&#xff0c;但是上次讲解不够深入&#xff0c;这里补充一下。这…
阅读更多...
Day59力扣打卡

Day59力扣打卡

打卡记录
阅读更多...
minio可用性磁盘/节点故障恢复的研究

minio可用性磁盘/节点故障恢复的研究

做poc真的很累。年初的报告拿出来按topic拿出来分享一下。 目的 通过模拟各类条件下的minio集群状态&#xff0c;确认minio是否符合官方“N/2硬盘在线&#xff0c;数据可读取&#xff1b;N/21硬盘在线&#xff0c;数据可读写”的描述。 同时通过停止minio集群中节点的服务停止…
阅读更多...
青少年CTF-Crypto(Morse code/ASCII和凯撒)

青少年CTF-Crypto(Morse code/ASCII和凯撒)

FLAG&#xff1a;你这一生到底想干嘛 专研方向: Web安全 &#xff0c;Md5碰撞 每日emo&#xff1a;不要因为别人都交卷了&#xff0c;就乱选答案 文章目录 1.Morse code2、ASCII和凯撒的约定 1.Morse code 题目提示摩尔斯电码&#xff0c;这个是给的附件 直接用摩尔斯解密&am…
阅读更多...
基础算法(1):排序(1):选择排序

基础算法(1):排序(1):选择排序

今天对算法产生了兴趣&#xff0c;开始学习基础算法&#xff0c;比如排序&#xff0c;模拟&#xff0c;贪心&#xff0c;递推等内容&#xff0c;算法是很重要的&#xff0c;它是解决某个问题的特定方法&#xff0c;程序数据结构算法&#xff0c;所以对算法的学习是至关重要的&a…
阅读更多...
【数组Array】力扣-5 最长回文子串

【数组Array】力扣-5 最长回文子串

目录 题目描述 题解labuladong 题目描述 给你一个字符串 s&#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同&#xff0c;则该字符串称为回文字符串。 示例 1&#xff1a; 输入&#xff1a;s "babad" 输出&#xff1a;"bab"…
阅读更多...
Spring上IOC之@EnableAspectJAutoProxy

Spring上IOC之@EnableAspectJAutoProxy

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
最新文章

Copyright @ 2022~2023