秋招小白学数据结构-1-数据结构前置知识

一.冒泡排序的时间复杂度

时间复杂度是默认最坏情况下的运算次数

思路：一个数组需要从无序状态变成由小到大排序，比如{9，1，5，8，3，7，4，6，2}，9和1先比较 小的换到前面去，然后9和5在比较，这样下去直到和2比较，最后最大的数字9就被换到了最后一个。这个数组有九（n）个数字，那么这一趟排序下来就比较了8次（n-1）

确定轮数：轮数是由要比较的轮数确定的 每次都有一个最大的数字安顿在最后 那么最后只剩一个数字的时候（在最前面那个）就没人和他作比较了。所以需要作比较的轮数就是n-1轮

确定每一轮的比较次数：第一次是n个数字 每两个位置之间画弧线表示比较，那就是要比较n-1次。第二次就是n-1个数字，比较n-2次，这样下去最后一次比较肯定是只比较两个数字，就是1次

那么总的比较次数就是：n-1 + n-2 +...+1 比较轮数是n-1次

这是一个等差数列，首项加末项乘以项数除以二，得到：

复杂度：也就是O(n^2)

代码分析：

“外层循环次数” ≠ “有效操作次数”

• 表面代码：外层循环语法上是 n 次。
• 实际逻辑：只有前 n-1次外层循环产生了 “比较 / 交换” 操作，第 n 次是 “无效轮次”。因为第n次是end=1,此时内循环的i=1 不满足i<end

• 外层循环：用变量 end 标记未排序部分的末尾索引。初始时 end = array.length，表示整个数组都是未排序的；每轮结束后，最大的数字被安顿在最后。end 减 1，排除已冒泡到末尾的元素。end表示数组未排序元素的个数 
• 内层循环：只遍历未排序部分 数组下标[0, end)，比较相邻元素并交换。这样的话未排序数组最后一个元素的下标是end-1,i表示两两比较的右边那个数字的下标，则i最大满足i<end
• 如图：
• 

优化：提前终止排序

如果数组已经有序（或者某一轮比较后发现没有交换操作），就没必要继续循环了。代码里用 boolean sorted = true; 标记是否发生交换，若一轮内层循环后 sorted 还是 true，说明数组已经有序，直接 break 跳出外层循环，减少不必要的比较，这是对冒泡排序的效率优化，让最好情况（数组本身有序）的时间复杂度降到 O(n) 。

二、二分法查找的时间复杂度

最差的情况是最后一个才被找到 这就是n/x=1的意思

n是元素的个数，将x=2^y带入n/x=1得2^y=n,

y是查找次数 也就是时间复杂度 y=log2为底数的n

代码：

三、递归的时间复杂度

1.阶乘

复杂度：(n-1)*1  ->  n 

2.斐波那契数列：

f(n-0):运算一次 2的0次方

f(n-1)这行：运算两次 2的1次方

f(n-2)这行：运算四次 2的2次方

f(1)=f(n-（n-1）) 所以这一行运算2的n-1次方次

 四、空间复杂度

1.冒泡排序（bubbleSort）

核心逻辑：原地交换相邻元素，把大的 “冒泡” 到末尾，最多额外用几个临时变量（比如 end、sorted、交换时的临时存储 ）。

空间复杂度分析：
不管数组多大（n 多长），额外占用的空间就固定几个变量（end 是 int、sorted 是 boolean、交换用的临时变量也是基本类型 ），不会随 n 变大而增加。所以空间复杂度是 O(1)（常数阶，和数据规模无关 ）。

2.斐波那契数组（fibonacci 函数，返回数组那种）

核心逻辑：创建一个长度为 n+1 的数组 fibArray，存每个斐波那契数（fibArray[0] 到 fibArray[n] ）。

空间复杂度分析：
数组长度是 n+1，额外空间随 n 线性增长（n 越大，数组越长，占空间越多 ）。所以空间复杂度是 O(n)（线性阶，和数据规模 n 成正比 ）。

3.递归阶乘（factorial 递归实现）

核心逻辑：递归调用 factorial(N-1)，每次递归会在调用栈里存一份当前的方法上下文（比如参数 N、返回地址等 ）。

空间复杂度分析：
递归最深会到 N 层（比如算 factorial(5)，会递归到 factorial(4)→factorial(3)→…→factorial(1) ），调用栈里最多同时有 N 层递归的 “上下文”。所以空间复杂度是 O(n)（n 是输入的 N，栈空间随 n 线性增长 ）。

简单总结：

• 冒泡排序：额外空间固定 → O(1)
• 斐波那契数组：额外空间随 n 线性增长（数组长度 ）→ O(n)
• 递归阶乘：调用栈深度随 n 线性增长 → O(n)

 五、包装类

• 缓存范围：默认 -128 到 127（可通过 JVM 参数调整上限，但下限固定 -128 ），这个区间的整数会提前创建好 Integer 对象，存在 IntegerCache.cache 数组里复用。
• 超出范围：像 200 不在 [-128, 127] ，每次 valueOf 都会 new Integer(i) ，生成新对象。

在 Java 中，基本数据类型（如int、double、boolean等）对应的有包装类（如Integer、Double、Boolean等）。装箱和拆箱描述了基本数据类型和其包装类之间的转换过程

显示装箱

• 定义：显式装箱是指通过调用包装类的构造方法或者valueOf方法，将基本数据类型的值显式地转换为对应的包装类对象。
• 示例代码：

// 使用valueOf方法进行装箱
int num= 20;
Integer integer= Integer.valueOf(num); 

• 原理：以Integer为例，valueOf方法内部会先判断传入的整数值是否在IntegerCache缓存范围内（默认为 -128 到 127 ），如果在这个范围内，就直接返回缓存中的Integer对象；如果不在，则创建一个新的Integer对象。这样做可以在一定程度上提高性能，减少不必要的对象创建。

隐式装箱

• 定义：隐式装箱是 Java 5 引入的新特性，允许编译器自动将基本数据类型转换为对应的包装类对象，不需要显式地调用构造方法或valueOf方法。在需要使用包装类对象的地方，直接传入基本数据类型的值，编译器会在背后自动完成装箱操作。
• 示例代码：

int num3 = 30;
// 隐式装箱，编译器自动将int类型的num3转换为Integer对象
Integer integer3 = num3; // 在方法调用中使用隐式装箱
List<Integer> integerList = new ArrayList<>();
integerList.add(40); // 这里40是int类型，会自动装箱为Integer

• 原理：编译器在编译阶段，会在代码中插入相应的装箱方法调用（如Integer.valueOf），来完成基本数据类型到包装类对象的转换。从开发者的角度看，代码更加简洁，不需要手动编写装箱代码。

拆箱

• 定义：拆箱是将包装类对象转换为对应的基本数据类型值的过程，同样也分为显式拆箱和隐式拆箱。显式拆箱需要调用包装类的xxxValue方法（xxx代表对应的基本数据类型，如intValue、doubleValue等），隐式拆箱则是由编译器自动完成。
• 示例代码：

// 显式拆箱
Integer integer4 = 50;
int num4 = integer4.intValue(); // 隐式拆箱
Integer integer5 = 60;
// 在需要基本数据类型的地方，编译器自动将Integer对象integer5拆箱为int类型
int sum = integer5 + 10; 

• 原理：对于显式拆箱，调用xxxValue方法会直接返回包装类对象中存储的基本数据类型值。隐式拆箱时，编译器在编译阶段会在代码中插入相应的拆箱方法调用，从而实现将包装类对象转换为基本数据类型值。

注意事项

• 空指针异常：在进行拆箱操作时，如果包装类对象为null，会抛出NullPointerException。因此在进行拆箱之前，最好先进行null检查。

Integer integer = null;
// 下面这行代码会抛出NullPointerException
// int num = integer.intValue(); 
if (integer != null) {int num = integer.intValue();
}

• 性能影响：虽然装箱和拆箱操作带来了编程的便利性，但频繁的装箱和拆箱会有一定的性能开销，因为涉及到对象的创建和销毁。在性能敏感的场景下，需要谨慎使用。

六、泛型

这段 Java 代码展示了泛型（Generics） 的基本用法，核心是让类 / 方法能适配不同数据类型，同时保证类型安全。

1.为什么需要泛型？

直接用 Object[] 存数据，取出时要手动强转，还可能因类型不匹配报错（比如存 String 取 Integer ）。泛型的作用是让容器 / 类提前约定类型，编译期就能检查类型错误，减少强转代码。

2.代码里的泛型设计

1. 泛型类定义：class MyArray <T>

• <T> 是类型参数（也叫类型变量），代表 “任意类型”，定义类时是占位符，用的时候（比如 MyArray<Integer>）再确定具体类型（Integer）。
• 作用：让 MyArray 类能适配不同类型（Integer、String 等），不用为每种类型写一套类。

2. 泛型方法：setValue 和 getValue

• setValue(int pos, T val)：参数 val 类型是 T，和类的泛型类型绑定。存数据时，编译器会检查 val 类型是否符合 MyArray<T> 的 T，保证类型安全。
• getValue(int pos)：返回值类型是 T，取出数据时自动强转为 T（代码里 return (T)array[pos] ），调用方不用手动强转（如 int a = myArray.getValue(1) 直接用 int 接收）。

3. 泛型的实际使用：

// 创建存 Integer 类型的数组
MyArray<Integer> myArray = new MyArray<>(); 
myArray.setValue(0, 10); // 存 Integer，符合 T=Integer
int a = myArray.getValue(1); // 取出自动转 Integer → 拆箱为 int// 创建存 String 类型的数组
MyArray<String> myArray2 = new MyArray<>(); 
myArray2.setValue(0, "abcd"); // 存 String，符合 T=String
String ret = myArray2.getValue(1); // 取出自动转 String

• MyArray<Integer> 里，T 被替换成 Integer，所有 T 的位置都用 Integer 约束。
• MyArray<String> 同理，T 替换成 String，保证存、取的类型一致。

4.泛型的底层原理（类型擦除）

Java 的泛型是编译期特性，编译后字节码里没有 <T> ，会被替换成 Object（即 “类型擦除”）。比如：

• 编译后 MyArray 的 array 还是 Object[]，但编译器会在编译期检查类型，确保存、取时类型匹配。
• getValue 里的 (T)array[pos] ，编译后是 (Object)array[pos] ，但运行时会根据 T 实际类型强转（如果类型不匹配，运行时抛 ClassCastException ）。

5.泛型的好处

1. 类型安全：编译期检查类型，避免运行时因类型不匹配报错（比如存 String 取 Integer ，编译直接报错）。
2. 简化代码：不用手动频繁强转，代码更简洁（对比直接用 Object[] 存数据，取时要 (Integer)array[0] ）。
3. 通用性：一套类 / 方法适配多种类型，减少重复代码（比如 MyArray 既存 Integer 又存 String ）。

 七、String引用类型

题1：

1. 初始阶段：创建 Example ex

• 堆内存：
  • 新建 Example 对象（地址 0x18），包含：
    • str 成员变量：指向 String 对象（内容 "good"，地址 0x77 ）。
    • ch 成员变量：指向 char 数组（内容 ['a','b','c']，地址 0x99 ）。
• 栈内存：main 方法里的 ex 变量，存 Example 对象地址 0x18。

2. 调用 ex.change(ex.str, ex.ch)

传参时，实参的 “引用值（地址）” 会复制给形参：

• 形参 str（方法内的局部变量）：复制 ex.str 的地址 0x77，指向 "good"。
• 形参 ch（方法内的局部变量）：复制 ex.ch 的地址 0x99，指向 ['a','b','c']。

3. 执行 change 方法内的逻辑

• str = "test ok";：
  String 是不可变对象，str = "test ok" 会新建一个 String 对象（内容 "test ok"，地址 0x88 ），并让形参 str 指向新地址。此时：

  • 形参 str 指向 0x88（不再关联 ex.str 的 0x77 ）。
  • 实参 ex.str 仍指向 0x77（不受影响）。

• ch[0] = 'g';：
  char 数组是可变对象，形参 ch 存的是数组地址 0x99。通过 ch[0] = 'g' 修改的是地址 0x99 对应的数组内容。此时：

  • 数组内容从 ['a','b','c'] 变成 ['g','b','c']。
  • 实参 ex.ch 指向的也是 0x99，所以实参会同步变化。

4. 方法执行完毕，回到 main

• 形参 str、ch 出栈销毁，不影响实参。
• 打印 ex.str（仍指向 0x77，值为 "good" ）和 ex.ch（数组内容已改，值为 ['g','b','c'] ）。

题2：

这段 Java 代码是一个名为 Solution 的类，其中 countSegments 方法用于统计字符串 s 中连续非空字符段（以空格分隔）的数量，以下逐行详细解释：

类与方法定义

class Solution {public int countSegments(String s) {

• 定义了一个名为 Solution 的类，类中包含一个公共的（public）、返回值为 int 类型的方法 countSegments，该方法接收一个 String 类型的参数 s，用于处理和统计字符串中的字符段信息。

空字符串处理

if(s.length() == 0) {return 0;
}

• 首先检查输入字符串 s 的长度，如果长度为 0（即空字符串），直接返回 0，表示没有字符段。

分割字符串

String[] ret = s.split(" ");

• 使用 split 方法，以空格（" "）作为分隔符，将字符串 s 分割成若干子字符串，并把这些子字符串存储在字符串数组 ret 中。
  • 例如，若 s 是 "Hello world "（末尾有多个空格 ），split 后 ret 可能是 ["Hello", "world", "", ""]（连续的空格会分割出空字符串 ）。

统计有效字符段

int count = 0;
for(String s1 : ret) {if(s1.length() != 0) {count++;}
}

• 初始化一个计数器 count 为 0，用于记录有效字符段的数量。
• 通过增强 for 循环遍历字符串数组 ret 中的每个元素 s1：
  • 检查 s1 的长度是否不为 0，如果是，说明这是一个有效的非空字符段，将 count 加 1。
  • 这样就可以过滤掉 split 方法因连续空格产生的空字符串，只统计真正有内容的字符段。

题3：

包含两个方法，用于实现判断字符是否为大写字母以及将字符串中的大写字母转换为小写字母的功能，以下逐部分详细解释：

isUpper 方法

public boolean isUpper(char ch) {if(ch >= 'A' && ch <= 'Z') {return true;}return false;
}

• 方法作用：判断传入的字符 ch 是否是大写英文字母。
• 参数：char ch，表示要判断的单个字符。
• 逻辑：
  • 通过比较字符 ch 的 ASCII 码范围，判断是否在 'A'（ASCII 码 65 ）到 'Z'（ASCII 码 90 ）之间。
  • 如果在这个范围内，说明是大写字母，返回 true；否则返回 false 。

toLowerCase 方法

public String toLowerCase(String s) {StringBuffer stringBuffer = new StringBuffer();for(int i = 0;i < s.length();i++) {char ch = s.charAt(i);if(isUpper(ch)) {ch = (char)(ch + 32);stringBuffer.append(ch);} else {stringBuffer.append(ch);}}return stringBuffer.toString();
}

• 方法作用：将传入的字符串 s 中的所有大写英文字母转换为小写，其他字符（如小写字母、数字、符号等）保持不变，最后返回转换后的字符串。
• 参数：String s，表示要处理的原始字符串。
• 逻辑拆解：

  • 初始化 StringBuffer：

    StringBuffer stringBuffer = new StringBuffer();
    

    创建一个 StringBuffer 对象 stringBuffer，用于动态拼接字符（因为 String 本身是不可变的，用 StringBuffer 拼接更高效 ）。

  • 遍历字符串：

    for(int i = 0;i < s.length();i++) {char ch = s.charAt(i);
    

    通过 for 循环遍历字符串 s 的每个字符，每次取出一个字符 ch（用 charAt(i) 获取索引 i 位置的字符 ）。

  • 判断并转换字符：

    if(isUpper(ch)) {ch = (char)(ch + 32);stringBuffer.append(ch);
    } else {stringBuffer.append(ch);
    }
    

• 调用 isUpper(ch) 方法判断当前字符是否是大写字母。
• 如果是大写字母，利用ASCII 码的规律（大写字母 + 32 等于对应的小写字母，如 'A' + 32 = 'a' ），将 ch 转换为小写（(char)(ch + 32) 强制类型转换为 char ），再添加到 stringBuffer 中。
• 如果不是大写字母（比如本身就是小写、数字、符号等 ），直接将原字符 ch 添加到 stringBuffer 中。

八、泛型的上边界

【1】泛型类

这段 Java 代码结合泛型边界实现了一个通用的 “查找数组最大值” 功能，既体现了泛型的灵活性，又通过边界约束保证逻辑合法性。

一、代码逐行讲解（泛型类 + 方法实现）

1. 泛型类定义：class Alg<T extends Comparable<T>>

• 泛型边界（<T extends Comparable<T>>）：
  要求类型 T 必须实现 Comparable 接口（Comparable 是 Java 里用于 “可比较类型” 的接口，实现它的类必须重写 compareTo 方法 ）。
  作用：保证传入的 T 类型支持比较操作（因为后面要用 max.compareTo(...) ），否则编译器直接报错。

• 通俗理解：Alg 类是个 “泛型工具箱”，但只允许放入能自己比较大小的类型（如 Integer、String 等，这些类默认实现了 Comparable ）。

2. 方法 findMaxValue(T[] array)

public T findMaxValue(T[] array) {T max = array[0]; // 假设第一个元素是最大值（初始值）for (int i = 1; i < array.length; i++) {// 核心：用 compareTo 比较大小if (max.compareTo(array[i]) < 0) { max = array[i]; // 发现更大的值，更新 max}}return max;
}

• 逻辑：
  • 先把数组第一个元素 array[0] 设为 max（初始最大值 ）。
  • 遍历数组剩余元素，用 max.compareTo(array[i]) 比较：
    • 返回值 < 0 → max 比 array[i] 小 → 更新 max 为 array[i]。
    • 返回值 >= 0 → max 大于等于 array[i] → 不更新。
  • 遍历结束后，max 就是数组里的最大值。

3. 测试类 Test2

public class Test2 {public static void main(String[] args) {// 创建 Alg<Integer> 对象：T 被指定为 IntegerAlg<Integer> alg = new Alg<>(); Integer[] integers = {1,2,3,4,5,6,7};// 调用方法，返回 Integer 类型的最大值Integer ret = alg.findMaxValue(integers); System.out.println(ret); // 输出 7}
}

• 关键点：
  • Alg<Integer> 中，T 具体化为 Integer。因为 Integer 实现了 Comparable<Integer> 接口，满足泛型边界 T extends Comparable<T>。
  • 运行后，findMaxValue 会遍历数组 {1,2,3,4,5,6,7}，找到最大值 7 并输出。

二、泛型边界的核心作用（为什么需要 extends Comparable<T>）

1. 保证类型安全：
   如果没有边界约束（比如写成 class Alg<T> ），传入的 T 可能不支持 compareTo 方法。例如，若传入自定义类 Dog（没实现 Comparable ），调用 max.compareTo(...) 会直接编译报错。
   加上 T extends Comparable<T> 后，编译器会强制检查 T 是否具备 “可比较” 的能力，提前避免运行时错误。

2. 明确功能依赖：
   泛型边界清晰告诉使用者：“这个 Alg 类的方法需要类型 T 能比较大小，所以传入的类型必须实现 Comparable”。代码可读性和健壮性更高。

三、泛型边界的其他常见用法

除了 <T extends Comparable<T>>，Java 泛型边界还有这些形式：

• 多边界约束：class Alg<T extends Comparable<T> & Serializable>（T 需同时实现 Comparable 和 Serializable 接口 ）。
• 通配符边界：List<? extends Number>（集合里的元素必须是 Number 或其子类，如 Integer、Double ）。

这段代码的核心是：

• 用泛型类 Alg<T> 实现 “通用找最大值” 逻辑，适配多种类型。
• 用泛型边界 T extends Comparable<T> 约束 T 必须支持比较，保证 compareTo 方法能合法调用。

本质是通过泛型 + 边界，让代码既通用又安全，避免了重复写 “Integer 找最大值”“String 找最大值” 等重复逻辑，也提前拦截了类型不兼容的错误～

【2】泛型方法

 之前的 Alg<T> 是泛型类（类级别声明泛型 T ），而这里的 findMaxValue 是泛型方法（方法级别声明泛型 T ）。

• 泛型类：泛型参数作用于整个类，所有方法共享同一个 T。
• 泛型方法：泛型参数仅作用于当前方法，更灵活（类可以是非泛型类，方法自己声明泛型 ）。

九、静态泛型方法

简单说，泛型方法就是 “给方法单独开一个泛型通道”，让方法能像 “迷你泛型工具” 一样，灵活处理不同类型～

一、核心优势：无需创建对象，直接调用

静态方法属于类本身，不属于任何实例。静态泛型方法可以直接通过类名调用，无需先创建对象，更适合工具类（如 Collections.sort、Arrays.asList 等）。

public class GenericUtils {// 静态泛型方法：交换数组中两个元素的位置public static <T> void swap(T[] array, int i, int j) {T temp = array[i];array[i] = array[j];array[j] = temp;}
}// 直接通过类名调用，无需创建 GenericUtils 对象
Integer[] arr = {1, 2, 3};
GenericUtils.swap(arr, 0, 2); // 交换索引 0 和 2 的元素

二、与实例泛型方法的对比

三、静态泛型方法的典型场景

1. 集合工具类（如 java.util.Collections）

public class Collections {// 静态泛型方法：二分查找public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {// ...}
}// 使用示例
List<Integer> list = Arrays.asList(1, 3, 5);
int index = Collections.binarySearch(list, 3); // 直接通过类名调用

2. 数组工具类（如 java.util.Arrays）

public class Arrays {// 静态泛型方法：将数组转为 Listpublic static <T> List<T> asList(T... a) {return new ArrayList<>(a);}
}// 使用示例
String[] arr = {"a", "b", "c"};
List<String> list = Arrays.asList(arr); // 直接通过类名调用

3. 工厂方法（创建泛型对象）

public class Pair<K, V> {private K key;private V value;private Pair(K key, V value) {this.key = key;this.value = value;}// 静态泛型工厂方法：简化对象创建public static <K, V> Pair<K, V> of(K key, V value) {return new Pair<>(key, value);}
}// 使用示例：无需显式指定泛型类型（类型推导）
Pair<String, Integer> pair = Pair.of("age", 25); // 自动推导 K=String, V=Integer