从最常考的全排列开始吧~
全排列模板1，最常用的写法
-
public
class 全排列_模板1 {
-
-
public static void main(String[] args) {
-
dfs(
0);
-
System.out.println(ans);
//9的全排有362880种
-
}
-
-
static
int[] a =
new
int[] {
1,
2,
3,
4,
5,
6,
7,
8,
9};
-
-
static
int n=
9,ans=
0;
-
-
static void dfs(int m) {
-
if(m>=n) {
-
System.out.println(
"一些核心的操作 比如ans:"+ans);
-
ans++;
-
for(
int i=
0;i<n;i++)
-
System.out.print(a[i]+
" ");
-
System.out.println();
-
-
return;
-
}
-
-
for(
int i=m;i<n;i++) {
-
swap(i,m);
-
dfs(m+
1);
-
swap(i,m);
//回溯
-
}
-
-
-
}
-
-
static void swap(int i,int j) {
-
int t = a[i];
-
a[i] = a[j];
-
a[j] = t;
-
}
-
-
}
全排列模板2，使用标记数组的写法
-
public
class 全排列_模板2 {
-
-
public static void main(String[] args) {
-
vis =
new
boolean[n];
-
b =
new
int[n];
-
dfs(
0);
-
System.out.println(ans);
//9的全排有362880种
-
}
-
-
static
int[] a =
new
int[] {
1,
2,
3,
4,
5,
6,
7,
8,
9};
-
static
int[] b;
-
static
boolean[] vis;
-
static
int n=
9,ans=
0;
-
-
static void dfs(int m) {
-
if(m>=n) {
-
System.out.println(
"一些核心的操作 比如ans:"+ans);
-
ans++;
-
for(
int i=
0;i<n;i++)
-
System.out.print(b[i]+
" ");
-
System.out.println();
-
-
return;
-
}
-
-
for(
int i=
0;i<n;i++)
-
if(!vis[i]) {
-
vis[i] =
true;
-
b[m] = a[i];
-
dfs(m+
1);
-
b[m] =
0;
//其实这个也可以不用回溯，它会被覆盖
-
vis[i] =
false;
//回溯
-
}
-
-
}
-
-
}
下面是需要排重的全排_模板
在上面模板上使用了哈希表查重，把一些数组并接成字符串
-
import java.util.HashSet;
-
-
public
class 全排列_模板3 {
-
-
public static void main(String[] args) {
-
dfs(
0);
-
System.out.println(ans);
//9的全排有362880种
-
System.out.println(set.size());
//1680
-
}
-
-
static
int[] a =
new
int[] {
1,
1,
1,
2,
2,
2,
3,
3,
3};
-
-
static
int n=
9,ans=
0;
-
static HashSet<String> set =
new HashSet<>();
-
-
static void dfs(int m) {
-
if(m>=n) {
-
System.out.println(
"一些核心的操作 比如ans:"+ans);
-
ans++;
-
String s=
"";
-
for(
int i=
0;i<n;i++) {
-
s+=a[i];
-
System.out.print(a[i]+
" ");
-
}
-
System.out.println();
-
set.add(s);
-
return;
-
}
-
-
for(
int i=m;i<n;i++) {
-
swap(i,m);
-
dfs(m+
1);
-
swap(i,m);
//回溯
-
}
-
-
}
-
-
static void swap(int i,int j) {
-
int t = a[i];
-
a[i] = a[j];
-
a[j] = t;
-
}
-
-
}
使用哈希表查重后是无序的，那么遇到需要打印字典序的有重复元素的全排呢
子集的写法也和全排很相似
leetcode 78. 子集(Subsets) beat 100%
leetcode 90. 子集 II(Subsets II) beat 98.57%
判断闰年
-
static boolean is(int x) {
-
return x%
400==
0 || (x%
4==
0 && x%
100!=
0);
-
}
筛素数O(
)
-
static boolean is(int n) {
-
if(n==
1)
-
return
false;
-
for(
int i=
2;i*i<=Math.sqrt(n);i++)
-
if(n%i==
0)
-
return
false;
-
-
return
true;
-
}
倍筛法_素数O(nlogn)
-
public
class 倍筛模板 {
-
-
public static void main(String[] args) {
-
boolean[] is =
new
boolean[
1000005];
-
is[
1] =
true;
//true表示不是素数
-
for(
int i=
2;i<
1000005;i++)
-
if(!is[
2])
-
for(
int j=
2*i;j<
1000005;j+=i)
-
is[j] =
true;
-
System.out.println(is[
2004]);
-
}
-
-
}
01背包
-
public
class _01背包 {
-
-
public static void main(String[] args) {
-
Scanner in =
new Scanner(System.in);
-
int m = in.nextInt();
//大小
-
int n = in.nextInt();
//物品数
-
int[] dp =
new
int[m+
5];
//开背包质量的大小
-
for(
int i=
1;i<=n;i++) {
-
int v = in.nextInt();
//物品体积
-
int w = in.nextInt();
//物品价值
-
for(
int j=m;j>=v;j--)
-
dp[j] = Math.max(dp[j], dp[j-v]+w);
-
}
-
System.out.println(dp[m]);
-
}
-
-
}
完全背包
-
import java.util.Scanner;
-
-
public
class _完全背包 {
-
-
public static void main(String[] args) {
-
Scanner in =
new Scanner(System.in);
-
int m = in.nextInt();
//大小
-
int n = in.nextInt();
//物品数
-
int[] dp =
new
int[m+
5];
//开背包质量的大小
-
for(
int i=
1;i<=n;i++) {
-
int v = in.nextInt();
//物品体积
-
int w = in.nextInt();
//物品价值
-
for(
int j=v;j<=m;j++)
-
dp[j] = Math.max(dp[j], dp[j-v]+w);
-
}
-
System.out.println(dp[m]);
-
}
-
-
}
最小公倍数gcd
-
static int gcd(int a,int b) {
-
return b==
0?a:gcd(b,a%b);
-
}
最大公约数lcm
-
static int lcm(int a,int b) {
-
return a*b/gcd(a,b);
-
}
多个数共同的gcd和lcm模板
-
static int gcd(int[] a) {
-
int n = a.length;
-
int g = a[
0];
-
for(
int i=
1;i<n;i++)
-
g = gcd(g,a[i]);
-
-
return g;
-
}
-
-
static int lcm(int[] a) {
-
int n = a.length;
-
int l = a[
0];
-
for(
int i=
1;i<n;i++)
-
l = lcm(l,a[i]);
-
-
return l;
-
}
二分答案_模板
蓝桥杯 2017年第八届真题 分巧克力 经典的二分答案 输入挂
-
static void f(int[] a) {
-
int n = a.length;
-
int l=
0,r=n-
1,ans=
0;
//一般上界需要自己构造
-
while(l<=r) {
-
int mid = l + (r-l)/
2;
-
if(ok(a[mid])) {
-
r = mid-
1;
-
ans = mid;
-
}
else
-
l = mid+
1;
-
}
-
System.out.println(ans);
-
}
-
-
static boolean ok(int x) {
-
return
false;
//按照题意写
-
}
二分lower_bound的实现（找到第一个大于等于给定值key的那个数）如[1,2,2,3]查找2，会返回第一个2的下标
-
public static int lowerBound(int []nums,int l,int r,int target){
-
while(l<=r){
//r=n-1
-
int m = (l+r)/
2;
-
if(nums[m]>=target) r= m-
1;
-
else l = m +
1;
-
}
-
return l;
-
}
upper_bound的实现(要求在按照非递减顺序排好序的数组中找到第一个大于给定值key的那个数)(不常用)
-
public static int upperBound(int []nums ,int l,int r, int target){
-
while(l<r){
//其中 r = nums.length
-
int m = (l+r)/
2;
-
if(nums[m]<=target) l = m+
1;
-
else r = m;
-
}
-
return l;
-
}
各种排序实现
- 冒泡排序(学会手写)
- 选择排序(没什么应用)
- 插入排序(对近乎有序的数组复杂度提升到O(n))
- 计数排序(给定区间排序)
- 归并排序(求逆序数)
- 快速排序(找第K大数)
- 堆排序(优先队列API)
- 希尔排序(插入排序的升级版)
大数类BigInteger和BigDecimal及方法API
考场上查API
进制问题,如有价值1，2，4，8等价值的硬币，如何用最小的硬币数凑出100元
-
static int f(int n,int k) {
//调用API转成k进制，缺点题目有上界为8
-
int ans=
0;
-
String s = Integer.toString(n, k);
-
System.
out.println(s);
-
for(
int i=
0;i<s.length();i++)
-
ans+=s.charAt(i)-
'0';
-
-
return ans;
-
}
头条面试题:找钱问题，共1024，64，16，4，1几种面值
-
static void solve(){
-
Scanner cin =
new Scanner(System.
in);
-
int N =
1024-cin.nextInt(), ans =
0;
-
for(
int i=
0; i<
4; i++){
-
ans += N/arr[i];
-
N %= arr[i];
-
}
-
System.
out.println(ans);
-
}
-
！
堆的应用，给定一个只包括
'('
，
')'
，
'{'
，
'}'
，
'['
，
']'
的字符串，判断字符串是否有效
leetcode 20. 有效的括号(Valid Parentheses)
-
public boolean isValid(String s) {
-
if(s==
null||s.equals(
""))
-
return
true;
-
-
char[] ch = s.toCharArray();
-
Stack<Character> stack =
new Stack<>();
-
-
for(
int i=
0;i<ch.length;i++)
-
{
-
if(ch[i]==
'(' || ch[i]==
'[' || ch[i]==
'{')
-
stack.push(ch[i]);
-
else
if(ch[i]==
')' || ch[i]==
']' || ch[i]==
'}')
-
{
-
if(!stack.isEmpty())
-
{
-
char p = stack.pop();
-
if(p==
'(' && ch[i]==
')')
-
continue;
-
if(p==
'[' && ch[i]==
']')
-
continue;
-
if(p==
'{' && ch[i]==
'}')
-
continue;
-
}
-
return
false;
-
}
-
}
-
-
return stack.empty();
-
}
快速幂及矩阵快速幂模板
-
static long mpow(long a,long n) {
//快速幂,mod一般题目给1e9+7
-
if(n==
0 || a==
1)
-
return
1;
-
long ans=
1;
-
while(n!=
0) {
-
if(n%
2==
1)
-
ans = a*ans%mod;
-
a=a*a%mod;
-
n>>=
1;
-
}
-
-
return ans;
-
}
矩阵乘法模板
-
//这里是矩阵的乘法模板，默认方阵
-
static
int[][] mul(
int[][] a,
int[][] b){
-
int n = a.length;
-
int[][] ans =
new
int[n][n];
-
for(
int i=
0;i<n;i++)
-
for(
int j=
0;j<n;j++)
-
for(
int k=
0;k<n;k++)
-
ans[i][j] =(ans[i][j] + a[i][k]*b[k][j])%MOD;
//ans[i][j] += a[i][k]*a[k][j];
-
return ans;
-
}
矩阵快速幂模板
-
-
//矩阵快速幂_模板
-
static
int[][] mpow(
int[][] a,
int n){
-
int N = a.length;
-
int[][] ans =
new
int[N][N];
-
for(
int i=
0;i<N;i++)
-
ans[i][i] =
1;
//初始化为单位矩阵W
-
while(n>
0) {
//写 n!=0也行,会快些么，反正位运算是会快的.这个不清楚
-
if((n&
1)==
1)
-
ans = mul(ans,a);
-
a = mul(a,a);
-
n>>=
1;
-
}
-
return ans;
-
}
阶乘逆元求组合数C(n,m)模板_O(nlogn)
-
public static void main(String[] args) {
-
Scanner in =
new Scanner(System.in);
-
n = in.nextInt();
-
f =
new
long[n+
5];
-
inv =
new
long[n+
5];
-
f[
0]=
1;
-
for(
int i=
1;i<n+
5;i++) {
-
f[i]=f[i-
1]*i%mod;
-
inv[i] = mpow(f[i],mod-
2);
-
}
-
-
-
}
-
-
static
int n;
-
static
long mod =
1000000009;
-
static
long[] f;
-
static
long[] inv;
-
-
static long C(int n,int m) {
-
return f[n]*inv[m]%mod*inv[n-m]%mod;
-
}
-
-
static long mpow(long a,long n) {
//快速幂
-
if(n==
0 || a==
1)
-
return
1;
-
long ans=
1;
-
while(n!=
0) {
-
if(n%
2==
1)
-
ans = a*ans%mod;
-
a=a*a%mod;
-
n>>=
1;
-
}
-
-
return ans;
-
}
欧拉函数模板 定义:小于n的正整数中与n
互质
的数的数目（φ(1)=1）
-
static int Euler(int n) {
//O(n) 有时候需要long
-
int ans=n;
-
-
for(
int i=
2;i<=n;i++)
-
if(n%i==
0) {
-
ans=ans/i*(i-
1);
-
while(n%i==
0)
-
n/=i;
-
}
-
-
return ans;
-
}
-
static int Euler(int n) {
//O(sqrt(n))
-
int ans=n;
-
-
for(
int i=
2;i*i<=n;i++)
-
if(n%i==
0) {
-
ans=ans/i*(i-
1);
n*(1-(1/p))转化为n/p*(p-1)
-
while(n%i==
0)
-
n/=i;
-
}
-
if(n>
1)
//优化 O(sqrt(n)) 不过要在出口 if(n>1)ans/n*(n-1) O(n)不用
-
ans=ans/n*(n-
1);
-
-
return ans;
-
}
前缀和模板
-
import java.util.Scanner;
-
-
public
class 前缀和模板 {
-
-
public static void main(String[] args) {
-
Scanner in =
new Scanner(System.in);
-
int n = in.nextInt();
-
int[] sum =
new
int[n+
1];
-
for(
int i=
1;i<=n;i++)
-
sum[i] = sum[i-
1] + in.nextInt();
//前i个数的和
-
-
}
-
-
}
线段树模板
并查集模板
-
static
int n,m,cnt=
0;
-
static
int[] f =
new
int[
10005];
//初始化一般是f[i]=i
-
-
static int find(int x) {
-
if(f[x]==x)
-
return x;
-
return f[x] = find(f[x]);
-
}
-
-
static void union(int x,int y) {
-
int a = find(x);
-
int b = find(y);
-
if(a!=b) {
-
f[a] = b;
-
cnt++;
-
}
-
}
dfs求联通块模板
-
static
int n,m;
-
static
int[][] vis;
-
static
char[][] ch;
-
-
static
int[] dx =
new
int[] {
1,
1,
1,
0,
0,-
1,-
1,-
1};
-
static
int[] dy =
new
int[] {
0,-
1,
1,
1,-
1,
1,
0,-
1};
-
-
static void dfs(int t,int x,int y) {
// hdu1241 油田问题 八联通
-
vis[x][y] = t;
-
-
for(
int i=
0;i<
8;i++)
-
if(x+dx[i]>=
0 && x+dx[i]<n && y+dy[i]>=
0 && y+dy[i]<m && ch[x+dx[i]][y+dy[i]]==
'@' && vis[x+dx[i]][y+dy[i]]==
0)
-
dfs(t,x+dx[i],y+dy[i]);
-
-
}
-
int t=
0;
-
for(
int i=
0;i<n;i++)
-
for(
int j=
0;j<m;j++)
-
if(ch[i][j]==
'@' && vis[i][j]==
0)
-
dfs(++t,i,j);
-
System.out.println(t);
最小生成树模板
-
static
int n,m,cnt=
0,ans=
0;
-
static
int[] f;
-
-
static int find(int x) {
-
if(f[x]==x)
-
return x;
-
return f[x] = find(f[x]);
-
}
-
-
static int union(int x,int y) {
-
int a = find(x);
-
int b = find(y);
-
if(a!=b) {
-
f[a] = b;
-
return
1;
-
}
-
return
0;
-
}
-
-
-
static
class Edge implements Comparable<Edge>{
-
int a,b,c;
-
public Edge(int a,int b,int c) {
-
this.a = a;
-
this.b = b;
-
this.c = c;
-
}
-
@Override
-
public int compareTo(Edge o) {
-
return
this.c - o.c;
-
}
-
}
-
public static void main(String[] args) {
-
InputReader in =
new InputReader(System.in);
//用它来代替Scanner。
-
while(
true) {
-
n = in.nextInt();
-
if(n==
0)
-
break;
-
m = n*(n-
1)/
2;
-
cnt=
0;
-
ans=
0;
-
f =
new
int[n+
5];
-
for(
int i=
1;i<=n;i++)
-
f[i] = i;
-
-
PriorityQueue<Edge> pq =
new PriorityQueue<>();
-
-
for(
int i=
1;i<=m;i++) {
-
int a = in.nextInt();
-
int b = in.nextInt();
-
int c = in.nextInt();
-
int d = in.nextInt();
-
if(d==
1)
-
cnt+=union(a,b);
-
else
-
pq.add(
new Edge(a, b, c));
-
}
-
-
while(!pq.isEmpty()) {
-
Edge u = pq.poll();
-
if(union(u.a, u.b)==
1) {
-
cnt++;
-
ans+=u.c;
-
if(cnt==n-
1)
-
break;
-
}
-
}
-
-
System.out.println(ans);
-
}
-
-
-
}
输入挂模板
-
//解决javaIO读取过慢的方法，利用该类读取输入数据，不要用Scanner！！！
-
static
class InputReader {
-
public BufferedReader reader;
-
public StringTokenizer tokenizer;
-
-
public InputReader(InputStream stream) {
-
reader =
new BufferedReader(
new InputStreamReader(stream),
32768);
-
tokenizer =
null;
-
}
-
-
public String next() {
-
while (tokenizer ==
null || !tokenizer.hasMoreTokens()) {
-
try {
-
tokenizer =
new StringTokenizer(reader.readLine());
-
}
catch (IOException e) {
-
throw
new RuntimeException(e);
-
}
-
}
-
return tokenizer.nextToken();
-
}
-
-
public int nextInt() {
-
return Integer.parseInt(next());
-
}
-
-
}
拓扑排序模板
-
static ArrayList<Integer> list =
new ArrayList<>();
-
static ArrayList<Integer>[] edge =
new ArrayList[
105];
-
-
while(m-->
0) {
//建图 邻接表 并且用w[i]记录入度
-
String s1 = in.next();
-
String s2 = in.next();
-
if(!map.containsKey(s1))
-
map.put(s1,n++);
-
if(!map.containsKey(s2))
-
map.put(s2,n++);
-
w[map.get(s2)]++;
-
edge[map.get(s1)].add(map.get(s2));
-
}
-
-
for(
int i:map.values())
//把边为0的放进队列
-
if(w[i]==
0)
-
q.add(i);
-
while(!q.isEmpty()) {
-
int u = q.poll();
-
list.add(u);
-
for(
int v:edge[u]) {
-
w[v]--;
-
if(w[v]==
0)
-
q.add(v);
-
}
-
}
dijkstra模板O(n^2)
dijkstra邻接表+优先队列模板O(nlogn)