0%

[toc]

1.1运行状态#

  • 行于用户态的进程可以执行的操作和访问的资源都会受到极大的限制
  • 而运行在内核态的进程则可以执行任何操作并且在资源的使用上没有限制

1.1.1 用户态#

程在执行用户自己的代码时,则称其处于用户运行态(用户态),相当于运行用户自己的代码函数都是用户态,linux系统的底层调用接口不属于用户态。

  • 访管指令是用户态调用的

1.1.2 核心态#

  • 内核态,在操作系统内核运行的状态。
  • 核心态运行时的特
  • 负责管理进程、存储
    用户态什么时候会进入核心态?就是下面提到的系统调用、中断和异常。

Q: 为什么要区分系统态和用户态?#

A:

  • CPU将指令分为特权指令和非特权指令,对于那些危险的指令,只允许操作系统及其相关模块使用,普通的应用程序只能使用那些不会造成灾难的指令。Intel的CPU将特权级别分为4个级别:RING0,RING1,RING2,RING3。
  • 最主要原因是要把用户程序和系统程序区分开,以利于程序的共享和保护。显然,这也是以增加系统复杂度和系统开销为代价的。

1.2 系统调用#

  • 系统调用概念:从用户进程自身堆栈 切换为系统堆栈
  • 执行系统调用后,就会进入核心态
  • 时钟管理属于核心态的概念(用于进程切换计时和系统时间)
  • 和系统资源有关的都要用到系统调用,如下:
    1. 存储
    2. IO传输
    3. 文件管理
  • 系统调用需要在用户态触发trap命令

陷入指令是指用户程序所依靠的指令,用于发起系统调用,请求操作系统提供服务。陷入指令有其中一点特殊在于,其只能在用户态下执行,而不可以在核心态下执行

trap命令具体流程:

  1. 用户态程序将一些数据值放在寄存器中, 或者使用参数创建一个堆栈(stack frame), 以此表明需要操作系统提供的服务
  2. 用户态程序执行陷阱指令
  3. CPU切换到内核态, 并跳到位于内存指定位置的指令, 这些指令是操作系统的一部分,
  4. 后面的这些指令会读取程序放入内存的数据参数, 并执行程序请求的服务
  5. 系统调用完成后, 操作系统会重置CPU为用户态并返回系统调用的结果

1.3 中断和异常#

  • 外中断 = 中断: 即外设请求或者人为程序干预
  • 内中断= 异常: 指令中断(溢出)、 软件故障、硬件故障。

即中断就是正常行为, 异常则可能是故障引发。

1.4 linux延申#

在这里插入图片描述
https://www.cnblogs.com/bakari/p/5520860.html


Q: 插上电源之后,计算机系统做了什么?#

A:

  1. 加电––––打开电源开关,给主板和内部风扇供电。
  2. 启动引导程序––––CPU开始执行存储在ROM BIOS中的指令。
  3. 开机自检––––计算机对系统的主要部件进行诊断测试。
  4. 加载操作系统––––计算机将操作系统文件从磁盘读到内存中。
  5. 检查配置文件,定制操作系统的运行环境––––读取配置文件,根据用户的设置对操作系统进行定制。
    在Windows中对运行环境进行配置的方法很多,比如修改注册表,编辑System.ini、Win.ini等系统配置文件,或将希望启动完Windows后立即执行的内容放入Windows的启动(Startup)组中。
  6. 准备读取命令和数据––––计算机等待用户输入命令和数据。
    接通电源后,计算机做了那些基本操作

1662394885933

本期总结:#

  1. 滑动窗口最大值,一定要用过期有限队列

2395. 和相等的子数组 - 力扣(LeetCode)

1662394935649

直接哈希表,但是要处理long的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean findSubarrays(int[] nums) {
Set<Long> map = new HashSet<>();
for (int i = 0; i < nums.length;i++) {
if (i + 1 < nums.length) {
int j = i + 1;
if(map.contains((long)nums[i] + nums[j])) {
return true;
}
map.add((long) (nums[i] + nums[j]));
}
}
return false;
}

}

2396. 严格回文的数字 - 力扣(LeetCode)

1662395006184

还好,不需要考虑回文比较的性能,直接统计每个数字即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public boolean isStrictlyPalindromic(int n) {
int m = n - 2;
for (int i = 2; i <= n-2;i++) {
int num = n;
StringBuilder sb = new StringBuilder();
while (num > 0) {
sb.append(num % i);
num /= i;
}
String s1 = sb.toString();
String s2 = sb.reverse().toString();
if (!s1.equals(s2)) {
return false;
}
}
return true;
}
}

2397. 被列覆盖的最多行数 - 力扣(LeetCode)

1662395135512

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
class Solution {
public int maximumRows(int[][] mat, int cols) {
dfs(mat, cols, 0, new boolean[mat[0].length]);
return maxCount;
}
int maxCount = 0;
public void dfs(int[][] mat, int colRealCount, int colIndex, boolean[] select) {
if (colRealCount == 0) {
int count = 0;
for(int y = 0;y<mat.length;y++) {
boolean flag = true;
for (int x = 0; x < mat[0].length;x++) {
if (mat[y][x] == 1 && !select[x]) {
flag =false;
break;
}
}
if (flag) {
count++;
}
}
maxCount = Math.max(maxCount, count);
return;
}
for (int col = colIndex;col < mat[0].length;col++) {
select[col] = true;
dfs(mat, colRealCount-1, col+1, select);
select[col] = false;
}
}
}

直接dfs即可


2398. 预算内的最多机器人数目 - 力扣(LeetCode)

1662395196873

没有做完就总结, 已经忘记当时为什么11点30就提交了第一次,然后改了半个小时也没搞定。。

好像是因为 我要求的应该是滑动窗口的最大值以及滑动窗口的总和, 然而最大值那个好像搞错了,应该要引入过期队列的

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
class Solution {
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
int[][] array = new int[chargeTimes.length][2];
for (int i = 0; i < chargeTimes.length;i++) {
array[i] = new int[]{chargeTimes[i], runningCosts[i]};
}
int left = 0, right = runningCosts.length+1;
while (left < right) {
int mid = left + (right - left) / 2;
int queueCount = mid - 1;
int k = mid;
if (mid == 0) {
return 0;
}
long sum = 0;
boolean flag = false;
Queue<int[]> queue = new PriorityQueue<>((a,b)->(b[1]-a[1]));
for (int i = 0 ; i < array.length;i++) {
sum += array[i][1];
queue.offer(new int[]{i, array[i][0]});
if ( i < mid - 1) {
continue;
}
while (!queue.isEmpty() && queue.peek()[0] < i - queueCount) {
queue.poll();
}
int max = queue.peek()[1];
long ksum = sum ;
long buck = max + k * ksum;
if (buck <= budget) {
flag = true;
break;
}
sum -= array[i - queueCount][1];
}
if(flag) {
left = mid+1;
} else {
right = mid;
}
}

return Math.max(0, left-1);
}
}

排个序就好了,没啥难的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
int[] res = new int[queries.length];
for (int i = 0; i < queries.length;i++) {
int sum = 0;
int len = 0;
for (int j = 0;j<nums.length;j++) {
if (sum + nums[j] > queries[i]) {
break;
}
sum += nums[j];
len++;
}
res[i] = len;
}
return res;
}
}

6161. 从字符串中移除星号 - 力扣(LeetCode)

1661701444253

既然每次要移除最左边, 我就从右往左边遍历, 碰到星号,说明下次碰到字母时要变星号,记录一个数字即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public String removeStars(String s) {
boolean[] bs = new boolean[s.length()];
int needDeduceCount = 0;
for (int i = s.length()-1;i>=0;i--) {
if (s.charAt(i) == '*') {
needDeduceCount++;
bs[i] = true;
} else if (needDeduceCount > 0) {
needDeduceCount--;
bs[i] = true;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length();i++) {
if (bs[i]) {
continue;
}
sb.append(s.charAt(i));
}
return sb.toString();
}
}

6162. 收集垃圾的最少总时间 - 力扣(LeetCode)

1661701543477

这种题目啥情况,啥算法也不用,直接3次遍历即可,主要是得计算到最后一个有这个垃圾的房子时就要截至了

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
class Solution {
public int garbageCollection(String[] garbage, int[] travel) {
char[] cs = new char[]{'G', 'P', 'M'};
int res = 0;
for (char c : cs) {
int sum = 0;
int realSum = 0;
for (int i = 0; i < garbage.length; i++) {
String garba = garbage[i];
int count = 0;
for (char g : garba.toCharArray()) {
if (g == c) {
count++;
}
}
if (count > 0) {
sum += count;
realSum = sum;
}
if (i != garbage.length-1) {
sum += travel[i];
}
}
res += realSum;
}
return res;
}
}

6163. 给定条件下构造矩阵 - 力扣(LeetCode)

1661701601482

1661701607970

想了半太天才意识到是拓扑排序, 越是叶子的,越可以放前面, 越是根的,越可以放后面

早点想到的话应该20分钟就做出来了,拓扑还是很简单的

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
47
48
49
50
51
52
53
54
class Solution {
public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
int[] rows = new int[k+1];
int[] cols = new int[k+1];
if (!sort(k, rowConditions, rows)
|| !sort(k, colConditions, cols)) {
return new int[][]{};
}

int[][] res = new int[k][k];
for (int i = 1; i <=k;i++) {
res[rows[i]][cols[i]] = i;
}
return res;
}

private boolean sort(int k, int[][] rowConditions, int[] rows) {
int[] inCount = new int[k+1];
List<Integer>[] outLists = new List[k+1];
for (int i = 1; i <=k;i++) {
outLists[i] = new ArrayList();
}
for (int[] row : rowConditions) {
inCount[row[1]]++;
outLists[row[0]].add(row[1]);
}
int y = 0;
boolean[] vis = new boolean[k+1];
while (true) {
int i;
for (i = 1; i <= k; i++) {
if (inCount[i] > 0 || vis[i]) {
continue;
}
vis[i] = true;
for (int out : outLists[i]) {
inCount[out]--;
}
rows[i] = y;
y++;
break;
}
if(i == k+1) {
break;
}
}
for (int i = 1;i<=k;i++) {
if (inCount[i] >0) {
return false;
}
}
return true;
}
}

1662393708201

本期总结:#

  1. 子数字、子序列的题目, 一定要关注一下有没有”连续“二字!
  2. 排列组合公式可以记忆一下,特别是C二维数组中左边是啥,右边是啥

2399. 检查相同字母间的距离 - 力扣(LeetCode)

1662393833962

直接2个遍历找距离即可,因为每个字母恰好是2次!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean checkDistances(String s, int[] distance) {
for (int i = 0; i < s.length();i++) {
char c = s.charAt(i);
for (int j = i+1;j<s.length();j++) {
if (c == s.charAt(j)) {
int len = j - i - 1;
if (distance[c-'a'] != len) {
return false;
}
}
}
}
return true;

}
}

2400. 恰好移动 k 步到达某一位置的方法数目 - 力扣(LeetCode)

1662393987326

这个题目为啥想了20分钟。。

很明显左移和右移的个数是确定的!

那基本就是排列组合了,结果那个排列组合的方法又整了半天,组合数的计算方式总是记不住!

个数少的时候,直接杨辉三角解法即可, 注意我这个是c[n][m], n是大的那个!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
public int numberOfWays(int startPos, int endPos, int k) {
int cha = Math.abs(startPos - endPos);
int chak = k - cha;
if (chak %2 == 1) {
return 0;
}
if (chak < 0) {
return 0;
}
int k1 = cha + chak/2;
int k2 = chak/2;

int mod = 1000000007;
long[][] c = new long[k+1][k+1];
for(int i=0;i<=k;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
return (int)c[k][k1];
}
}

2401. 最长优雅子数组 - 力扣(LeetCode)

1662394562551

我TM又没看到“连续”二字!!!题目里也没有体现!

以后看到子数组和子序列都注意啊!注意是不是连续,我十多分钟都花在怎么处理非连续了!

知道连续以后就很容易了,记录最左边那个会造成同位1,然后时刻更新最左边的有效点

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
class Solution {
public int longestNiceSubarray(int[] nums) {
int[] indexNears = new int[33];
Arrays.fill(indexNears, -1);
int lastLeft = 0;
int res = 0;
for (int i = 0; i < nums.length;i++) {
int num = nums[i];
int k = 0;
int novalidLeft = -1;
while (num > 0) {
if (num % 2 == 1) {
novalidLeft = Math.max(novalidLeft, indexNears[k]);
indexNears[k] = i;
}
num/=2;
k++;
}
int canValidLeft = novalidLeft + 1;
if (canValidLeft > lastLeft) {
lastLeft = canValidLeft;
}
res = Math.max(res, i - lastLeft + 1);
}
return res;
}

}

2402. 会议室 III - 力扣(LeetCode)

等待后面纳入日常中重新写

题目我会做,就是几个细节没处理好导致gg,主要就是优先队列的比较函数

  1. 当同时有几个会议室需要释放时, 需要选最小的会议室先出队,这导致我的优先队列比较函数非常关键
  2. 会议延期要放入一个常规队列,且需要更新时间,还要对原先优先队列里的结束时间做过期处理
  3. 注意int范围越界,特别是比较函数不可以直接a[0] - b[0],都可能越界
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
public int mostBooked(int n, int[][] meetings) {
long[][] newMeetins = new long[meetings.length][2];
for (int i = 0; i < meetings.length;i++) {
newMeetins[i] = new long[]{meetings[i][0], meetings[i][1]};
}

int j = 0;
// 会议占用了哪个会议室
int[] places = new int[newMeetins.length];
//Arrays.fill(places, n+1);
Queue<long[]> meets = new PriorityQueue<>((a,b)->(!(a[1] == b[1] && a[0] == 1 && b[0] == 1) ? ( a[1] >= b[1] ? 1 : -1) :(places[(int)a[2]] - places[(int)b[2]])));


for (long[] meet : newMeetins) {
meets.add(new long[]{0, meet[0], j});
meets.add(new long[]{1, meet[1], j});
j++;
}


PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.addAll(IntStream.range(0, n).boxed().collect(Collectors.toSet()));
Queue<Integer> waitList = new LinkedList<>();
Set<Integer> waitSet = new HashSet<>();
int[] meetHappendCounts = new int[n];
while (!meets.isEmpty()) {
long[] meet = meets.poll();
long time = meet[1];
int meetIndex = (int)meet[2];
if (meet[0] == 0) {
if (!priorityQueue.isEmpty()) {
int place = priorityQueue.poll();
meetHappendCounts[place]++;
places[meetIndex] = place;
} else {
waitList.offer(meetIndex);
waitSet.add(meetIndex);
}
} else {
if (newMeetins[meetIndex][1] != time) {
continue;
}
if (waitSet.contains(meetIndex)) {
continue;
}
// 要识别这个end是不是延迟的
int place = places[meetIndex];
if (!waitList.isEmpty()) {
int waitmeet = waitList.poll();
waitSet.remove(waitmeet);
long startTime = newMeetins[waitmeet][0];
long endTime = newMeetins[waitmeet][1];
long use = endTime - startTime;
long newEndTime = time + use;
newMeetins[waitmeet][1] = (long)newEndTime;
meets.offer(new long[]{1, newEndTime, waitmeet});
places[waitmeet] = place;
meetHappendCounts[place]++;
} else {
priorityQueue.offer(place);
}
}
}

int max = 0;
int select = 0;
for (int i = 0; i < n;i++) {
if (meetHappendCounts[i] > max) {
max = meetHappendCounts[i];
select = i;
}
}
return select;
}
}

[toc]

一、提升开发者自测能力#

面试时的上机编程有一个特点,就是不会给出“错误用例”。
有时也会听到“为什么不能提示错误用例”之类的吐槽。
这种思维类似于"测试为什么没测出来这个bug" 、“缺少堆栈和日志,不能设断点,我没法排查这个问题”

然而被提单次数,会影响自己的代码质量评估。 生产环境往往也因为安全限制,无法直接远程调试。 因此这种思维是很危险和不可取的。
image.png

算法题熟练的同学,有个特点,就是能在接口中提前加上各种判断,或者写上todo注释作为开发遗留。
原因就是在大量的算法题练习过程中,掌握了边界的处理,或者通过阅读代码逻辑,找出其中漏洞。
学习开发者的白盒测试理论是很有利于解决这种情况的。
里面的几种边界,对于开发者自身应该要能熟练掌握。
image.png

因此大家平时如果在leetcode或者其他平台练习题目时,最好以零出错为目目标一次性搞定。 出错的第一时间, 先不要拿着用例去调试, 而是想一想自己为什么会漏了这种情况。 否则很容易形成对错误用例和调试的依赖。

二、加深对编程语言的使用#

1.api应用#

以java为例, 当你频繁用for循环写各种初始化或者赋值代码时,可能会觉得心很累。
例如需要将"0,1,2,3"这个字符串转成一个整数数组,新手写法是

1
2
3
4
5
6
7
public static int[] buildIntArray(String str) {
String[] numStrs = str.split(",");
int[] result = new int[numStrs.length];
for (int i = 0;i<result.length;i++) {
result[i] = Integer.valueOf(numStrs[i]);
}
}

而使用javaStream的话,一行代码就搞定了

1
2
3
public static int[] buildIntArray(String str) {
return Arrays.stream(str.split(",")).mapToInt(Integer::valueOf).toArray();
}

因此练习中即使解决了题目,也不妨看看其他人的代码, 进而将好的用法引申到工作中。(当然写太复杂的java stream代码会影响可读性,视情况而用)。

2. 语法问题查缺补漏#

另外练习过程中,也能遇到很多编程知识的应用。 假设我们需要自定义一个优先队列,有人写了下面这个代码,却有部分用例无法通过,为什么呢?

1
2
3
4
5
6
7
8
9
10
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
if (a != b) {
// 当a=b的另一种判断条件.....
} else {
return a - b;
}
}
});

实际上是因为 Integer包装类型不能用==和!=直接去比较, 因为Integer范围不在-128到127时,比较的就是引用地址而非实际大小了。因此应该用equals方法。从这里可以看出一些编程知识在开发工作中的重要性。

三、收获“思想”,作为程序优化的思想储备#

相信很多人从做题攻略和自主练习过程中, 学到了 动态规划、 链表、KMP、二分查找、 并查集等 诸多“套路”。 这些算法却在平时的业务开发中却很少用到, 不免会让人吐槽都是"花拳绣腿",折腾人,对绩效和KPI也没有帮助。

那么可以换个角度理解,学习数学有什么用? 如果仅仅是用于工程应用,不做研究,大部分也只是做api的调用者,不会追究到数学证明、公式推导等层面。
image.png

但数学作为从小到大一直在重点考察的学科一直陪伴着我们。为什么?
个人理解,是因为数学可以锻炼我们的逻辑思维能力,培养一种理性思维和解决问题的方式。

算法和数学都是一种思想。 包括你去学习设计模式、学习jvm原理、学习操作系统等,都是在学习一种思想。 而对思想的理解和加深,则需要大量的练习。因此上机编程成了重要的考察方式。

以二分查找为例,有的人只关注循环不变式模板、"逃课"api(指不用手写二分,可以直接用的接口,例如treeMap的floor())
有的人则会在大量的练习中,悟到什么时候、哪种情况下可以剔除不必要的搜索遍历过程,并使用二分解决性能问题。

因此建议大家在备考刷题的过程中, 除了关注"套路"、"题目面板"外,多关注一下这个解法的背后思想是什么, 当你能理解到这一个层次时, 往往对你的编程工作会有持续的潜移默化影响,尽管可能不是那么显而易见罢了。

四、保持代码思维和手感#

大家应该都有这种时期, 就是某段时间都是各种杂事,可能1个月就写了几百行代码,事后再捡起来就不会写了。
因此这种时期练练题目,对自己也维持手感也会有帮助。有句话叫做“ 流水不腐户枢不蠹”。
另外看到一段关于跑步的话,这里分享一下:

如果你经常跑步,你也许会知道其实 4 个多小时一点都不快,完全就是业余跑者的水平;也许你也知道,其实即便是大众跑者,5 年完成百公里也是相当难的,甚至身体的原因,不是所有人都能跑下来越野。
所以当我开始追求速度时,慢慢发现,当我在为 5 公里没有跑进 20 分而焦虑和努力时,学校里的那些体育生都在追求如何跑进 17 分了。后来我释然了:之前我对于跑步的疯狂,是因为没有搞懂跑步的意义:
因为跑步不会让我毕业。
因为跑步不会让我找到工作。
因为跑步不会让我找到女朋友。
跑步对于我的意义,就是能让我保持身体健康,仅此而已。


以上就是我的一些想法,个人技术水平和经验有限,没有资格让大家全部认同。
另外考查程序员素养的指标绝对不仅仅只是代码。上机题的考察方式本身也可能存在缺陷。如果你是对此有更深理解的朋友,也可以讲一下你对这方面的看法和收获,大家一起学习和参考。

[toc]

2022-09-27#

https://leetcode.cn/problems/c32eOV/

找循环链表入口,步骤如下:

  1. 先是1个快节点,1个慢节点,然后两个能相碰那就说明有环。
  2. 然后慢节点再走一遍,和快节点重新相遇,能计算出环的长度
  3. 然后再从头部开始,一个节点先走环的长度步, 然后两个节点一起开始走,相遇后就是入口了

2022-09-25#

面试题 17.19. 消失的两个数字 - 力扣(LeetCode)

凡是问你找到缺的数字, 都要考虑是否用位运算

1~n中找到缺失的数字, 则你可以在造一个真正的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
class Solution {
public int[] missingTwo(int[] nums) {
int sum = 0;
for (int i = 0;i<nums.length;i++) {
sum ^= nums[i];
}
int n = nums.length + 2;
for (int i =1;i<=n;i++) {
sum ^= i;
}
int bits = (~(sum-1)) & (sum);
int num1 = 0;
int num2 = 0;
for (int num : nums) {
if ((num & bits) > 0) {
num1 ^= num;
} else {
num2 ^= num;
}
}
for (int i = 1;i<=n;i++) {
if ((i&bits) > 0) {
num1 ^= i;
} else {
num2 ^= i;
}
}
return new int[]{num1, num2};
}
}

2022-09-24#

508. 出现次数最多的子树元素和 - 力扣(LeetCode)

搜索后用哈希表存储即可。

List快速转int[]的方法:

1
res.stream().mapToInt(Integer::intValue).toArray();

1130. 叶值的最小代价生成树 - 力扣(LeetCode)

一开始想着贪心,结果不行,并不能最前面选的是最优,那后面都是最优,即不能从上往下。

实际上要从下往上, 用动态规划存储,很容易就能处理了。

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
class Solution {
Map<Integer, Integer> caches = new HashMap<>();

public int mctFromLeafValues(int[] arr) {
int n = arr.length;
int[][] dp = new int[n][n];
int[][] maxs = new int[n][n];
for (int i = 0; i < n;i++) {
maxs[i][i] = arr[i];
}

for (int len = 2; len <= n;len++) {
for (int i = 0; i+len - 1 < n;i++) {
int minSum = Integer.MAX_VALUE;
int j = i + len - 1;
for (int k = i;k < j;k++) {
int mul = maxs[i][k] * maxs[k+1][j];
minSum = Math.min(minSum, mul + dp[i][k] + dp[k+1][j]);
}
dp[i][j] = minSum;
for (int k = i;k<=j;k++) {
maxs[i][j] = Math.max(maxs[i][j], arr[k]);
}
}
}
return dp[0][n-1];
}
}

1652. 拆炸弹 - 力扣(LeetCode)

题目数据量很小,直接暴力即可,如果数据量大了,可以改成使用滑动窗口。

2022-09-23 链·表题做懵逼,注意复用方法#

707. 设计链表 - 力扣(LeetCode)

这么简单的链表题为啥写了一个小时

因为数量级很小,不用维护复杂度,因此不用考虑设计一个尾节点,这会增加维护成本。

直接先写一个基础的getNode(index)方法,其他所有方法都基于这个来。

怎么避免写错或者写漏指针?

画一个图, 确认一下这次动作会有2根线变化,还是会有4根线变化,确认变化数量,从而避免遗漏。

注意next可能为空,要经常加判断

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class MyLinkedList {

static class Node {
Node pre;
Node next;
int val;
public Node(int val) {
this.val = val;
}
}

Node head = new Node(0);
int count = 0;
public MyLinkedList() {

}

public int get(int index) {
Node node = getNode(index);
return node != null ? node.val : -1;
}

public Node getNode(int index) {
if (index < 0) {
return head;
}
Node node = head.next;
while(node != null && index>0) {
node = node.next;
index--;
}
return node;
}

public void addAtHead(int val) {
Node node = new Node(val);
if (head.next != null) {
head.next.pre = node;
}
node.next = head.next;
head.next = node;
node.pre = head;
count++;
}

public void addAtTail(int val) {
Node node = new Node(val);

Node tail = getNode(count-1);

tail.next = node;
node.pre = tail;
count++;
}

public void addAtIndex(int index, int val) {
if (index > count) {
return;
}
Node node = getNode(index-1);
Node newNode = new Node(val);
Node next = node.next;

node.next =newNode;
newNode.pre = node;
newNode.next = next;
if (next != null) {
next.pre = newNode;
}

count--;
}

public void deleteAtIndex(int index) {
Node node = getNode(index);
if (node == null || head == node) {
return;
}
Node pre = node.pre;
Node next = node.next;
pre.next = next;
if (next != null) {
next.pre = pre;
}
count--;
}
}

改进版L:

实际上addIndex就可以替代Head和tail了,避免反复写

1
2
3
4
5
6
7
8
9

public void addAtHead(int val) {
addAtIndex(0, val);
}

public void addAtTail(int val) {
addAtIndex(size, val);
}

2022-09-20#

划分组可以用DP而不是DFS#

698. 划分为k个相等的子集 - 力扣(LeetCode)

先是最基础的DFS搜索,记忆化(因为只有16位很明显要状态压缩记忆化)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
Arrays.sort(nums);
int sum = Arrays.stream(nums).sum();
if (sum %k != 0) {
return false;
}
int subSum = sum/k;
dfs(nums, k, 0, subSum, 0, new boolean[nums.length]);
return res;
}
boolean res = false;
Set<Integer> set = new HashSet<>();
void dfs(int[] nums, int k, int count, int needSum, int nowSum, boolean[] vis) {
if (res) {
return;
}

int key = 0;
for (int i = 0; i < vis.length;i++) {
if (vis[i]) {
key += (1<<i);
}
}
if (set.contains(key)) {
return;
}

if (count == k) {
int useCount = 0;
for (int i = 0; i < vis.length;i++) {
if (vis[i]) {
useCount++;
}
}
if (useCount == nums.length) {
res = true;
}
set.add(key);
return;
}
for (int i = 0; i < nums.length;i++) {
if (vis[i]) {
continue;
}
int nextSum = nowSum + nums[i];
if (nextSum > needSum) {
continue;
}
vis[i] = true;
if (needSum == nextSum) {
dfs(nums, k, count+1, needSum, 0, vis);
} else {
dfs(nums, k, count, needSum, nextSum, vis);
}
vis[i] = false;
}
set.add(key);
}
}

其实可以用动态规划, 脑子里对这种优先想到的是 明确一个值例如1101, 去掉某个1找到他的前置状态然后判断

这种坏处在于必须按1的个数先遍历, 比较麻烦

可以从0, 找到任意一个1,尝试放入,并修改下一次的状态, 后面遇到对应状态已经设置过了就不处理了, 类似于上卖弄过程的反向的Dp。 前提你要确认Dp的状态是不会被变更的,这里的Dp和dpSum在位一致的情况下是不会更新的。

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
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
if (sum %k != 0) {
return false;
}
int subSum = sum/k;
Arrays.sort(nums);
int n = nums.length;
boolean[] dpFlag = new boolean[1<<n];
int[] dpSum = new int[1<<n];
dpFlag[0] = true;
// 从下往上压缩扩散压缩
for (int i = 0; i < 1<<n;i++) {
if (!dpFlag[i]) {
continue;
}
for (int j = 0; j < n;j++) {
// 放到一组内大于目标值,肯定不符合要求
if (dpSum[i] + nums[j] > subSum) {
break;
}
//
if ((i &(1<<j)) > 0) {
continue;
}
int nextIndex = i | (1<<j);
if (dpFlag[nextIndex]) {
continue;
}
// 取余是因为如果正好满足一组,就可以直接清0了
dpSum[nextIndex] = (dpSum[i] + nums[j])%subSum;
dpFlag[nextIndex] = true;
}
}

// n位全是1, 是(1<<n) - 1, 注意不是1<<n-1
return dpFlag[(1<<n)-1];
}

}

2022-09-16#

第一题: 多个连续区间长度、面积问题——扫描线#

多个连续区间,叠加部分要去掉或者叠加某个价值,这种题常见于那种任务流

区间的坐标很大导致无法遍历坐标值, 但可以遍历起点和终点坐标。

如果是求多个连续区间叠加后的横向长度(去除覆盖部分) ,就是最基础的扫描线应用

每次碰到关键点, 就将当前宽度(只能是0或者1)乘上(当前位置减去上一个位置)

然后直接更新上一个位置

并修改宽度(你只要考虑当前线段数量是否为0还是1)

求叠加线段长度的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public long getYLen(List<int[]> yList) {
Collections.sort(yList, (a,b)->(a[0] - b[0]));
int last = -1;
int count = 0;
long sum = 0;
for (int[] yp : yList) {
int y = yp[0];
boolean isStart = yp[2] == 0;
// 当前线段数量大于等于1,宽度就为1
sum += (count>=1?1:0) * (y - last);

// 根据是起点还是终点更新线段数量
if (isStart) {
count++;
} else {
count--;
}
last = y;
}
sum %= MOD;
return (int)sum;
}

而这题求的是面积

因此是二维的扫描线应用,即用到了两个方向上的扫描线

先是按x作为扫描点,从左往右遍历

每次遇到起点或者终点时, 先尝试计算 当前宽度 * (当前点-上一个点)

当前宽度则根据上面的y轴叠加线段的计算方式计算

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
47
48
49
50
51
52
53
54
public int rectangleArea(int[][] rectangles) {
List<int[]> xlist = new ArrayList<>();
for (int i = 0; i < rectangles.length;i++) {
int[] rect = rectangles[i];
int xLeft = rect[0];
int xRight = rect[2];
xlist.add(new int[]{xLeft, i, 0});
xlist.add(new int[]{xRight, i, 1});
}
Collections.sort(xlist, (a,b)->(a[0] - b[0]));

List<int[]> ylist = new ArrayList<>();
int lastX = 0;
long res = 0;
for (int[] xp : xlist) {
int x = xp[0];
int i = xp[1];
boolean isLeft = xp[2] == 0;
int[] rect = rectangles[i];
int yDown = rect[1];
int yUp = rect[3];
if (isLeft) {
// 把之前那段面积先加起来
long ylen = getYLen(ylist);
long sum = ylen * (x - lastX);
sum %= MOD;
res += sum;
res %= MOD;
// 接着加入这段新的y区间
ylist.add(new int[]{yUp, i, 1});
ylist.add(new int[]{yDown, i, 0});
lastX = x;
} else {
// 右点
// 先计算之前的面积
long ylen = getYLen(ylist);
long sum = ylen * (x - lastX);
sum %= MOD;
res += sum;
res %= MOD;
// 删除这段y区间
// 删除的时候要注意用迭代器
Iterator<int[]> it = ylist.iterator();
while (it.hasNext()) {
if (it.next()[1] == i) {
it.remove();
}
}
lastX = x;
}
}

return (int)res;
}

2022-09-15#

672. 灯泡开关 Ⅱ - 力扣(LeetCode)

这题最佳题解是找规律,逐步定位到只需要判断前面4个灯泡即可。

但是这个找规律其实并不好找,不符合计算机思维。实际上可以不用得到只判断4个灯泡这个条件。而是知道以下几点即可:

  1. 每个开关只有开奇数次才算生效。 因此要么0要么1,4个开关可以理解成4位二进制
  2. 当二进制中1的个数小于等于按压次数时,只要取余相同,则一定可以得到这种情况

那么基于这个,就可以直接模拟计算出16种按压情况下,n位灯泡的总数(用hashset)不用找那个规律。

注意编号是从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
class Solution {
public int flipLights(int n, int presses) {
Set<String> sets = new HashSet<>();
for (int i = 0; i < 16;i++) {
int[] arr = new int[n];

int[] bits = new int[4];
int sum = 0;
for (int j = 0; j < 4;j++) {
bits[j] = (i>>j)&1;
sum += bits[j];
}
if (sum <= presses && sum %2 == presses %2) {
StringBuilder sb= new StringBuilder();
for (int j = 0; j < arr.length;j++) {
if (bits[0] == 1) {
arr[j] = arr[j] ^ 1;
}
if (bits[1] ==1 && j %2 == 0) {
arr[j] = arr[j] ^ 1;
}
if (bits[2] ==1 && j %2 == 1) {
arr[j] = arr[j] ^ 1;
}
if (bits[3] ==1 && j %3 == 0) {
arr[j] = arr[j] ^ 1;
}
sb.append(arr[j]);
}
sets.add(sb.toString());
}
}
System.out.println(sets);
return sets.size();
}
}

2022-09-14#

第一题:前缀和+哈希或者前缀和+单调栈#

1124. 表现良好的最长时间段 - 力扣(LeetCode)

又是涉及sum[i]、sun[j]然后求j-i最大的题目

然后果不其然想歪了怎么也写错了

最后要么用哈希记录最左端位置,因为是逐个按1或者-1增加前缀和的,那么当你是-5的时候,前面如果有-6,则一定是最前面的-6, 如果没有-6说明不行。 如果你是5的前缀和,那默认当前位置最长了。

要么是单调栈,但是是特殊的单调栈,不会出栈,只是构造递减的栈,然后反向遍历,这个根本想不到。

这题实际上偏难了不算中等题。

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
class Solution {
public int longestWPI(int[] hours) {
int[] pre = new int[hours.length];
int sum = 0;
for (int i = 0; i < hours.length;i++) {
if (hours[i] > 8) {
sum++;
} else {
sum--;
}
pre[i] = sum;
}
Map<Integer, Integer> sumToIndexMap = new HashMap<>();
int res = 0;
for (int i = 0; i < hours.length;i++) {
if (pre[i] > 0) {
res = Math.max(res, i + 1);
} else {
int needPre = pre[i] - 1;
if (sumToIndexMap.containsKey(needPre)) {
int lastIndex = sumToIndexMap.get(needPre);
res = Math.max(res, i - lastIndex);
}
if (!sumToIndexMap.containsKey(pre[i])) {
sumToIndexMap.put(pre[i], i);
}
}
}
return res;
}
}

第二题: 注意java中|也是特殊正则符号,需要转移#

2315. 统计星号 - 力扣(LeetCode)

关键地方:

1
String[] ss = s.split("\\|");

注意|的写法

第三题#

1619. 删除某些元素后的数组均值 - 力扣(LeetCode)

2022-09-11#

857. 雇佣 K 名工人的最低成本 - 力扣(LeetCode)

这题想不到的是要按工资比例做排序

最低工资/价值 来从小到大排序

从左到右遍历,选中一个那个就是作为最低工资标准,则前面任意都直接拿价值乘这个工资标准比率即可

而又可以根据k个的quality和可以直接乘……&这个还是蛮难想到的, 但是想懂后其实就是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
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
Integer[] indexs = new Integer[quality.length];
int n = quality.length;
for (int i = 0; i < quality.length;i++) {
indexs[i] = i;
}

Arrays.sort(indexs, (a,b)->(((double)wage[a]/quality[a] - (double)wage[b]/quality[b] > 0 ? 1 : -1)));
Queue<Integer> minKQueue = new PriorityQueue<>((a,b)->(b-a));
long sum = 0;
double res = Double.MAX_VALUE;
for (int i = 0; i < n;i++) {
int index = indexs[i];
int qua = quality[index];
int wag = wage[index];
double rate = (double)wag/qua;
if (minKQueue.size() < k) {
minKQueue.offer(qua);
sum += qua;
} else if (minKQueue.size() == k && qua < minKQueue.peek()) {
sum -= minKQueue.poll();
minKQueue.offer(qua);
sum += qua;
}

if (minKQueue.size() == k) {
res = Math.min(res, sum * rate);
}
}
return res;
}
}

2022-09-08#

667. 优美的排列 II - 力扣(LeetCode)

规律题,还好没纠结

1662652885074

对于1~n的数字, 想要满足有n-1个前后差值不同,必须满足

[1, n, 2 , n-1, 3, n-2] 这样最小和最大值交叉出现

而如果是相同,则就是按顺序出现

那么想要任意k个差值不同,那就前面先都按顺序, 后面再交叉出现即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
int index = 0;
for(int i = 1; i <n-k;i++) {
res[index++] = i;
}
int left = n-k;
int right = n;
while(left <=right) {
if (index < n) {
res[index++] = left;
}
if (index < n) {
res[index++] = right;
}
left++;
right--;
}
return res;
}
}

2022-09-07#

第一题: 如果计算3个点是否一个直线#

1037. 有效的回旋镖 - 力扣(LeetCode)

y1 - y2 / (x1-x2) = (y1-y3) / (x1-x3)

即以(x1,y1)为出发点,确定和另外两个点是否都是同一个斜率

为了防止x1-x2为0的情况,转化为相乘的形式即可

第二题:修改跟节点#

1666. 改变二叉树的根节点 - 力扣(LeetCode)

1662563625565

其实就是按照她这个规则修改,而且就是从叶子到root修改

那就是每次要把儿子节点带上来,而且要注意修改父节点的指向,很麻烦

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
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/

class Solution {
public Node flipBinaryTree(Node root, Node node) {
dfs(root, node, null);
return node;
}

public void dfs(Node root, Node node, Node son) {
if (node == null) {
return ;
}
if (node.left == son) {
node.left = null;
} else {
node.right = null;
}
if (node == root) {
node.parent = son;
return ;
}
Node left = node.left;
Node parent = node.parent;
if (left != null) {
node.right = left;
}
node.left = parent;
dfs(root, parent, node);
node.parent = son;
return ;
}
}

2022-09-06#

1404. 将二进制表示减到 1 的步骤数 - 力扣(LeetCode)

剑指 Offer II 002. 二进制加法 - 力扣(LeetCode)

都是模拟二进制加法,都是注意反过来计算,然后最后末尾补1好一点

剑指 Offer II 093. 最长斐波那契数列 - 力扣(LeetCode)

这个问题因为涉及a+b=c,前面有a和b两个数字才能决定c, 因此状态应该是a和b共同决定,因此dp要有2位

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 int lenLongestFibSubseq(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length;i++) {
map.put(arr[i], i);
}

int[][] dp = new int[arr.length+1][arr.length+1];
int res = 0;
for (int i = 0; i < arr.length;i++) {
int num = arr[i];
for (int j = i-1;j>=0;j--) {
int num2 = arr[j];
int num3 = num - num2;
if (!map.containsKey(num3) || num3 >=num2) {
dp[j][i] = 2;
} else {
int index3 = map.get(num3);
dp[j][i] = dp[index3][j] + 1;
}
res = Math.max(res, dp[j][i]);
}
}
return res != 2 ? res : 0;
}

2022-09-05#

1974. 使用特殊打字机键入单词的最少时间 - 力扣(LeetCode)

1667. 修复表中的名字 - 力扣(LeetCode)

SQL中存在

1
CONCAT(UPPER(left(name, 1)), LOWER(RIGHT(name, length(name) - 1)))

这些函数, 可以把第一个大写,其他都小写

1741. 查找每个员工花费的总时间 - 力扣(LeetCode)

group by是可以针对2组key进行的

1
select event_day as day, emp_id, sum(out_time-in_time) as total_time from employees group by event_day,emp_id;

统计每个员工每天的工作总时间

2022-09-04 周赛#

2022-09-03:双周赛#

2022-09-02#

第一题: 递归简单题#

364. 加权嵌套序列和 II - 力扣(LeetCode)

题目比较难理解,类似于给了一个树, 注意maxDepth也就是树的最大深度的意思

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
class Solution {
int maxDep = 0;
public int depthSumInverse(List<NestedInteger> nestedList) {
Map<Integer, Integer> counts = new HashMap<>();
for (NestedInteger nest : nestedList) {
dfs(nest, 1);
}
int sum = 0;
for (NestedInteger nest : nestedList) {
sum += dfs2(nest, 1, maxDep);
}
return sum;
}

public void dfs(NestedInteger nest, int dep) {
maxDep = Math.max(maxDep, dep);
if(nest.isInteger()) {
return ;
} else {
List<NestedInteger> nexts = nest.getList();
int maxDep = 0;
for (NestedInteger next : nexts) {
dfs(next, dep + 1);
}
}
}

public int dfs2(NestedInteger nest, int dep, int maxDep) {
if(nest.isInteger()) {
int num = nest.getInteger();
return num * (maxDep - dep + 1);
} else {
List<NestedInteger> nexts = nest.getList();
int sum = 0;
for (NestedInteger next : nexts) {
sum += dfs2(next, dep + 1, maxDep);
}
return sum;
}
}

}

第二题:对角线判断#

2319. 判断矩阵是否是一个 X 矩阵 - 力扣(LeetCode)

1662168968681

主要考察对 正方形对角线的处理, 确定y的情况下,这一行上符合对角线的点是(y, y)和(y, xlen - 1 - y)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean checkXMatrix(int[][] grid) {
int ylen = grid.length;
int xlen = grid[0].length;
for (int y = 0; y < ylen;y++) {
int x1 = y;
int x2 = xlen - 1 - y;
if (grid[y][x1] == 0 || grid[y][x2] == 0) {
return false;
}
for (int x = 0; x < xlen;x++) {
if (x == x1 || x == x2) {
continue;
}
if (grid[y][x] != 0) {
return false;
}
}
}
return true;
}

第三题:加法树只要元素都一致那就是相等#

1612. 检查两棵二叉表达式树是否等价 - 力扣(LeetCode)

1662169121771

其实无论什么顺序, 因为只有加法,都是一样的,只要元素(叶子节点)完全一致即可,也可以用map判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean checkEquivalence(Node root1, Node root2) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
get(root1, list1);
get(root2, list2);
Collections.sort(list1);
Collections.sort(list2);
return list1.equals(list2);
}

public void get(Node node, List<Integer> list) {
if (node == null) {
return ;
}
if (node.val != '+') {
list.add((int)node.val);
}
get(node.left, list);
get(node.right, list) ;
}

2022-09-01#

第一题:简单二叉树递归#

2331. 计算布尔二叉树的值 - 力扣(LeetCode)

没啥好说的直接遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean evaluateTree(TreeNode root) {
int val = root.val;
if (val == 1) {
return true;
} else if (val == 0) {
return false;
} else if (val == 2){
return evaluateTree(root.left) || evaluateTree(root.right);
} else {
return evaluateTree(root.left) && evaluateTree(root.right);
}
}
}

第二题:简单回文判断#

2330. 有效的回文 IV - 力扣(LeetCode)

没看懂这题的意义是啥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean makePalindrome(String s) {
int left = 0, right = s.length()-1;
int count = 0;
while(left < right) {
if (s.charAt(left) != s.charAt(right)) {
count++;
}
left++;
right--;
}
return count <= 2;
}
}

第三题:贪心间隔摆放字符要求最长#

1662049690107

这种给几种字母让你排列, 一般都是要间隔放,而且每次都是优先放大的那2个。

这题我就是每次选2个当前最大的,然后放进去。 当都放完,看下有剩余的(且肯定是单个),再找到那个字母数量都+1, 再有剩余就不处理了。和答案思路基本一致

1662049857921

这题里面我用了int[]来表示, 答案定义了Pair类,以后可以参考下

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
class Solution {
public String longestDiverseString(int a, int b, int c) {
List<int[]> list = new ArrayList<>();
int[][] arr = new int[][]{{'a', a},{'b', b},{'c',c}};

while(arr[0][1] > 0 || arr[1][1] > 0 || arr[2][1] > 0) {
// 如何得到3个的排序?
// 每次选前2个放进来
Arrays.sort(arr, (x,y)->(y[1] - x[1]));
if (arr[1][1] != 0) {
list.add(new int[]{arr[0][0], 1});
arr[0][1]--;
list.add(new int[]{arr[1][0], 1});
arr[1][1]--;
} else {
list.add(new int[]{arr[0][0], 1});
arr[0][1]--;
for (int i = 0; i < list.size() && arr[0][1] > 0;i++) {
int[] ar = list.get(i);
if (ar[0] == arr[0][0]) {
ar[1]++;
arr[0][1]--;
}
}
break;
}
}
StringBuilder sb = new StringBuilder();
for (int[] ar : list) {
sb.append((char)ar[0]);
if (ar[1] ==2) {
sb.append((char)ar[0]);
}
}
return sb.toString();
}
}

[toc]

  • 增加了@AspectJ注解形式的AOP使用方式

    注意只是使用方式变了,底层的实现逻辑和基本概念还是相同的。

    注解形式的pointcut:
    可通过注解直接定义pointcut内容,就不需要实现里面的方法了
    这里的方法名仅仅是作为1个代号,代号可以提供给其它的pointcut去合并使用

    下面这个图,二者标识的pointcut其实是一样的
    82adc5bbf93caa060e7649ff9c73c9c3370480e7

    引用时也能包含包名

    pointcut表达式符号:
    execution(指定方法签名,支持通配): 标识仅支持方法执行类型的joinPoint
    并支持方法参数识别
    93ad48e07377ac8591a10b2564b89e7845238640

    within 匹配
    只能和包路径相关
    0c416b8d211008bddc39219e2ba16087ffefb398

    @within(注解类名)
    比上面多了个@,相当于只切入标注了某个注解的方法,且只用于对象是否标注了这个注解类名的注解

    this(objectType)
    当目标对象的代理对象是objectType,则切入

    target(objectType)
    当目标对象是objectType,则切入
    eb927a4ab949516c2436f86038ed53c1cc00d4e3
    9921eefea0e72b57b2ae905ef1d340d8ccbd9173
    @target(注解类型)
    如果对象的目标对象 拥有target括号里的注解类型,则切入

    args
    指定方法输入参数
    6150e3e656d5bf81f4cfe3d77d02dd5d223dd52b

    @annotation
    系统内所有标注了annotation的方法,都会切入。 和@within的区别在于前者是方法,后者是对象
    372535ab8ea8a2c77bf69b070a2c05bcde4cb335

    注解形式的Advice
    56a84406b604aecce420c12d942ba93526f26998
    可以和pointcut 合并?

    cad1ea69bdfce12bff029f46bbe9848b12322677

    ae8ce5ca694623441181af71dca6155d822e9e68

    0e176c14cd01488fe4e90e65cabf0f582d80c46e
    @AspectJ的注意事项:

    如果类中定义了多个相同位置的@advice, 则执行顺序取决于声明顺序

    070bcb0b29a519f5d2d842885461f5681c4e5bb2
    如果有多个AspectJ类, 然后不同aspectJ的advice冲突了,怎么办?
    需要实现Order接口,否则是不确定顺序
    96574a574ffed6e4dee6477a922da1a12a5d2051

    也可以指定实例化的方式,默认是单例实例化。

    4b69c4b45e1e1a67ba51196cf7654e1a2982daef

    嵌套执行代理的问题:
    f6a306ee8b151bbc9b210a7083de0a3bb16e3bd6
    79b459a1b92d33b253f8db3ae3250cb4ce30882c

    如果执行method1, 只会进行method1的代理, method2并不会动, 这是因为底层原理,导致 我们生成1个method1的代理后, 执行时里面的method2并不会动, 即method1的代理里没有method2的代理,。
    之所叫横切,就是因为他会切入到同一个逻辑层上,
    如果需要层层横切,需要在method1里调用method2的代理
    052b9e9888e60902ec8e7596f59f7300bbe3bb63
    而这个代理可以用注入的方式,不要在这里写死。https://www.cnblogs.com/cloudwill/p/13648539.html)

[toc]
SpringAOP采用动态代理机制和字节码生成技术实现。
在运行期间,为目标对象生成1个代理对象,并把横切逻辑织入到代理对象中。系统运行时用的是代理对象,而非目标对象。

复习静态代理模式:

fb5135fa4b3e6ebfb33692fe85e6fb56d07ca1d2
缺点: 一旦横切逻辑变多,我们要手动添加的类也越多。如果要创建N多个代理对象,会很麻烦。另外如果加了1个方法,每个代理中也都要加,数量是很恐怖的。


java动态代理缺点: 如果类没有实现任何的接口,就无法使用动态代理生成动态代理对象。(即需要1个类似于request方法的对外接口,让外界即可用代理类访问,也可用原生类访问)


SpringAOP的动态代理#

  • 如果发现对象实现了interface,就会用动态代理为其生成代理实例。
  • 如果没有实现interface,则会尝试使用CGLIB的开源动态字节码生成类库,来为目标对象生成动态的代理实力。

JDK代理#

Q: 为什么jdk代理的方式必须要接口?
A:
因为java动态代理的代理生成方法Proxy.newProxyInstance中,第二个参数就是被代理对象的inteface,通过这个他才能识别对哪些方法做代理(即根据接口找到方法做代理)

而且返回值就是这个接口类型。

Info proxyInfo = (Info)Proxy.newProxyInstance(代理类对象.getClass().getClassLoader(),实际对象.handler.getInterfaces(), 代理类对象.

CGLIB动态字节码生成:#

对目标对象进行继承,生成子类,然后子类中通过覆写方法来扩展父类的方法,把横切逻辑加入, 然后让系统调用扩展后的这个子类即可。
例子:
原类:
10b062705bc164ed9b0c075253f19d700b9bbc14
先实现1个MethodInterceptor(继承自Callback)接口,作为扩展类,里面就包含了横切逻辑 e25c6ab0a93a9c3853c1572ea84ae06c2333095e 541de8756dc5fb393e27d95706eeb4d32f839c62

然后通过CGLIB的Enhancer对来生成扩展子类
92faab1eefa2f8665648526eb8bf4ec8053c354e

缺陷: 无法对final方法做覆写


Q: 如果我做了AOP, AOP的那个类里有一个private方法,这个方法是在AOP的范围内的,有什么问题?
A: 如果那个方法里用到一个autowire注入的对象,就会报空指针。
原因:

  • AOP本质是继承原类,生成一个CGLIB新类, 重写里面的public或者protect方法,替换成自己切入的那个方法。
  • 从public方法切入后,实际上会走进原生bean对象,因此用的autowire对象是原生bean里的东西,是注入过的。
  • 而private不会重写,因此代码没变,”不会跳转到原生bean里去调用“, 而CGLIB代理对象是不会做bean注入的(因为顺序问题,先bean初始化再AOP), 所以我们调用privatge时,用的是CGLIB对象里的autowire成员,他从未被注入过。
    详细源码:SpringAOP私有方法导致@Autowire注入失败原理

[toc]
OOP(面向对象)无法解决系统需求(即所有业务模块的通用需求)的实现在系统中各处散落的问题

AOP: 面向切面编程

c202d80ab64f3b6840f064a267a68a99c312ee05

三种AOP类型#

静态AOP:#

第一代AOP, AspectJ.
优点: 直接以Java字节码编译到java类中,不会对系统造成性能损失,
缺点:不够灵活,如果需要修改插入位置,就要重新编译。

动态AOP:#

在系统运行后插入到系统中, 且织入信息以外部XML文件格式保存。
缺点:性能有问题。但已经可以容忍这种损失j

java自带的AOP:#

  1. 动态代理 缺点:只针对接口有效,且必须实现接口,有局限性
    2. 动态字节码增强: 修改class文件的字节码来插入一些操作缺点: 如果要扩展的类或者方法声明为final,就不能进行子类化扩展
    3. java代码生成, 通过工具生成代码部署到原代码中早起EJF容器使用最多,现在已经不用了
    4. 自定义类加载器在类加载的时候,通过类加载器,修改读入的class字节码数据缺点:某些服务器可能不支持自定义或者本身类加载器会控制整个类加载体系,导致冲突
    5. AOL扩展:直接用AOL这个语言去做。这个最强,也最难用。

AOP概念#

Joinpoint 切入点#

切入点的位置选择共有7处:

  • 方法调用 : 外部调用时的位置,还没进去
  • 方法执行: 调用方法的内部的之前, 在方法调用之后
  • 构造方法调用
  • 字段设置 set或者this.xxx=xxx
  • 字段获取 getxxx
  • 异常处理执行
  • 类初始化

PointCut#

我认为是joinPoint的集合描述即如何描述
属于同一批的joinpoint, 即切到哪些地方?怎么描述我要切入的点?
4种表述方式:

  1. 直接指定joinpoint所在方法名称
  2. 正则表达式3
  3. 使用特定的表述语言
  4. 在1-3的基础上,进行pointcut计算

Advice#

代表你要怎么织入到joinpoint,即合适执行切面方法的策略, 在之前还是之后,还是其他。

  1. beforAdvice
    在joinpoint指定位置之前执行
    不会中断程序执行流程

  2. AfterAdvice
    在连接点之后执行的advice类型。还可以细分
    ① After return Advice 只有连接点完全执行完后,且无异常,才执行切面方法
    ②After throwing advice 只有抛出异常才执行
    ③After Advice ①和②的结合。
    55b7e304a004c8a0a9c266fb2fa416bea8c747a4

  3. Aroud Advice
    可以在joinpoint的之前之后都进行执行设置,类似于进行了包裹

  4. Introduction

根据jointPoint可以完成的功能来区分

Aspectpointcut#

和advice定义的封装实体
79cf416c8cc6bba1c32c878c410338da309aaa4d
包含以下内容

  • 织入器
    通过什么方式去织入,即实现, 例如类加载器之类的

  • 目标对象
    符合pointCut条件,将被织入的对象,称为目标对象
    cbabf8d110b5cb869c5d9b975860b831001151eb


AOP应用案例:
异常捕捉:
62e0eff9d85533f8e8d8fd0bee1708e3fbe6e50b
可针对unchecked excpetion进行Fault Barrier的切入

安全检查:
1661957687639

调用每个方法前都做一下检查

缓存:
63e8d127f0be72f456bf449370b9f5c2e8f9ce26
key可以理解为输入参数?

不过Spring已经支持Caching产品了使用了

[toc]

ApplicationContext除了拥有 BeanFactory支持的所有功能之外,还进一步扩展了基本容器的功能,包括
BeanFactoryPostProcessor、
BeanPostProcessor
其他特殊类型bean的自动识别
容器启动后bean实例的自动初始化
国际化的信息支持
容器内事件发布等


3种ApplicationContext的实现
FileSystemXmlApplicationContext :从文件系统加载bean
ClassPathXmlApplicationContext :从Classpath加载bean
XmlWebApplicationContext :用于Web应用程序的ApplicationContext实现


新特性一:统一资源加载策略#

Spring提出了一套基于Resource和ResourceLoader接口的资源抽象和加载策略。

  • ByteArrayResource 将字节(byte)数组提供的数据作为一种资源进行封装? ClassPathResource 从Java应用程序的ClassPath中加载具体资源并进行封装
  • FileSystemResource 以文件或者URL的形 式对该类型资源进行访问,只要能跟File打的交道
  • UrlResource 通过java.net.URL进行的具体资源查找定位的实现类,内部委派URL进行具 体的资源操作。
  • InputStreamResource 较为少用。

ResourceLoader:查找和定位这些资源,资源定位器
在这里插入图片描述
相关资源的ResourceLoader实现类:

  • DefaultResourceLoader
    在这里插入图片描述

  • FileSystemResourceLoader
    在这里插入图片描述

  • ResourcePatternResolver(ResourceLoade的子接口)
    是1个批量查找的ResourceLoader,会返回resource数组 实
    可以根据指定的资源路径匹配模式, 每次返回多个Resource实例
    支持基 于Ant风格的路径匹配模式(类似于**/.suffix之类的路径形式),支持ResourcePatternResolver新 增加的classpath:前缀等

总关系图
在这里插入图片描述
ApplicationContextt默认继承了ResourcePatternResolver,间接实现了ResourceLoader接口
任何的ApplicationContext实现都可以看作是一个 ResourceLoader甚至ResourcePatternResolver

  • ApplicationContext的资源用法:
    1.扮演ResourceLoader的角色
    在这里插入图片描述

2.ResourceLoader类型的注入
ApplicationContext类型容器可以自动识别Aware接口
因此会自动把自己注入到需要ResourceLoader的实例中
在这里插入图片描述

3.Resource类型的注入
BeanFactory如果想注入Resource类型的bean定义,就需要注册自定义的PropertyEditor到 BeanFactory容器
而Application- Context容器可以正确识别Resource类型并转换后注入相关对象
在这里插入图片描述

  1. 在特定情况下,ApplicationContext的Resource加载行为

Spring扩展了协议前缀的集合。
ResourceLoader中增加了一种新 的资源路径协议——classpath:,
ResourcePatternResolver又增加了一种——classpath*:。
classpath*:与classpath:的唯一区别就在于,如果能够在classpath中找到多个指定的资源,则 返回多个

ClassPathXmlApplicationContext默认从classpath中加载bean定义配置文件
在这里插入图片描述

FileSystemXmlApplicationContext默认尝试从文件系统中加载bean定义文件
在这里插入图片描述

但通过加前缀file或者classpath,可以修改加载方式

新增特性二:国际化信息支持#

1.Java SE 提供的国际化支持:
不同的 Locale代表不同的国家和地区,每个国家和地区在Locale这里都有相应的简写代码表ResourceBundle用来保存特定于某个Locale的信息
通过结合ResourceBundle和Locale,我们就能够实现应用程序的国际化信息支持

Spring在Java SE的国际化支持的基础上,进一步抽象了国际化信息的访问接口,也就是 MessageSource
在这里插入图片描述

ApplicationContext还 实现了MessageSource接口,
3种MessageSource实现
StaticMessageSource 。可以通过编程的方式添加信息条目,多用于测试,不应该用于正式的生产环境。
ResourceBundleMessage 是常用的、用于正式生产环境
ReloadableResourceBundleMessageSource 定期刷新并检查底层的properties资源文件是否有变更。

ApplicationContext 启动的时候,会自动识别容器中类型为MessageSourceAware的bean定义
并将自身作为MessageSource注入相应对象实例中
PS:看一下自己工程里怎么实现的

新增特性三:容器内部事件发布#

java自带事件发布:
在这里插入图片描述
ApplicationContext 容器内部允许以ApplicationEvent的形式发布事件,。
容器内注册的ApplicationListener类型的bean定义会被ApplicationContext容器自动识别
一旦容器内发布ApplicationEvent及其子类型的事件, 注册到容器的ApplicationListener就会对这些事件进行处理。

application自定义事件ApplicationEvent
Spring提供了三个实现。

  • ContextClosedEvent:ApplicationContext容器在即将关闭的时候发布的事件类型。
  • ContextRefreshedEvent:ApplicationContext容器在初始化或者刷新的时候发布的事件类 型。
  • RequestHandledEvent:Web请求处理后发布的事件,其有一子类ServletRequestHandled- Event提供特定于Java EE的Servlet相关事件。

application自定义监听器ApplicationListener
在启动时,会自动识别并加载EventListener类型bean定义, 一旦容器内有事件发布,将通知这些注册到容器的EventListener

application自定义发布者ApplicationContext
ApplicationContext接口定义还继承了ApplicationEventPublisher接口

容器启动伊始,就会检查容器内是否存在名称为ApplicationEventMulticaster的 ApplicationEventMulticaster对象实例。
有的话就使用提供的实现,没有则默认初始化一个 SimpleApplicationEventMulticaster作为将会使用的ApplicationEventMulticaster
在这里插入图片描述

Spring的ApplicationContext容器内的事件发布机制,主要用于单一容器内的简单消息通知和处 理,并不适合分布式、多进程、多容器之间的事件通知
发布步骤:
1.MethodExecutionEvent的改装
在这里插入图片描述

2.MethodExecutionEventListener的改
在这里插入图片描述

3.MethodExeuctionEventPublisher改造
在这里插入图片描述

  1. 注册到ApplicationContext容器
    在这里插入图片描述

特性四:多配置模块加载的简化
在这里插入图片描述

[toc]

第一题:数组问题#

1007. 行相等的最少多米诺旋转 - 力扣(LeetCode)

1661956709671

1661956718077

很简单,搞3个统计数量的数组即可, 一个是去重后的总数,一个是A中各数字的总数,一个是B中各数字的总数

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
class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int[] counts = new int[7];
int[] counts1 = new int[7];
int[] counts2 = new int[7];
for (int i = 0; i < tops.length;i++) {
if (tops[i] == bottoms[i]) {
counts[tops[i]]++;
} else {
counts[tops[i]]++;
counts[bottoms[i]]++;
}
counts1[tops[i]]++;
counts2[bottoms[i]]++;
}
int res = Integer.MAX_VALUE;
for (int i = 1; i<=6;i++) {
if (counts[i] == tops.length) {
int changeCount = Math.min(tops.length - counts1[i], tops.length - counts2[i]);
res = Math.min(res, changeCount);
}
}
if (res == Integer.MAX_VALUE) {
return -1;
} else {
return res;
}
}
}

第二题: 链表倒数第k个,用2个指针维护即可#

1721. 交换链表中的节点 - 力扣(LeetCode)

1661956816895

求倒数第k个,那就是先走k步,然后再以起点为另一个指针,两边一起走,直到走到尾部即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode newHead = new ListNode();
newHead.next = head;
ListNode node1 = head;
int count = k-1;
while(count-- > 0) {
node1 = node1.next;
}
ListNode node2 = newHead;
ListNode node = node1;
while(node != null) {
node = node.next;
node2 = node2.next;
}
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
return head;
}
}

第三题: 栈的验证#

946. 验证栈序列 - 力扣(LeetCode)

1661957045969

数据结构很基础的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new LinkedList<>();
int i1 = 0, i2 = 0;
for( i2 = 0;i2 < popped.length;i2++) {
int pop = popped[i2];
if (!stack.isEmpty() && stack.peek() == pop) {
stack.pop();
continue;
}

while(i1 < pushed.length && pushed[i1] != pop) {
stack.push(pushed[i1]);
i1++;
}
if (i1 == pushed.length) {
return false;
}
i1++;
}
return true;
}
}