用Java刷算法题的那些必知必会

5 年前 Work>Development 16 分钟读完 (约 2416 字)

考虑到还有许多公司仍然对其SDE岗位要求应试者需要有Java/C++/C类的语言技能，或是更偏好这类应试者，若是能在刷题时直接用这类语言一步到位也是更好的。即便前端人员需要重新学习，JavaScript的语法在很多方面和Java很相近，所以从JavaScript进阶到Java语法的学习曲线比较平缓。这篇文章以供转战使用Java刷题或需要巩固基础以进行算法题练习的朋友参考。

常用的包

这些包通常在OA时已经被导入在后台环境，所以一般情况下无须手动指明。

1 2	import java.util.; import java.lang.;

数据类型、接口和类

接口：抽象方法的集合，但没有特定方法的实现
类：通过继承接口从而继承接口的抽象方法并针对不同的方法有自己的实现

接口	特点	常用类
List	元素不唯一	LinkedList、ArrayList
Set	元素唯一	HashSet、TreeSet
Map	键值映射	HashMap、TreeMap

常用类列表

该部分仅列出了在算法题中经常用到的类型与数据结构。

类	适用情况
数组 Array	既定长度，可模拟pair、tuple等immutable容器
动态数组 ArrayList	长度动态可改的灵活数组
栈 Stack	LIFO后进先出
队列 Queue	FIFO先进先出
集合 HashSet	当需要存储非重复元素或去重时，优先考虑该类型，但其不保证有序
哈希表 HashMap	实现O(1)的读取与写入键值对，但其不保证有序
优先队列 PriorityQueue	利用Heap进行排序性存值

基本变量类型 - Basic Variable Types

类型	备注
byte
int	范围 -2^31 to 2^31 – 1
long	范围 -2^63 to 2^63 – 1
float
double
char
boolean

字符 - Char

用途	语法	备注
创建	`char example = 'a'`	注意是单引号
比较	`example1 = example2`
判断是否为纯数字字母	`Character.isLetterOrDigit(example)`

字符串 - String

用途	语法	备注
创建	`String example = "Hello"`	注意是双引号
根据char数组创建	`String example = new String({'a', 'b'})`
重复已有字符串3次以创建新字符串	`const newExample = example.repeat(3);`
获取长度	`example.length()`
获取第3位字符	`example.charAt(3)`	绝不能用[]
第3位字符的ascii码	`(int) example.charAt(3)`
将ascii码66转为对应字符	`(char) 66`	字符+数字实现字符递增
字符’a’第一次出现的位置	`example.indexOf('a')`
字符’a’最后一次出现的位置	`example.lastIndexOf('a')`
将字符串中的所有’a’替换为’b’	`example.replace('a', 'b')`
以空格为分界转换为数组	`example.split(' ')`
将字符串转换为字符数组	`example.toCharArray()`
提取前5位字符组成的子字符串	`example.substring(0, 5)`
将字符串全部化为小写	`example.toLowerCase()`
将字符串全部化为大写	`example.toUpperCase()`
将字符串转化为整数	`Integer.parseInt(example);`
将整数转化为字符串	`Integer.toString(example);`
判断字符串是不是纯整数	`Integer.parseInt(example);`	要用try-catch捕获异常
判断两个字符串是否一样	`str1.equals(str2)`	绝对不能用==

数字 & 数学 - Number & Math

用途	语法	备注
最大整数	`Integer.MAX_VALUE`
最小整数	`Integer.MIN_VALUE`

数组 - Array

int[] example1 = new int[]{1, 2, 3};  //初始化int数组
int[] example2 = new int[3];  //初始化长度为3的int数组

Arrays.fill(example2, 0);  //将数组全部初始化为0
example1[0] = 0; //修改第0位元素
example1.length; //数组长度（注意，不是方法！）
Arrays.equals(example1, example2); //比较两个数组
Arrays.sort(example1); //数组递增排序
Arrays.sort(example1, Collections.reverseOrder()); //数组递减排序

String text = Arrays.toString(example1); //将数组转化为字符串(需要导入java.util.*)

// 除了用普通index方法遍历外：
for(int num: example1){
    System.out.println(num);
}

// 不声明且直接推入容器
ArrayList<int[]> arrList = new ArrayList<>();
arrList.add(new int[]{1,2});

动态数组 - ArrayList

import java.util.*; 

ArrayList<String> example = new ArrayList<>(); 
example.add("a"); //向尾部添加元素
example.add("c"); 
example.add(1, "b"); //在第1位添加元素
String val = example.get(0); //获取第0位元素
int firstPos = example.indexOf("b"); //找到指定元素第一次出现的位置
int lastPos = example.lastIndexOf("b"); //找到指定元素最后一次出现的位置
List<String> sub_example = example.subList(0, 2); //获取子数组
int length = example.size(); //得到数组长度

example.remove(0); //删除第0位元素
String converted = String.join(", ", example); //将数组转换为字符串并用', '分隔
example.clear(); //清空数组

// 除了用普通index方法遍历外：
for(String x: example){
    System.out.println(x);
}

//将ArrayList转化为Array，注意在括号中要声明存放结果的数据结构
String[] arr = example.toArray(new String[example.size()]);

动态数组的排序默认用Collection中的sort方法，若要自定义则需要comparator。

自定义comparator的时候要注意计算时可能出现的数据溢出，建议用cast或者Object（像是Integer）来处理。

// 方法一：对数字或字符串进行常规排序
ArrayList<Integer> example = new ArrayList<>();
Collections.sort(arraylist); // 默认升序
Collections.sort(al, Collections.reverseOrder()); // 降序

// 方法二：根据列表中所含的对象的特定成员进行排序（也可以用在Linked List上）
class Employee {
    int id;
    public Employee(int id){
        this.id = id;
    }
}
class SortbyId implements Comparator<Employee> 
{
    public int compare(Employee a, Employee b){ 
        /**
         * 返回值为负数则a比b小（a在b前面），返回为正数则a大于b（a在b后面），返回为零意味着o1等于o2
         */
        return a.id - b.id; // 倒序则改为：b.id-a.id
    } 
} 

ArrayList<Employee> example = new ArrayList<>();
Collections.sort(example, new SortbyId()); 

//方法三：也可以用Lambda函数实现（Java 8即可）
Collections.sort(example, (Employee a, Employee b) -> {
    return a.id - b.id;
});

栈 - Stack

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("a"); //推入元素
String top = stack.peek(); //查看栈首位元素
int length = stack.size(); //得到栈高度
String val = stack.pop(); //出栈且返回该值
stack.clear(); //清除整个栈

队列 - Queue

因避免捕获异常，不建议用add和remove操作

import java.util.LinkedList; 
import java.util.Queue; 

Queue<String> queue = new LinkedList<>(); 
queue.offer("a"); //插入元素
String top = queue.peek(); //查看队列首位元素
int length = queue.size(); //得到队列长度
String val = queue.poll(); //出队且返回该值
queue.clear(); //清除整个队列

优先队列 - PriorityQueue

因避免捕获异常，不建议用add和remove操作

import java.util.PriorityQueue; 

PriorityQueue<Integer> pQueue = new PriorityQueue<>(); 
PriorityQueue<Integer> pQueueInit = new PriorityQueue<>(n, cmp); //定义初始大小n，以及定义好的比较函数
pQueue.offer(15); 
pQueue.offer(5); 
int top = pQueue.peek(); //查看优先队列首位元素，默认从小到大排序
int length = pQueue.size(); //得到优先队列长度
int val = pQueue.poll(); //出队且返回该值
int[] array = pQueue.toArray(); //将优先队列转换为数组

/* 迭代器对集合进行遍历 */
Iterator itr = pQueue.iterator();
while (itr.hasNext()) 
    System.out.println(itr.next()); 

pQueue.clear(); //清除整个优先队列

集合 - HashSet

import java.util.HashSet; 

HashSet<String> set = new HashSet<>(); 

set.add("a"); //增加元素
set.add("b"); 
set.add("c"); 

boolean exists = set.contains("b"); //检查元素是否存在
int length = set.size(); //查看集合大小
set.remove("b"); //删除元素

/* 循环对集合进行遍历 */
for (String ptr : set) {
    System.out.println(ptr);
}

/* 迭代器对集合进行遍历（不常用） */
Iterator<String> i = h.iterator(); 
while (i.hasNext()) 
    System.out.println(i.next()); 

/* 对集合进行拷贝 */
HashSet<String> cloned_set = new HashSet<>(); 
cloned_set.addAll(set); 

set.clear(); //清空集合

哈希表 - HashMap

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>(); 

map.put("a", 1); //增加/修改指定键值对
map.put("b", 2); 
map.put("c", 3);

int val = map.get("a"); //根据键获取值
boolean keyExists = map.containsKey("c"); //判断指定键是否存在
boolean valExists = map.containsValue(2); //判断指定值是否存在
map.remove("b"); //删除指定键值对
int size = map.size(); //得到哈希表的大小

/* 通过所有键遍历整个哈希表 */
for (String key : map.keySet()) {
    System.out.println(map.get(key));
}

/* 遍历哈希表中的所有值*/
for (int value : map.values()) {
    System.out.println(value);
}

/* 构造浅拷贝 */
HashMap<Integer, String> cloned_map = new HashMap<>(); 
cloned_map.putAll(hash_map); 

map.clear(); //清除整个哈希表

指针

Java一律遵循pass-by-value原则。白话理解，基本类型的值就直接保存在变量中，引用类型的变量保存的都是实际内容所在的地址，从而传递到函数参数的情况不一样，前者是值、后者是对应的地址，但都为相同的副本。就后者而言，如果在函数内改变了原先副本的地址（指向新对象），原传入的参数还是不变，所以一切改动都不会影响原传入参数。

this关键字指的是在当前对象的实例，涵盖对象中的成员变量或者方法。

// 情况一：基本类型
public double(int i) { 
    i *= 2;
} 

// 情况二：引用类型（对象）
/* 如果该函数中重新将参数变量指向另一个对象，则main中的结果不变 */
public change(int[] arr){
    arr[0] = 100;
}

public static void main(String[] args) { 
    int[] arr = { 1, 2, 3, 4, 5 };
    int i = 100;
    double(i);
    change(arr);
    System.out.println(i); // 100，不变
    System.out.println(count[0]); // 100，变了
}

所以对有时需要对参数传入的对象进行拷贝来保存特定的结果。深拷贝的方法需要手动实现，可以使用递归或是序列化的方法。这里只考虑容器单层存储基本数据类型和String（因其为final类型不可改）的浅拷贝情况，具体的方法和实现如下：

// 数组
String[] a1 = {"a1", "a2"};
String[] a2 = a1.clone();

// 动态数组
List<String> newList = new ArrayList<>(oldList); //第一种 
newList.addAll(oldList); //第二种

// 哈希表
Map<String, Integer> newMap = new HashMap<>(oldMap); //第一种 
Map<String, Integer> newMap = oldMap.clone(); //第二种

#面试 #算法，刷题，干货 #后端