java算法易筋经：常见java-API使用技巧
摘要：算法练习的本质也在于锻炼编程思维，强化程序员的内力。因此给自己后面会持续更新的算法技巧内容简称算法易筋经。
本文分享自华为云社区《<java算法易筋经>之常见java-API使用》，原文作者：breakDraw 。
易筋经源于我国古代中医导引术,具有强健体魄、预防疾病的效果,长期以来在佛家及民间习武人士之间广为流传。算法练习的本质也在于锻炼编程思维，强化程序员的内力。因此给自己后面会持续更新的算法技巧内容简称算法易筋经。
无论你使用什么语言开始训练算法， 总是得掌握基本的。 我这边只以java举例，其他语言类似。以leetcode类型的平台为主。
java数组和list互转
有时候给定的输入是个数组，中间过程我们想转成list并使用list的一些api。 但是这没那么简单。
请打开自己的编译器，然后看下下面几个问题能否不用for循环写成功。（用for循环也是对的，考试时如果忘记了，就选择能用的方法）
- 请把字符串数组转list
- 请把字符串list转数组
- 请把list<Integer>转int[]
- 请把int[]转成List<Integer>
就像下面这样，自己造个类，测试一下看能否秒写：
public class ListArrayUtil {
// 请把字符串数组转list
public List<String> arrToListStr(String[] arr) {
return null;
}
// 请把字符串list转数组
public String[] listToArrStr(List<String> list) {
return null;
}
// 请把list数组转成int[]
public List<Integer> arrToListInt (List<Integer> num) {
return null;
}
// 请把int[] 数组转成list
public List<Integer> arrToListInt (int[] num) {
return null;
}
}有些人可能会误以为int[]和Integer[]是可以自动转的，然后对于数组而言，编译器无法用识别，会报错。因此如果涉及这种基础类型的数组列表转换，请记住要么马上使用stream，要么直接for循环写一下，不要卡在这个编译错误这研究半天。
我的答案：
public class ListArrayUtil {
// 请把字符串数组转list
public List<String> arrToListStr(String[] arr) {
return Arrays.asList(arr);
}
// 请把字符串list转数组
public String[] listToArrStr(List<String> list) {
return list.toArray(new String[list.size()]);
}
// 请把list数组转成int[]
public int[] arrToListInt (List<Integer> list) {
// 不可以toArray，int[]和Integer[]是不同的
//return list.toArray(new int[list.size()]);
return list.stream()
.mapToInt(Integer::valueOf)
.toArray();
}
// 请把int[] 数组转成list
public List<Integer> arrToListInt (int[] num) {
// 不可以asList，因为int[]和Integer[]不同
// return Arrays.<Integer>asList(num);
return Arrays
.stream(num)
.boxed()
.collect(Collectors.toList());
}
}list和数组的初始化
初始化可没那么简单，尤其是涉及返回List[]作为结果时，总是有人会忘记要先初始化数组里的每个list才能使用。请完成以下内容：
- 初始化list<Integer>为5个1
- 初始化int[]为5个1
- 初始化1个包含5个list的lis[]数组，并且里面的list已经初始化完成
正确答案如下：
public class ListUtil {
// 初始化list为5个1
public static List<Integer> fillList() {
List<Integer> list = Collections.nCopies(5,1);
System.out.println(list);
return list;
}
// 初始化arr为5个1
public static int[] fillArr() {
int[] arr = new int[5];
Arrays.fill(arr, 1);
return arr;
}
// 返回1个list数组，并且里面的list已经初始化完成
public static List[] fillListArray() {
List[] lists = new List[5];
IntStream.rangeClosed(0, 4).boxed()
.forEach(i->lists[i] = new ArrayList());
return lists;
}
}排序
关于如何快速对list和数组排序，在IDEA自己解答以下问题：
- Arrays和List如何对int[]数组做倒序排序
Arrays.sort()
Collections.sort() - 对于一个新对象，怎么做自定义排序？
如下。定义一个comparable
public class Student implements Comparable<Student> {
private int stuId;
private String stuName;
private int score;
@Override
public int compareTo(Student o) {
return stuId-o.stuId;
}
}参考题目： https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
map相关
- 如果map里的value是个list，每次往某个key里的list放数据时，必须要先初始化list， 怎么减少初始化代码？
答案：
使用getOrDefault:
map.getOrDefault(key, new ArrayList<>()).add(xxx)
图结果那边还蛮常用的
不做重复的put
if (!map.containsKey(key)) {
map.put(key, value);
}可以优化成
map.putIfAbsent(key, value)
字面意思： absent指不存在，那么就是不存在的时候，把value放入，如果存在，则直接返回原value值。
map中的值做更新
例如每次对key中的值加1
有两种方式：
map.put(key, map.getOrDefault(key, 0)+1);
map.compute(key, (k,v)->(v==null?1:v+1));
在一个比较复杂的情况下，compute比较有用。
computeIfAbsent（key, (k,v)->f(k,v)） 只在key不存在的时候，才计算这个labmda式子。 如果存在的话，就不计算了，直接返回旧值。
computeIfPresent（key, (k,v)->f(k,v)） 只有存在才会更新，不存在就不更新。
常见队列用法
- 普通队列：
- 优先队列priorityQueue：
能够保证出队的永远是按照你设定的最大或者最小的元素。
很有用。
用labma写内部比较式子，避免忘记接口怎么写
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
a[1] - b[1] 是小顶堆
a[1]-b[1] >0，则交换。
如何记忆？
堆更新的时候，都是从上往下更新的， 让
那么a是上面的点，b是下面的点（儿子节点）
当返回大于0时，交换a和b。
这样就好理解了
大顶堆： a-b<0时，需要交换，即父亲比儿子小，所以需要交换
小丁堆： a-b>0, 需要交换， 即父亲比儿子大，得换，让父亲是小顶。
- 优先队列延时删除
当优先队列中某个元素会被删除，但是不在堆顶时，使用延迟删除， 直到他走到堆顶才会清理。
因此这时候要使用额外的数量realCount来统计队列实际数量， 并使用特定的删除标志位（勿用会干扰到队列compare方法的方式去设定删除标志位）
简易二分查找
- 在一个list中找到最靠近x且大于等于x值的元素
不想手写二分的话用这个方法：
- 在一个list中找到最靠近x且小于等于x的元素
使用treeMap放置数据
floorKey（key) 可以找到小于等于给定键的最大键
如果不存在这样的键，则返回null。
ceilingKey(key) 找到大于等于给定键的最小键
不存在则返回null
记忆：
ceiling向上舍入，那就是找key的上边。 ceiling有天花板的意思，于是就理解成是向上找。
floor 向下摄入，那就是找key的下边。 有沉入水下的意思，于是理解成向下。
- 在list中找到最靠近x且大于（不包含等于）x的元素
例题： https://leetcode-cn.com/problems/previous-permutation-with-one-swap/submissions/
