算法与数据结构基础（Java）

• • 1、数组
  • 2、字符串
  • 3、动态数组 ArrayList
  • 4、双链表 linkedList
  • 5、哈希表 HashMap
  • 6、哈希集合 HashSet
  • 7、队列 Queue
  • 8、堆栈 Stack

初始化方法：

int m = 5, n = 10;

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

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

有的题目会以函数参数的形式传入，一般来说要在函数开头做一个非空检查，然后用索引下标访问其中的元素。

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

for (int i = 0; i < nums.length; i++) {
	//访问 nums[i]
}

//增强 for 循环
for (int num : nums) {
	//访问 num
}

Java的字符串不支持用 [ ] 直接访问其中的字符，而且不能直接修改，要用 toCharArray 转化成 char[ ] 类型后才能修改。 然后转化回 String 类型

String s1 = "hello world";
//获取 s1[2] 中的字符
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 + "!";
//输出：hallo world!
System.out.println(s3);

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

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();
//输出：abcdefghi123
System.out.println(res);

注：字符串相等性比较。一定要用字符串的 equals 方法比较两个字符串是否相同，不要使用 == 比较，否则可能出现不易察觉的bug。

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

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

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

常用方法(E 代表元素类型)：

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

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

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

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

ArrayList 列表底层是用数组实现的，而 linkedList 底层是用双链表实现的，初始化方法：

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

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

常用方法(E 代表元素类型)：

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

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

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

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

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

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

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

初始化方法：

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

//字符串映射到数组的哈希表
HashMap 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)

//获得 key 的值，如果 key 不存在，则返回 defaultValue
V getOrDefault(Object key, V defaultValue)

//获得哈希表中的所有 key
Set keySet()

//如果 key 不存在，则将键值对 key 和value 存入哈希表
//如果 key 存在，则什么都不做
V putIfAbsent(K key, V value)

初始化方法：

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

常用方法(E 表示元素类型)：

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

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

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

Queue 是一个接口(Interface)，初始化：

//新建一个存储 String 的队列
Queue q = new linkedList<>();

常用方法（E 表示元素类型）：

//判断队列是否为空
boolean isEmpty()

//返回队列中元素的个数
int size()

//返回对头的元素
E peek()

//删除并返回队头的元素
E poll()

//将元素 e 插入队尾
boolean offer(E e)

初始化方法：

Stack s = new Stack<>();

常用方法（E 表示元素类型）：

//判断堆栈是否为空
boolean isEmpty()

//返回堆栈中元素的个数
int size()

//将元素压入栈顶
E push(E item)

//返回栈顶元素
E peek()

//删除并返回栈顶元素
E pop()