到今天为止，在菊厂的实习就结束啦。回到宿舍后把答辩时做的题总结总结，记录在这里。
当然了，写总结的时候回想了一下，自己答辩时写的代码真丑……
289 生命游戏
根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
题目描述：
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live（1）即为活细胞， 或 dead（0）即为死细胞。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
输入样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 输入:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
|
解决代码 ：
简单直白，完全按照题目解释做了两个循环。第一个循环用于标记，第二个循环用于赋值。
1——保持1
-1——1转0
0——保持0
-2——0转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 void gameOfLife(int[][] board) {
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
board[i][j] = checkLoc(board, i, j);
}
}
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
board[i][j] = board[i][j] == 1 || board[i][j] == -2 ? 1 : 0;
}
}
}
public int checkLoc(int[][] board, int i, int j){
int count = 0;
int left = Math.max(j - 1, 0);
int right = Math.min(j + 1, board[i].length - 1);
int top = Math.max(i - 1, 0);
int bottom = Math.min(i + 1, board.length - 1);
for(int x = top; x <= bottom; x++){
for(int y = left; y <= right; y++){
count = board[x][y] == 1 || board[x][y] == -1 ? count + 1 : count;
}
}
return board[i][j] == 1 ? (count == 3 || count == 4 ? 1 : -1) : (count == 3 ? -2 : 0);
}
}
|
554 砖墙
题目描述：
你的面前有一堵方形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
输入样例：
1
2
3
4
5
6
| 输入: [[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
|
提示：
- 每一行砖块的宽度之和应该相等，并且不能超过 INT_MAX。
- 每一行砖块的数量在 [1,10,000] 范围内， 墙的高度在 [1,10,000] 范围内， 总的砖块数量不超过 20,000。
解决代码1：
穿过最少砖的直线肯定是穿过缝隙最多的线，所以可以遍历整个List，获取每一行每条缝隙对应的砖宽， 将砖宽度和砖宽度出现的次数存入Map，最后遍历map获取出现次数最多的宽度，总行数-出现次数即为结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int LeastBricks(List<List<Integer>> wall) {
Map<Integer, Integer> map = new HashMap();
for(List<Integer> list : wall) {
int acc = 0;
for(int i = 0; i < list.size() - 1; i++) {
acc += list.get(i);
map.put(acc, map.getOrDefault(acc, 0) + 1);
}
}
int max = 0;
for (int v : map.values()) {
if (v > max) {
max = v;
}
}
return wall.size() - max;
}
}
|
621 任务调度器
题目描述：
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例：
1
2
3
| 输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
|
注：
- 任务的总个数为 [1, 10000]。
- n 的取值范围为 [0, 100]。
解决代码1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int leastInterval(char[] tasks, int n) {
if(n==0) return tasks.length;
int[] number = new int[26];
for (int i = 0; i<tasks.length; i++){
number[tasks[i]-'A']++;
}
Arrays.sort(number);
int max = number[number.length-1];
int i=number.length-1; int max_len =0;
while(number[i--]==max) max_len++;
return Math.max((max-1)*(n+1)+max_len,tasks.length);
}
}
|
解决代码2：
解释一下这个公式怎么来的 (count[25] - 1) * (n + 1) + maxCount：
- 假设数组 [“A”,”A”,”A”,”B”,”B”,”C”]，n = 2，A的频率最高，记为count = 3，所以两个A之间必须间隔2个任务，才能满足题意并且是最短时间（两个A的间隔大于2的总时间必然不是最短），因此执行顺序为： A->X->X->A->X->X->A，这里的X表示除了A以外其他字母，或者是待命，不用关心具体是什么，反正用来填充两个A的间隔的。上面执行顺序的规律是： 有count - 1个A，其中每个A需要搭配n个X，再加上最后一个A，所以总时间为 (count - 1) * (n + 1) + 1；
- 要注意可能会出现多个频率相同且都是最高的任务，比如 [“A”,”A”,”A”,”B”,”B”,”B”,”C”,”C”]，所以最后会剩下一个A和一个B，因此最后要加上频率最高的不同任务的个数 maxCount；
- 公式算出的值可能会比数组的长度小，如[“A”,”A”,”B”,”B”]，n = 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
| class Solution {
public int leastInterval(char[] tasks, int n) {
int len = tasks.length;
if(len < 1 || n < 0){
return 0;
}
int[] nums = new int[26];
int i = 0;
while(i < len){
nums[tasks[i++] - 65]++;
}
Arrays.sort(nums);
int res = (nums[25] - 1) * (n + 1);
i = 25;
while(i >= 0 && nums[i] == nums[25]){
res++;
i--;
}
return res > len ? res : len;
}
}
|