【数据结构与算法——TypeScript】数组、栈、队列、链表

【数据结构与算法——TypeScript】

算法(Algorithm)的认识

  • 解决问题的过程中，不仅仅 数据的存储方式会影响效率，算法的优劣也会影响效率

  • 什么是算法？

    • 定义：
      🟢 一个有限指令集，每条指令的描述不依赖于言语 （编写指令：java/c++/ts/js）
      🟢 接收一些输入（有些情况下不需要输入）（接收：排序：无序数组）
      🟢 产生输出 （产出：有序数组）
      🟢 一定在有限步骤之后终止

  • 举例：电灯不工作的解决算法
    电灯不工作的解决算法

  • 算法的通俗理解

    • Algorithm这个单词本意就是 解决问题的办法/步骤逻辑。
    • 数据结构的实现，离不开算法。

线性结构(Linear List)

  • 线性结构（Linear List）是由n（n≧0）个数据元素（结点）a[0],a[1],a[2],…,a[n-1]组成的有限序列。

  • 其中：

    • 【数据元素的个数 n 定义为表的长度】= “list”.length()(“list”.length() = 0 (表示没有一个元素) 时，称为空表)。
    • 将非空的线性表 （n>=1）,记作：（a[0],a[1],a[2],…,a[n-1]）。
    • 数据元素 a[i] (0 <= i <= n-1) 只是抽象符号，其具体含义在不同情况下可以不同。

  • 常见线性结构：
    💚 数组结构（Array）
    💚 栈结构（Stack）
    💚 队列结构（Queue）
    💚 链表结构（LinkedList）

数组(Array)结构

  • 数组(Array)结构是一种重要的数据结构

    • 几乎是每种编程语言都会提供的一种 原生数据结构（语言自带的）；
    • 并且我们 可以借助于数组结构来实现其他的数据结构，比如：栈（Stack）、队列（Queue）、堆（Heap）；

  • 通常数组的内存都是连续的，所以数组在知道下标值的情况下，访问效率是非常高的
    数组

  • TypeScript中数组的各种用法，和JavaScript是一致的：
    https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array

栈结构(Stack)

认识栈结构和特性 ❤️

认识栈结构

  • 栈 也是一种非常常见的数据结构，并且在程序中的应用非常广泛。

  • 数组：

    • 是一种 线性结构，可以在数组的 任意位置 插入和删除数据。
    • 但，为了实现某些功能，必须对这种 任意性加入限制。
    • 而 栈和队列 就是比较常见的 受限的线性结构。

  • 栈结构示意图
    ❤️ 后进先出/先进后出
    在这里插入图片描述

栈结构特性

  • 栈（Stack）,它是一种受限的线性结构， 后进先出（LIFO）
    • 其限制是仅允许在 表的一端 进行插入和删除运算。这一端被称为 栈顶，相对地，另一端就是 栈低。
    • LIFO（last in first out）表示 后进入的元素，第一个弹出栈空间。类似于，自动餐托盘，最后放上的托盘，往往先拿出去使用。
    • 向一个栈插入新元素，又叫 进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
    • 从一个栈删除元素又称之为 出栈 或者 退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈结构特性 —— 面试题

面试题目

  • ❓题目：
    🔖 有六个元素6,5,4,3,2,1顺序入栈,问下列哪一个不是合法的出栈序列?()
    A. 5 4 3 6 1 2
    B. 4 5 3 2 1 6
    C. 3 4 6 5 2 1
    D. 2 3 4 1 5 6

  • 分析：

    • A. 5 4 3 6 2 1
      • 6，5进栈，5出栈，4进栈，4出栈，3进栈，3出栈，6出栈，2进栈，1进栈，1出栈，2出栈
    • B. 4 5 3 2 1 6
      • 6，5，4进栈，4出栈，5出栈，3进栈，3出栈，2进栈，2出栈，1入栈，1出栈，6出栈
    • C. 3 4 6（x） 5 2 1 ❌
      • 6，5，4，3进栈，3出栈，4出栈，5出栈
    • D. 2 3 4 1 5 6
      • 6，5，4，3，2进栈，2出栈，3出栈，4出栈，1进栈，1出栈，5出栈，6出栈
    • 答案： C

实现栈结构的封装

  • 常见的方式：
    🔹 基于数组实现
    🔹 基于链表实现

🔹 基于数组实现：创建栈的类

  • 代码解析：
    • 创建一个 Stack ，用户创建栈的类，可以定义一个泛型类。
    • 在构造函数中，定义一个变量，存储当前栈对象中的所有元素。
    • 这个变量是一个数组类型。
    • 之后，无论是入栈还是出栈操作，都是从数组中添加和删除元素。
    • 栈的一些操作方法，无论是什么语言，操作都是比较类似的。

栈结构常见的方法

🔸栈的常见操作

  • push(element):添加一个新元素到栈顶。
  • pop()：删除栈顶元素，返回被移除的元素。
  • peek():仅返回栈顶元素，不对栈做任何修改。
  • isEmpty():判断栈里是否有元素。有，返回true，否，返回false。
  • size():返回栈里的元素个数。这个方法和数组的length属性类型。

实现

import { IStack } from './IStack';class ArrayStack<T = any> implements IStack<T> {// 定义一个数组/链表，用于存储元素private data: T[] = [];// 实现栈中的操作方法// push(element)：添加一个新元素到栈顶push(element: T): void {this.data.push(element);}// pop()：删除栈顶元素，返回被移除的元素。pop(): T | undefined {return this.data.pop();}// peek():仅返回栈顶元素，不对栈做任何修改。peek(): T | undefined {return this.data[this.data.length - 1];}// isEmpty():判断栈里是否有元素。有，返回true，否，返回false。isEmpty(): boolean {return this.data.length === 0;}// size():返回栈里的元素个数。这个方法和数组的length属性类型。size(): number {return this.data.length;}
}export default ArrayStack;

export interface IStack<T> {push(element: T): void;pop(): T | undefined;peek(): T | undefined;isEmpty(): boolean;size(): number;
}

栈面试题 —— 十进制转二进制

  • 为什么需要十进制转二进制？

    • 现实生活中，主要使用 十进制。
    • 但，在计算机科学中， 二进制非常重要，因为 计算机里的所有内容都是用二进制数字表示的（0和1）。
    • 没有十进制和二进制互相转换的能力，与计算机交流就很困难。
    • 转换二进制是计算机科学和编程领域中经常使用的算法。

  • 如何实现时十进制转二进制(整数)？

    • 将十进制数字和2整除（二进制是满2进1），直到结果为0
    • 把十进制数字35转为二进制的数字：
      • 35/2 = 17…1, 余 1
      • 17/2 = 8…1, 余 1
      • 8/2 = 4…0,余 0
      • 4/2 = 2…0,余 0
      • 2/2 = 1…0,余 0
      • 1/2 = 0…1,余 1
      • 从后往前：100011

  • 简单实现

    import ArrayStack from './02_实现栈结构Stack(重构)';function decimalToBinary(decimal: number): string {// 1. 创建一个栈，用于存储余数const stack = new ArrayStack<number>();// 2. 使用循环:while:不确定次数，只知道循环结束条件while (decimal > 0) {const result = decimal % 2;stack.push(result);decimal = Math.floor(decimal / 2);}// 3.将所有的余数已放入到stack中，依次取出所有余数let binary = '';while (!stack.isEmpty()) {binary += stack.pop();}return binary;
}
export {};console.log('35:', decimalToBinary(35));
console.log('100:', decimalToBinary(100));

栈面试题 —— 有效括号

  • 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

    • ❗️有效字符串需满足：
      • 左括号必须用相同类型的右括号闭合。
      • 左括号必须以正确的顺序闭合。
      • 每个右括号都有一个对应的相同类型的左括号
      • Leecode 20:https://leetcode.cn/problems/valid-parentheses/

  • 示例 1：

    输入：s = “()”
    输出：true

  • 示例 2：

    输入：s = “()[]{}”
    输出：true

  • 示例 3：

    输入：s = “(]”
    输出：false

  • ⚠️ 提示：

    • 1 <= s.length <= 10的4次
    • s 仅由括号 ‘()[]{}’ 组成

  • 代码

import ArrayStack from './02_实现栈结构Stack(重构)';function isValid(s: string): boolean {// 1. 创建一个栈结构：const stack = new ArrayStack<string>();// 2. 遍历字符串for (let i = 0; i < s.length; i++) {const c = s[i];switch (c) {case '(':stack.push(')');break;case '{':stack.push('}');break;case '[':stack.push(']');break;default:if (c !== stack.pop()) return false;break;}}return stack.isEmpty();
}console.log(isValid('()'));
console.log(isValid('()[]{}'));
console.log(isValid('(]'));
console.log(isValid('([])'));
console.log(isValid('({[}])'));

队列结构(Queue)

认识队列和特性

  • 受限的线性结构

    • 这种受限的线性结构对于解决某些 特别问题有特别的结果。
    • 受限的数据结构：队列。

  • 队列（Queue），它是一种受限的线性结构，先进先出（FILO:First In Last Out）

    • 受限之处：只允许在队列的前端（front），进行删除操作；
    • 在队列的 后端（rear) 进行插入操作；
      在这里插入图片描述

实现队列结构封装

  • 基于 数组实现（性能低）
  • 基于 链表实现（更好）

队列结构常见方法

  • enqueue(element):向队列尾部添加一个（或者多个）新的项。
  • dequeue():移除队列的第一（即排在队列最前面的）项，也是最先移除的元素；
  • front/peek():返回队列中第一个元素——最先被添加，也是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息）
  • isEmpty():如果队列中不包含任何元素，返回true，否则返回false
  • size():返回队列包含的元素个数，与数组的length属性类似

基于数组实现

import { IQueue } from './IQueue';class ArrayQueue<T = any> implements IQueue<T> {// 内部通过数组保存private data: T[] = [];// 队列常见操作/*** enqueue(element):向队列尾部添加一个（或者多个）新的项。* dequeue():移除队列的第一（即排在队列最前面的）项，也是最先移除的元素；* front/peek():返回队列中第一个元素——最先被添加，也是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息）* isEmpty():如果队列中不包含任何元素，返回true，否则返回false；* size():返回队列包含的元素个数，与数组的length属性类似*/enqueue(element: T): void {this.data.push(element);}dequeue(): T | undefined {return this.data.shift();}peek(): T | undefined {return this.data[0];}isEmpty(): boolean {return this.data.length === 0;}get size(): number {return this.data.length;}
}
export default ArrayQueue;
import type { IList } from '../types/IList';export interface IQueue<T> extends IList<T> {enqueue(element: T): void;dequeue(): T | undefined;
}

export interface IList<T> {peek(): T | undefined;isEmpty(): boolean;get size(): number;
}

面试题 —— 击鼓传花

  • 击鼓传花，是一个常见的面试算法题：使用队列可以非常方便的实现最终的结果

  • 原游戏规则

    • 班级中玩一个游戏，所有同学围成一个圈，从某位同学手里开始向旁边的同学传一束花；
    • 这个时候某个人（比如班长），在击鼓，鼓声停下的一刻，花落在谁的手里，谁就出来表演节目。

  • 修改游戏规则

    • 几个朋友一起玩一个游戏， 围成一圈，开始数数，数到某个数字的人自动淘汰；
    • 最后 剩下的这个人获胜，请问最后剩下的人是原来在哪一个位置上的人？

  • 封装一个基于队列的函数：

    • 参数：所有参与人的姓名，基于的数字；
    • 结果：最终剩下的一个人的姓名

  • 分析：

    • 假如数到3的人，淘汰；
      • 那么，队列中 数的1，2的人，出队之后，又入队；
      • 数到 3 的人，出队，不需要入队
    • 直到，队列的size() 等于1 的时候，取到队列里的人

  • 代码

import ArrayQueue from './01_基于数组的队列结构Queue';function hotPatato(names: string[], num: number) {if (names.length === 0) return -1;// 1. 创建一个队列结构const queue = new ArrayQueue<string>();// 2. 将所有的name加入队列for (const name of names) {queue.enqueue(name);}// 3. 淘汰的规则while (queue.size > 1) {// 小于 num 的不淘汰for (let i = 1; i < num; i++) {const name = queue.dequeue();if (name) queue.enqueue(name);}// num 淘汰queue.dequeue();}// 取出最后一个人const leftName = queue.dequeue()!;// 取出最后一个人的原索引const index = names.indexOf(leftName);return index;
}
const leftIndex = hotPatato(['why', 'JIM', 'JANE', 'LENO', 'CURRY', 'TIM', 'TOM', 'JERRY', 'JENO', 'TIA'], 5);
console.log(leftIndex);

面试题 —— 约瑟夫环

  • 什么是约瑟夫环问题（历史）？

  • 阿乔问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

    • 人们站在一个等待被处决的圈子里；
    • 计数从圆圈中指定的点开始，并沿指定方向围绕圆圈进行；
    • 在跳过指定数量的人之后，处刑下一个人；
    • 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放；
    • 在给定数量的情况下，站在第几个位置可以避免被处刑？

  • Leecode 剑指 Offer 62. 圆圈中最后剩下的数字

  • https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

  • 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。

  • 求出这个圆圈里剩下的最后一个数字。

  • 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

  • 示例 1：

    输入: n = 5, m = 3
    输出: 3

  • 示例 2：

    输入: n = 10, m = 17
    输出: 2

  • 代码

import ArrayQueue from './01_基于数组的队列结构Queue';function lastRemaining(n: number, m: number): number {const queue = new ArrayQueue<number>();for (let i = 0; i < n; i++) {queue.enqueue(i);}while (queue.size > 1) {for (let i = 1; i < m; i++) {queue.enqueue(queue.dequeue()!);}queue.dequeue();}return queue.dequeue()!;
}console.log(lastRemaining(5, 3));
console.log(lastRemaining(10, 17));

链表结构（LinkedList）

认识链表及特性

数组的缺点

  • 链表和数组一样，可以用于 存储一系列的元素，但是链表和数组的 实现机制完全不同。
  • 用于存储数据的线性结构：链表。

🥺

  • 数组：

    • 要存储多个元素，数组（或选择链表）可能是 最常用的数据结构
    • 几乎每种语言都有默认实现 数组结构

  • 💔 但是，数组有很多缺点

    • 数组的创建通常需要申请一段 连续的内存空间（一整块的内存），并且大小是固定的（大多数编程语言数组都是固定的），所以当前数组 不能满足容量需求时，需要 扩容。（一般情况下时申请一个更大的数组，比如2倍。然后将原数组中的元素复制过去）
    • 而且在 数组开头或者中间位置插入数据的成本很高，需要 进行大量元素的位移。

🥰 链表的优势

  • 要存储多个元素，另外一个选择就是 链表

  • 不同于数组，链表中的元素在内存中 不必是连续的空间。

    • 链表的每个元素由一个存储 元素本身的节点和 一个指向下一个元素的引用（有些语音称为指针或链接）组成。

  • ❣️ 相对于数组，链表的优势有

    • 🟩 内存空间不是必须连续的
      • ✓ 可以充分利用计算机的内存，实现灵活的 内存动态管理。
    • 🟩 链表不必在创建时就 确定大小，并且大小可以 无限延伸下去。
    • 🟩 链表在 插入和删除数据时，时间复杂度可以达到O(1)
      • ✔️ 相对数组效率高很多

  • 💔 相对于数组，链表的缺点有

    • ❌ 链表访问任何一个位置的元素时，都需要 从头开始访问（无法跳过第一个元素访问任何一个元素）。
    • ❌ 无法通过下标直接访问元素，需要从头一个一个访问，直到找到对应的元素。

什么是链表？

  • 链表是什么？
    • 链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客（类似于数据），并且这个节点会连接下一个节点，以此类推。

在这里插入图片描述

封装链表的类结构

分析代码

在这里插入图片描述

  • 封装一个 Node类，用于封装每一个节点上的信息（包括值和指向下一个节点的引用），它是一个泛型。
  • 封装一个 LinkedList类，用于表示我们的链表结构。
  • 链表中保存两个属性：链表长度、链表的第一个节点。
// 1. 创建Node节点类
class Node<T> {value: T;next: Node<T> | null = null;constructor(value: T) {this.value = value;}
}// 2.创建LinkedList类
class LinkedList<T> {head: Node<T> | null = null;private size: number = 0;get length() {return this.size;}
}const linkedList = new LinkedList<string>();
console.log(linkedList.head);
export {};

封装链表的相关方法

  • append(element):向链尾添加一个新的项
      1. 链表本身为空，新添加数据时唯一的节点
      1. 链表本身不为空，需要向其他节点后面追加节点

      在这里插入图片描述

  // 追加节点append(value: T) {// 1.根据value创建一个新节点const newNode = new Node(value);//  1. 链表本身为空，新添加数据时唯一的节点//  2. 链表本身不为空，需要向其他节点后面追加节点if (!this.head) {this.head = newNode;} else {let current = this.head;while (current.next) {current = current.next;}// current此时，肯定是指向最后一个节点current.next = newNode;}this.size++;}

  • insert(position,element):向链表的特定位置插入一个新的项

    • 1.添加到第一个位置
      • 添加到第一个位置，表示新添加的节点是头，就需要将原来的头节点，作为新的节点的next
      • 这个时候的head应该指向新节点

    在这里插入图片描述

      1. 其他位置

-在这里插入图片描述

  //插入 insert(position, element): 向链表的特定位置插入一个新的项;insert(value: T, position: number): boolean {if (position < 0 || position > this.size) return false;// 是否添加到第一个const newNode = new Node(value);if (position === 0) {newNode.next = this.head;this.head = newNode;} else {let current = this.head;let previous: Node<T> | null = null;let index = 0;while (index++ < position && current) {previous = current;current = current.next;}// index === positionnewNode.next = current;previous!.next = newNode;}this.size++;return true;}
  • get(position):获取对应位置的元素
  // 获取getget(position: number): T | null {if (position < 0 || position >= this.size) return null;// 查找元素let index = 0;let current = this.head;while (index++ < position && current) {current = current?.next;}// index === positionreturn current?.value ?? null;}
  • indexOf(element):返回元素在链表中的索引。如果链表中没有该元素则返回 -1
  // 获取索引indexOf(value: T): number {// 遍历let current = this.head;let index = 0;while (current) {if (current.value === value) {return index;}current = current.next;index++;}return -1;}
  • update(position,element):修改某个位置的元素
  // 更新update(value: T, position: number): boolean {if (position < 0 || position >= this.size) return false;let currentNode = this.head;let index = 0;while (index++ < position && current) {currentNode = currentNode.next;}currentNode!.value = value;return true;}
  • removeAt(position):从链表的特定位置移除一项

    • 常见两种

        1. 根据位置位移对应的数据
        1. 根据数据，先找到对应的位置，再移除数据

    • 移除第一项：

      • 移除第一项时，直接让head指向第二项信息
      • 第一项信息没有引用指向，就在链表中不再有效，后面会被回收
        在这里插入图片描述

    • 移除其他项：

      • 首先，通过while循环，找到正确的位置
      • 其次，直接将上一项的next指向current项的next，这样中间的项就没有引用指向它，也就不存于链表中，后面就会被回收

      在这里插入图片描述

  // 删除removeAt(position: number): T | null {// 越界判断if (position < 0 || position >= this.size) return null;// 删除元素// 判断是否是删除第一个节点let current = this.head;if (position === 0) {this.head = this.head?.next ?? null;} else {let previous: Node<T> | null = null;let index = 0;while (index++ < position && current) {previous = current;current = current.next;}// index === positionprevious!.next = current?.next ?? null;}this.size--;return current?.value ?? null;}
  • remove(element):从链表中移除一项
  // 根据value删除remove(value: T): T | null {const index = this.indexOf(value);return this.removeAt(index);}
  • isEmpty():如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false
// 链表是否为空isEmpty(): boolean {return this.size === 0;}
  • size():返回链表包含的元素个数。与数组的length属性类似

完整代码

// 1. 创建Node节点类
class Node<T> {value: T;next: Node<T> | null = null;constructor(value: T) {this.value = value;}
}// 2.创建LinkedList类
class LinkedList<T> {private head: Node<T> | null = null;private size: number = 0;get length() {return this.size;}// 封装私有方法：// 根据position 获取到当前节点（不是节点的value，而是获取节点）private getNode(position: number): Node<T> | null {let current = this.head;let index = 0;while (index++ < position && current) {current = current.next;}return current;}// 追加节点append(value: T) {// 1.根据value创建一个新节点const newNode = new Node(value);//  1. 链表本身为空，新添加数据时唯一的节点//  2. 链表本身不为空，需要向其他节点后面追加节点if (!this.head) {this.head = newNode;} else {let current = this.head;while (current.next) {current = current.next;}// current此时，肯定是指向最后一个节点current.next = newNode;}this.size++;}// 遍历链表的方法traverse() {const values: T[] = [];let current = this.head;while (current) {values.push(current.value);current = current.next;}console.log(values.join(' -> '));}// 插入 insert(position, element): 向链表的特定位置插入一个新的项;insert(value: T, position: number): boolean {if (position < 0 || position > this.size) return false;// 是否添加到第一个const newNode = new Node(value);if (position === 0) {newNode.next = this.head;this.head = newNode;} else {let previous = this.getNode(position - 1);// index === positionnewNode.next = previous?.next ?? null;previous!.next = newNode;}this.size++;return true;}// 根据位置删除removeAt(position: number): T | null {// 越界判断if (position < 0 || position >= this.size) return null;// 删除元素// 判断是否是删除第一个节点let current = this.head;if (position === 0) {this.head = this.head?.next ?? null;} else {// 重构let previous = this.getNode(position - 1);// index === positionprevious!.next = previous?.next?.next ?? null;}this.size--;return current?.value ?? null;}// 获取getget(position: number): T | null {if (position < 0 || position >= this.size) return null;// 查找元素return this.getNode(position)?.value ?? null;}// 更新update(value: T, position: number): boolean {if (position < 0 || position >= this.size) return false;const currentNode = this.getNode(position);currentNode!.value = value;return true;}// 获取索引indexOf(value: T): number {// 遍历let current = this.head;let index = 0;while (current) {if (current.value === value) {return index;}current = current.next;index++;}return -1;}// 根据value删除remove(value: T): T | null {const index = this.indexOf(value);return this.removeAt(index);}// 链表是否为空isEmpty(): boolean {return this.size === 0;}
}
const linkedList = new LinkedList<string>();
linkedList.append('aaa');
linkedList.append('bbb');
linkedList.append('ccc');linkedList.insert('abc', 0);
linkedList.insert('abcd', 0);linkedList.insert('中间444', 2);
linkedList.insert('nba', 6);
linkedList.traverse();linkedList.removeAt(0);
linkedList.traverse();
linkedList.removeAt(2);
linkedList.traverse();console.log('-----测试get-----');
console.log(linkedList.get(0));
console.log(linkedList.get(1));
console.log(linkedList.get(2));console.log('-----测试update-----');
console.log(linkedList.update('11111', 1));
linkedList.traverse();console.log('-----测试indexOf-----');
console.log(linkedList.indexOf('11111'));
linkedList.traverse();
export {};

链表常见的面试题

    1. 设计链表 https://leetcode.cn/problems/design-linked-list/

    • 你可以选择使用单链表或者双链表，设计并实现自己的链表。

    • 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

    • 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

    • 实现 MyLinkedList 类：

      • MyLinkedList() 初始化 MyLinkedList 对象。
      • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
      • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
      • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
      • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
      • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
class Node<T> {val: T;next: Node<T> | null = null;constructor(val: T) {this.val = val;}
}
class MyLinkedList<T> {private head: Node<T> | null = null;private size: number = 0;private getNode(index: number): Node<T> | null {let current = this.head;let i = 0;while (i++ < index && current) {current = current.next;}return current;}// int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。get(index: number): any {if (index < 0 || index >= this.size) {return -1;}return this.getNode(index)?.val ?? null;}addAtHead(val: T): void {const newNode = new Node(val);newNode.next = this.head;this.head = newNode;this.size++;}addAtTail(val: T): void {const newNode = new Node(val);if (!this.head) {this.head = newNode;} else {let current = this.head;while (current.next) {current = current.next;}// current此时，肯定是指向最后一个节点current.next = newNode;}this.size++;}addAtIndex(index: number, val: T): boolean {if (index < 0 || index > this.size) return false;const newNode = new Node(val);if (index === 0) {newNode.next = this.head;this.head = newNode;} else {let previous = this.getNode(index - 1);// index === positionnewNode.next = previous?.next ?? null;previous!.next = newNode;}this.size++;return true;}deleteAtIndex(index: number): T | null {if (index < 0 || index >= this.size) return null;// 删除元素// 判断是否是删除第一个节点let current = this.head;if (index === 0) {this.head = this.head?.next ?? null;} else {// 重构let previous = this.getNode(index - 1);// index === positionprevious!.next = previous?.next?.next ?? null;}this.size--;return current?.val ?? null;}
}
export {};
    1. 删除链表中的节点
    • https://leetcode.cn/problems/delete-node-in-a-linked-list/
      有一个单链表的 head，我们想删除它其中的一个节点 node。

    给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

    链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

    删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

    • 给定节点的值不应该存在于链表中。
    • 链表中的节点数应该减少 1。
    • node 前面的所有值顺序相同。
    • node 后面的所有值顺序相同。

    自定义测试：

    • 对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
    • 我们将构建链表，并将节点传递给你的函数。
    • 输出将是调用你函数后的整个链表。
class ListNode {val: number;next: ListNode | null;constructor(val?: number, next?: ListNode | null) {this.val = val === undefined ? 0 : val;this.next = next === undefined ? null : next;}
}
function deleteNode(node: ListNode | null): void {node!.val = node!.next!.val;node!.next = node!.next!.next;
}
export {};
    1. 反转链表
    • https://leetcode.cn/problems/reverse-linked-list/
    • 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
class ListNode {val: number;next: ListNode | null;constructor(val?: number, next?: ListNode | null) {this.val = val === undefined ? 0 : val;this.next = next === undefined ? null : next;}
}function reverseList(head: ListNode | null): ListNode | null {if (!head || !head.next) return head;const newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【音视频SDK测评】线上K歌软件开发技术选型

【音视频SDK测评】线上K歌软件开发技术选型

摘要 在线K歌软件的开发有许多技术难点&#xff0c;需考虑到音频录制和处理、实时音频传输和同步、音频压缩和解压缩、设备兼容性问题等技术难点外&#xff0c;此外&#xff0c;开发者还应关注音乐版权问题&#xff0c;确保开发的应用合规合法。 前言 前面写了几期关于直播 …
阅读更多...
[STL]详解list模拟实现

[STL]详解list模拟实现

[STL]list模拟实现 文章目录 [STL]list模拟实现1. 整体结构总览2. 成员变量解析3. 默认成员函数构造函数1迭代器区间构造函数拷贝构造函数赋值运算符重载析构函数 4. 迭代器及相关函数迭代器整体结构总览迭代器的模拟实现begin函数和end函数begin函数和end函数const版本 5. 数据…
阅读更多...
C语言指针详解

C语言指针详解

C语言指针详解 字符指针1.如何定义2.类型和指向的内容3.代码例子 指针数组1.如何定义2.类型和内容 数组指针1.如何定义2.类型和指向类型3.数组名vs&数组名数组指针运用 数组参数&指针参数一维数组传参二维数组传参一级指针传参二级指针传参 函数指针1.如何定义2.类型和…
阅读更多...
【前端知识】React 基础巩固(三十九)——React-Router的基本使用

【前端知识】React 基础巩固(三十九)——React-Router的基本使用

React 基础巩固(三十九)——React-Router的基本使用 一、Router的基本使用 Router中包含了对路径改变的监听&#xff0c;并且会将相应的路径传递给子组件。 Router包括两个API&#xff1a; BrowserRouter使用history模式 HashRouter使用hash模式&#xff08;路径后面带有#号…
阅读更多...
APP自动化测试-Python+Appium+Pytest+Allure框架实战封装（详细）

APP自动化测试-Python+Appium+Pytest+Allure框架实战封装（详细）

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 pytest只是单独的…
阅读更多...
无人驾驶实战-第五课（动态环境感知与3D检测算法）

无人驾驶实战-第五课（动态环境感知与3D检测算法）

激光雷达的分类&#xff1a; 机械式Lidar&#xff1a;TOF、N个独立激光单元、旋转产生360度视场 MEMS式Lidar&#xff1a;不旋转 激光雷达的输出是点云&#xff0c;点云数据特点&#xff1a; 简单&#xff1a;x y z i &#xff08;i为信号强度&#xff09; 稀疏&#xff1a;7%&…
阅读更多...
【工具】自动搜索Research网站的学术会议排名

【工具】自动搜索Research网站的学术会议排名

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] Research.com是一个可以搜索学术会议网站的影响因子的网站。 好用是好用&#xff0c;但有一个缺点&#xff1a;得手动选择类目。有这么多类目&#xff0c;一个个手动选也太累了。 所以做了一个自动搜索的小工具&a…
阅读更多...
HTTP杂谈之Referer和Origin请求头再探

HTTP杂谈之Referer和Origin请求头再探

一 关于Referer和Origin的汇总 1) 知识是凌乱的,各位看官看个热闹即可2) 内容不断更新1、理解有盲区,需要及时纠正2、内容交叉有重复,需要适当删减3、扩展视野3) 以下内容都与Referer和Origin请求头有关联 nginx防盗链 HTTP杂谈之Referrer-Policy响应头 iframe标签referre…
阅读更多...
新手入门Jenkins自动化部署入门详细教程

新手入门Jenkins自动化部署入门详细教程

1. 背景 在实际开发中&#xff0c;我们经常要一边开发一边测试&#xff0c;当然这里说的测试并不是程序员对自己代码的单元测试&#xff0c;而是同组程序员将代码提交后&#xff0c;由测试人员测试&#xff1b; 或者前后端分离后&#xff0c;经常会修改接口&#xff0c;然后重新…
阅读更多...
vue element el-upload附件上传、在线预览、下载当前预览文件

vue element el-upload附件上传、在线预览、下载当前预览文件

上传 在线预览&#xff08;iframe&#xff09;&#xff1a; payload&#xff1a; response&#xff1a; 全部代码&#xff1a; <template><div><el-table :data"tableData" border style"width: 100%"><el-table-column prop"d…
阅读更多...
.Net6 Core Web API 配置 log4net + MySQL

.Net6 Core Web API 配置 log4net + MySQL

目录 一、导入NuGet 包 二、添加配置文件 log4net.config 三、创建MySQL表格 四、Program全局配置 五、帮助类编写 六、效果展示 小编没有使用依赖注入的方式。 一、导入NuGet 包 ---- log4net 基础包 ---- Microsoft.Extensions.Logging.Log4Net…
阅读更多...
天线辐射机制

天线辐射机制

电磁场如何从源中产生并最终脱离天线辐射到自由空间中去的呢&#xff1f;让我们首先来研究一下一些基本的辐射源。 1、单线Single Wire 导线是一种电荷运动产生电流特性的材料&#xff0c;假设用qv&#xff08;库仑/m3&#xff09;表示的一个电体积电荷密度均匀分布在一个横截…
阅读更多...
ansible控制主机和受控主机之间免密及提权案例

ansible控制主机和受控主机之间免密及提权案例

目录 案例描述 环境准备 案例一--免密远程控制主机 效果展示&#xff1a; 解决方案 1.添加主机 2.通过ssh-key生成密钥对 3.生成ssh-copy-id 4.验证 案例二-----免密普通用户提权 效果展示 解决方案 1.使用普通用户&#xff0c;与案例一 一样&#xff0c;进行发送密钥…
阅读更多...
pytest 自定义HOOK函数

pytest 自定义HOOK函数

除了系统提过的HOOK函数外&#xff0c;也可以通过自定义HOOK的方式实现想要的功能。 首先创建一个py文件&#xff0c;里面定义自己的HOOK函数&#xff0c;主要pytest里面的hook函数必须以pytest开头。 #myhook.pydef pytest_myhook(user):"""自定义HOOK函数&q…
阅读更多...
【JavaEE初阶】Servlet(四) Cookie Session

【JavaEE初阶】Servlet(四) Cookie Session

文章目录 1. Cookie && Session1.1 Cookie && Session1.2 Servlet会话管理操作 1. Cookie && Session 1.1 Cookie && Session Cookie是什么? Cookie是浏览器提供的持久化存储数据的机制.Cookie从哪里来? Cookie从服务器返回给浏览器. 服务…
阅读更多...
中小企业如何做好MES管理系统实施建设

中小企业如何做好MES管理系统实施建设

中小企业在生产制造领域面临着诸多挑战&#xff0c;包括提升产品竞争力、规范生产制造等。为了应对这些挑战&#xff0c;越来越多的中小企业开始实施MES生产管理系统。然而&#xff0c;由于企业规模小、资源实力不足等原因&#xff0c;很多企业在实施MES管理系统时存在一定的困…
阅读更多...
opencv rtsp 硬件解码

opencv rtsp 硬件解码

讨论使用opencv的reader 硬件解码的方案有太多种&#xff0c;如果使用ffmpeg硬件解码是最方便的&#xff0c;不方便的是把解码过后的GPU 拉到 CPU 上&#xff0c;再使用opencv的Mat 从cpu 上上载到gpu上&#xff0c;是不是多了两个过程&#xff0c;应该是直接从GPU mat 直接去…
阅读更多...
腾讯测试大佬分享4个关于 Python 函数（方法）的冷知识

腾讯测试大佬分享4个关于 Python 函数（方法）的冷知识

关于参数标识 不知道大家在工作中有没有遇到一种情况&#xff0c;你的同事 A 写了一个方法给你调用&#xff0c;然后你调用时不知道该传什么参数&#xff0c;然后这个同事 A 还很 cao dan 的居然不加班&#xff01;你一脸茫然的看着这个方法&#xff0c;当你尝试传进去一个 ab…
阅读更多...
使用pg_prewarm缓存PostgreSQL数据库表

使用pg_prewarm缓存PostgreSQL数据库表

pg_prewarm pg_prewarm 直接利用系统缓存的代码,对操作系统发出异步prefetch请求&#xff0c;在应用中&#xff0c;尤其在OLAP的情况下&#xff0c;对于大表的分析等等是非常耗费查询的时间的&#xff0c;而即使我们使用select table的方式&#xff0c;这张表也并不可能将所有…
阅读更多...
后端整理（MySql）

后端整理（MySql）

1 事务 1.1 事务ACID原则 原子性&#xff08;Atomicity&#xff09; 事务的原子性指的是事务的操作&#xff0c;要么全部成功&#xff0c;要么全部失败回滚 一致性&#xff08;Consistency&#xff09; 事务的一致性是指事务必须使数据库从一个一致状态转变成另一个一致性…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023