刷题Snippet

Page content

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) 该方法将一个数组转换成一个字符串。该方法按顺序把多个数组元素连缀在一起,多个数组元素使用英文逗号,和空格隔开。

本文由 络壳 原创或整理,转载请注明出处