hello算法笔记 01

只看不记不练我会忘光光，这里随便记一下，不在于格式，希望日积月累算法至少要入门。

1 Java 链表学习

一、需要补充的基础概念

1. Java 无显式指针，但有 “对象引用”

   • 关键区别：Java 没有 C/C++ 中 */& 这样的显式指针语法，但对象引用（如 ListNode next）本质等价于 “安全指针”
   • 作用：通过引用（next）建立节点间的关联，实现链表的链式结构，避免野指针、越界等风险
   • 示例：node1.next = node2 表示让 node1 的 next 引用指向 node2 对象，和指针 “指向节点” 逻辑完全一致

2. 链表不能像数组直接初始化

   • 错误写法：ListNode list = [1,11,2]（Java 不支持这种链表字面量初始化）【是的，这是我一开始犯的错】
   • 正确步骤：
     1. 先创建单个节点对象（new ListNode(值)）
     2. 通过 next 引用手动连接节点（node1.next = node2; node2.next = node3）
   • 本质原因：链表是 “离散节点通过引用连接”，数组是 “连续内存块”，存储结构不同导致初始化方式不同

3. 链表遍历的核心逻辑（不能用固定次数循环）

   • 错误思路：for (int i=0; i<长度; i++)（链表无内置 “长度” 属性，无法提前知道循环次数）
   • 正确方式：while (当前节点 != null) 循环
     • 用临时变量 current 遍历（避免修改原头节点 head）
     • 步骤：打印当前节点值 → current = current.next 移动到下一个节点 → 直到 current 为 null（链表结尾）

二、新学习到的实用技能

1. 链表节点类（ListNode）的标准定义

   • 必须包含两个核心成员：
     • int val：存储当前节点的数据（可根据需求改为 String/Object 等类型）
     • ListNode next：存储下一个节点的引用（默认值为 null，表示链表结尾）
   • 必须有构造方法：ListNode(int val) { this.val = val; this.next = null; }，用于创建节点时直接赋值

2. 链表的基础操作实现

   操作功能	实现核心逻辑
   查找目标值索引	遍历链表，用 index 记录位置，找到匹配值返回 index，遍历结束未找到返回 -1
   打印整个链表	用 current 临时节点遍历，非尾节点打印 值 -> ，尾节点只打印值
   插入节点（中间位置）	新节点 next 指向原后续节点 → 原前驱节点 next 指向新节点（顺序不能反）
   （示例：1→11→2 插入 4）	node2_3.next = node2; node1.next = node2_3 → 最终 1→4→11→2

3. 链表操作的注意事项

   • 操作时保护头节点：遍历 / 查找时用 current = head 临时变量，不要直接修改 head（否则会丢失链表起始位置）
   • 插入 / 删除节点时注意 “引用指向顺序”：先处理新节点的 next，再处理原节点的 next（避免节点丢失）
   • 判空处理：遍历前先判断 head == null（空链表），避免 NullPointerException

三、代码示例（整合所有知识点）

java

运行

public class ListNodeTest {
    // 1. 标准链表节点类定义（static修饰：内部类可在main中直接使用）
    static class ListNode {
        int val;          // 节点数据
        ListNode next;    // 指向 next 节点的引用

        // 构造方法：创建节点时赋值
        ListNode(int val) {
            this.val = val;
            this.next = null; // 默认为null，可不写，但显式声明更清晰
        }
    }

    // 2. 查找目标值首个出现的索引
    public static int findTargetIndex(ListNode head, int target) {
        if (head == null) return -1; // 空链表直接返回-1
        int index = 0;
        ListNode current = head;     // 临时节点遍历，保护head
        while (current != null) {
            if (current.val == target) {
                return index;        // 找到目标，返回当前索引
            }
            current = current.next;  // 移动到下一个节点
            index++;                 // 索引自增
        }
        return -1;                   // 遍历结束未找到
    }

    // 3. 打印整个链表
    public static void printList(ListNode head) {
        if (head == null) {          // 处理空链表情况
            System.out.println("链表为空");
            return;
        }
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            // 非尾节点打印 " -> "
            if (current.next != null) {
                System.out.print(" -> ");
            }
            current = current.next;
        }
        System.out.println(); // 换行，优化格式
    }

    // 4. 主方法：测试所有功能
    public static void main(String[] args) {
        // 步骤1：创建节点
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(11);
        ListNode node3 = new ListNode(2);

        // 步骤2：连接节点，形成初始链表：1 -> 11 -> 2
        node1.next = node2;
        node2.next = node3;

        // 步骤3：打印初始链表
        System.out.print("初始链表：");
        printList(node1);

        // 步骤4：插入新节点（1 -> 4 -> 11 -> 2）
        ListNode node4 = new ListNode(4);
        node1.next = node4;    // 原前驱节点（node1）指向新节点
        node4.next = node2;    // 新节点指向原后续节点（node2）

        // 步骤5：打印修改后链表
        System.out.print("插入节点后：");
        printList(node1);

        // 步骤6：查找目标值
        int target = 11;
        int index = findTargetIndex(node1, target);
        if (index != -1) {
            System.out.println("目标值 " + target + " 的索引：" + index);
        } else {
            System.out.println("未找到目标值 " + target);
        }
    }
}

四、核心逻辑总结

• 链表的本质：离散节点 + 引用连接，所有操作都围绕 “修改引用指向” 展开
• 关键思想：用 current 临时节点遍历，保护头节点；用 current != null 判断链表结尾
• 常见错误：直接修改 head 导致链表丢失、初始化时用数组语法、插入节点时顺序颠倒【全是我踩到的坑】

2 Python 链表（与 Java 思路对比）

【也是类似的吧，要def一个链表。】

一、核心共性：链表的本质逻辑一致

无论是 Java 还是 Python，链表的核心都是 “节点对象 + 引用连接”，不存在语言层面的 “内置链表”，都需要手动定义节点类。主要共性：

1. 节点类必须包含两个核心属性：
   • 存储数据的值（Java 中是 int val，Python 中可动态类型，如 self.val）
   • 指向下一个节点的引用（Java 中是 ListNode next，Python 中是 self.next，默认 None 对应 Java 的 null）
2. 链表操作（创建、遍历、查找、插入）的逻辑完全相同：
   • 不能像数组一样用 [1,11,2] 直接初始化，必须逐个创建节点并连接
   • 遍历靠 while current is not None（对应 Java 的 while (current != null)），不能用固定次数循环

二、Python 链表完整代码（对应你的 Java 逻辑）

下面的代码实现了 “创建链表、插入节点、打印链表、查找目标值”，和你之前 Java 代码的功能完全一致：

python

运行

# 1. 定义链表节点类（对应 Java 的 static class ListNode）
class ListNode:
    def __init__(self, val):  # 对应 Java 的构造方法
        self.val = val        # 存储节点数据（Python 动态类型，可存int/str等）
        self.next = None      # 指向下一个节点的引用，默认None（对应Java的null）


# 2. 打印链表（对应 Java 的 printList 方法）
def print_list(head):
    current = head  # 临时节点遍历，保护头节点（和Java逻辑一致）
    while current is not None:
        print(current.val, end="")  # 打印当前节点值
        if current.next is not None:
            print(" -> ", end="")   # 非尾节点加箭头
        current = current.next      # 移动到下一个节点
    print()  # 换行


# 3. 查找目标值的首个索引（对应 Java 的 find 方法）
def find_target_index(head, target):
    if head is None:  # 处理空链表
        return -1
    index = 0
    current = head
    while current is not None:
        if current.val == target:
            return index  # 找到目标，返回索引
        current = current.next
        index += 1
    return -1  # 未找到


# 4. 主逻辑（对应 Java 的 main 方法）
if __name__ == "__main__":
    # 步骤1：创建节点（和Java new ListNode(值) 逻辑一致）
    node1 = ListNode(1)
    node2 = ListNode(11)
    node3 = ListNode(2)

    # 步骤2：连接节点，形成初始链表：1 -> 11 -> 2
    node1.next = node2
    node2.next = node3

    # 打印初始链表
    print("初始链表：", end="")
    print_list(node1)

    # 步骤3：插入新节点（1 -> 4 -> 11 -> 2）
    node4 = ListNode(4)
    node1.next = node4    # 原前驱（node1）指向新节点
    node4.next = node2    # 新节点指向原后续（node2）—— 顺序不能反！

    # 打印修改后的链表
    print("插入节点后：", end="")
    print_list(node1)

    # 步骤4：查找目标值
    target = 11
    index = find_target_index(node1, target)
    if index != -1:
        print(f"目标值 {target} 的索引：{index}")
    else:
        print(f"未找到目标值 {target}")

三、Python 与 Java 的语法差异（重点对比）

虽然逻辑一致，但 Python 语法更简洁，主要差异如下表：

四、运行结果（和 Java 完全一致）

执行上述 Python 代码，输出如下：

plaintext

初始链表：1 -> 11 -> 2
插入节点后：1 -> 4 -> 11 -> 2
目标值 11 的索引：2

总结

Python 实现链表的核心逻辑和 Java 完全相同：都是先定义节点类，再通过 “引用连接节点”，遍历 / 查找靠 while 循环判断 None。唯一需要适应的是 Python 的语法细节（如 __init__ 构造方法、is not None 判空、无静态类修饰等），上手成本很低！

3 java的list列表

/* 初始化列表 */
// 无初始值
List<Integer> nums1 = new ArrayList<>();
// 有初始值（注意数组的元素类型需为 int[] 的包装类 Integer[]）
Integer[] numbers = new Integer[] { 1, 3, 2, 5, 4 };
List<Integer> nums = new ArrayList<>(Arrays.asList(numbers));

【为什么要这么包装类？】

在 Java 中，Arrays.asList() 方法的参数要求是一个对象数组（泛型数组），而不是基本类型数组。这与 Java 的泛型机制和自动装箱 / 拆箱特性有关：

1. 泛型不支持基本类型：
   Java 的泛型只支持对象类型（引用类型），不支持 int、double 等基本类型。List<Integer> 中的元素必须是 Integer 类型（int 的包装类）。

2. Arrays.asList () 的限制：
   当你传入基本类型数组（如 int[]）时，Arrays.asList() 会将整个数组当作一个元素处理，返回 List<int[]> 类型，而不是你期望的 List<Integer>。

3. 为什么使用 Integer []：
   当使用 Integer[] 时，Arrays.asList() 会正确识别每个元素为 Integer 类型，返回 List<Integer>，这样才能正确初始化 ArrayList<Integer>。

如果直接使用 int[] 会导致类型不匹配：

int[] numbers = {1, 3, 2, 5, 4};
// 错误：会得到 List<int[]> 而不是 List<Integer>
List<Integer> nums = new ArrayList<>(Arrays.asList(numbers)); 

因此，必须使用包装类数组 Integer[] 才能通过 Arrays.asList() 正确创建 List<Integer> 集合。

【我感觉就是用泛型包装数组，然后调用array.aslist方法创建list 的，而不是像python一样直接写list？】

你提到的 Java 中用泛型包装数组、通过 Arrays.asList 方法创建 List，和 Python 直接用 list 构建列表的差异，本质是两种语言设计理念、类型系统不同导致的，展开说说它们的区别和背后逻辑：

1. Java 为啥要 “麻烦” 包装 + Arrays.asList

• 泛型只支持对象类型：
  Java 的泛型是 “伪泛型”（编译期擦除），且泛型参数不能用基本类型（如 int、double ）。所以想创建元素是数值的 List，得用 Integer 包装类，把 int[] 转成 Integer[] 才能适配 List<Integer> 。
  比如：

  // 必须用包装类数组
  Integer[] arr = {1, 2, 3}; 
  List<Integer> list = Arrays.asList(arr);
  

• Arrays.asList 的作用：
  它负责把数组转换为固定大小的 List 视图（基于原数组，修改会影响彼此），让数组能以集合的形式操作。但因为 Java 严格区分基本类型和包装类型，所以必须用包装类数组做参数。

2. Python list 为啥更 “直接”

• 动态类型 + 自动装箱：
  Python 是动态类型语言，没有 “基本类型 vs 包装类型” 的区分，数值、字符串等都是对象。创建列表时，直接写 [1, 2, 3] ，Python 会自动处理元素的类型，无需手动 “包装”。
  比如：

  # 直接创建，无需额外操作
  my_list = [1, 2, 3]  
  

• 语言设计哲学：
  Python 追求 “简洁、可读性优先”，语法尽可能贴近自然语言，所以用直观的 list 字面量就能创建列表，减少开发者的心智负担。

3. 两种方式的核心差异总结

4. 怎么选？根据语言场景来

• Java：虽然麻烦，但静态类型能在编译期提前发现类型错误，适合大型、要求严谨的项目；
• Python：简洁高效，适合快速开发、脚本场景，用起来更 “无负担”。

简单说，Java 是为了类型安全和框架适配，不得不 “麻烦”；Python 是为了易用性，把复杂逻辑藏在语法糖里。理解这点，就能明白为啥 Java 要 “包装数组 + Arrays.asList” 啦～

【不过我说的对吗，是这样的吧，一开始创建的是泛型数组而不是list列表？】

你的理解方向是对的，但可以更精准地拆解 Java 里数组转 List 这件事的细节：

1. 核心区别：数组 ≠ List（结构和特性不同）

• 数组（比如 Integer[]）：
  是 Java 里的固定长度、直接内存存储的结构，声明后长度不能变，访问通过索引，语法是 [] 。
  比如 Integer[] arr = {1,2,3}; ，它是 “静态” 容器，更贴近内存层面的连续存储。

• List（比如 List<Integer>）：
  是 Java 集合框架里的动态容器，支持增删、迭代器等丰富操作，语法是用 .add() .get() 等方法。
  比如 List<Integer> list = new ArrayList<>(); ，它是 “动态” 容器，更贴近业务开发的灵活需求。

2. Arrays.asList(...) 到底做了什么？

它不是 “创建泛型数组”，而是把数组转换成 List 的 “视图”：

• 传 Integer[] 进去，得到的 List 会复用原数组的内容（修改 List 会影响原数组，反之亦然）；
• 这个 List 是固定长度的（不能 add/remove 改变大小），因为本质是数组的 “包装”。

比如：

java

运行

Integer[] arr = {1,2,3};
List<Integer> list = Arrays.asList(arr);

list.set(0, 100); 
System.out.println(arr[0]); // 输出 100，因为共享内容

// 会报错！因为数组长度固定，List 也不能扩容
list.add(4); 

3. 为啥必须用 Integer[] 而不是 int[]？

这是 Java 泛型不支持基本类型 导致的：

• List<int> 是不合法的！泛型参数必须是 “对象类型”，所以只能用 Integer 包装类；
• 如果传 int[] 给 Arrays.asList，会变成 List<int[]>（把整个数组当一个元素），完全不符合预期。

比如：

java

运行

int[] arr = {1,2,3};
// 这里得到的是 List<int[]>，而不是 List<Integer>！
List<int[]> wrongList = Arrays.asList(arr); 

4. 和 Python list 的本质差异

Python 的 list 是原生支持动态扩容、灵活操作的容器，语法上直接 [1,2,3] 就能创建，不需要 “数组转容器” 的过程。

而 Java 里：

• 数组是更底层的结构，List 是高层的集合框架；
• 你需要主动用 Arrays.asList 做 “桥接”，才能让数组用 List 的方式操作（虽然有诸多限制）。

总结一下你的理解修正：

→ 不是 “创建泛型数组”，而是用泛型包装的数组（Integer[]），通过 Arrays.asList 转换成 List 视图。

→ 核心是 Java 里数组和 List 是两套体系，需要工具方法桥接，而 Python 把 “动态列表” 直接做成了语法原生支持的结构～