前言：笔者在这段时间准备蓝桥杯竞赛，由于个人原因选择Java作为语言，刷题中也是不断感到Java有些语法还是不够方便（非常羡慕隔壁C++的STL…），不过有些常见的技巧/方法/模板，也是自己做了些总结，十分之不全面，比完赛会继续完善…
！！！！！提交结果时记得检查有无不该加的头文件，主类名是否为Main！！！！！！
2.优化输入输出时间（快速IO模板）：
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class Main {
static InputReader in = new InputReader();
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception {
/**
你的代码写在这里
(输入实例： int a = in.nextInt();)
*/
out.close(); //不关闭输出流的话，控制台会没有输出，所以一定要关，in最好也关，不过实测没有因为不关in出过问题
}
static class InputReader{
private StringTokenizer st;
private BufferedReader bf;
public InputReader() {
bf = new BufferedReader(new InputStreamReader(System.in));
st = null;
}
public String next() throws IOException{
while(st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public String nextLine() throws IOException{
return bf.readLine();
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public BigDecimal nextBigDecimal() throws IOException{
return new BigDecimal(next());
}
}
}
3.快速幂模板
long FastPower(long base, long power) { //base是底数，power是幂数，result是结果
long result= 1;
while(power > 0) {
if((power & 1) != 0) {
result*= base;
power -= 1;
}
base *= base;
power >>= 1;
}
return result;
}
4.自定义类排序
例如：
public class Main {
static class Point{
double x;
double y;
public Point() {}
public Point(double x, double y){
this.x = x;
this.y = y;
}
}
public static double INF = 2 << 19;
static InputReader in;
static PrintWriter out;
public static int n;
public static double dist(Point a, Point b) {
double aa = Math.pow(a.x - b.x, 2);
double bb = Math.pow(a.y - b.y, 2);
return Math.sqrt(aa + bb);
}
public static double merge(Point[] point, int left, int right) {
double d = INF;
if(left >= right)
return d;
if(left + 1 == right)
return dist(point[left], point[right]);
int mid = (left + right) >> 1;
double d1 = merge(point, left, mid);
double d2 = merge(point, mid+1, right);
d = Math.min(d1, d2);
int i, j, k = 0;
ArrayList<Point> tem = new ArrayList<>();
for(i = left; i <= right; ++i) {
if(Math.abs(point[mid].x - point[i].x) <= d) {
tem.add(point[i]);
k++;
}
}
Collections.sort(tem, new Comparator<Point>() {
@Override
public final int compare(Point pFirst, Point pSecond) {
if(pFirst.y < pSecond.y)
return -1;
if(pFirst.y > pSecond.y)
return 1;
if(pFirst.x < pSecond.x)
return -1;
if(pFirst.x > pSecond.x)
return 1;
return 0;
}
});
for(i = 0; i < k; i++) {
for(j = i + 1; j < k && (tem.get(j).y - tem.get(i).y) < d; j++) {
double d3 = dist(tem.get(j), tem.get(i));
if(d3 < d) d = d3;
}
}
return d;
}
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
n = in.nextInt();
Point[] point = new Point[n];
for(int i = 0; i < n; i++) {
double x = in.nextDouble();
double y = in.nextDouble();
point[i] = new Point(x, y);
}
Arrays.sort(point, new Comparator<Point>() {
@Override
public int compare(Point pFirst, Point pSecond) {
if(pFirst.x < pSecond.x)
return -1;
if(pFirst.x > pSecond.x)
return 1;
if(pFirst.y < pSecond.y)
return -1;
if(pFirst.y > pSecond.y)
return 1;
return 0;
}
});
System.out.printf("%.4f", merge(point, 0, n-1));
}
5.归并排序模板
void sort_change(int l,int mid,int r){
//排序部分，把大区间再次分成小区间排序
int k1=l,k2=mid+1,k=l;
//初始化三个指针，一个指左区间左端点，一个指右区间左端点，一个指最终答案区间的左端点
while(k1<=mid&&k2<=r){
if(a[k1]>a[k2]){
temp[k]=a[k2];
k++,k2++;
}
else{
temp[k]=a[k1];
k++,k1++;
}
//每次取两个区间中最小的数字加入答案,指针右移
}
while(k1<=mid){
temp[k]=a[k1];
k++,k1++;
}//如果右区间的数字已经取完了，将左区间剩余数字按照一样从小到大的顺序放入答案
while(k2<=r){
temp[k]=a[k2];
k++,k2++;
}//如果左区间的数字已经取完了，将右区间剩余数字按照一样从小到大的顺序放入答案
for(int i=l;i<=r;i++) a[i]=temp[i];//将储存答案的数组的值赋回原来的数组
}
void sort_re(int l,int r){
if(l>=r) return ;//如果该区间不满足条件，即左边在右边的右边，return
int mid=(l+r)/2;//二分思想
sort_re(l,mid);//给左子区间排序
sort_re(mid+1,r);//给右子区间排序
sort_change(l,mid,r);//保证左右子区间排列得整整齐齐之后，才能并起来
//将大区间化成小区间然后排序
}
6.Int, Integer等数组类型转换
int[] data = {1,2,3};
// int[]转List<Integer>
// Arrays.stream(data): int[] -> IntStream
// IntStream.boxed(): IntStream -> Stream<Integer>
// Stream<Integer>.collect(Collectors.toList()): Stream<Integer> -> List<Integer>
List<Integer> list1 = Arrays.stream(data).boxed().collect(Collectors.toList());
// int[]转Integer[]
Integer[] arr1 = Arrays.stream(data).boxed().toArray(Integer[]::new);
// List<Integer>转int[]
// Collection<Integer>.stream(): Collection<Integer> -> Stream<Integer>
// Stream<Integer>.mapToInt(Integer::intValue): Stream<Integer> -> IntStream
// IntStream.toArray(): IntStream -> int[]
int[] arr2 = list1.stream().mapToInt(Integer::intValue).toArray();
// List<Integer>转Integer[]
Integer[] arr3 = list1.toArray(new Integer[0]);
// Integer[]转List<Integer>
List<Integer> list2 = Arrays.asList(arr3);
// Integer[]转int[]
int[] arr4 = Arrays.stream(arr1).mapToInt(Integer::valueOf).toArray();
7.sort降序排序
Integer[] arr={9,8,7,6,5,4,3,2,1};
Arrays.sort(arr,Collections.reverseOrder());
或
Integer[] arr={9,8,7,6,5,4,3,2,1};
Comparator cmp=new CMP();
Arrays.sort(arr,cmp);
class CMP implements Comparator<Integer>{
@Override //可以去掉。作用是检查下面的方法名是不是父类中所有的
public int compare(Integer a,Integer b){
// 升序排序的话反过来就行
return b-a;
}
或
List<Integer> integersList = Ints.asList(array);
Collections.reverse(integersList);//冒泡交换
System.out.println("Guava降序输出：");
for (int num : integersList) {
System.out.println(num);
}
或利用二维数组的自定义排序，如下：
int[][] arr = new int[3][2];
arr[0][0] = 5;
arr[0][1] = 3;
arr[1][0] = 1;
arr[1][1] = 4;
arr[2][0] = 6;
arr[2][1] = 2;
Arrays.sort(arr, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0]-b[0];
}
});
即按第一列升序排序：
1,4
5,3
6,2
8.高精度运算
1.valueOf(parament); 将参数转换为制定的类型
比如 int a=3;
BigInteger b=BigInteger.valueOf(a);
则b=3;
String s=”12345”;
BigInteger c=BigInteger.valueOf(s);
则c=12345；
2.add(); 大整数相加
BigInteger a=new BigInteger(“23”);
BigInteger b=new BigInteger(“34”);
a.add(b);
3.subtract(); 相减
4.multiply(); 相乘
5.divide(); 相除取整
6.remainder(); 取余
7.pow(); a.pow(b)=a^b
8.gcd(); 最大公约数
9.abs(); 绝对值
10.negate(); 取反数
11.mod(); a.mod(b)=a%b=a.remainder(b);
12.max(); min();
13.public int compareTo();
14.boolean equals(); 是否相等
15.BigInteger构造函数：
一般用到以下两种：
BigInteger(String val);
将指定字符串转换为十进制表示形式；
BigInteger(String val,int radix);
将指定基数的 BigInteger 的字符串表示形式转换为 BigInteger
int n;
BigInteger m;
n=cin.nextInt(); //读入一个int;
m=cin.nextBigInteger();//读入一个BigInteger;
（1）一维前缀和：
预处理：定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
查询a数组中第left个数到第right个数的和：
sum[r]-sum[l-1]
（原理：
sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];
）
（2）二维前缀和：
预处理：
s[i] [j] = s[i-1][j] + s[i][j-1 ] + a[i] [j] - s[i-1][ j-1]
结论：
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]
差分：若a数组为b数组的前缀和数组，则b数组为a的差分数组
例如：a[i] = b[1] + b[2 ]+ b[3] +......+ b[i]
则：b[n] = a[n] - a[n-1];
若求对a数组中 [left，right] 区间每个数加上c，只需：
b[left] += c , b[right+1] -= c
二维差分：
构造差分数组：b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]
求以（x1, y1)为左上角，（x2, y2)为右下角的子矩阵中所有元素加c，则：
b[x1,y1] += c;
b[x2+1, y1] -= c;
b[x1, y2+1] -= c;
b[x2+1, y2+1] += c;
10.最大公约数/最小公倍数
最大公约数：
int gcd(int a,int b)
{
return b == 0 ? a : gcd(b,a%b) ;
}
最小公倍数：
两数乘积除以最大公约数
11.二分答案的两个模板：
（1）（最大值最小化）：
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
{
r=mid;
}
else
{
l=mid+1;
}
}
（2）（最小值最大化）：
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
12.TreeSet找比某个数大 / 小的数
小于 lower
小于等于 floor
大于等于 ceiling
大于 higher
13、 KMP算法
（2）求next数组：
void GetNext(char T[])
{
int j=0,k=-1;
next[j]=k;
while(T[j]!='\0')
{
if(k==-1||T[j]==T[k])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
（2）KMP主程序：
int KMP(char S[], char T[]) //KMP算法, S为主串，T为字串
{
int next[MaxSize],i=0,j=0;
GetNext(char T[]);
while (i<s.length && j<t.length)
{
if (j==-1 || s.data[i]==t.data[j])
{
i++;j++; //i,j各增1
}
else j=next[j]; //i不变,j后退，现在知道为什么这样让子串回退了吧
}
if (j>=t.length)
return(i-t.length); //返回匹配模式串的首字符下标
else
return(-1); //返回不匹配标志
}
14.线段树（模板题可至洛谷）：
（1）单点修改+区间查询（求区间和）（P3374）：
static long search(int i, int l, int r) {
if(tree[i].l >= l && tree[i].r <= r) {
return tree[i].sum;
}
if(tree[i].r < l || tree[i].l > r) {
return 0;
}
int sum = 0;
int mid = (tree[i].l + tree[i].r) >> 1;
if(tree[i].l <= mid) sum += search(i*2, l, r);
if(tree[i].r > mid) sum += search(i*2+1, l, r);
return sum;
}
static void add(int i, int x, long k) {
if(tree[i].l == tree[i].r) {
tree[i].sum += k;
return;
}
int mid = (tree[i].l + tree[i].r) >> 1;
if(x <= mid) add(i*2, x, k);
else add(i*2+1, x, k);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
return;
}
(2).区间修改+单点查询（P3368）（注：涉及区间修改的，要带懒标记（往往能用到））
void push_down(int i)
{
if(tree[i].lazy != 0)
{
tree[i << 1].lazy += tree[i].lazy;
tree[i << 1 | 1].lazy += tree[i].lazy;
int mid = (tree[i].l + tree[i].r) >> 1;
tree[i << 1].sum += tree[i].lazy * (mid - tree[i << 1].l + 1);
tree[i << 1 | 1].sum += tree[i].lazy * (tree[i << 1 | 1].r - mid);
tree[i].lazy = 0;
}
return;
}
void add(int i, int l, int r, int k)
{
if(tree[i].l >= l && tree[i].r <= r)
{
tree[i].sum += k * (tree[i].r - tree[i].l + 1);
tree[i].lazy += k;
return;
}
push_down(i);
int mid = (tree[i].l + tree[i].r) >> 1;
if(l <= mid) add(i*2, l, r, k);
if(r > mid) add(i*2+1, l, r, k);
tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
return;
}
ll search(int i, int x)
{
if(tree[i].l == x && tree[i].r == x)
{
return tree[i].sum;
}
push_down(i);
int mid = (tree[i].l + tree[i].r) >> 1;
if(x <= mid) return search(i*2, x);
else return search(i*2+1, x);
}
（3）区间修改+区间查询（P3372）：
static class Tree{
int l, r;
long sum, lazy;
}
static Tree[] tree;
static long[] input;
static void build(int i, int l, int r) {
tree[i] = new Tree();
tree[i].l = l;
tree[i].r = r;
tree[i].lazy = 0;
if(l == r) {
tree[i].sum = input[l];
return;
}
int mid = (l + r) >> 1;
build(i*2, l, mid);
build(i*2+1, mid+1, r);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
}
static long search(int i, int l, int r) {
if(tree[i].l >= l && tree[i].r <= r) {
return tree[i].sum;
}
if(tree[i].r < l || tree[i].l > r) {
return 0;
}
push_down(i);
long sum = 0;
if(tree[i*2].r >= l) {
sum += search(i*2, l, r);
}
if(tree[i*2+1].l <= r) {
sum += search(i*2+1, l, r);
}
return sum;
}
static void add(int i, int l, int r, long k) {
if(tree[i].l >= l && tree[i].r <= r) {
tree[i].sum += k*(tree[i].r - tree[i].l + 1);
tree[i].lazy += k;
return;
}
push_down(i);
if(tree[i*2].r >= l) add(i*2, l, r, k);
if(tree[i*2+1].l <= r) add(i*2+1, l, r, k);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
return;
}
static void push_down(int i) {
if(tree[i].lazy != 0) {
tree[i << 1].lazy += tree[i].lazy;
tree[i << 1 | 1].lazy += tree[i].lazy;
int mid = (tree[i].l + tree[i].r) >> 1;
tree[i << 1].sum += tree[i].lazy*(mid - tree[i].l + 1);
tree[i << 1 | 1].sum += tree[i].lazy*(tree[i].r - mid);
tree[i].lazy = 0;
}
return;
}
15.全排列：
static void fullSort(int[] arr, int start, int end) {
// 递归终止条件
if (start == end) {
.........
return;
}
for (int i = start; i <= end; i++) {
swap(arr, i, start);
fullSort(arr, start + 1, end);
swap(arr, i, start);
}
}
static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
16.关于求对数
（详解参见以下博客）
https://blog.csdn.net/xiaojin21cen/article/details/98944689?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165311820516781683965191%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=165311820516781683965191&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allbaidu_landing_v2~default-3-98944689-null-null.142v10control,157v4control&utm_term=java%E6%B1%82%E5%AF%B9%E6%95%B0&spm=1018.2226.3001.4187
总结：
X^Y = N 转化为 logxN = Y 转化为 logxN = Math.log(N) / Math.log(a)
17.任意进制转换
// 如果题目要进行转化的进制在2~36之间的话直接调用库函数就行了。
String s = in.readLine();
int a = Integer.parseInt(s, 16) // 将16进制的字符串转化十进制数
//BigInteger a = new BigInteger(s, 16);// 高精度数
out.write(Integer.toString(a, 8)); // 转化为8进制输出
17.匈牙利算法
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ //扫描每个目标
if (line[x][j]==true && used[j]==false)
//如果有连接并且还没有标记过
{
used[j]=1;
if (girl[j]==0 || find(girl[j])) {
girl[j]=x;
return true;
}
}
}
return false;
}
18.邻接矩阵存图（加边方式）
（引申：迪杰斯特拉、floyd、spfa等最短路算法）
static int[] head, to, next, ans, dis;
static int tot = 0;
static void add(int x, int y) {
to[++tot] = y;
next[tot] = head[x];
head[x] = tot;
return;
}
19.大顶堆：
（PriorityQUeue默认小顶堆）
PriorityQueue<Integer>bigHeap=new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
（2022-06-19修改一些笔误）
总的来说，我对ruby还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用
我试图在一个项目中使用rake，如果我把所有东西都放到Rakefile中，它会很大并且很难读取/找到东西，所以我试着将每个命名空间放在lib/rake中它自己的文件中，我添加了这个到我的rake文件的顶部:Dir['#{File.dirname(__FILE__)}/lib/rake/*.rake'].map{|f|requiref}它加载文件没问题，但没有任务。我现在只有一个.rake文件作为测试，名为“servers.rake”，它看起来像这样:namespace:serverdotask:testdoputs"test"endend所以当我运行rakeserver:testid时
作为我的Rails应用程序的一部分，我编写了一个小导入程序，它从我们的LDAP系统中吸取数据并将其塞入一个用户表中。不幸的是，与LDAP相关的代码在遍历我们的32K用户时泄漏了大量内存，我一直无法弄清楚如何解决这个问题。这个问题似乎在某种程度上与LDAP库有关，因为当我删除对LDAP内容的调用时，内存使用情况会很好地稳定下来。此外，不断增加的对象是Net::BER::BerIdentifiedString和Net::BER::BerIdentifiedArray，它们都是LDAP库的一部分。当我运行导入时，内存使用量最终达到超过1GB的峰值。如果问题存在，我需要找到一些方法来更正我的代
Rails2.3可以选择随时使用RouteSet#add_configuration_file添加更多路由。是否可以在Rails3项目中做同样的事情？ 最佳答案 在config/application.rb中:config.paths.config.routes在Rails3.2(也可能是Rails3.1)中，使用:config.paths["config/routes"] 关于ruby-on-rails-Rails3中的多个路由文件，我们在StackOverflow上找到一个类似的问题
我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何
我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer
刚入门rails，开始慢慢理解。有人可以解释或给我一些关于在application_controller中编码的好处或时间和原因的想法吗？有哪些用例。您如何为Rails应用程序使用应用程序Controller？我不想在那里放太多代码，因为据我了解，每个请求都会调用此Controller。这是真的？ 最佳答案 ApplicationController实际上是您应用程序中的每个其他Controller都将从中继承的类(尽管这不是强制性的)。我同意不要用太多代码弄乱它并保持干净整洁的态度，尽管在某些情况下ApplicationContr
我想向我的Controller传递一个参数，它是一个简单的复选框，但我不知道如何在模型的form_for中引入它，这是我的观点:{:id=>'go_finance'}do|f|%>Transferirde:para:Entrada:"input",:placeholder=>"Quantofoiganho?"%>Saída:"output",:placeholder=>"Quantofoigasto?"%>Nota:我想做一个额外的复选框，但我该怎么做，模型中没有一个对象，而是一个要检查的对象，以便在Controller中创建一个ifelse，如果没有检查，请帮助我，非常感谢,谢谢
我注意到像bundler这样的项目在每个specfile中执行requirespec_helper我还注意到rspec使用选项--require，它允许您在引导rspec时要求一个文件。您还可以将其添加到.rspec文件中，因此只要您运行不带参数的rspec就会添加它。使用上述方法有什么缺点可以解释为什么像bundler这样的项目选择在每个规范文件中都需要spec_helper吗？ 最佳答案 我不在Bundler上工作，所以我不能直接谈论他们的做法。并非所有项目都checkin.rspec文件。原因是这个文件，通常按照当前的惯例，只
我正在使用active_admin，我在Rails3应用程序的应用程序中有一个目录管理，其中包含模型和页面的声明。时不时地我也有一个类，当那个类有一个常量时，就像这样:classFooBAR="bar"end然后，我在每个必须在我的Rails应用程序中重新加载一些代码的请求中收到此警告:/Users/pupeno/helloworld/app/admin/billing.rb:12:warning:alreadyinitializedconstantBAR知道发生了什么以及如何避免这些警告吗？ 最佳答案 在纯Ruby中:classA