学习本站所需的 Java 基础
提示
自 2024/8/10 起,本站所有文章、习题中的多语言解法都经过了手动校准,修正了 chatGPT 的翻译错误。不过如果你有时间的话,依然建议了解一下 Java 的基本语法。
我比较推荐大家用 Java 语言学习算法,主要有以下几个原因:
1、Java 是强类型语言。因为我们就是要学习运用各种数据结构写算法嘛,所以清楚地知道每个变量是什么类型非常重要,方便你 debug,也方便 IDE 进行语法检查。如果是 Python 这样的动态语言,每个变量的类型不明显,可能有碍大家的理解。
2、Java 这种语言中规中矩,没有什么花里胡哨的语言特性。即便你之前没学过 Java 语言,单看代码也能轻易地理解逻辑。
另外,抛开算法不谈,单就编程技术的学习来说,我也建议大家多学习几门语言,尤其是像 Java 这种使用非常广泛的语言。因为任何人的职业生涯都不可能只用一种编程语言的,一般都是换个工作就会换一套技术栈,所以主流编程语言最基本的语法要能看的懂,这对以后得工作也会有很大帮助。
本站的所有解法代码都会避开 Java 的高级语言特性,用最朴素的、最容易看懂的方式写代码。
下面我会带大家过一遍学习我的算法教程所需的 Java 基本用法,以便不了解 Java 的小伙也能伴顺畅地学习我的文章。
首先,Java 的基本知识网上有很多,我就不重复造轮子了,我就随便贴一个中文教程吧,你如果有更喜欢的 Java 教程也可以看你喜欢的:
https://www.runoob.com/java/java-tutorial.html
我圈出的这一部分是 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
方法的时间复杂度是 ,因为必须遍历整个链表才能判断元素是否存在。
在数据结构基础部分,我会在 动手实现链表 中带着大家实现一个 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
实现了这个接口,即类型 K
有 compareTo
这个方法,这意味着两个 K
类型的数据可以比较大小。
另外再说下 Java 的接口,免得有些读者疑惑。我们有时候会看到这样的写法:
Queue<String> q = new LinkedList<>();
List<String> list = new LinkedList<>();
实际 new
出来的是 LinkedList
类型,但为什么用 Queue
类型和 List
类型接收呢?因为 Queue
和 List
都是 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 算法代码了。