1.String.Join 方法 (A (String), B (String[]))

在指定 String 数组B的每个元素之间串联指定的分隔符 A,从而产生单个串联的字符串

String [] tmpStr = {abc, def, ghi};
String jn = string.Join(“-“, tmpStr); // 此时输出为”abc-def-ghi”
// 常见用法:字符串数组chs->字符串str
String.join("",strings)//{"abcdefghi"}

2.split() 根据匹配给定的正则表达式来拆分字符串

String str = "Welcome-to-Runoob";
for (String retval: str.split("-")){
System.out.println(retval);
}
// 分隔符返回值 :Welcome to Runoob
// 此方法常用来字符串->字符串数组(输入模式下的输入数组后的处理)

3.StringBuilder的delete()与deleteCharAt()

两个都是用来删除StringBuilder字符串指定索引处字符的方法

delete(int a,int b)有两个参数,删除索引从[a,b)的字符;

deleteCharAt(int a)只有一个参数,使用时删除索引为a的字符;

StringBuffer buff = new StringBuffer("0123456789");
System.out.println("buff="+buff);

//删除下标从3到5的字符
buff.delete(3,5);
System.out.println("deletionBack="+ buff);

buff = new StringBuffer("0123456789");
//删除下标为8字符
buff.deleteCharAt(8);
System.out.println("delectCharAtBack="+buff);
// 输出如下:
// buff=0123456789
// deletionBack=01256789
// delectCharAtBack=012345679

4.List与数组互相转换

具体参考Java:List与数组相互转换


5.字符->字符串

String.valueOf(str.charAt(i))

6.StringBuilder的append()方法可以接受很多种类型


7.StringBuilder的setCharAt()方法

//第一个参数为索引,第二个参数为该索引处设置的值
public void setCharAt(int index, char ch)
sb.setCharAt(end, temp);

8.重载的remove()方法

ArrayList有两个remove()重载法,分别是:remove(int index) remove(Object o)

若参数输入为1,到底是删除对象1还是删除索引为1的元素呢?

最后发现:remove(1)是删除索引为1的元素;remove(new Integer(1))则删除元素1

因为1默认是基本类型int


9.数组转List集合方法:(注意包装类型)

方法1:
Integer[] nums = new Integer[5]; // 这里不能用int
Arrays.fill(nums,1);
List<Integer> list = Arrays.asList(nums);

方法2:
Integer[] nums = new Integer[5];
List<Integer> list = new ArrayList<>();
Collections.addAll(list, nums);

10.Java中的Math.atan2(double x, double y)方法

将指定的直角坐标(x, y)转换为极坐标(r, θ),并返回弧度θ。

该方法通过计算 y/x 的反正切值来计算弧度θ,值域为(-π, π]。

atan2与atan区别:

参数个数不同:atan(double a),而atan2(double y, double x)。

参数含义不同:atan中的参数a一般传y/x,也就是斜率k,而atan2中的两个参数就是实际中的x坐标和y坐标。

值域不同:atan值域为(-π/2,π/2),而atan2的值域为[-π,π]。

public static void main(String[] args) {
double x = 2, y = 2;
System.out.println(Math.atan2(y, x)); // 0.7853981633974483
System.out.println(Math.atan(y / x)); // 0.7853981633974483
double x2 = 4, y2 = 3;
double x1 = 2, y1 = 1;
System.out.println(Math.atan2(y2 - y1, x2 - x1)); // 0.7853981633974483(45°)
System.out.println(Math.atan((y2 - y1) / (x2 - x1))); // 0.7853981633974483
// 下面有区别
System.out.println(Math.atan2(y1 - y2, x1 - x2)); // -2.356194490192345(-135°)
System.out.println(Math.atan((y1 - y2) / (x1 - x2))); // 0.7853981633974483
}

11.TreeSet返回最小元素与最大元素的API

TreeSet<Integer> set = new TreeSet<>(排序规则));
int first = set.first(); // 排序规则的首个元素
int last = set.last(); // 排序规则的最后一个元素
set.remove(o); // 移除对应元素

12.关于TreeSet自定义排序规则后修改规则中元素的问题

与规则相关并有扰乱顺序的风险时,必须确保这个元素的排序是没有被影响过的,否则在remove()时,会出现定位失败,有可能删除失败,或者删除出错!

因此,当我们用TreeSet作为一个自动排序容器时,更新元素的位置,必须分三个步骤:

1、remove老的元素

2、修改

3、插入修改后的元素

PS:set.add(T t)如果存在了,将不会进行任何操作并返回false

6126. 设计食物评分系统

参考:关于TreeSet的排序对于删除操作的影响


13.List数组的正确写法

创建时候指定类型,然后统一初始化一次,后面直接add即可

这里也用到List存图的方式,比较适合稀疏图,因为List容量可变

通常来说邻接矩阵适合稠密图,稀疏图可以采用HashMap(离散化程度大)或者List数组(离散化程度小/节点索引为[1,n]情形)

207. 课程表

public boolean canFinish(int n, int[][] pres) {
/*
拓扑排序:
只要课程没有循环依赖(成环),就可以顺利按照拓扑排序的规则完成所有课程
思路就是优先消除入度为0的课程,因为这个课程可以直接学不用依赖别的课程
消除到最后看看还有没有没哟被消去的课程即可
*/
// 存储课程之间的依赖关系,比如0依赖1,list[0]中就有1
List<Integer>[] list = new ArrayList[n];
for (int i = 0; i < n; i++) {
list[i] = new ArrayList<>();
}
for (int[] p : pres) {
int next = p[0], pre = p[1];
list[pre].add(next);
}
int[] inDegree = new int[n]; // 入度数组
for (int i = 0; i < n; i++) {
for (int num : list[i]) {
inDegree[num]++;
}
}
int cnt = 0; // 统计入度为0的节点
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
que.add(i);
cnt++;
}
}
while (!que.isEmpty()) {
int poll = que.poll();
for (int num : list[poll]) {
if (--inDegree[num] == 0) {
que.add(num);
cnt++;
}
}
}
return cnt == n;
}

14.关于static关键字在力扣提交的速度优化

375. 猜数字大小 II

优化前代码如下 (67ms/40.2MB)

class Solution {
int[][] memo; // memo[i][j]记录猜中区间[i,j]之间所需的最少钱数
int INF = 0x3f3f3f3f;

public int getMoneyAmount(int n) {
memo = new int[n + 1][n + 1];
return dfs(1, n);
}

private int dfs(int i, int j) {
// base case
if (j - i <= 0) return 0;
// memo中存在
if (memo[i][j] != 0) return memo[i][j];
int min = INF; // 最小值
for (int k = i; k <= j; k++) {
// 维护合法分割点的最小钱数
// 当前分割点的钱数=分割点k猜错的开销+左右区间开销大的一边(保证任意数字都可通过该最大开销猜中)
int cur = k + Math.max(dfs(i, k - 1), dfs(k + 1, j));
min = Math.min(min, cur);
}
memo[i][j] = min; // 记录猜中当前区间的最小钱值
return min;
}
}

static优化后 (8ms/38.1MB)

注意static的优化要在成员里面加上static并且有相应的初始化器

static int[][] memo = new int[201][201];

static int INF = 0x3f3f3f3f;

class Solution {
static int[][] memo = new int[201][201]; // memo[i][j]记录猜中区间[i,j]之间所需的最少钱数
static int INF = 0x3f3f3f3f;

public int getMoneyAmount(int n) {
return dfs(1, n);
}

private int dfs(int i, int j) {
// base case
if (j - i <= 0) return 0;
// memo中存在
if (memo[i][j] != 0) return memo[i][j];
int min = INF; // 最小值
for (int k = i; k <= j; k++) {
// 维护合法分割点的最小钱数
// 当前分割点的钱数=分割点k猜错的开销+左右区间开销大的一边(保证任意数字都可通过该最大开销猜中)
int cur = k + Math.max(dfs(i, k - 1), dfs(k + 1, j));
min = Math.min(min, cur);
}
memo[i][j] = min; // 记录猜中当前区间的最小钱值
return min;
}
}

从67ms直接优化到8ms优化效果超级理想

注意:有部分题型不能在成员中初始化static变量否则会出错!如下:

877. 石子游戏

664. 奇怪的打印机


15.维护两个集合(数组)中前两个最大值

有时候我们不仅要求最大值,有可能还要实时维护次大值,次大值可能会用到

如何高效地维护最大值与次大值呢?最高效的方法就是利用两个变量max1(最大值)与max2(次大值)进行滚动维护

当遇到下一个数字nums[i]>max1大,此时max2=max1;max1=nums[i]

也就是说原来的max1取代了原来的max2,而nums[i]取代原来max1位置(卷起来了)

而max1>=nums[i]>max2时,我们令nums[i]取代原来max2位置,原来的max2就被取代了

当nums[i]==max2 可以维持原状,当nums[i]

PS: 当然,如果我们不熟悉的话可以用优先队列去维护,甚至维护前k大元素都可以

class Solution {
public int minimumOperations(int[] nums) {
/*
考虑两种间隔的前两个最大值+分类讨论
要想最少操作次数,就要充分利用原理有出现的数字
记偶数索引的最多出现的数字为a1,次多出现的数字为a2
记奇数索引的最多出现的数字为b1,次多出现的数字为b2
1.当a1!=b1 这是最理想的结果,直接将其他数字改成a1与b1,总的操作次数为n-(m1[a1]+m2[b1])
2.当a1==b1 此时就有点麻烦了,不能同时将其他数字变为a1与b1因为会产生冲突
此时我们可以有两种选择:选a1与b2 或 a2与b1 (a2与b2数目不多于前两者可以忽略)
取数目总和大的,最后结果为:n-max(m1[a1]+m2[b2],m1[a2]+m2[b1])
重点就是如何维护两个最大值了
*/
int n = nums.length;
int[] m1 = new int[100010], m2 = new int[100010];
int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
// 偶数索引
m1[nums[i]]++;
int cur = m1[nums[i]]; // cur为当前数字nums[i]出现的次数
if (a1 == 0 || cur > m1[a1]) { // 最大出现次数的数字还没出现||当前数字出现次数已经大于a1出现次数
// nums[i]取代a1位置,之前的a1退居a2位置
a2 = a1;
a1 = nums[i];
} else if (nums[i] != a1 && (a2 == 0 || cur > m1[a2])) {
// nums[i]!=a1说明这个nums[i]不是最大值的,此时若次大值处还没赋值或者nums[i]出现次数比原先的a2多
// 那么nums[i]可以取代原来a2的位置
a2 = nums[i];
}
} else {
// 奇数索引
m2[nums[i]]++;
int cur = m2[nums[i]];
if (b1 == 0 || cur > m2[b1]) {
b2 = b1;
b1 = nums[i];
} else if (nums[i] != b1 && (b2 == 0 || cur > m2[b2])) {
b2 = nums[i];
}
}
}
if (a1 != b1) return n - (m1[a1] + m2[b1]);
return n - Math.max(m1[a1] + m2[b2], m1[a2] + m2[b1]);
}
}

16.最大公约数gcd与最小公倍数

public class BiggestFactor {
@Test
public void test() {
int a = 8, b = 5;
System.out.println(a + "与" + b + "最大公约数为:" + maxCommonFactor(a, b));
System.out.println(a + "与" + b + "最小公倍数为:" + minCommonMultiple(a, b));
}

// 最小公倍数:结合最大公约数
private int minCommonMultiple(int a, int b) {
return a * b / maxCommonFactor(a, b);
}

// 最大公约数:辗转相除法
private int maxCommonFactor(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
// return b > 0 ? gcd(b, a % b) : a; (一步到位写法)
}
}

拓展:求一个数组的最大公约数-> 滚动因子 O(N)

6122. 使数组可以被整除的最少删除次数

public int minOperations(int[] nums, int[] numsDivide) {
/*
求最大公因数问题:
原问题等价于求numsDivide的最大公因数maxFac,只要在nums中找到一个可以整除maxFac的数字,那么该数字必定可以被numsDivide所有数整除
将nums排序后找出最小的可以满足上述条件的数字,那么该数字前面的数字就是要删除的数字数目
关键是怎样在接近O(N)时间复杂度内求解数组的最大公因数?
答案是利用前面部分的maxFac与numsDivide[i]求最大公因数,求出来的就表示满足numsDivide[0,i-1]+numsDivide[i]=numsDivide[0,i]的最大公因数
当遍历整个数组就是整个数组的最大公因数
*/
Arrays.sort(nums);
int m = numsDivide.length, n = nums.length;
// 求数组的最大公因数
int maxFac = numsDivide[0];
for (int i = 1; i < m; i++) {
maxFac = gcd(maxFac, numsDivide[i]);
}
for (int i = 0; i < n; i++) {
if (maxFac % nums[i] == 0) return i;
}
return -1;
}

// 求a与b的最大公约数
private int gcd(int a, int b) {
return b > 0 ? gcd(b, a % b) : a;
}

同理可以求得整个数组的最小公倍数

private int minCommonMultiple(int[] nums) {
int res = nums[0];
for (int i = 1; i < nums.lebnght; i++) {
res = maxCommonFactor(res, nums[i]);
}

// 最小公倍数:结合最大公约数
private int minCommonMultiple(int a, int b) {
return a * b / maxCommonFactor(a, b);
}

// 最大公约数:辗转相除法
private int maxCommonFactor(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
// return b > 0 ? gcd(b, a % b) : a; (一步到位写法)
}
return res;
}

17.螺旋矩阵模拟转向trick

6111. 螺旋矩阵 IV

周赛中发现了灵神的这个模拟转向的小trick 可以应用至任意的螺旋矩阵题目

class Solution {
public int[][] spiralMatrix(int m, int n, ListNode head) {
/*
一个模拟的万能转向trick(参考灵神)
*/
int[][] res = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(res[i], -1);
}
ListNode cur = head;
// 上右下左四个进给方向
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// idx为进给方向,x与y是遍历指针
int idx = 0, x = 0, y = -1; // 为了进给第一步向右走了之后才赋值,初始化(x,y)=(0.-1)
// 链表还没走完就继续循环
while (cur != null) {
int newX = x + dirs[idx][0], newY = y + dirs[idx][1];
// 越界或者碰到已经覆盖过的->转向
if (newX < 0 || newX >= m || newY < 0 || newY >= n || res[newX][newY] != -1) idx = (idx + 1) % 4;
x += dirs[idx][0];
y += dirs[idx][1];
res[x][y] = cur.val;
cur = cur.next;
}
return res;
}
}