51工具盒子1.String.Join 方法 (A (String), B (String[])) {#1-String-Join-方法-A-String-B-String}
在指定 String 数组B的每个元素之间串联指定的分隔符 A，从而产生单个串联的字符串
|-----------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 | String [] tmpStr = {abc, def, ghi}; String jn = string.Join("-", tmpStr); // 此时输出为"abc-def-ghi" // 常见用法:字符串数组chs->字符串str String.join("",strings)//{"abcdefghi"} |
2.split() 根据匹配给定的正则表达式来拆分字符串 {#2-split-根据匹配给定的正则表达式来拆分字符串}
|---------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 | String str = "Welcome-to-Runoob"; for (String retval: str.split("-")){ System.out.println(retval); } // 分隔符返回值 :Welcome to Runoob // 此方法常用来字符串->字符串数组(输入模式下的输入数组后的处理) |
3.StringBuilder的delete()与deleteCharAt() {#3-StringBuilder的delete-与deleteCharAt}
两个都是用来删除StringBuilder字符串指定索引处字符的方法
delete（int a,int b）有两个参数，删除索引从[a,b)的字符；
deleteCharAt（int a）只有一个参数，使用时删除索引为a的字符；
|---------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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与数组互相转换 {#4-List与数组互相转换}
具体参考Java：List与数组相互转换
5.字符->字符串 {#5-字符-字符串}
|-----------|---------------------------------------|
| 1 | String.valueOf(str.charAt(i)) |
6.StringBuilder的append()方法可以接受很多种类型 {#6-StringBuilder的append-方法可以接受很多种类型}
7.StringBuilder的setCharAt()方法 {#7-StringBuilder的setCharAt-方法}
|---------------|------------------------------------------------------------------------------------------------------|
| 1 2 3 | //第一个参数为索引,第二个参数为该索引处设置的值 public void setCharAt(int index, char ch) sb.setCharAt(end, temp); |
8.重载的remove()方法 {#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集合方法：(注意包装类型) {#9-数组转List集合方法：-注意包装类型}
|---------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 | 方法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)方法 {#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的值域为[-π,π]。
|------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 | 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 {#11-TreeSet返回最小元素与最大元素的API}
|-----------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 | TreeSet<Integer> set = new TreeSet<>(排序规则)); int first = set.first(); // 排序规则的首个元素 int last = set.last(); // 排序规则的最后一个元素 set.remove(o); // 移除对应元素 |
12.关于TreeSet自定义排序规则后修改规则中元素的问题 {#12-关于TreeSet自定义排序规则后修改规则中元素的问题}
与规则相关并有扰乱顺序的风险时，必须确保这个元素的排序是没有被影响过的，否则在remove()时，会出现定位失败，有可能删除失败，或者删除出错！
因此，当我们用TreeSet作为一个自动排序容器时，更新元素的位置，必须分三个步骤：
1、remove老的元素
2、修改
3、插入修改后的元素
PS:set.add(T t)如果存在了，将不会进行任何操作并返回false
13.List数组的正确写法 {#13-List数组的正确写法}
创建时候指定类型，然后统一初始化一次，后面直接add即可
这里也用到List存图的方式，比较适合稀疏图，因为List容量可变
通常来说邻接矩阵适合稠密图，稀疏图可以采用HashMap（离散化程度大）或者List数组(离散化程度小/节点索引为[1,n]情形)
|---------------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | 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关键字在力扣提交的速度优化 {#14-关于static关键字在力扣提交的速度优化}
优化前代码如下 (67ms/40.2MB) ：
|---------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 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;
|------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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变量否则会出错！如下：
15.维护两个集合（数组）中前两个最大值 {#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大元素都可以
|------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | 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与最小公倍数 {#16-最大公约数gcd与最小公倍数}
|------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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)
|------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | 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; } |
同理可以求得整个数组的最小公倍数
|------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | private int minCommonMultiple_(int[] nums) { int res = nums[0]; for (int i = 1; i < nums.lebnght; i++) { res = minCommonMultiple(res, nums[i]); } return res; } // 最小公倍数 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; (一步到位写法) } |
17.螺旋矩阵模拟转向trick {#17-螺旋矩阵模拟转向trick}
周赛中发现了灵神的这个模拟转向的小trick 可以应用至任意的螺旋矩阵题目
|---------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | 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; } } |
