Java Basic to Learn the Algo Notes
Tips
Starting from 2024/8/10, all articles and exercises on this site have been manually calibrated to correct chatGPT translation errors. However, if you have time, it is still recommended to learn the basic syntax of Java.
I recommend everyone to learn algorithms using the Java language for several reasons:
Java is a strongly-typed language. Since we are learning to use various data structures to write algorithms, it's crucial to know the type of each variable clearly. This makes debugging easier and allows the IDE to perform syntax checks. In dynamic languages like Python, variable types are not as explicit, which might hinder understanding.
Java is a straightforward language with no fancy language features. Even if you haven't learned Java before, you can easily understand the logic by just looking at the code.
Apart from algorithms, when it comes to learning programming techniques, I also suggest learning multiple languages, especially widely-used ones like Java. In one's career, it's unlikely to stick to just one programming language. Usually, changing jobs means working with a different tech stack, so understanding the basic syntax of major programming languages can be very helpful for future work.
All the solution codes on this site will avoid advanced Java language features and will be written in the most straightforward and easy-to-understand way.
Next, I will guide you through the basic Java usage needed to follow my algorithm tutorials, so even those unfamiliar with Java can smoothly learn from my articles.
First, there are many basic Java tutorials available online, so I won't reinvent the wheel. Here’s a link to a Chinese tutorial, but feel free to use any Java tutorial you prefer:
https://www.runoob.com/java/java-tutorial.html
I marked the section on basic Java usage that you need to check out. Of course, this site also has other Java fundamentals that you can quickly browse if you have time:
Next, I will specifically introduce the Java standard library data structures and some language features that may cause pitfalls, which I will use in the tutorials.
Basic Usage of Java Standard Library Data Structures
The most basic data types in Java are called Primitive Types, such as int, char, long, boolean
, which are keywords in lowercase letters. You might be familiar with these from the C language, which also primarily uses primitive types where even a string is represented as a char[]
array, making it inconvenient to manipulate due to the need for pointers.
As an advanced programming language, Java provides many advanced data types encapsulated as classes in the standard library (class names in Java start with an uppercase letter). For instance, Java strings are represented by the String
class, which has methods like length()
and substring()
, making usage much more convenient without worrying about underlying operational details.
Here are some basic Java types.
1. Arrays.
Initialization method:
int m = 5, n = 10;
// 初始化一个大小为 10 的 int 数组
// 其中的值默认初始化为 0
int[] nums = new int[n]
// 初始化一个 m * n 的二维布尔数组
// 其中的元素默认初始化为 false
boolean[][] visited = new boolean[m][n];
As a primitive type, this is similar to the int
array in C language. If more complex operations are involved, it can be cumbersome to use. Therefore, we often use the dynamic array ArrayList
.
2. Strings String
Handling strings in Java is quite troublesome because it doesn't support direct access to characters using []
, and strings cannot be modified directly. You need to convert them to char[]
type to modify them. Here are some features of String
that we will use:
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);
In Java, strings cannot be modified directly. You need to convert the string to a char[]
array using toCharArray
, make the modifications, and then convert it back to a String
.
Additionally, although strings support concatenation using the +
operator, it is not very efficient and is not recommended for use within a for loop. If you need to perform frequent string concatenations, it is recommended to use StringBuilder
or 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);
Another important issue is the comparison of string equality. This issue involves language features. Simply put, you must use the equals
method to compare whether two strings are the same. Do not use ==
for comparison, as this may cause subtle bugs.
3. Dynamic Array ArrayList
ArrayList
is essentially a wrapper around Java's built-in array type. Here is the initialization method:
// 初始化一个存储 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)
When solving algorithm problems, these simple methods are usually sufficient, and you should be able to understand them at a glance.
In the basic data structure section, I will guide you through the implementation of an ArrayList
in Implementing a Dynamic Array, so you can understand the underlying principles of this common data structure.
4. Doubly Linked List - LinkedList
The ArrayList
is implemented with an array underneath, while the LinkedList
is implemented with a doubly linked list. The initialization methods are also similar:
// 初始化一个存储 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()
These are also the simplest methods. Unlike ArrayList
, we use LinkedList
more often for operations on the head and tail elements because the underlying data structure is a linked list, making direct operations on the head and tail elements more efficient. Only the contains
method has a time complexity of O(N)
since it must traverse the entire list to determine if an element exists.
In the basics of data structures, I will guide you through implementing a LinkedList
in Hands-on LinkedList Implementation so that you can understand the underlying principles of this common data structure.
5. Hash Table HashMap
A hash table is a very commonly used data structure to store key-value mappings. Here’s how to initialize it:
// 整数映射到字符串的哈希表
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. Hash Set HashSet
Initialization method:
// 新建一个存储 String 的哈希集合
Set<String> set = new HashSet<>();
// 我们可能在算法题中用到的方法(`E` 表示元素类型):
// 如果 e 不存在,则添加 e 到哈希集合
boolean add(E e)
// 判断元素 o 是否存在于哈希集合中
boolean contains(Object o)
// 如果元素 o 存在,在删除元素 o
boolean remove(Object o)
Once you implement MyHashMap
, you will understand that the underlying mechanism of HashSet
is actually the same as that of HashMap
.
Basic Usage of Java Classes
Let's first talk about generic programming. Generics are a feature provided by Java that allow the implementation of data structures to be decoupled from the data types.
For example, when we use a LinkedList
(doubly-linked list), we can freely set the type of elements it contains. However, it is important to note that only classes can be used in generics, not primitive types:
// 装整数的双链表
LinkedList<Integer> list1 = new LinkedList<>();
// 报错,不能用 int 这种原始类型作为泛型
LinkedList<int> list2 = new LinkedList<>();
// 装字符串的双链表
LinkedList<String> list3 = new LinkedList<>();
When implementing our own data structure classes, we also need to use generics so that our data structures can hold any type.
For example, in the article Hand-by-Hand Guide to Implementing LinkedList, the MyLinkedList
class uses a generic type E
. When you create a new instance, whatever type you pass in will become the type for E
:
public class MyLinkedList<E> {
// 在链表尾部添加元素
public void addLast(E e) {
// ...
}
}
// 使用方法:
MyLinkedList<Integer> list1 = new MyLinkedList<>();
MyLinkedList<String> list2 = new MyLinkedList<>();
Of course, some special data structures have requirements for the types of data they store. For example, the TreeMap
data structure uses a BST (Binary Search Tree) to store key-value pairs. Therefore, TreeMap
requires that the keys inserted into it must be "comparable", meaning that for any two keys, it must be possible to determine which one is greater or smaller.
In Java, you can add extends
to a generic variable to specify certain characteristics of the generic type:
// 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<>();
The Comparable
is an interface provided by the Java standard library, implemented as follows:
public interface Comparable<T> {
public int compareTo(T o);
}
So K extends Comparable<K>
means that the generic type K
implements this interface, which means the type K
has the compareTo
method. This allows two K
type data to be compared.
Additionally, let's clarify Java interfaces to avoid confusion for some readers. Sometimes we see the following syntax:
Queue<String> q = new LinkedList<>();
List<String> list = new LinkedList<>();
In practice, the newly created object is of type LinkedList
, but why do we use Queue
and List
types to receive it? This is because Queue
and List
are interface types in the Java standard library:
public interface Queue<E> extends Collection<E> {
boolean offer(E e);
E poll();
E peek();
// 还有若干方法...
}
public interface List<E> extends Collection<E> {
// 若干方法...
}
An interface is a collection of methods. As long as a class declares that it implements all the methods in the interface using the implements
keyword, the type of this interface can be used to receive instances of this class.
Specifically, the standard library provides the LinkedList
class, which implements all the methods in the List
interface:
// Deque 是 Queue 的子接口,包含了 Queue 接口的所有方法,所以实现了 Deque 就等于实现了 Queue 接口
// 还有若干接口,这里省略了
public class LinkedList<E> implements List<E>, Deque<E> {
// ...
// Queue 接口中声明的若干方法都会被实现
boolean offer(E e) {...}
E poll() {...}
E peek() {...}
// ...
// List 接口的若干方法也都会被实现
// ...
}
Therefore, you can use the List
interface to accept the LinkedList
type, and similarly, use the Queue
interface.
Of course, there are many in-depth design methods and principles related to interfaces and inheritance in programming languages. If you are interested, you can research and learn more on your own. Since our current focus is on data structures and algorithms, mastering these fundamental concepts is sufficient for you to understand the Java algorithm code I write.