Arrays类
(1) Arrays.toString(); //返回数组的字符串形式
(2) Arrays.sort(); //排序(自然排序 和 定制排序)
static class Edge implements Comparable<Edge> { int a; int b; int w; Edge(int a, int b, int w) { this.a = a; this.b = b; this.w = w; } public int compareTo(Edge e) { return w - e.w; } }
public class 数位排序 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); Integer[] array = new Integer[n]; for (int i = 0; i < n; i++) { array[i] = i + 1; } Arrays.sort(array, (o1, o2) -> digitSum(o1) != digitSum(o2) ? digitSum(o1) - digitSum(o2) : o1 - o2); System.out.println(array[m - 1]); scan.close(); } private static int digitSum(Integer num) { int ans = 0; while (num > 0) { ans += num % 10; num /= 10; } return ans; } }
(3）Arrays.binarySearch(int[] a,int key); //参数：a - 要搜索的数组,key - 要搜索的值
//使用二进制搜索算法在指定的整数数组中搜索指定的值。
//注意！：在进行此调用之前，必须对数组进行排序（如通过sort(int[])方法）。
//如果数组中不存在该元素，就返回一个负数： return -(low + 1);
（low即是该元素应该出现的索引位置）
(4）Arrays.copyOf(int[] original, int newLength );
//从 original 数组中 拷贝 newLength 个元素到 新的数组中
//参数：original – 要复制的数组
newLength – 要返回的副本的长度
(5）Arrays.fill(int[] a, int val); //数组元素的填充
//将指定的 int 值分配给指定的 int 数组的每个元素。
//参数：a - 要填充的数组 val – 要存储在数组所有元素中的值
(6）Arrays.equals(); //如果两个指定的 int 数组彼此相等，则返回true 。
(7）Arrays.asList( ); //会将输入的数据转成一个List集合
例如：List list = Arrays.asList(3,6,888,99);
基础数论
欧几里得（辗转相除法）求最大公约数：
static int gcd(int a, int b) { //最大公约数 if(b==0) return a; else return gcd(b,a%b); }
最小公倍数 = 两数相乘 ÷ 两数的最大公约数.
static int lcm(int a , int b) { return a * b / gcd(a,b); }
判断奇偶数：
将这个数与1做&运算。 原因：二进制中奇数最后一位为1，偶数最后一位为0.
判断闰年：
①、普通年能被4整除且不能被100整除的为闰年. ②、世纪年能被400整除的是闰年
用2得到8最快的方法：
2<<2。 原因：二进制中左移n位相当于乘以2的n次方.
分解质因数：
- 例1：
public class demo_数论_分解质因数 { /** * 根据算术基本定理又称唯─分解定理，对于任何一个合数，我们都可以用几个质数的幂的乘积来表示。 * 如: * 12 = 2^2 * 3 * 20 = 2^2 * 5 * 30 = 2 * 3 * 5 * 接下来我们利用这个公式分解质因数。 * 设一个质数为p,如果 n % p == 0，那么p就是n的一个质因数， * 接下来就是求p的指数，我们让n = n / p , 这样就从n中剔除了一个p, * 接着重复上述两步，直到 n % p != 0 */ public static void prime(int n) { for (int i = 2; i <= n / i; i++) {//即i*i<=n int a = 0, b = 0; while (n % i == 0) { a = i; n /= i; b++; } if (b > 0) System.out.println("质因数之一： " + a + " 的 " + b + " 次方"); } if (n > 1) System.out.println("有一个大于根号n 的质因数:" + n); } /** * 注意：以上代码中for循环的结束条件也是i <= n / i，因为根据公式，最多只可能有一个质因数是大于 根号n, * 因为有两个的话，乘积肯定超过n了。所以当for循环结束后判断n是否大于1，如果大于就说明有一个大于 根号n 的质因数。 */ public static void main(String[] args) { prime(30); } }
例2：
import java.util.*; /** * 1. 编程将一个正整数n分解质因数。 * 输入输出示例1： * 请输入一个数:90 * 90=2*3*3*5 * 输入输出示例2： * 请输入一个数:50 * 50=2*5*5 */ public class demo01 { public static void main(String[] args) { Queue<Integer> queue = new LinkedList<>(); Scanner scanner = new Scanner(System.in); int num = scanner.nextInt(); int org = num; for (int i = 2; i < num; i++) { int a = 0, b = 0; while (num % i == 0) { a = i; num /= i; b++; } if (b != 0) while (b-- > 0) { queue.add(a); } } if (num > 1) queue.add(num); System.out.print(org+"="); while (!queue.isEmpty()){ System.out.print(queue.poll()); if (!queue.isEmpty()) System.out.print("*"); } } }
" 快速幂" && “素数筛法” 见后文的 --> Algorithm
格式控制
String.format("%02d", year) year格式化为至少2位十进制整数 --> int year = 5;结果为05
double ans=0.11111111; 作格式转换 String.format("%.nf", ans) 作输出 System.out.printf("%.nf",ans); --> n为小数点后保留的位数。 System.out.printf("%.2f",4); 输出---> 4.00
=======================================================
输入字符数组
c[i] = scan.nextLine().toCharArray();
=======================================================
测试类
import java.io.*; import java.util.*; public class Main{ static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException{ //测试writr 不能直接输出int类型 int a = 65; out.write(a); out.write("\n"); out.write(a + "\n"); // 使用 + 号拼接个字符串 使参数整体为一个字符串 out.write(Integer.toString(a)); // 输出a的字符串形式 out.write("\n"); //测试 read() 和 readLine(); int b = in.read(); // read()只读取一个字符 int c = in.read(); // 吸收 \n int x = in.read(); // 吸收 \r // String e = in.readLine(); String d = in.readLine(); out.write("\n"); out.write(b + "\n"); out.write(c + "\n"); out.write(x + "\n"); out.write(d + "\n"); //out.write(e); out.flush(); } }
一共输入了：
1 （按回车键）
ABC DEF
然后下面输出了
49（1的ASCii码）
13（回车键的ACSii码）
10 (换行键的ASCII码)
ABC DEF
无穷大的坑!
System.out.println(Integer.MIN_VALUE - 1);//2147483647 System.out.println(Integer.MAX_VALUE);//2147483647 System.out.println(Integer.MIN_VALUE);//-2147483648 最好是都右移一位避免过于极端 System.out.println(Integer.MAX_VALUE >> 1);//1073741823 System.out.println(Integer.MIN_VALUE >> 1);//-1073741824
坐标存储小技巧
保存经过的每一个点位置信息，采用(x)*m+y的公式表示(x,y);m:大于最长边的随便一个数 private static Queue<Integer> location = new LinkedList<>(); int x, y;//当前位置坐标 location.add(x * m + y); int l = location.poll();//获取当前位置的坐标 x = l / 50;//获取当前位置x y = l % 50;//获取当前位置y
合排序
ArrayList<Integer> list = new ArrayList<>(); list.add(2); list.add(0); list.add(5); list.sort(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1.compareTo(o2);//0 2 5 前后 --> 从小到大 } }); 把上面的代码可以使用lambda表达式进一步简化 升序： list.sort((a,b)->{ return Integer.compare(a,b); }); list.sort(Integer::compare); 直接调用list.sort(Comparator.naturalOrder()); 降序： list.sort((a,b) ->{ return Integer.compare(b,a); }); 直接调用list.sort(Comparator.reverseOrder());
Collection工具类的使用
排序操作
reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素升序排序
sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
@Test public void test1() { List list = new ArrayList(); list.add(123); list.add(43); list.add(765); list.add(-97); list.add(0); System.out.println(list);//[123, 43, 765, -97, 0] //reverse(List)：反转 List 中元素的顺序 Collections.reverse(list); System.out.println(list);//[0, -97, 765, 43, 123] //shuffle(List)：对 List 集合元素进行随机排序 Collections.shuffle(list); System.out.println(list);//[765, -97, 123, 0, 43] //sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序 Collections.sort(list); System.out.println(list);//[-97, 0, 43, 123, 765] //swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换 Collections.swap(list,1,4); System.out.println(list);//[-97, 765, 43, 123, 0] }
查找、替换
Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection，Comparator)
int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
void copy(List dest,List src)：将src中的内容复制到dest中
boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所旧值
@Test public void test2(){ List list = new ArrayList(); list.add(123); list.add(123); list.add(123); list.add(43); list.add(765); list.add(-97); list.add(0); System.out.println(list);//[123, 43, 765, -97, 0] //Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素 Comparable max = Collections.max(list); System.out.println(max);//765 //Object min(Collection) Comparable min = Collections.min(list); System.out.println(min);//-97 //int frequency(Collection，Object)：返回指定集合中指定元素的出现次数 int frequency = Collections.frequency(list,123); System.out.println(frequency);//3 //void copy(List dest,List src)：将src中的内容复制到dest中 List dest = Arrays.asList(new Object[list.size()]); System.out.println(dest.size());//7 Collections.copy(dest,list); System.out.println(dest);//[123, 123, 123, 43, 765, -97, 0] //boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值 }
Pattern类的使用（匹配正则表达式）
//根据匹配不同的内容返回不同的数值； //注意：这里的匹配指的是 " 仅含有 "， //所以，如果要判断一个字符串中是否包含多种字符，可以采用顺序拼接，也可以采用逐个判断 //拼接是这样写：Pattern.matches("^[a-z]+[\\d]+$", str),如果是a4一类的，则为true，很局限... //所以，这道题采用逐个判断 public class demo04 { private static int teShu(String str) { if (Pattern.matches("^[@#!%*$~]+$", str)) return 1; if (Pattern.matches("[\\d]+", str)) return 2; if (Pattern.matches("^[a-z]+$", str)) return 3; if (Pattern.matches("^[A-Z]+$", str)) return 4; return 0; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); if (str.length() < 8) { System.out.println("NG"); return; } String[] split = str.split(""); int[] kinds = new int[5]; for (String s : split) { if (kinds[1] == 1 && kinds[2] == 1 && kinds[3] == 1 && kinds[4] == 1) break; if (teShu(s) == 1) { kinds[1] = 1; } else if (teShu(s) == 2) { kinds[2] = 1; } else if (teShu(s) == 3) { kinds[3] = 1; } else if (teShu(s) == 4) { kinds[4] = 1; } } int count = kinds[1] + kinds[2] + kinds[3] + kinds[4]; if (count <= 1) { System.out.println("NG"); } else if (count == 2) { System.out.println("MG"); } else if (count == 3) { System.out.println("VG"); } else if (count == 4) { System.out.println("EG"); } } }
进制转换（x进制转10进制，10进制转y进制）
// 如果题目要进行转化的进制在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进制输出 //out.write(a.toString(8)); out.flush();
🍏五、Algorithm（重点二）
快速幂
快速幂的思想是：
①把指数想象成二进制的表示方式；
②如果指数不等于0，则判断最后一位是否为1（&），如果是，则用结果变量result 乘 底数 并取模（根据题意设定模的大小），否则不能乘，因为0 * result = 0；
③每进行一次，底数 = 底数 * 底数 % 模 （将指数表示为二进制之后，底数应该对应每次的指数），
即 a的1次 a的2次 a的4次 a的8次 （同底数相乘，指数相加，正好对应二进制的每一位），
例如：20的3次方（3的二进制为11）= 20的（2的1次方）次方 * 20的（2的0次方）次方；
④将指数往右边移动一位，方便进行下一次的判断
⑤其实到这里，快速幂的思想分析已然结束，但是格外的取模操作让人感到不太理解（不考虑数据溢出的情况下可以不取模），为什么每次都可以取模？其实只要是乘法，不论何时取模都是一样的，可以参考 以下公式：
例如：（a * b）% c = (a % c) * (b % c); --> (5 * 6) % 4 = ( 5 % 4) * (6 % 4) = 2
下面以一道省赛例题为例，在不清楚数据是否会溢出的情况下，推荐使用快速幂：
import java.io.*; public class Main { static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int mod = 7; public static void main(String[] args) throws IOException { bw.write(String.valueOf(FastPower(20, 22) + 6)); bw.flush(); bw.close(); } public static int FastPower(int a, int b) { int res = 1; while (b != 0) { if ((b & 1) == 1) { res = res * a % mod; } //无论如何，a都要不断倍增，b都要不断右移 a *= a % mod; b = b >> 1; } return res; } }
素数筛法
埃氏筛
其思想就是：筛掉质数的倍数
package java_Algorithm; public class demo85_数论2_埃氏筛 { static final int N = (int) (1e7 + 5); static int[] st = new int[N]; public static void E_sieve(int n) { for (int i = 2; i <= n / i; i++) if (st[i] == 0) for (int j = i * i; j <= n; j += i) st[j] = 1; // j是i的一个倍数，j是合数，筛掉。 } }
欧拉筛（最快）
欧拉筛，又称为线性筛，时间复杂度为O ( n ) O(n)O(n)。
先看下代码再看解析：
public class Main { static final int N = (int) (1e7 + 5); static int count = 0; static int[] status = new int[N], primes = new int[N]; static void ola(int n) { for (int i = 2; i <= n; i++) { if (status[i] == 0) primes[count++] = i;//将质数存到primes中 for (int j = 0; primes[j] <= n / i; j++) {//要确保质数的第i倍是小于等于n的。 status[primes[j] * i] = 1; if (i % primes[j] == 0) break;//欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。或者说是被合数的最大因子筛掉。 } } } public static void main(String[] args) { ola(8); for (int i = 0; i < count; i++) { System.out.println(primes[i]); } } }
欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。或者说是被合数的最大因子筛掉。
例题：
代码：
package java_Algorithm; public class 欧拉筛 { static final int N = (int) (1e7 + 5); static int cnt = 0; static int[] st = new int[N], primes = new int[N]; static void ola(int n) { for (int i = 2; i <= n; i++) { if (st[i] == 0) primes[cnt++] = i;//将质数存到primes中 for (int j = 0; primes[j] <= n / i; j++) {//要确保质数的第i倍是小于等于n的。 st[primes[j] * i] = 1; if (i % primes[j] == 0) break; } } } public static void main(String[] args) { ola(8); for (int i = 0; i < cnt; i++) { System.out.println(primes[i]); } } }
双指针（链表）
如果有环，fast一定会追上slow，如果没有环，fast跑完之后就会return false。
//判断是否有环 --- 双指针！！！ public static boolean isCycle(LinkedNode head) { LinkedNode fast = head; LinkedNode slow = head; while (fast != null && fast.next != null) { slow = slow.next;//必须保证 ：fast != null fast = fast.next.next;//必须保证 ：fast.next != null if (fast == slow) { return true; } } return false; }
完整的链表代码
//判断是否有环 — 双指针！！！
//返回倒数第k个节点的值(无环)
//合并两个有序无环单链表，返回新链表的头结点
package java_wuji.JXY.algorithm; public class LinkedListTest { public static class LinkedNode { public int value; public LinkedNode next; } public static void print(LinkedNode head) { while (head != null) { System.out.print(head.value + " "); head = head.next; } System.out.println(); } //判断是否有环 --- 双指针！！！ public static boolean isCycle(LinkedNode head) { LinkedNode fast = head; LinkedNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true; } } return false; } //返回倒数第k个节点的值(无环) public static int getNthFromEnd(LinkedNode head, int k) { LinkedNode fast = head; LinkedNode slow = head; //先让他们间隔k-1个距离，即：规定好初始时的间隔 for (int i = 0; i < k - 1; i++) { fast = fast.next; } //当fast指向最后一个结点时结束循环 while (fast.next != null) { fast = fast.next; slow = slow.next; } return slow.value; } //合并两个有序无环单链表，返回新链表的头结点 public static LinkedNode mergedTwoSortedLinkedList(LinkedNode l1, LinkedNode l2) { LinkedNode preHead = new LinkedNode(); LinkedNode prev = preHead; while (l1 != null && l2 != null) { if (l1.value <= l2.value) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev.next = l1 == null ? l2 : l1; return preHead.next; } public static void main(String[] args) { LinkedNode node1 = new LinkedNode(); node1.value = 1; LinkedNode node2 = new LinkedNode(); node2.value = 2; LinkedNode node3 = new LinkedNode(); node3.value = 3; LinkedNode node4 = new LinkedNode(); node4.value = 4; node1.next = node2; // node2.next = node3; node3.next = node4; // node4.next = node1;//形成环 // print(node1); // System.out.println(isCycle(node1)); // System.out.println(getNthFromEnd(node1, 2)); LinkedNode node = mergedTwoSortedLinkedList(node1, node3); print(node); } }
前缀和 与 差分
前缀和(一维)
高中时曾学过数列的前n项和Sn，即若存在一组数列{ a1，a2，a3，…，an }，则Sn = a1+a2+a3+…+an，在计算机领域，我们把Sn称为“前缀和”。
我们知道，对于m(m<n)，有：
Sn - Sm= (a1+a2+a3+…+am-1+am+am+1+…+an) - ( a1+a2+a3+…+am) = am+1+am+2+…+an
根据该公式，我们便找到了解决上面提出的问题的一种方法，即定义一个数组prefix[ ]用以保存数列中的前n项和（此时，prefix[1]=S1，prefix[2]=S2，…，prefix[n]=Sn），这样就可以在求区间[L，R]里的数列之和时直接用prefix[R] - prefix[L-1]得到。而构造前缀数组的方法如下（为了方便起见，通常要求前缀数组中的索引从1开始）：
public static void main(String[] args) throws IOException { Scanner scanner = new Scanner(System.in); int N = (int) (1e7 + 5); int[] prefix = new int[N]; int[] arr = new int[N]; int n = 3; for (int i = 1; i <= n; i++) { arr[i] = scanner.nextInt(); prefix[i] = prefix[i - 1] + arr[i]; } for (int i = 1; i <= n; i++) { System.out.print(prefix[i] + " "); } }
差分
差分与前缀和实际上是刚好相反的两个概念（若设原数组为ary[ ]，前缀和为prefix[ ]，差分为subfix[ ]）。则前缀和的当前项等于原数组中的当前项再加上前缀和的前一项，即prefix[i] = ary[i] + prefix[i-1]；而差分的当前项则等于原数组中的当前项减去原数组中的前一项，即：subfix[i] = ary[i] - ary[i-1]。于是可以得到构造差分数组的方法如下（其索引也是从1开始）。
int subfix[N],ary[N]; for(int i=1;i<=n;i++) { cin>>ary[i]; subfix[i]=ary[i]-ary[i-1]; }
接下来举个例子以直观地认识差分数组：
设数组ary[ ]={1，2，4，3，6，2}，那么其对应的差分数组subfix[ ]={1，1，2，-1，3，-4}。现在若我们对原数组中区间为[2，4]的元素都加上2的话，则原数组变为ary[ ]={1，4，6，5，6，2}，差分数组变为subfix[ ]={1，3，2，-1，1，-4}。我们发现，subfix[ ]中只有subfix[2]和subfix[5]发生了改变。这是因为区间[2，4]中的元素是同时加上2的，所以在区间[2,4]中的元素之差并未发生改变。同样地，其外部非端点部分的元素之差也不会发生改变。但是在给定区间的起始端点处（索引为2），由于该元素增加了2，故其相对其前一个元素而言增加了2，因此该处subfix[2]的值就增加了2；相反，在给定区间的结束端点处（索引为4），由于该元素增加了2，故其相对其后一个元素而言增加了2，因此在其后的subfix[5]的值就减少了2。
根据差分数组的此特性，我们可以先通过原数组来构建一个差分数组，此过程的时间复杂度为O(n)。然后再把上述问题中于每次操作里需要修改值的某段区间[L，R]优化为仅仅只对区间的两个端点进行修改，这样就可以把修改操作的时间复杂度降低到常数级，进而使得这m个操作的时间复杂度降至O(m)。最终计算区间[L，R]内的数列之和时，仅需要再调用一次SumOfSection函数便可得到，该算法的平均时间复杂的为O(m)。此时，整个程序的时间复杂度将降低至max{ O(m), O(n) }。下面给出求解上述问题的完整代码：
#include<iostream> using namespace std; const int N=100010; // 数组的最大阈值 int n,m,ans; // 数列长度、操作次数、最终答案 int l,r,value; // m次操作的左右边界与Value int ary[N]; // 原数组 int subfix[N]; // 差分数组 int main() { cin>>n>>m; // 输入原数组 for(int i=1;i<=n;i++) cin>>ary[i]; // 构建subfix数组 for(int i=1;i<=n;i++) subfix[i] = ary[i] - ary[i-1]; // 执行m次操作 for(int i=m;i>0;i--){ cin>>l>>r>>value; subfix[l] += value; subfix[r+1] -= value; } // 还原原数组 for(int i=1;i<=n;i++) ary[i] = ary[i-1] + subfix[i]; cin>>l>>r; // 计算最终询问给出的区间之和 for(int i=l;i<=r;i++) ans += ary[i]; cout<<ans<<endl; return 0; }
import java.io.*; public class demo78_差分_小明的彩灯 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static final int N = 500005; static long[] arr = new long[N]; static long[] sub = new long[N]; public static void main(String[] args) throws IOException { String[] firstLine = br.readLine().split(" "); int n = Integer.parseInt(firstLine[0]); int m = Integer.parseInt(firstLine[1]); String[] nextLine = br.readLine().split(" "); for (int i = 1; i <= n; i++) { arr[i] = Long.parseLong(nextLine[i - 1]); sub[i] = arr[i] - arr[i - 1]; } while (m-- > 0) { String[] subLine = br.readLine().split(" "); sub[Integer.parseInt(subLine[0])] += Long.parseLong(subLine[2]); sub[Integer.parseInt(subLine[1]) + 1] -= Long.parseLong(subLine[2]); } for (int i = 1; i <= n; i++) { arr[i] = arr[i - 1] + sub[i]; if (arr[i] < 0) System.out.print(0 + " "); else System.out.print(arr[i] + " "); } } }
