Home - wenzhoullq/leetcode GitHub Wiki

TreeSet

因为TreeSet的比较函数,TreeSet ts = new TreeSet<>((a,b)->nums[a]!=nums[b]),即便是a!=b,在ts.add(a)和ts.add(b)中,a和b会被去重,因此如果想写,则需要改为TreeSet ts = new TreeSet<>((a,b)->nums[a]!=nums[b]?nums[a]-nums[b]:a-b)

TreeMap

//合并
 tm.merge(num,1,Integer::sum); //替代tm.put(num,tm.getOrDefault(num,0)+1);

//按value降序
       for(var e:tm.descendingMap().entrySet()){
          int c = e.getKey(), num = e.getValue();
       }

快读快写

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        pw.println();
        pw.close();//有close才有最后的输出
    }
}

时间复杂度

数据规模 算法可接受时间复杂度 常见题型
<= 10 O(n!) 全排列回溯
<= 30 O(2^n) dfs
<= 100 O(n^4) 四层for循环无优化
<= 500 O(n^3) 三层for循环无优化
< 10^4 O(n^2) 二层for循环无优化
<= 10^6 O(nlogn) 快排，归并，二分*O(n)
<= 10^7 O(n) 遍历
<= 10^14 O(sqrt(n))
- O(logn) 二分

数学

    //快速幂
    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0)
                res = res * x % MOD;
            x = x * x % MOD;
        }
        return res;
    }
    // 组合数
    private long comb(long n, int k) {
        long res = n;
        for (int i = 2; i <= k; i++)
            res = res * --n / i; 
        return res % MOD;
    }
   // gcd 最小公约数
   private static long gcd(long a,long b){
	   return (a==0?b:gcd(b%a,a));
   }
   // lcm 最小公倍数
   private static long lcm(long a,long b){
          return a  / gcd(a,b) * b;
   }

List

容知ArrayLit底层是数组，而LinkedList底层是链表，如果涉及到get操作，那么选择ArrayList；因为数据较小的时候相差不大，但是数据较大的时候get方法的O(n)和O(1)就体现出来了

  • List转int[]
     ans.stream().mapToInt(Integer::intValue).toArray();
  • int[] 转 List
      Array.asList();

取模

乘法可以取模, ((a+b)%mod+mod)%mod,除法不能滚动取模

⚠️ **GitHub.com Fallback** ⚠️