跳至主要內容

 

labuladong约 3358 字大约 11 分钟

提示

我的网站解法代码现已支持了所有主流编程语言,包括 Java、Python、C++、JavaScript 和 Go,不过依然建议你简单了解一下 Java 语言,因为其他语言都是我用 chatGPT 从 Java 翻译过去的,如果偶尔遇到错误可能需要你对照理解 Java 的代码逻辑。

目前我的算法教程基本上都是用 Java 语言写的代码,主要有以下几个原因:

1、Java 是强类型语言。因为我们就是要学习运用各种数据结构写算法嘛,所以清楚地知道每个变量是什么类型非常重要,方便你 debug,也方便 IDE 进行语法检查。如果是 Python 这样的动态语言,每个变量的类型不明显,可能有碍大家的理解。

2、Java 这种语言中规中矩,没有什么花里胡哨的语言特性。即便你之前没学过 Java 语言,单看代码也能轻易地理解逻辑。所以如果你有其他比较熟悉的语言,完全可以把我的代码思路用自己的语言实现。

另外,抛开算法不谈,单就编程技术的学习来说,我也建议大家多学习几门语言,尤其是像 Java 这种使用非常广泛的语言。因为任何人的职业生涯都不可能只用一种编程语言的,一般都是换个工作就会换一套技术栈,所以主流编程语言最基本的语法要能看的懂,这对以后得工作也会有很大帮助。

当然了,对于一些不怎么熟悉 Java 且其他语言基础也比较差的读者,初学时肯定会有一点吃力。因为算法本身就比较烧脑了,再加上对语言特性不太熟悉,很可能会因为一些语言特性的坑而导致算法错误,这当然是我们不希望看到的。

不过不用担心,我的所有解法代码都会刻意避开 Java 的高级语言特性,用最朴素的、最容易看懂的方式写代码。

下面我还会带大家过一遍学习我的算法教程所需的 Java 基本用法,以便不了解 Java 的小伙也能伴顺畅地学习我的文章。

首先,Java 的基本知识网上有很多,我就不重复造轮子了,我就随便贴一个中文教程吧,你如果有更喜欢的 Java 教程也可以看你喜欢的:

https://www.runoob.com/java/java-tutorial.htmlopen in new window

我圈出的这一部分是 Java 的基本用法,你需要看一下。当然这个网站也有其他的 Java 基础知识,你有空也可以快速浏览一下:

下面我具体介绍一下我在教程中会用到的 Java 的标准库的数据结构以及一些可能踩坑的语言特性。

Java 标准库数据结构的基本用法

Java 中最基本的数据类型叫 Primitive Type(原始类型),比如 int, char, long, boolean 这种小写字母的关键字。大家应该都学过 C 语言,所以对于原始类型应该不陌生,因为 C 语言里几乎只有原始类型,连字符串都只能用 char[] 字符数组来表示,只能使用指针进行操作,使用起来非常不方便。

当然,作为高级编程语言,Java 提供了很多高级数据类型,都封装成了标准库中的(Java 中类的名字都以大写字母开头),比如 Java 中的字符串就是 String 类,这个类有 length(), substring() 等方法,这样我们就不用管底层的操作细节,使用起来方便多了。

以下是一些基本的 Java 类型。

1、数组

初始化方法:

int m = 5, n = 10;

// 初始化一个大小为 10 的 int 数组
// 其中的值默认初始化为 0
int[] nums = new int[n]

// 初始化一个 m * n 的二维布尔数组
// 其中的元素默认初始化为 false
boolean[][] visited = new boolean[m][n];

作为原始类型,这就类似 C 语言的 int 数组,如果涉及到比较复杂的操作,用起来比较麻烦,所以我们更多地使用 ArrayList 动态数组。

2、字符串 String

Java 的字符串处理起来挺麻烦的,因为它不支持用 [] 直接访问其中的字符,而且不能直接修改,要转化成 char[] 类型才能修改。主要说下 String 中我们会用到的一些特性:

String s1 = "hello world";
// 获取 s1[2] 那个字符 l
char c = s1.charAt(2);

char[] chars = s1.toCharArray();
chars[1] = 'a';
String s2 = new String(chars);
// 输出:hallo world
System.out.println(s2);

// 注意,一定要用 equals 方法判断字符串是否相同
if (s1.equals(s2)) {
    // s1 和 s2 相同
} else {
    // s1 和 s2 不相同
}

// 字符串可以用加号进行拼接
String s3 = s1 + "!";
// 输出:hello world!
System.out.println(s3);

Java 的字符串不能直接修改,要用 toCharArray 转化成 char[] 的数组进行修改,然后再转换回 String 类型。

另外,虽然字符串支持用 + 进行拼接,但是效率并不高,并不建议在 for 循环中使用。如果需要进行频繁的字符串拼接,推荐使用 StringBuilder/StringBuffer

StringBuilder sb = new StringBuilder();

for (char c = 'a'; c <= 'f'; c++) {
    sb.append(c);
}

// append 方法支持拼接字符、字符串、数字等类型
sb.append('g').append("hij").append(123);

String res = sb.toString();
// 输出:abcdefghij123
System.out.println(res);

还有一个重要的问题就是字符串的相等性比较,这个问题涉及语言特性,简单说就是一定要用字符串的 equals 方法比较两个字符串是否相同,不要用 == 比较,否则可能出现不易察觉的 bug。

3、动态数组 ArrayList

ArrayList 相当于把 Java 内置的数组类型做了包装,初始化方法:

// 初始化一个存储 String 类型的动态数组
ArrayList<String> strings = new ArrayList<>();

// 初始化一个存储 int 类型的动态数组
ArrayList<Integer> nums = new ArrayList<>();

常用的方法如下(E 代表元素类型):

// 判断数组是否为空
boolean isEmpty()

// 返回数组的元素个数
int	size()

// 返回索引 index 的元素
E get(int index)

// 在数组尾部添加元素 e
boolean	add(E e)

我们做算法题时这些最简单的方法就够用了,你应该看一眼就能明白。

在数据结构基础部分,我会在 动手实现动态数组 中带着大家实现一个 ArrayList,以便了解这种常见数据结构的底层原理。

4、双链表 LinkedList

ArrayList 列表底层是数组实现的,而 LinkedList 底层是双链表实现的,初始化方法也是类似的:

// 初始化一个存储 int 类型的双链表
LinkedList<Integer> nums = new LinkedList<>();

// 初始化一个存储 String 类型的双链表
LinkedList<String> strings = new LinkedList<>();

一般算法题中我们会用到以下方法(E 代表元素类型):

// 判断链表是否为空
boolean	isEmpty()

// 返回链表的元素个数
int	size()

// 判断链表中是否存在元素 o
boolean	contains(Object o)

// 在链表尾部添加元素 e
boolean	add(E e)

// 在链表尾部添加元素 e
void addLast(E e)

// 在链表头部添加元素 e
void addFirst(E e)

// 删除链表头部第一个元素
E removeFirst()

// 删除链表尾部最后一个元素
E removeLast()

这些也都是最简单的方法,和 ArrayList 不同的是,我们更多地使用了 LinkedList 对于头部和尾部元素的操作,因为底层数据结构为链表,直接操作头尾的元素效率较高。其中只有 contains 方法的时间复杂度是 O(N),因为必须遍历整个链表才能判断元素是否存在。

在数据结构基础部分,我会在 动手实现链表 中带着大家实现一个 LinkedList,以便了解这种常见数据结构的底层原理。

5、哈希表 HashMap

哈希表是非常常用的数据结构,用来存储键值对映射,初始化方法:

// 整数映射到字符串的哈希表
HashMap<Integer, String> map = new HashMap<>();

// 字符串映射到数组的哈希表
HashMap<String, int[]> map = new HashMap<>();

在算法题中,我们只会用以下几个基本方法(K 代表键的类型,V 代表值的类型):

// 判断哈希表中是否存在键 key
boolean	containsKey(Object key)

// 获得键 key 对应的值,若 key 不存在,则返回 null
V get(Object key)

// 将 key, value 键值对存入哈希表
V put(K key, V value)

// 如果 key 存在,删除 key 并返回对应的值
V remove(Object key)

6、哈希集合 HashSet

初始化方法:

// 新建一个存储 String 的哈希集合
Set<String> set = new HashSet<>();

我们可能在算法题中用到的方法(E 表示元素类型):

// 如果 e 不存在,则添加 e 到哈希集合
boolean	add(E e)

// 判断元素 o 是否存在于哈希集合中
boolean	contains(Object o)

// 如果元素 o 存在,在删除元素 o
boolean	remove(Object o)

等你实现了 MyHashMap,就知道 HashSet 底层和 HashMap 其实是一样的。

Java 类的一些基本用法

首先说一下泛型编程。泛型是 Java 提供的一种模板,能够将数据结构的实现和数据类型解耦。

比如说我们在使用 LinkedList 双链表的时候,可以随意设置其中的元素类型。不过需要注意,在泛型中只能使用类,不能使用原始类型:

// 装整数的双链表
LinkedList<Integer> list1 = new LinkedList<>();
// 报错,不能用 int 这种原始类型作为泛型
LinkedList<int> list2 = new LinkedList<>();

// 装字符串的双链表
LinkedList<String> list3 = new LinkedList<>();

我们在实现自己的数据结构类时,也需要使用泛型,以便我们的数据结构能够装任何类型。

比如在 手把手带你实现 LinkedList 中实现的 MyLinkedList,在 new 的时候传入什么类型,那么这个 E 就会变成什么类型:

public class MyLinkedList<E> {

    // 在链表尾部添加元素
    public void addLast(E e) {
        // ...
    }
}

// 使用方法:
MyLinkedList<Integer> list1 = new MyLinkedList<>();
MyLinkedList<String> list2 = new MyLinkedList<>();

当然,某些特殊数据结构对存储的数据类型有要求。比如 TreeMap 这种数据结构,由于底层是用 BST(二叉搜索树)来存储键值对,所以 TreeMap 要求存入其中的键必须是「可比较的」,即对于任意两个键,必须能够知道它俩谁大谁小。

在 Java 中,可以给泛型变量添加 extends 来指定该泛型的某些特性:

// MyTreeMap 接收两个泛型 K 和 V,其中 K 必须实现 Comparable 接口
// 即必须实现 compareTo 方法,这样才可以比较大小
public class MyTreeMap<K extends Comparable<K>, V> {
    public V put(K key, V val) {
        // ...
    }
}

// 使用方法:
MyTreeMap<Integer, Integer> map1 = new MyTreeMap<>();
MyTreeMap<String, Integer> map2 = new MyTreeMap<>();

这个 Comparable 是 Java 标准库提供的一个接口,实现如下:

public interface Comparable<T> {
    public int compareTo(T o);
}

所以 K extends Comparable<K> 的意思就是说,泛型 K 实现了这个接口,即类型 KcompareTo 这个方法,这意味着两个 K 类型的数据可以比较大小。

另外再说下 Java 的接口,免得有些读者疑惑。我们有时候会看到这样的写法:

Queue<String> q = new LinkedList<>();
List<String> list = new LinkedList<>();

实际 new 出来的是 LinkedList 类型,但为什么用 Queue 类型和 List 类型接收呢?因为 QueueList 都是 Java 标准库中的接口类型:

public interface Queue<E> extends Collection<E> {
    boolean offer(E e);
    E poll();
    E peek();
    // 还有若干方法...
}

public interface List<E> extends Collection<E> {
    // 若干方法...
}

所谓接口,就是一组方法的集合,只要一个类使用 implements 关键词申明自己实现了接口中的所有方法,那么就可以用这个接口的类型来接收这个类的实例化对象。

具体地,标准库提供的 LinkedList 类实现了 List 接口中的所有方法:

// Deque 是 Queue 的子接口,包含了 Queue 接口的所有方法,所以实现了 Deque 就等于实现了 Queue 接口
// 还有若干接口,这里省略了
public class LinkedList<E> implements List<E>, Deque<E> {
    // ...

    // Queue 接口中声明的若干方法都会被实现
    boolean offer(E e) {...}
    E poll() {...}
    E peek() {...}
    // ...

    // List 接口的若干方法也都会被实现
    // ...
}

所以可以用 List 接口接收 LinkedList 类型,Queue 接口同理。

当然,编程语言的接口和继承往深里说有很多设计方法的学问,大家有兴趣可以自己搜索学习。因为我们当前的重点在数据结构和算法,所以掌握这些最最基本的知识完全足够你理解我写的 Java 算法代码了。