刷题Snippet
01 背包问题的模版
// 01背包
for (int i = 0; i < n; i++) {
for (int j = m; j >= V[i]; j--) {
f[j] = max(f[j], f[j-V[i]] + W[i]);
}
}
// 完全背包
for (int i = 0; i < n; i++) {
for (int j = V[i]; j <= m; j++) {
f[j] = max(f[j], f[j-V[i]] + W[i]);
}
}
//
f[i][j] = max(f[i][j], f[i-M[i]][j-N[j]])
- f[j]代表当前背包容量为 j 的时候，可以获取的最大价值。完全背包是从左向右遍历，f[j-V[i]]取到的是拿第 i 个物品时的值，是新值，可以重复无限的拿，f[j]的值也会随之增加。
- V：商品的体积
- W：商品的价值
数位 DP 模板
ll dfs(int pos,int state,...,bool lead,bool limit){
if(!pos) return ...; //返回填完的数是否满足条件
//当前状态已经搜索过，直接使用dp值
if(dp[pos][state]...!=-1&&!limit&&!lead) return dp[pos][state]...;
ll ret=0; //暂时记录当前方案数
int bound=limit?a[pos]:9; //当前位能取到的最大值
for(int i=0;i<=bound;i++){
//有前导0 并且当前位也是前导0
if(!i&&lead) ret+=dfs(pos-1,...,1,i==bound&&limit);
//有前导0 但当前位不是前导0，当前位就是最高位
else if(i&&lead) ret+=dfs(pos-1,...,0,i==bound&&limit);
else if(...) ...;
}
if(!limit&&!lead) dp[pos][state]...=ret; //当前状态方案数记录
return ret;
}
ll solve(ll x){
len=0; //数位长度
while(x) a[++len]=x%10,x/=10;
memset(dp,-1,sizeof(dp)); //初始化-1（因为方案数可能为0）
return dfs(len,...,1,1);
}
排序
数组排序
Arrays.sort(nums); // 对数组进行排序，排序规则是从小到大，即升序。
Arrays.sort() vs Collections.sort()
- Arrays.sort works for arrays which can be of primitive data type also.
- Collections.sort() works for objects Collections like ArrayList, LinkedList, etc. We can use Collections.sort() to sort an array after creating an ArrayList of given array items.
Collections.sort(list, (a, b) -> {
int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
return cnt1 != cnt2 ? -1 : 1;
});
/* Collections.sort method is sorting the
elements of ArrayList in ascending order. */
Collections.sort(al, Collections.reverseOrder());
逆序
Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 }; // 数组类型为Integer
Arrays.sort(a, Collections.reverseOrder());
Java 字典按值排序
List<Entry<K, V>> list = new ArrayList<>(map.entrySet());
list.sort(Entry.comparingByValue());
Stream<Map.Entry<K,V>> sorted = map.entrySet().stream().sorted(Map.Entry.comparingByValue());
// function to sort hashmap by values
public static HashMap<String, Integer> sortByValue(HashMap<String, Integer> hm) {
// Create a list from elements of HashMap
List<Map.Entry<String, Integer> > list = new LinkedList<Map.Entry<String, Integer>>(hm.entrySet());
// Sort the list using lambda expression
Collections.sort(list, (i1, i2) -> i1.getValue().compareTo(i2.getValue()));
// put data from sorted list to hashmap
HashMap<String, Integer> temp = new LinkedHashMap<String, Integer>();
for (Map.Entry<String, Integer> aa : list) {
temp.put(aa.getKey(), aa.getValue());
}
return temp;
}
二维数组 - 每一行按第一列元素进行排序
// Python sort 函数对二维数组每一行按第一列元素进行排序
intervals.sort(key=lambda i:i[0])
// Java通过 sort 函数对二维数组每一行按第一列元素进行排序 - 自定义Comparator
// 重写比较器方法,o1[] - o2[] 表示当 o1 大于 o2 时,将 o1 放在 o2 后面,即基本的升序排序
// 而 o1[0] - o2[0] 表示按二维数组的每一行第一列元素排序,类似的 o[1] - o2[1]代表按第二列进行排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
数组 & list
反转
Collections.reverse(list);
队列
Queue<Integer> q = new ArrayDeque<>();
// 默认是小根堆，实现大根堆需要重写一下比较器。
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
集合
计算元素个数
# Python
len(set(nums))
// Java
Arrays.stream(nums).distinct().count()
初始化数组
初始化一维数组
// type[] arrayName = new int[size];
int[] arr = new int[5];
初始化二维数组
二维数组可以初始化，和一维数组一样，可以通过 3 种方式来指定元素的初始值。这 3 种方式的语法如下：
type[][] arrayName = new type[][]{值 1,值 2,值 3,…,值 n}; // 在定义时初始化
type[][] arrayName = new type[size1][size2]; // 给定空间，在赋值
type[][] arrayName = new type[size][]; // 数组第二维长度为空，可变化
int[][] temp0 = new int[][]{{1,2},{3,4}};
int[][] temp1 = new int[2][2];
int[][] temp2 = new int[2][];
// 二维list
List<List<Integer>> ans = new ArrayList<>();
Jave Arrays 工具类
Arrays 类是一个工具类，其中包含了数组操作的很多方法。 这个 Arrays 类里均为 static 修饰的方法（static 修饰的方法可以直接通过类名调用），可以直接通过 Arrays.xxx(xxx) 的形式调用方法。
1）int binarySearch(type[] a, type key)
使用二分法查询 key 元素值在 a 数组中出现的索引，如果 a 数组不包含 key 元素值，则返回负数。调用该方法时要求数组中元素己经按升序排列，这样才能得到正确结果。
2）int binarySearch(type[] a, int fromIndex, int toIndex, type key)
这个方法与前一个方法类似，但它只搜索 a 数组中 fromIndex 到 toIndex 索引的元素。调用该方法时要求数组中元素己经按升序排列，这样才能得到正确结果。
3）type[] copyOf(type[] original, int length)
这个方法将会把 original 数组复制成一个新数组，其中 length 是新数组的长度。如果 length 小于 original 数组的长度，则新数组就是原数组的前面 length 个元素，如果 length 大于 original 数组的长度，则新数组的前面元索就是原数组的所有元素，后面补充 0（数值类型）、false（布尔类型）或者 null（引用类型）。
4）type[] copyOfRange(type[] original, int from, int to)
这个方法与前面方法相似，但这个方法只复制 original 数组的 from 索引到 to 索引的元素。
5）boolean equals(type[] a, type[] a2)
如果 a 数组和 a2 数组的长度相等，而且 a 数组和 a2 数组的数组元素也一一相同，该方法将返回 true。
6）void fill(type[] a, type val)
该方法将会把 a 数组的所有元素都赋值为 val。
7）void fill(type[] a, int fromIndex, int toIndex, type val)
该方法与前一个方法的作用相同，区别只是该方法仅仅将 a 数组的 fromIndex 到 toIndex 索引的数组元素赋值为 val。
8）void sort(type[] a)
该方法对 a 数组的数组元素进行排序。
9）void sort(type[] a, int fromIndex, int toIndex)
该方法与前一个方法相似，区别是该方法仅仅对 fromIndex 到 toIndex 索引的元素进行排序。
10）String toString(type[] a)
该方法将一个数组转换成一个字符串。该方法按顺序把多个数组元素连缀在一起，多个数组元素使用英文逗号,和空格隔开。
