数据结构与算法

算法(algorithm)

二分查找

基础版本

有左右两个指针,和一个中间指针。
对比中间值和目标值,如果
中间值比目标值小,则说明目标值在中间值的右侧,则将左指针移动到中间值+1的位置
目标值比中间值小,则说明目标值在中间值的左侧,则将右指针移动到中间值-1的位置
相等,则说明找到了目标值,返回下标即可。

public int search(int[] nums, int target) {
    int i = 0, j = nums.length - 1;
    while (i <= j) {   //当i > j时,会退出循环,就是没有找到。
        // >>> 无符号右移1位 等同于  除以2并向下取整   7 >>> 1 = 3
        int m = (i + j) >>> 1;
        if (target < nums[m]) {
            j = m - 1;
        } else if (nums[m] < target) {
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

平衡版本

不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的(通过 i)
i 指针可能是查找目标
j 指针不可能是查找目标
因为 1. 2. 3. 当区域内还剩一个元素时, 表示为 j - i == 1
改变 i 边界时, m 可能就是目标, 同时因为 2. 所以有 i=m
改变 j 边界时, m 已经比较过不是目标, 同时因为 3. 所以有 j=m
三分支改为二分支, 循环内比较次数减少

public static int binarySearchBalance(int[] a, int target) {
    int i = 0, j = a.length;
    while (1 < j - i) {         // 范围内待查找的元素个数 > 1 时
        int m = (i + j) >>> 1;
        if (target < a[m]) {    // 目标在左边
            j = m;
        } else {                // 目标在 m 或右边
            i = m;
        }
    }
    return target == a[i] ? i : -1;
}

左边界版本

二分查找 Leftmost,查找左侧第一个目标值的下标。

    public static int binarySearchLeftmost(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        //候选的位置
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                //记录候选位置
                candidate = m;
                //右指针左移,继续向左查找。
                j = m - 1;
            }
        }
        return candidate;
    }

右边界版本

二分查找 Rightmost,查找右侧第一个目标值的下标。

    public static int binarySearchRightmost(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        //候选的位置
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                //记录候选位置
                candidate = m;
                //右指针右移,继续向右查找。
                i = m + 1;
            }
        }
        return candidate;
    }

实际应用

二分查找

704. 二分查找

image.png

class Solution {
    public int search(int[] nums, int target) {
        int i = 0, j = nums.length;
        while (1 < j - i) {         // 范围内待查找的元素个数 > 1 时
            int m = (i + j) >>> 1;
            if (target < nums[m]) {    // 目标在左边
                j = m;
            } else {                // 目标在 m 或右边
                i = m;
            }
        }
        return target == nums[i] ? i : -1;
    }
}

在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

image.png

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = left(nums,target);
        if(left == -1 ){
            return new int[]{-1,-1};
        }
        return new int[]{left,right(nums,target)};
    }

    public int left(int[] nums, int target){
        int i = 0, j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate; 
    }
    public int right(int[] nums, int target){
        int i = 0, j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }
}

搜索插入位置

35. 搜索插入位置

image.png

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return i;
    }
}

回溯算法

动态规划

贪心算法

哈希算法

递归

概述

定义

计算机科学中,递归是一种解决计算问题的方法,其中解决方案取决于同一类问题的更小子集

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

比如单链表递归遍历的例子:

void f(Node node) {
    if(node == null) {
        return;
    }
    println("before:" + node.value)
    f(node.next);
    println("after:" + node.value)
}

说明:

  1. 自己调用自己,如果说每个函数对应着一种解决方案,自己调用自己意味着解决方案是一样的(有规律的)
  2. 每次调用,函数处理的数据会较上次缩减(子集),而且最后会缩减至无需继续递归
  3. 内层函数调用(子集处理)完成,外层函数才能算调用完成

原理

假设链表中有 3 个节点,value 分别为 1,2,3,以上代码的执行流程就类似于下面的伪码

// 1 -> 2 -> 3 -> null  f(1)

void f(Node node = 1) {
    println("before:" + node.value) // 1
    void f(Node node = 2) {
        println("before:" + node.value) // 2
        void f(Node node = 3) {
            println("before:" + node.value) // 3
            void f(Node node = null) {
                if(node == null) {
                    return;
                }
            }
            println("after:" + node.value) // 3
        }
        println("after:" + node.value) // 2
    }
    println("after:" + node.value) // 1
}

思路

  1. 确定能否使用递归求解
  2. 推导出递推关系,即父问题与子问题的关系,以及递归的结束条件

例如之前遍历链表的递推关系为

  • 深入到最里层叫做
  • 从最里层出来叫做
  • 的过程中,外层函数内的局部变量(以及方法参数)并未消失,的时候还可以用到

的过程就是上一句调用方法执行结束之后)

单路递归 Single Recursion

阶乘

用递归方法求阶乘

  • 阶乘的定义 ,其中 为自然数,当然
  • 递推关系

代码

private static int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n - 1);
}

拆解伪码如下,假设 n 初始值为 3

f(int n = 3) { // 解决不了,递
    return 3 * f(int n = 2) { // 解决不了,继续递
        return 2 * f(int n = 1) {
            if (n == 1) { // 可以解决, 开始归
                return 1;
            }
        }
    }
}

反向打印字符串

用递归反向打印字符串,n 为字符在整个字符串 str 中的索引位置

  • :n 从 0 开始,每次 n + 1,一直递到 n == str.length() - 1
  • :从 n == str.length() 开始归,从归打印,自然是逆序的

递推关系
![](https://www.yuque.com/api/services/graph/generate_redirect/latex?f(n)%20%3D%20%0A%5Cbegin%7Bcases%7D%0A%E5%81%9C%E6%AD%A2%20%26%20n%20%3D%20str.length()%20%5C%5C%0Af(n%2B1)%20%26%200%20%5Cleq%20n%20%5Cleq%20str.length()%20-%201%0A%5Cend%7Bcases%7D%0A#card=math&code=f%28n%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0A%E5%81%9C%E6%AD%A2%20%26%20n%20%3D%20str.length%28%29%20%5C%5C%0Af%28n%2B1%29%20%26%200%20%5Cleq%20n%20%5Cleq%20str.length%28%29%20-%201%0A%5Cend%7Bcases%7D%0A&id=fpk56)
代码为

public static void reversePrint(String str, int index) {
    if (index == str.length()) {
        return;
    }
    reversePrint(str, index + 1);
    System.out.println(str.charAt(index));
}

拆解伪码如下,假设字符串为 "abc"

void reversePrint(String str, int index = 0) {
    void reversePrint(String str, int index = 1) {
        void reversePrint(String str, int index = 2) {
            void reversePrint(String str, int index = 3) { 
                if (index == str.length()) {
                    return; // 开始归
                }
            }
            System.out.println(str.charAt(index)); // 打印 c
        }
        System.out.println(str.charAt(index)); // 打印 b
    }
    System.out.println(str.charAt(index)); // 打印 a
}

多路递归 Multi Recursion

斐波那契数列

  • 之前的例子是每个递归函数只包含一个自身的调用,这称之为 single recursion
  • 如果每个递归函数例包含多个自身调用,称之为 multi recursion
递推关系

下面的表格列出了数列的前几项

_F_0 _F_1 _F_2 _F_3 _F_4 _F_5 _F_6 _F_7 _F_8 _F_9 _F_10 _F_11 _F_12 _F_13
0 1 1 2 3 5 8 13 21 34 55 89 144 233
实现
public static int f(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}
执行流程
  • 绿色代表正在执行(对应递),灰色代表执行结束(对应归)
  • 递不到头,不能归,对应着深度优先搜索

2.gif

时间复杂度
  • 递归的次数也符合斐波那契规律,
  • 时间复杂度推导过程
    • 斐波那契通项公式
    • 简化为:#card=math&code=f%28n%29%20%3D%20%5Cfrac%7B1%7D%7B2.236%7D%2A%28%7B1.618%7D%5En%20-%20%7B%28-0.618%29%7D%5En%29&id=gcxm5)
    • 带入递归次数公式 -1#card=math&code=2%2A%5Cfrac%7B1%7D%7B2.236%7D%2A%28%7B1.618%7D%5E%7Bn%2B1%7D%20-%20%7B%28-0.618%29%7D%5E%7Bn%2B1%7D%29-1&id=n0MbW)
    • 时间复杂度为
  1. 更多 Fibonacci 参考[8][9][^10]
  2. 以上时间复杂度分析,未考虑大数相加的因素

兔子问题

image.png

  • 第一个月,有一对未成熟的兔子(黑色,注意图中个头较小)
  • 第二个月,它们成熟
  • 第三个月,它们能产下一对新的小兔子(蓝色)
  • 所有兔子遵循相同规律,求第 个月的兔子数

分析
兔子问题如何与斐波那契联系起来呢?设第 n 个月兔子数为

  • = 上个月兔子数 + 新生的小兔子数
  • 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
  • 因为需要一个月兔子就成熟,所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
  • 上个月兔子数,即
  • 上上个月的兔子数,即

因此本质还是斐波那契数列,只是从其第一项开始

青蛙爬楼梯

70. 爬楼梯

  • 楼梯有
  • 青蛙要爬到楼顶,可以一次跳一阶,也可以一次跳两阶
  • 只能向上跳,问有多少种跳法

分析

n 跳法 规律
1 (1) 暂时看不出
2 (1,1)  (2) 暂时看不出
3 (1,1,1)  (1,2)  (2,1) 暂时看不出
4 (1,1,1,1)    (1,2,1)    (2,1,1)
(1,1,2)  (2,2) 最后一跳,跳一个台阶的,基于f(3)
最后一跳,跳两个台阶的,基于f(2)
5 ... ...
  • 因此本质上还是斐波那契数列,只是从其第二项开始
  • 对应 leetcode 题目

递归优化

记忆法

上述代码存在很多重复的计算,例如求 f(5) 递归分解过程

image.png

可以看到(颜色相同的是重复的):

  • f(3) 重复了 2 次
  • f(2) 重复了 3 次
  • f(1) 重复了 5 次
  • f(0) 重复了 3 次

随着 n 的增大,重复次数非常可观,如何优化呢?
Memoization 记忆法(也称备忘录)是一种优化技术,通过存储函数调用结果(通常比较昂贵),当再次出现相同的输入(子问题)时,就能实现加速效果,改进后的代码

public static void main(String[] args) {
    int n = 13;
    int[] cache = new int[n + 1];
    Arrays.fill(cache, -1);
    cache[0] = 0;
    cache[1] = 1;
    System.out.println(f(cache, n));
}

public static int f(int[] cache, int n) {
    if (cache[n] != -1) {
        return cache[n];
    }

    cache[n] = f(cache, n - 1) + f(cache, n - 2);
    return cache[n];
}

优化后的图示,只要结果被缓存,就不会执行其子问题

  • 改进后的时间复杂度为 O(n)
  • 请自行验证改进后的效果
  • 请自行分析改进后的空间复杂度

注意

  1. 记忆法是动态规划的一种情况,强调的是自顶向下的解决
  2. 记忆法的本质是空间换时间

尾调用

如果函数的最后一步是调用一个函数,那么称为尾调用,例如

function a() {
    return b()
}

下面三段代码不能叫做尾调用

function a() {
    const c = b()
    return c
}
  • 因为最后一步并非调用函数
function a() {
    return b() + 1
}
  • 最后一步执行的是加法
function a(x) {
    return b() + x
}
  • 最后一步执行的是加法

C++,Scala语言可以优化尾调用,将递归运算优化为线性运算。因为前一个函数其实已经执行完毕了。
没优化之前的伪码

function a() {
    return function b() {
        return function c() {
            return 1000
        }
    }
}

优化后伪码如下

a()
b()
c()

实际应用

汉诺塔

面试题 08.06. 汉诺塔问题 - 力扣(LeetCode)

image-20230830105250837
image-20230830112132314

由图可以分析得知,当有四个盘子时,需要做的步骤为:

  1. 圆盘123 a -> b
  2. 圆盘 4 a -> c
  3. 圆盘123 b -> c

而第一步,圆盘123 a -> b 又可以分为

  1. 圆盘12 a -> b
  2. 圆盘 3 a -> c
  3. 圆盘12 b -> c

由此可见,每一部操作都可以分为三个步骤,三个步骤中的第一步和第三部又可以继续往下分,因此可以将大问题分割为多个同样的小问题。代码如下

public static void exchange(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
        if (n == 0){
            return;
        }
        //三个柱子分别扮演的角色为,源柱子,借用柱子,目标柱子
        //进来之后,总共n个圆盘,分成三步
        //1.将n-1块盘子,从a,借助c,移动到b
        exchange(n - 1, a, c, b);
        //2.将a的最底下的盘子移动到c
        //这一步其实是最关键的移动步骤:
        // 是将源柱子的最上面一个方块,移动到临时柱子,或者,将临时柱子上的方块移动到目标柱子。
        // 通过不断地变换源柱子,借用柱子,目标柱子,实现移位。
        c.add(a.remove(a.size() - 1));
        //3.将n-1块盘子,从b,借助a,移动到c
        exchange(n - 1, b, a, c);
    }

杨辉三角

118. 杨辉三角 - 力扣(LeetCode)

分析

image-20230830142421441

把它斜着看↙ ↙ ↙ ↙ ↙

j             0   1   2  3   4
i           ↙  ↙  ↙  ↙  ↙
0          1
1        1   1
2      1   2   1
3    1   3   3   1
4  1   4   6   4   1
  • 行 $i$,列 $j$,那么 $[i][j]$ 的取值应为 $[i-1][j-1] + [i-1][j]$
  • 当 $j=0$ 或 $i=j$ 时,$[i][j]$ 取值为 $1$

代码实现

    public static int get(int[][] array, int i, int j) {
        if (array[i][j] != 0) {
            return array[i][j];
        }
        if (j == 0 || i == j) {
            return 1;
        }
        int res = get(array, i - 1, j - 1) + get(array, i - 1, j);
        array[i][j] = res;
        return res;
    }

    public static List<List<Integer>> generate(int numRows) {
        //存储单个步骤生成的结果,避免不必要地重复运算。
        int[][] array = new int[numRows][numRows];
        ArrayList<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            ArrayList<Integer> integers = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                integers.add(get(array, i, j));
            }
            lists.add(integers);
        }
        return lists;
    }

排序

字符串操作

数据结构(Data Structure)

数组

普通数组

定义

在计算机科学中,数组是由一组元素(值或变量)组成的数据结构,每个元素有至少一个索引或键来标识。

索引

因为数组内的元素是连续存储的,所以数组中元素的地址,可以通过其索引计算出来,例如:

int[] array = {1,2,3,4,5}

知道了数组的数据起始地址 ,就可以由公式 计算出索引 元素的地址

  • 即索引,在 Java、C 等语言都是从 0 开始
  • 是每个元素占用字节,例如
  • 小测试
byte[] array = {1,2,3,4,5}

已知 array 的数据的起始地址是 0x7138f94c8,那么元素 3 的地址是什么?

答:0x7138f94c8 + 2 * 1 = 0x7138f94ca

空间占用

Java 中数组结构为

image.png

  • 8 字节 markword
  • 4 字节 class 指针(压缩 class 指针的情况),标记当前数组的类型,例如int[].class
  • 4 字节 数组大小(决定了数组最大容量是
  • 数组元素 + 对齐字节java 中所有对象大小都是 8 字节的整数倍[^12],不足的要用对齐字节补足

例如:int[] array = {1, 2, 3, 4, 5};的大小为 40 个字节,组成如下:

8 + 4 + 4 + 5*4 + 4(alignment) //不补齐的话大小为36,不是8的整数倍,再补4 -> 40就可以。

性能

即根据索引查找元素,时间复杂度是

动态数组

定义

底层也是使用数组来实现,只不过自己手动实现了数组的扩容。当容量达到阈值的时候就扩容为原来的1.5倍。

/**
 * 自己实现动态数组
 *
 * @author XuYang
 * @date 2023/8/25 15:27
 */
public class MyArrayList implements Iterable<Integer> {

    private int size = 0;
    private int capacity = 8;
    private int[] array = {};

    /**
     * 在最后插入
     */
    public void addLast(int element) {
        add(size, element);
    }

    /**
     * 在指定下标插入
     */
    public void add(int index, int element) {

        checkAndGrow();
        if (index >= 0 && index < size) {
            //源数组,源数组起始位置,目标数组,目标数组的位置,拷贝多少元素?
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    /**
     * 动态扩容
     */
    public void checkAndGrow() {
        if (size == 0) {
            array = new int[capacity];
        } else if (size == capacity) {
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }

    /**
     * 删除元素并返回删除的元素值
     */
    public int remove(int index) {
        int removed = array[index];
        if (index < size - 1) {
            System.arraycopy(array, index + 1, array, index, size - index - 1);
        }
        size--;
        return removed;
    }

    /**
     * get
     */
    public int get(int index) {
        return array[index];
    }

    /**
     * 普通遍历方式
     */
    public void foreach() {
        for (int i = 0; i < size; i++) {
            System.out.println(array[i]);
        }
    }

    /**
     * 函数式接口遍历
     */
    public void foreach(Consumer<Integer> consumer) {
        for (int i = 0; i < size; i++) {
            consumer.accept(array[i]);
        }
    }

    /**
     * 实现Iterator接口后就可以使用for i : array这种写法
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;

            /**
             * 有没有下个元素
             */
            @Override
            public boolean hasNext() {
                return i < size;
            }

            /**
             * 获取当前元素并移动到下个元素
             */
            @Override
            public Integer next() {
                return array[i++];
            }
        };
    }

    /**
     * stream遍历
     */
    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }

    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(5);
        list.addLast(6);
        list.addLast(7);
        list.addLast(8);
        list.addLast(9);
        list.addLast(10);

//        list.foreach(System.out::println);

//        for (Integer i : list) {
//            System.out.println(i);
//        }

        list.stream().forEach(System.out::println);
    }
}

性能

插入和删除:

  • 头部位置,时间复杂度是 O(n)
  • 中间位置,时间复杂度是 O(n)
  • 尾部位置,时间复杂度是 O(1)

访问都是 O(1)

链表

概述

定义

在计算机科学中,链表是数据元素的线性集合,其每个元素都指向下一个元素,元素存储上并不连续
可以分为:

  • 单向链表,每个元素只知道其下一个元素是谁

image.png

  • 双向链表,每个元素知道其上一个元素和下一个元素

image.png

  • 循环链表,通常的链表尾节点 tail 指向的都是 null,而循环链表的 tail 指向的是头节点 head

image.png

链表内还有一种特殊的节点称为哨兵(Sentinel)节点,也叫做哑元( Dummy)节点,它不存储数据,通常用作头尾,用来简化边界判断,如下图所示:

image.png

性能

根据 index 查找,时间复杂度
插入或删除:

  • 起始位置:
  • 结束位置:如果已知 tail 尾节点是 ,不知道 tail 尾节点是
  • 中间位置:根据 index 查找时间 +

单向链表

public class MyLinkedListSingly implements Iterable<Integer> {
    private Node head;

    /**
     * 使用-静态-内部类,尽量对外减少暴露
     * 静态:能加static表示内部类不需要使用外部资源。
     */
    private static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 头插法
     */
    public void addFirst(int value) {
        //1.链表为空和链表非空都适用
        head = new Node(value, head);
    }

    /**
     * 尾插法
     */
    public void addLast(int value) {
        Node last = findLast();
        if (last == null) {
            addFirst(value);
            return;
        }
        last.next = new Node(value, null);
    }

    /**
     * while遍历
     */
    public void loop(Consumer<Integer> consumer) {
        Node pointer = head;
        while (pointer != null) {
            consumer.accept(pointer.value);
            pointer = pointer.next;
        }
    }

    /**
     * for遍历
     */
    public void foreach(Consumer<Integer> consumer) {
        for (Node p = head; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }

    /**
     * 迭代器遍历
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head;

            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int v = p.value;
                p = p.next;
                return v;
            }
        };
    }

    /**
     * 递归遍历
     */
    public void recursionNode() {
        recursionNode(head);
    }

    private void recursionNode(Node p) {
        if (p == null) {
            return ;
        }
        System.out.println(p.value);
        recursionNode(p.next);
    }

    /**
     * 查找尾部元素
     */
    private Node findLast() {
        if (head == null) {
            return null;
        }
        Node p;
        for (p = head; p.next != null; p = p.next) {
        }
        return p;
    }

    /**
     * 根据索引查询节点
     */
    private Node findNode(int index) {
        int i = 0;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    /**
     * 根据索引获取值
     */
    public int get(int index) {
        Node node = findNode(index);
        if (node == null) {
            throw new IllegalArgumentException("索引不合法!");
        }
        return node.value;
    }

    /**
     * 根据索引插入
     */
    public void insert(int index, int value) {
        if (index == 0) {
            addFirst(value);
            return;
        }
        Node preNode = findNode(index - 1);
        if (preNode == null) {
            throw new IllegalArgumentException("索引不合法!");
        }
        preNode.next = new Node(value, preNode.next);
    }

    /**
     * 删除第一个节点
     */
    public void removeFirst() {
        if (head == null) {
            throw new IllegalArgumentException("链表为空!");
        }
        head = head.next;
    }

    /**
     * 根据索引删除
     */
    public void remove(int index) {
        if (index == 0) {
            removeFirst();
            return;
        }
        Node preNode = findNode(index - 1);
        if (preNode == null) {
            throw new IllegalArgumentException("被删除的上一个节点为空!");
        }
        Node removed = preNode.next;
        if (removed == null) {
            throw new IllegalArgumentException("被删除的节点为空!");
        }
        preNode.next = removed.next;
    }

    /**
     * 反转链表
     */
    public void reverse() {
        if (head == null || head.next == null) {
            return;
        }
        Node p = head.next;
        Node newHead = head;
        while (p != null) {
            head.next = p.next;
            p.next = newHead;
            newHead = p;
            p = head.next;
        }
        head = newHead;
    }

    public static void main(String[] args) {
        MyLinkedListSingly singly = new MyLinkedListSingly();
        singly.addLast(10);
        singly.addLast(20);
        singly.addLast(30);
        singly.addLast(40);
        singly.remove(4);
        singly.recursionNode();
    }
}

单向链表-带哨兵

主要就是将头节点设置为一个无意义的节点,节省对头结点判断的代码。

public class MyLinkedListSinglySentinel implements Iterable<Integer> {

    /**
     * 先给head添加一个无意义的节点,这样就不用判断头结点是否为空了
     * 省去一些判断临界值的步骤。
     */
    private Node head = new Node(666, null);

    public static void main(String[] args) {
        MyLinkedListSinglySentinel singly = new MyLinkedListSinglySentinel();

        singly.addFirst(10);
        singly.addFirst(20);
        singly.addFirst(30);
        singly.addFirst(40);
        singly.removeFirst();
        singly.recursionNode();
    }

    /**
     * 头插法
     */
    public void addFirst(int value) {
        //1.链表为空和链表非空都适用
        insert(0,value);
    }

    /**
     * 尾插法
     */
    public void addLast(int value) {
        Node last = findLast();
        last.next = new Node(value, null);
    }

    /**
     * while遍历
     */
    public void loop(Consumer<Integer> consumer) {
        Node pointer = head.next;
        while (pointer != null) {
            consumer.accept(pointer.value);
            pointer = pointer.next;
        }
    }

    /**
     * for遍历
     */
    public void foreach(Consumer<Integer> consumer) {
        for (Node p = head.next; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }

    /**
     * 迭代器遍历
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head;

            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int v = p.value;
                p = p.next;
                return v;
            }
        };
    }

    /**
     * 递归遍历
     */
    public void recursionNode() {
        recursionNode(head.next);
    }

    private Node recursionNode(Node p) {
        if (p == null) {
            return null;
        }
        System.out.println(p.value);
        return recursionNode(p.next);
    }

    /**
     * 查找尾部元素
     */
    private Node findLast() {
        Node p;
        for (p = head; p.next != null; p = p.next) {
        }
        return p;
    }

    /**
     * 根据索引查询节点
     */
    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    /**
     * 根据索引获取值
     */
    public int get(int index) {
        Node node = findNode(index);
        if (node == null) {
            throw new IllegalArgumentException("索引不合法!");
        }
        return node.value;
    }

    /**
     * 根据索引插入
     */
    public void insert(int index, int value) {
        Node preNode = findNode(index - 1);
        if (preNode == null) {
            throw new IllegalArgumentException("索引不合法!");
        }
        preNode.next = new Node(value, preNode.next);
    }

    /**
     * 删除第一个节点
     */
    public void removeFirst() {
        remove(0);
    }

    /**
     * 根据索引删除
     */
    public void remove(int index) {
        Node preNode = findNode(index - 1);
        if (preNode == null) {
            throw new IllegalArgumentException("被删除的上一个节点为空!");
        }
        Node removed = preNode.next;
        if (removed == null) {
            throw new IllegalArgumentException("被删除的节点为空!");
        }
        preNode.next = removed.next;
    }

    /**
     * 使用-静态-内部类,尽量对外减少暴露
     * 静态:能加static表示内部类不需要使用外部资源。
     */
    private static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

}

双向链表-带哨兵

public class MyLinkedListBidirectional implements Iterable<Integer> {

    Node head;
    Node tail;

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    private static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    public MyLinkedListBidirectional() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.prev = head;
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    public void addFirst(int value) {
        insert(0, value);
    }

    public void insert(int index, int value) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw new IllegalArgumentException("索引不合法!");
        }
        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;
    }

    public int remove(int index) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw new IllegalArgumentException("索引不合法!");
        }
        Node removed = prev.next;
        if (removed == tail) {
            throw new IllegalArgumentException("索引不合法!");
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;
        return removed.value;
    }

    public void addLast(int value) {
        Node prev = tail.prev;
        Node added = new Node(prev, value, tail);
        prev.next = added;
        tail.prev = added;
    }

    public int removeLast() {
        Node removed = tail.prev;
        if (removed == head) {
            throw new IllegalArgumentException("链表为空!");
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
        return removed.value;
    }

    public static void main(String[] args) {
        MyLinkedListBidirectional list = new MyLinkedListBidirectional();
        list.addLast(5);
        list.addLast(4);
        list.addLast(3);
        list.addLast(2);
        list.addLast(1);
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

}

双向环形链表

public class MyLinkedListDoubly implements Iterable<Integer>{
    private Node sentinel = new Node(null, -1, null);

    public MyLinkedListDoubly() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new IterableIter<Integer>() {
            Node p = sentinel.next;
            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    private static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    public void addFirst(int value){
        Node added = new Node(sentinel, value, sentinel.next);
        sentinel.next = added;
        sentinel.next.prev = added;
    }

    public void addLast(int value) {
        Node added = new Node(sentinel.prev, value, sentinel);
        sentinel.prev.next = added;
        sentinel.prev = added;
    }

    public void removeFirst(){
        Node removed = sentinel.next;
        sentinel.next = removed.next;
        removed.next.prev = sentinel;
    }

    public void removeLast(){
        Node removed = sentinel.prev;
        removed.prev.next = sentinel;
        sentinel.prev = removed.prev;
    }
    public void removeByValue(int value) {
        Node node = findByValue(value);
        if (node == null){
            return;
        }
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private Node findByValue(int value){
        Node p = sentinel.next;
        while (p != sentinel) {
            if (p.value == value){
                return p;
            }
            p = p.next;
        }
        return null;
    }
    public static void main(String[] args) {
        MyLinkedListDoubly list = new MyLinkedListDoubly();
        list.addLast(5);
        list.addLast(4);
        list.addLast(3);
        list.addLast(2);
        list.removeByValue(3);
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

}

实际应用

反转单向链表

206. 反转链表 - 力扣(LeetCode)

image-20230830170837700

public class ReverseSinglyLinkedList {
    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 1.依次取出元素,放到新链表的头部。
     */
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        ListNode p = head;
        while (p != null) {
            //新建一个节点,指向上一个旧的newHead
            newHead = new ListNode(p.val, newHead);
            p = p.next;
        }
        return newHead;
    }

    /**
     * 2.从链表的第二个节点开始取,取到了就放到头上,取不到证明结束
     */
    public ListNode reverseList2(ListNode head) {

        if (head == null || head.next == null) { // 不足两个节点
            return head;
        }
        //从链表的第二个节点开始依次往后取,取出来放到最前面。然后让第一个节点指向第三个。
        //p 依次表示第二\第三\第四\...节点
        ListNode p = head.next;
        //newHead表示新的头节点,一开始,newHead和head是同一个,到了后面,head会往后走,newHead保持最前面。
        ListNode newHead = head;
        while (p != null) {
            //这里的这个head变量,实际意义已经不再代表头节点了,他始终只代表原始的头结点,这个头节点一直被往后挤,他更大的意义是在于
            //表示p的前一个节点,然后让head指向p的下一个,把p抽出来。
            head.next = p.next;
            //将p节点放到最新的头节点之前
            p.next = newHead;
            //更新newHead,现在p是newHead。
            newHead = p;
            //p继续往后走。head的next在前面已经指向p的后一个。
            p = head.next;
        }
        return newHead;

    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public ListNode removeFirst() {
            ListNode removed = head;
            if (head != null) {
                head = head.next;
            }
            return removed;
        }

        public void addFirst(ListNode node) {
            node.next = head;
            head = node;
        }
    }

    /**
     * 3.构造List集合,一边删除一边添加
     */
    public ListNode reverseList3(ListNode head) {
        List oldList = new List(head);
        List newList = new List(null);
        ListNode firstNode;
        while ((firstNode = oldList.removeFirst()) != null) {
            newList.addFirst(firstNode);
        }
        return newList.head;
    }

   /**
     * 4.把链表1的头,不断插入新链表的头。
     */
    public ListNode reverseList4(ListNode head) {
        if (head == null || head.next == null) { // 不足两个节点
            return head;
        }
        ListNode newHead = null;
        ListNode p = head;
        while (p != null) {
            ListNode nextNode = p.next;
            p.next = newHead;
            newHead = p;
            p = nextNode;
        }
        return newHead;
    }
}

根据值删除节点

203. 移除链表元素 - 力扣(LeetCode)

image-20230831100039543

public class RemoveNodeByValue {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }

    public ListNode removeElements(ListNode head, int val) {
        //本质就是一前一后两个指针,比如,p1,p2
        //p2在前面走,如果遇到目前值就删了目标值,再往前走一步,
        //如果没有遇到目标值,p1p2一起往前。
        //单向链表加了哨兵后可以避免处理特殊情况,如删除第一个head节点。
        ListNode sentinel = new ListNode(0, head);
        ListNode p1 = sentinel;
        ListNode p2 = sentinel.next;
        while (p2 != null) {
            if (p2.val == val){
                //p2指向的节点值==目标值,删除p2指向的节点
                p1.next = p2.next;
            }else {
                //p2指向的节点值!=目标值,让p1,往前走一步
                p1 = p2;
            }
            //不管相等与否,p2都得往前走一步。
            p2 = p2.next;
        }
        return sentinel.next;
    }
    /**
     * 递归方法,
     * 每个节点的处理方式是一样的,所以先专注处理单个节点。
     * 如果当前节点等于val,那就不管了,让当前节点.next去当头结点再去执行。
     * 如果当前阶段不等于val,那我就是新的头,就应该返回我,但是应该更新一下我的next去执行,我的next=f(我.next, val);
     */
    public ListNode removeElements1(ListNode head, int val) {
        if (head == null){
            return null;
        }
        if (head.val == val){
            return removeElements1(head.next, val);
        }else {
            head.next = removeElements1(head.next, val);
            return head;
        }
    }
}

删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)

image-20230831145020598

public class RemoveNodeFromEnd {
    /**
     * 递归
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1, head);
        recursion(sentinel, n);
        return sentinel.next;
    }

    public int recursion(ListNode p, int n) {
        if (p == null) {
            return 0;
        }
        int nth = recursion(p.next, n);
        if (nth == n) {
            p.next = p.next.next;
        }
        return nth + 1;
    }

    /**
     * 快慢指针法
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(0, head);
        ListNode p1 = sentinel;
        ListNode p2 = sentinel;
        //多走n+1步,这样p1就会在removed节点之前停下,如果正好走n步,那p1就会指向removed,这样就不知道removed前面是谁,没法删除。
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }
        //两个一起向前走,走到快指针==null
        while (p2 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        //此处p1指removed的前一个节点,p1.next = p1.next.next就删掉了removed
        p1.next = p1.next.next;
        return sentinel.next;
    }
}

删除排序链表中的重复元素-保留一个重复值

83. 删除排序链表中的重复元素

image-20230831152038908

public class RemoveDuplicatesReserve {

    /**
     * 双指针,同步指针
     * p1,p2
     * p1和p2相同时,p1不动,p1的指向后一个,p2往后走一步
     * 不同时,一起往前走一步。
     */
    public static ListNode deleteDuplicates(ListNode head) {
        //如果不带哨兵就判断一下节点不足的情况
        if (head == null || head.next == null) {
            return head;
        }
        //带哨兵的话,得让哨兵的值跟案例的值不同,按理说是个bug
        //ListNode sentinel = new ListNode(Integer.MIN_VALUE, head);
        ListNode p1 = head;
        ListNode p2 = head.next;
        while (p2 != null){
            if (p1.val == p2.val){
                p1.next = p2.next;
            }else {
                p1 = p1.next;
            }
            p2 = p2.next;
        }
        //这里能直接返回,是因为没有去动head本身,都是在循环的向后去找。然后修改指向关系,所以直接返回就可以。
        return head;
    }

    /**
     * 递归
     * 递归函数负责返回:从当前节点(我)开始,完成去重的链表
     * 1. 若我与 next 重复,返回 next
     * 2. 若我与 next 不重复,返回我,但 next 应当更新
     */
    public static ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        if (head.val == head.next.val){
            return deleteDuplicates1(head.next);
        }else {
            head.next = deleteDuplicates1(head.next);
            return head;
        }
    }
}

删除排序链表中的重复元素-不保留重复值

82. 删除排序链表中的重复元素 II - 力扣(LeetCode)

image-20230831162837247

public class RemoveDuplicatesNotReserve {

    /**
     * 三个指针,p1指向removed前一个,p2指向removed,p3指向removed的后一个,一直移动到不是removed
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode sentinel = new ListNode(-1, head);
        ListNode p1 = sentinel;
        ListNode p2, p3;
        while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
            if (p2.val == p3.val) {
                while ((p3 = p3.next) != null && p3.val == p2.val) {
                }
                p1.next = p3;
            } else {
                p1 = p1.next;
            }
        }
        return sentinel.next;
    }
}

队列

暂无评论

发送评论 编辑评论


				
下一篇