1.String.Join 方法 (A (String), B (String[])) 在指定 String 数组B的每个元素之间串联指定的分隔符 A,从而产生单个串联的字符串
String [] tmpStr = {abc, def, ghi}; String jn = string.Join(“-“, tmpStr); String.join("" ,strings)
2.split() 根据匹配给定的正则表达式来拆分字符串 String str = "Welcome-to-Runoob" ;for (String retval: str.split("-" )){ System.out.println(retval); }
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); buff.delete(3 ,5 ); System.out.println("deletionBack=" + buff); buff = new StringBuffer ("0123456789" ); buff.deleteCharAt(8 ); System.out.println("delectCharAtBack=" +buff);
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 ]; 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)); System.out.println(Math.atan(y / x)); double x2 = 4 , y2 = 3 ; double x1 = 2 , y1 = 1 ; System.out.println(Math.atan2(y2 - y1, x2 - x1)); System.out.println(Math.atan((y2 - y1) / (x2 - x1))); System.out.println(Math.atan2(y1 - y2, x1 - x2)); System.out.println(Math.atan((y1 - y2) / (x1 - x2))); }
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) { 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 ; 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; 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) { if (j - i <= 0 ) return 0 ; if (memo[i][j] != 0 ) return memo[i][j]; int min = INF; for (int k = i; k <= j; 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 ]; static int INF = 0x3f3f3f3f ; public int getMoneyAmount (int n) { return dfs(1 , n); } private int dfs (int i, int j) { if (j - i <= 0 ) return 0 ; if (memo[i][j] != 0 ) return memo[i][j]; int min = INF; for (int k = i; k <= j; 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) { 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]]; if (a1 == 0 || cur > m1[a1]) { a2 = a1; a1 = nums[i]; } else if (nums[i] != a1 && (a2 == 0 || cur > m1[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; } }
拓展:求一个数组的最大公约数-> 滚动因子 O(N)
6122. 使数组可以被整除的最少删除次数
public int minOperations (int [] nums, int [] numsDivide) { 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 ; } 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 res; }
17.螺旋矩阵模拟转向trick 6111. 螺旋矩阵 IV
周赛中发现了灵神的这个模拟转向的小trick 可以应用至任意的螺旋矩阵题目
class Solution { public int [][] spiralMatrix(int m, int n, ListNode head) { 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 }}; int idx = 0 , x = 0 , y = -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; } }