我的部分秋招笔试

Article Directory
  1. 1. 建树、建图之类
    1. 1.1. 1631. 最小体力消耗路径
      1. 1.1.1. 并查集 + Kruskal
    2. 1.2. 数节点染色计算总体权重
    3. 1.3. 树的 层序遍历,编码解码需要会
    4. 1.4. 生活在树上
    5. 1.5. 124. 二叉树中的最大路径和
  2. 2. 0723科大讯飞
  3. 3. 0810ZOOM
    1. 3.1. 数节点染色计算总体权重
      1. 3.1.1. 题目
      2. 3.1.2. 输入
      3. 3.1.3. 思路
    2. 3.2. 股票推荐
      1. 3.2.1. 题目
      2. 3.2.2. 输入
  4. 4. 0811兴业数金
    1. 4.1. 序列化的内容包括以下几个方面:
    2. 4.2. 不能被序列化的内容有:
    3. 4.3. Java中transient关键字的详细总结
  5. 5. 0813美团
    1. 5.1. 扑克
    2. 5.2. 合法三元组
  6. 6. 0820美团
  7. 7. 0820网易互联网
    1. 7.1. 两个正整数操作
    2. 7.2. 拟合:三元组ai>aj, ai=ak
      1. 7.2.1. 注意:
  8. 8. 0825荣耀
    1. 8.1. 会议最长时间
    2. 8.2. 两个背包问题
  9. 9. 0825美的
    1. 9.1. 同一直线上,最多的点
  10. 10. 0827完美世界
    1. 10.1. 1049. 最后一块石头的重量 II
    2. 10.2. 56. 合并区间
  11. 11. 0828小红书
    1. 11.1. 一对一
      1. 11.1.1. 注意:树
  12. 12. 0827美团
    1. 12.1. 挑剔
    2. 12.2. 裁缝
    3. 12.3. 下雨
  13. 13. 0827京东
    1. 13.1. 漂亮串
  14. 14. 0828小红书
    1. 14.1. 一对一
  15. 15. 0830携程
    1. 15.1. rgb染色
    2. 15.2. 平滑值
  16. 16. 0831顺丰
    1. 16.1. 猜数列游戏
    2. 16.2. 圣诞树
  17. 17. 0831华为
    1. 17.1. 字符串压缩替换
    2. 17.2. 走迷宫(带有陷阱炸弹强)
      1. 17.2.1. 减枝一般两种
    3. 17.3. 充电桩问题
  18. 18. 0903美团笔试
  19. 19. 0903搜狐畅游
  20. 20. 0904飞哥网易互联网
    1. 20.1. 树的权值因数和
    2. 20.2. 数组每次减去k,找最大的最小
  21. 21. 0904滴滴
  22. 22. 0908 腾讯音乐
    1. 22.1. 二叉树中序和前序
  23. 23. 二叉树权值
  24. 24. 0914小米
    1. 24.1. 92. 反转链表 II
    2. 24.2. 二叉搜索树与双向链表
  25. 25. 0915奇安信
    1. 25.1. 夏季优惠
    2. 25.2. 蚂蚁走网格,吃食物
  26. 26. 0915荣耀
    1. 26.1. 输出环的问题
  27. 27. 0918雷火
    1. 27.1. 走迷宫啊
  28. 28. 随便放的几个
    1. 28.1. 15. 三数之和
    2. 28.2. 890. 查找和替换模式
    3. 28.3. 532. 数组中的 k-diff 数对
    4. 28.4. 954. 二倍数对数组

笔试、面试问题

秋招招聘汇总+避雷公司8.07更新+简历指导(已指导百人)

【2023秋招&提前批】互联网招聘信息最新汇总8月8日更新

23届联想面经分享: 秋招上岸

蔚来技术岗最全面经汇总

蔚来提前批 大数据 一面二面 7.24

【通关版】招银网络科技最详面经汇总!

衫川机器人

归纳

建树、建图之类

1631. 最小体力消耗路径

并查集 + Kruskal

此处是List<int[]>,使用了点-点-权重的建图方式,每一次只需要找到权重最小的,而且不在联通图中的即可

数节点染色计算总体权重

【2022-08-10】ZOOM秋招笔试两道编程题

建树 + dfs

此处使用邻接表的形式,节点node中存了该节点在数组中的编号,然后权重

树的 层序遍历,编码解码需要会

生活在树上

【2022-08-13】美团秋招笔试四道编程题

tbG5SB1uMkaTslZ

这一题直接dfs做就行

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
// 未提交验证
import java.util.*;

public class LivingInTree {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}

// 从上往下找一条路径的最大值,那么需要全部遍历完呀肯定
dfs(nums, n, nums[0], 1); // nums[0],根节点,使其对应的k为1

System.out.println(ans);
}

static int ans = 0;
public static void dfs(int[] nums, int n, int sum, int k) {
if (k * 2 + 1 > n) { // 表明已经是叶子节点,左右孩子都没有
ans = Math.max(ans, sum);
return;
}

// 只要有一个,那都要往下递归的
if (k * 2 <= n) {
dfs(nums, n, sum + nums[k * 2 - 1], k * 2);
} // 不确定要不要写else,就是sum不便放进去的
if (k * 2 + 1 <= n) {
dfs(nums, n, sum + nums[k * 2], k * 2 + 1);
} // 不确定要不要写else,就是sum不便放进去的
}
}


// 有些解法使用层序
public class Main
{
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n = Integer.parseInt(cin.nextLine());
String[] _nums = cin.nextLine().split(" ");
int[] nums = new int[n + 1];
for (int i = 1; i <= n; i++) nums[i] = Integer.parseInt(_nums[i - 1]);
int ans = 0;
Queue<Integer> q = new ArrayDeque<>();
q.offer(1);
while (!q.isEmpty()) {
int t = q.poll();
ans = Math.max(ans, nums[t]);
if (2 * t <= n){
nums[2 * t] += nums[t];
q.offer(2 * t);
}
if (2 * t + 1 <= n) {
nums[2 * t + 1] += nums[t];
q.offer(2 * t + 1);
}
}
System.out.println(ans);
}
}
// vx公众号关注TechGuide 实时题库 闪电速递

124. 二叉树中的最大路径和

蔚来笔试题目

leetcode上面是直接给出根节点的,而这个的话,需要自己根据这个来建立一棵树,当然也是简单的。

zSUpuONQ2Zf87M5

caNl5KUwALvjkzx

首先数组 存上所有的节点,然后根据第三行建立连接就行了。此处根据第三行当然也可以变成数组+链表存储二叉树,但是这样肯定没有第一种方法来的方便。

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
import java.util.Scanner;

public class TreeMaxSum {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int val) {
this.val = val;
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
TreeNode[] treeNodes = new TreeNode[n];
TreeNode root = null;

for (int i = 0; i < n; i++) {
treeNodes[i] = new TreeNode(scanner.nextInt());
}

for (int i = 0; i < n; i++) {
// 0是跟节点,此处左右子树都可以,所以相比而言,还是缺少了一些东西的
int parentIndex = scanner.nextInt();
if (parentIndex == 0) {
root = treeNodes[i];
} else {
// 左边不空的话先放左边
// 注意0代表是根,1代表第0个节点
if (treeNodes[parentIndex-1].left == null) {
treeNodes[parentIndex-1].left = treeNodes[i];
} else {
treeNodes[parentIndex-1].right = treeNodes[i];
}
}
}

dfs(root);

System.out.println(ans);
}

static int ans = Integer.MIN_VALUE;
/**
* 考虑
* @return
*/
public static int dfs(TreeNode node) {
if (node == null) {
return 0;
}

// 只有在最大贡献值大于 0 时,才会选取对应子节点
int leftGain = Math.max(dfs(node.left), 0);
int rightGain = Math.max(dfs(node.right), 0);


ans = Math.max(leftGain + rightGain + node.val, ans);

return Math.max(leftGain + node.val, rightGain + node.val);
}
}

题目

0723科大讯飞

五个球队一次两两比赛,然后五个队伍的分数从高到底排序,去重后看看有多少种,然后判断题目给出的一个数据是否是在里面的。

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
// 此处使用队列,进行模拟
import java.util.*;
import java.util.stream.Collectors;

public class TemplateLianBiao {
// 打表测试
// 5个组两两比较,一共可以比赛十个场次
public static Deque<int[]> queue = new ArrayDeque<>();

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int[] scores = new int[5];
for (int i = 0; i < 5; i++) {
scores[i] = in.nextInt();
}
Set<List<Integer>> set = new HashSet<>();

queue.offerLast(new int[]{0, 0, 0, 0, 0});
// 0与其余比较
for (int i = 0; i < 5; i++) {
for (int j = i+1; j < 5; j++) {
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] temp = queue.pollFirst();
temp[i] += 3;
temp[j] += 0;
queue.offerLast(temp.clone());
temp[i] -= 3;
temp[j] -= 0;
temp[i] += 1;
temp[j] += 1;
queue.offerLast(temp.clone());
temp[i] -= 1;
temp[j] -= 1;
temp[i] += 0;
temp[j] += 3;
queue.offerLast(temp.clone());
}
}
}

while (!queue.isEmpty()) {
int[] temp = queue.pollFirst();

Arrays.sort(temp);
for (int i = 0; i < 2; i++) {
int temoInt = temp[i];
temp[i] = temp[4-i];
temp[4-i] = temoInt;
}
set.add(Arrays.asList(temp[0], temp[1], temp[2], temp[3], temp[4]));
}

System.out.print(a == set.size() ? "yes" : "no");
System.out.print(set.contains(Arrays.asList(scores[0], scores[1], scores[2], scores[3], scores[4])) ? " yes" : " no");
}
}
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// 未验证
import java.util.*;

// [[0,1,1,1],[0,0,0,1],[1,0,8,1],[1,0,1,1]]
// 一个方阵,有0可通行,1阻碍,8建议
// 可从边缘的任意地方进去得到奖励,然后找出步数最少的路径
// 若一样,一个即可

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] strs = scanner.nextLine().split("\\],\\[");
strs[0] = strs[0].substring(2, strs[0].length());
strs[n-1] = strs[n-1].substring(0, strs[n-1].length()-2);

int[][] g = new int[n][n];
for (int i = 0; i < n; i++) {
g[i] = Arrays.stream(strs[i].split(",")).mapToInt(Integer::valueOf).toArray();
}


for (int i = 0; i < n; i++) {
System.out.println(Arrays.toString(g[i]));
}

for (int i = 0; i < n; i++) {
if (g[i][0] == 0) {
boolean[][] visited = new boolean[n][n];
visited[i][0] = true;
List<int[]> list = new ArrayList<>();
list.add(new int[]{i, 0});

dfs(g, new int[]{i, 0}, list, visited);
}
if (g[n-1][0] == 0) {
boolean[][] visited = new boolean[n][n];
visited[n-1][0] = true;
List<int[]> list = new ArrayList<>();
list.add(new int[]{n-1, 0});

dfs(g, new int[]{n-1, 0}, list, visited);
}
}

for (int i = 1; i < n; i++) {
if (g[0][i] == 0) {
boolean[][] visited = new boolean[n][n];
visited[0][i] = true;
List<int[]> list = new ArrayList<>();
list.add(new int[]{0, i});

dfs(g, new int[]{0, i}, list, visited);
}
if (g[n-1][i] == 0) {
boolean[][] visited = new boolean[n][n];
visited[n-1][i] = true;
List<int[]> list = new ArrayList<>();
list.add(new int[]{n-1, i});

dfs(g, new int[]{n-1, i}, list, new boolean[n][n]);
}
}

System.out.print("[");
for (int i = 0; i < minPath.size()-1; i++) {
int[] temp = minPath.get(i);
System.out.print("(" + temp[0] + "," + temp[1] + "),");
}
System.out.print("(" + minPath.get(minPath.size()-1)[0] + "," + minPath.get(minPath.size()-1)[1] + ")" + "]");
}


/**
* 深度 + 回溯,算带有路径的好算一点
* @param g
* @param curIndex
* @param path
*/
static int n = 4;
static int minPathCount = Integer.MAX_VALUE;
static List<int[]> minPath;
static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static void dfs(int[][] g, int[] curIndex, List<int[]> path, boolean[][] visited) {
int x = curIndex[0], y = curIndex[1];
if (g[x][y] == 8) {
if (minPathCount > path.size()) {
minPathCount = path.size();
minPath = new ArrayList<>(path);
}
return;
}
if (path.size() > minPathCount) {
return;
}

for (int i = 0; i < n; i++) {
int newX = x + dir[i][0], newY = y + dir[i][1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY] && g[newX][newY] != 1) {
visited[newX][newY] = true;
path.add(new int[]{newX, newY});

dfs(g, new int[]{newX, newY}, path, visited);

visited[newX][newY] = false;
path.remove(path.size() - 1);
}
}
}
}

0810ZOOM

【2022-08-10】ZOOM秋招笔试两道编程题

数节点染色计算总体权重

题目

给你一棵树,树上每个节点要么是红色要么是黑色,根节点为1。每个节点的权重值为根节点到该节点路径上红色节点个数和蓝色节点个数的差的绝对值。求所有节点权重值之和。

输入

第一行输入n个节点 第二行为每个节点的颜色 接下来n-1行为a b节点之间有一条线

5
RBBRB
1 5
2 5
1 3
5 4

思路

考虑建树

但是,如果使用树节点,然后内部维护一个子节点的链表,这样的话建树有难度,因为①里面只给出了节点需要,根据序号找到该节点就稍微麻烦点;其次就是题目说的②ab之间有连线,也没说哪个是父亲节点。

如果只有问题①,那感觉好解决的,使用map,将序号和节点映射即可。

注意,这个题目建图,因为不知道这棵树的父亲节点是谁,是个无向图,然后dfs的时候考虑一下父亲节点不dfs就好了*,下面的小红书一对一,携程rgb,顺丰圣诞树都可以参考一下这个建树

所以本题目考虑,存图的方式,邻接矩阵:

1 题解用的是,节点node,然后node.next链接邻居节点,一开始插入的时候使用头插入(本节点的下一个插入)。(当作无向图的话,父亲节点也会被记录进去,所以等等dfs的时候需要有一个visit标记是否是父节点被访问过,或者说是否是该路径上的节点;没有尝试如果使用,节点中使用链表维护子节点的方法是不需要visited的

2 当然,我觉得使用数组+链表邻接矩阵的方法也是可以的

1和2的区别是1数组里面每一个第一个都是本节点,其余是相邻节xs点,而2里面数组里面的都是邻居节点

注意节点里面至少要有一个参数存放该节点是数组graph中的哪一个

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
import java.util.List;
import java.util.Scanner;

// 题解
class ListNode{
long val;
ListNode next;
public ListNode(long val, ListNode next){
this.val = val;
this.next = next;
}
}

public class TechGuide{

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int root = 0;
int n = sc.nextInt();
System.out.println(n);
int color[] = new int[n];
ListNode[] Graph = new ListNode[n];
for (int i = 0; i < n; i++) {
Graph[i] = new ListNode(0,null);
}
sc.nextLine();
String str = sc.nextLine();
System.out.println(str);
for (int i = 0; i < n; i++) {
if(str.charAt(i)=='R'){
color[i] = 1;
}
}
for (int i = 0; i < n-1; i++) {
int u = sc.nextInt()-1;
int v = sc.nextInt()-1;
insert(u,v,Graph);
}
int visited[] = new int[n];
dfs(root,visited,0,0,color,Graph);
long ans = 0;
for (int i = 0; i < n; i++) {
ans+=Graph[i].val;
}
System.out.println(ans);
}


public static void insert(int u,int v,ListNode[] G){
ListNode vNode = new ListNode(v,G[u].next);
G[u].next = vNode;
ListNode uNode = new ListNode(u,G[v].next);
G[v].next = uNode;
}

public static void dfs(int root,int[] visited,int red,int blue,int color[],ListNode[] G){
visited[root] = 1;
if(color[root]==1) red++;
else blue++;
G[root].val = Math.abs(red-blue);
ListNode p = G[root].next;
while(p!=null){
if(visited[(int)p.val]!=1){
dfs((int)p.val,visited,red,blue,color,G);
}
p = p.next;
}
visited[root] = 0;
}
}
// 微信公众号关注TechGuide 实时题库 闪电速递


// ######################################*######################################
// 自己做的
package org.jcwang.zoom;

import java.util.*;

/**
* 建树 + dfs
* 树节点染色体计算总体权重
* 使用邻接表,使用数组 + 链表,注意因为这个节点只有一个值,所以都不用创建节点了,那个值直接在list里面的元素表示就好
* 好吧,是需要创建的,因为节点的值需要存的是当前节点的编号,就是在graph数组中是第几个的意思
*/
public class Main2 {
private static class ListNode {
long num;
boolean isRed;

public ListNode(long num, boolean isRed) {
this.num = num;
this.isRed = isRed;
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

List<ListNode>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}

boolean[] color = new boolean[n];
String str = scanner.next(); // 注意此处如果使用nextline的话需要前面先读取nextLine一次
for (int i = 0; i < n; i++) {
color[i] = str.charAt(i) == 'R';
}

for (int i = 0; i < n-1; i++) { // n-1条线,建树
int a = scanner.nextInt() - 1;
int b = scanner.nextInt() - 1;
// 由于不知道那个是父亲,所以当作无向图都存储一遍,后面遍历子节点的时候需要用标记父亲节点,来避免遍历父亲,而不是回溯的意思吧?
graph[a].add(new ListNode(b, color[b])); // 如果是存放节点的话,此处应该是加入新创建的节点
graph[b].add(new ListNode(a, color[a]));
}

boolean[] visited = new boolean[n];
System.out.println("访问顺序:" + 0);
dfs(graph, new ListNode(0, color[0]), 0, 0, visited);
System.out.println(ans);
}

static int ans = 0;
/**
* dfs遍历,求每一个节点的染色体差,然后相加
* @param graph
* @param curNode 如果是节点的话,这个值应该是节点的引用
*/
public static void dfs(List<ListNode>[] graph, ListNode curNode, int red, int blue, boolean[] visited) {
// 标记父节点,以便不至于访问字节点的时候有访问到,因为是按照邻居节点存的
// 即访问了该节点,其他的节点访问的时候不能访问了
visited[(int)curNode.num] = true;

if (curNode.isRed) {
red += 1;
} else {
blue += 1;
}
ans += Math.abs(red - blue);

for (ListNode listNode: graph[(int)curNode.num]) {
// 就是等会儿访问该子节点的邻居节点,可能是该子节点的父亲节点,需要剔除
if (!visited[(int)listNode.num]) {
System.out.println("访问顺序:" + listNode.num);
dfs(graph, listNode, red, blue, visited);
}
}

// 该节点到此结束了,后面该节点又能被访问了
visited[(int)curNode.num] = false;
}
}

股票推荐

并查集

ZOOM 8月10号笔试

题目

完成股票推荐系统设计,每个用户可能关注几个公司,比如A,B,C,如果有另一个用户只关注了A,那么就会给他推荐B,C。这时候如果来了一个用户关注C,D,那么后来关注C的用户,都会推荐A,B,关注A的用户都会推荐BCD。在有上面的关系后,求用户查询的时候,会给它推荐的公司的个数。

(感觉,应该是后来关注c的,会推荐 ABC)

输入

第一行输入q表示操作次数 接下来输入一次操作 共有两种操作 1.注册 格式为 1 name n 表示有一个name的人关注了n个股票 第二行输入n个字符串表示这n个股票 n个字符串不相同 2.查询 格式为 输入2 name 表示查询系统会给此人推荐多少股票 保证至少有一次查询 例

5
1 Alice 2
Zoom Apple
2 Bob
2 Alice
1 Bob 2
Apple MicroSoft
2 Bob

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// 没有放入检验
package org.jcwang.zoom;

import java.util.*;

public class GuPiao {
public static void main(String[] args) {
Solution solution = new GuPiao().new Solution();
solution.tuijian();
}

class Solution {
// 并查集参数
int N = 500001;
int[] parent = new int[N];
int[] rank = new int[N]; // 判断该联通的深度
int size[] = new int[N]; // 题目中需要,判断这个联通的有多少个个数

// 并查集:查找
int find(int x) {
// 若自己等于自己,证明是根
if (parent[x] != x) {
parent[x] = find(parent[x]);
}

return parent[x];
}

// 并查集:查询
boolean query(int a, int b) {
return (parent[find(a)] == parent[find(b)]);
}

// 并查集:融合
// 此处用rank加了优化
void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);

if (rank[rootA] > rank[rootB]) {
// 让深度小的当作根
int temp = rootA;
rootA = rootB;
rootB = temp;
}

parent[rootB] = rootA;
size[rootA] += size[rootB];
if (rank[rootA] == rank[rootB]) {
rank[rootA] += 1; // 根的深度+1
}
}

int index = 0; // 给股票编号,放入并查集


void tuijian() {
// 并查集初始化
for (int i = 0; i < N; i++) {
parent[i] = i;
rank[i] = 0; // 一开始0还是1无伤大雅?只要判断大小就行了
size[i] = 1;
}

Map<String, Integer> nameStockIndexMap = new HashMap<>();
Map<String, Integer> stockStockIndexMap = new HashMap<>();
Map<String, Integer> nameStockNumMap = new HashMap<>();

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

while (n-- != 0) {
int op = scanner.nextInt();
switch (op) {
case 1: // 加入股票
String name = scanner.next();
int stockNum = scanner.nextInt();
int firstStock = -1;

for (int i = 0; i < stockNum; i++) {
String stockName = scanner.next();
int curStockIndex = -1;
// 股票有编号,则取出,没有编号,那么新建
if (stockStockIndexMap.containsKey(stockName)) {
curStockIndex = stockStockIndexMap.get(stockName);
} else {
curStockIndex = index++;

}
stockStockIndexMap.put(stockName, curStockIndex);
nameStockIndexMap.put(name, curStockIndex);
nameStockNumMap.put(name, stockNum);

if (i == 0) {
firstStock = curStockIndex;
} else {
// 将后面的stock融合到第一张去
// 需要判断,股票不联通的时候才融合
if (!query(curStockIndex, firstStock)) {
union(curStockIndex, firstStock);
}
}
}
break;
case 2:
String name2 = scanner.next();
if (!nameStockIndexMap.containsKey(name2)) {
System.out.println("error");
} else {
System.out.println(size[find(nameStockIndexMap.get(name2))] - nameStockNumMap.get(name2));
}
break;
default:
break;
}
}
}
}
}

0811兴业数金

序列化的内容包括以下几个方面:

属性,包括基本数据类型、数组以及其他对象的引用;

类名;

不能被序列化的内容有:

方法;

有static修饰的属性;

有transient修饰的属性;

Java中transient关键字的详细总结

zodHnTjkUsJlBGN

RXw56oIkipFAHjb

Mybatis是这样防止sql注入的

你真的懂mysql中order by吗

JDK1.8和1.7下的HashMap的区别

0813美团

扑克

可以用queue模拟,而不是用数组,加标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main
{
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n = Integer.parseInt(cin.nextLine());
int[] card = Arrays.stream(cin.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
int[] origin = new int[n];
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) d.offerLast(n - i - 1);
for (int i = 0; i < n; i++) {
d.offerFirst(d.pollLast());
d.offerFirst(d.pollLast());
origin[d.pollLast()] = card[i];
}
for (int i = 0; i < n; i++) {
System.out.printf("%d ", origin[i]);
}
}
}
// vx公众号关注TechGuide 实时题库 闪电速递

合法三元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main
{
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n = Integer.parseInt(cin.nextLine());
int[] nums = Arrays.stream(cin.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
long count = 0;
Map<Integer, Integer> mp = new HashMap<>();
mp.put(nums[n - 1], 1);
for (int i = n - 2; i >= 1; i--) {
for (int j = i - 1; j >= 0; j--) {
count += mp.getOrDefault(3 * nums[i] - nums[j], 0);
}
mp.put(nums[i], mp.getOrDefault(nums[i], 0) + 1);
}
System.out.println(count);
}
}
// vx公众号关注TechGuide 实时题库 闪电速递

0820美团

![ScreenShot2022-09-01at19.16.10](https://gitee.com/JiaChengCC/u-pic-chart-bed/raw/master/uPic/Screen Shot 2022-09-01 at 19.16.10.png)

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
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int main() {
freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i < n + 1; ++i) {
dp[i][0] = dp[i - 1][0] + abs(a[i - 1]);
}
for (int i = 1; i < m + 1; ++i) {
dp[0][i] = dp[0][i - 1] + abs(b[i - 1]);
}
for (int i = 1; i < n + 1; ++i) {
for (int j = 1; j < m + 1; ++j) {
if (a[i - 1] == b[i - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(abs(a[i-1] - b[j-1]) + dp[i - 1][j - 1], min(dp[i - 1][j] + abs(a[i - 1]), dp[i][j - 1] + abs(b[j - 1])));
}
}
cout << dp[n][m];
return 0;
}
// vx公众号关注TechGuide 获取完整题解

0820网易互联网

【2022-08-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
55
56
import java.util.*;

// 未验证
public class BeiShuZijiChongxinzuo {
/**
* 使用回溯法,把所有每个数组的结果遍历存下来
* 然后用map记录当前结果下,操作的次数
* @param args
*/

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String A = scanner.next(), B = scanner.next();

// 存储数字AB变化后的结果,以及变化后需要的步数
Map<Integer, Integer> mapA = new HashMap<>();
Map<Integer, Integer> mapB = new HashMap<>();

dfs(mapA, A, 0, 0, 0);
dfs(mapB, B, 0, 0, 0);

int ans = Integer.MAX_VALUE;
for (Integer a : mapA.keySet()) {
for (Integer b : mapB.keySet()) {
if (a % b == 0 || b % a == 0) {
ans = Math.min(ans, mapA.get(a) + mapB.get(b));
}
}
}

System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
}

// 使用dfs得到所有的变化
// 感觉对一个正数做加一个数字少一个数字的变化,用String好处理一点
public static void dfs(Map<Integer, Integer> map, String str, int curIndex, int val, int opCount) {
// 选完了
if (curIndex == str.length()) {
if (val != 0) {
map.put(val, str.length() - opCount);
}

return;
}

// 不选,表示去掉,操作次数+1
dfs(map, str, curIndex + 1, val, opCount + 1);

// 选
// 回溯,其实如果val写在里面,就不需要此处加上,后面减去了
// 其实val在后面也没必要减去,因为这个是局部变量,也不是引用类型
val = val * 10 + (str.charAt(curIndex) - '0');
dfs(map, str, curIndex + 1, val, opCount);
val = (val - (str.charAt(curIndex) - '0')) / 10;
}
}

拟合:三元组ai>aj, ai=ak

【2022-08-20】网易秋招笔试四道编程题

由于a的值太大,所以考虑离散化

两个数组分别存放左边开始,右边开始的对应值的个数。如l[i]表示在0~当前下标中,i出现的个数。

然后用树状数组维护相同数字的个数的乘积。

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
// 未验证
import java.util.*;
import java.util.stream.Collectors;

public class SanYuanZu {
// 注意,要从1开始,0的话,+lowbit(0)上不去,死循环了
static int N = 1;
static int[] tr;
static int lowbit(int x) {
return x & (-x);
}

static void update(int x, int value) {
for (int i = x; i < N; i += lowbit(i)) {
tr[i] += value;
}
}

static int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(x)) {
ans += tr[i];
}
return ans;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

// 离散化,1 treeset排序去重
Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toCollection(() -> new TreeSet<>((a, b) -> b - a)));
// 2 map编号,这里没有用stream是因为,编号递增不能放入lambda表达式,因为他需要final的量
Map<Integer, Integer> map = new HashMap<>();
for (Integer num : set) {
map.put(num, N++);
}

// 3 然后根据编号,反映给原始数组nums,此处完整的lambda表达式为 num -> { return map.get(num);}
nums = Arrays.stream(nums).map(map::get).toArray();

int[] l = new int[N+10], r = new int[N + 10];
tr = new int[N + 10];
// 右边的,需要先全部放进去
for (int num : nums) {
r[num] += 1;
}

int ans = 0;
// 注意,这个num是离散化之后映射的结果了
for (int num : nums) {
// set是从大到小排序的
// 遍历到该num的时候,这个数是先不算的,需要找到他的左右两边比他大的,相等的
// query的时候,由于是严格大于,所以需要-1。
ans += query(num-1);

// 之前的去掉
update(num, -l[num] * r[num]);
l[num] += 1;
r[num] -= 1;
// 放入新的
update(num, l[num] * r[num]);
}

System.out.println(ans);
}
}

注意:

个人想法:

针对这个题目,有点想法,是用树状数组,那么肯定需要有类似于前缀和的思想,或者说求的个数,也是需要有区间性质的,就跟上面一样。

而不是说比如下面这一题:(见0904滴滴)

1
2
3
4
5
6
/**
给一个数字,这个数字十进制下每个数位的异或和,就是美丽数。
然后询问T次,每次给定区间L,R,t求区间中美丽数字为t的个数。
那么这个个数题目,是定向的等于t,所以其实桶的思想差不多了(而且t的范围不大,最多16),而不会计算前缀的个数吧??
可以用一点类似莫队的思想,将LR区间排序,每次算一点
**/

0825荣耀

【2022-08-25】荣耀秋招笔试三道编程题

会议最长时间

971661436474_.pic

简书:解答

不是想象的 排序 + 贪心

是 排序 + 24小的dp,注意我对这个dp写的一些注解

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
89
90
91
92
93
94
95
96
97
98
99
import java.util.*;

public class ConferenceTime {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int T = Integer.parseInt(scanner.nextLine());

while (T-- != 0) {
int n = Integer.parseInt(scanner.nextLine());

int[][] times = new int[n][2];
for (int i = 0; i < n; i++) {
times[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
}

// 先将会议时间按照start排序
Arrays.sort(times, (time1, time2) -> time1[0] - time2[0]);

// 表示从0~i时间的最长会议时间,这是个子问题
int[] dp = new int[24];

for (int i = 0; i < 1; i++) {
int start = times[i][0], end = times[i][1];

// 还是一维的想起来简单点
// 对于这个会议,我看看end之后的每个时间,是取还是不取,更新
// 需要根据start排序的,因为这样的话,我在这个会议使用那个dp[start]的时候,这个dp[start]是肯定不会再更新了
// 因为按照start排序了,而且是更新每次end(包括)之后的,即使是更新start(不包括)之后,也不会变更了。
for (int j = end; j < 24; j++) {
dp[j] = Math.max(dp[start] + end - start, dp[j]);
}
}

Arrays.stream(dp).forEach(num -> System.out.print(num + " "));
System.out.println(dp[23]);
}
}
}

/*
案例:
1
6
15 17
8 11
10 16
11 12
13 15
9 12
*/


import java.util.*;

public class ConferenceTime {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int T = Integer.parseInt(scanner.nextLine());

while (T-- != 0) {
int n = Integer.parseInt(scanner.nextLine());

int[][] times = new int[n][2];
for (int i = 0; i < n; i++) {
times[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
}

// 先将会议时间按照start排序
Arrays.sort(times, (time1, time2) -> time1[0] - time2[0]);

// 第一维用 + 1,就不用考虑边界问题了
// 第一维表示会议编号,0表示不取,第二维表示从0~i时间的最长会议时间,这是个子问题
int[][] dp = new int[times.length + 1][24];

// 边界,不用,不取的时候是0,dp0表示不取货物

for (int i = 1; i <= times.length; i++) {
int start = times[i-1][0], end = times[i-1][1];

// 这个就是理解一下,
// 如果j小于end,那么这个会议是加不进去的,所以直接等于前面的
// 如果j大于,那么考虑加上这个和不加上这个,那一个更大取哪一个
// 此处的会议是需要根据start排序的,因为不排序的话,需要用的那个dp[i-1][start]这次更新了,下次还会被更新到,但是前面已经用过了,导致出错
for (int j = 0; j < 24; j++) {
if (j < end) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][start] + end - start, dp[i-1][j]);
}
}
}

Arrays.stream(dp[times.length]).forEach(num -> System.out.print(num + " "));
System.out.println(dp[times.length][23]);
}
}
}

两个背包问题

a253a191f53e3c0c86692b0e67975f5d

背包问题的很不错的变种

非常注意,不是贪心。

此处,居然是重量为一半,的01背包问题,然后看此时最多的重量是多少,然后用总的sum 减去 一半情况最多时候的dp重量

注意,如果单纯用二维dp,会有10%过不去,需要改成一维dp的滚动数组。这个一维的dp,由于需要依赖上一次的前面,所以反着dp。

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
public class CangKu {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int M = Integer.parseInt(scanner.nextLine());
// 输入 + 从大到小排序
int[] nums = Arrays.stream(scanner.nextLine().split(" "))
.mapToInt(Integer::valueOf)
.toArray();

// 考虑动态规划,看一般的背包能装多少
int n = nums.length;
// 表示背包的一半的重量
int m = Arrays.stream(nums).sum() / 2;
// 对一半重量进行01背包问题dp
int[] dp = new int[m + 1];


for (int i = 1; i < n + 1; i++) {
// 因为一维dp,所以反着来
for (int j = m; j >= 0; j--) {
if (j < nums[i - 1]) {
// 装不下
dp[j] = dp[j];
} else {
dp[j] = Math.max(dp[j], dp[j - nums[i-1]] + nums[i - 1]);
}
}
}

System.out.println(Arrays.stream(nums).sum() - dp[m]);
}
}

0825美的

第一题是模拟题,好好读题,细心点就行

同一直线上,最多的点

宫水三叶:优化(枚举直线 + 哈希表统计)

斜率的话,朴素的,可以(x2 - x1) * (y3 - y2) == (x3 - x2) * (y2 - y1)

如果是像下面这样的,可以将斜率用字符串存起来(为了保证斜率的精度问题),首先得求出最大公约数

然后是枚举遍历,每一次从一个点出发,然后用map村上斜率的个数,取最多的,最后记得加上自己这个点。

每次循环都是考虑以这个点为出发点的斜率。

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 {
public int maxPoints(int[][] ps) {
int n = ps.length;
int ans = 1;
for (int i = 0; i < n; i++) {
Map<String, Integer> map = new HashMap<>();
// 由当前点 i 发出的直线所经过的最多点数量
int max = 0;
for (int j = i + 1; j < n; j++) {
int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
int a = x1 - x2, b = y1 - y2;
int k = gcd(a, b);
String key = (a / k) + "_" + (b / k);
map.put(key, map.getOrDefault(key, 0) + 1);
max = Math.max(max, map.get(key));
}
ans = Math.max(ans, max + 1);
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}

0827完美世界

1049. 最后一块石头的重量 II

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
public static class ShowMeBug1 {
// 本题面试官已设置测试用例
// 请根据题目要求确定返回值类型和参数列表(输入)
public int lastGarbageSize(int[] garbages) {
// 在这⾥写代码
// 使用动态规划
int n = garbages.length;
int sum = 0;
for (int g: garbages) {
sum += g;
}
int m = sum / 2;
boolean[][] dp = new boolean[n + 1][m + 1];

// 边界,0表示不取物品的时候
dp[0][0] = true;

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {

if (j < garbages[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] || dp[i-1][j - garbages[i-1]];
}
}
}

for (int j = m; j>=0; j--) {
if (dp[n][j]) {
return sum - 2 * j;
}
}

return 0;
}
}

56. 合并区间

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
public static class ShowMeBug {
// 本题面试官已设置测试用例
// 请根据题目要求确定返回值类型和参数列表(输入)
public int[][] mergeCard(int[][] cards) {
// 在这⾥写代码

List<int[]> ans = new ArrayList<>();
int count = 0;

// 按照start从小到大排序
Arrays.sort(cards, (card1, card2) -> card1[0] - card2[0]);

// 放入第一个
ans.add(cards[0]);

for (int i = 1; i < cards.length; i++) {
int b = cards[i][0], e = cards[i][1];

// 如果没有相交
if (b > ans.get(count)[1]) {
ans.add(cards[i]);
count += 1;
} else {
// 相交
ans.get(count)[1] = Math.max(e, ans.get(count)[1]);
}
}

// 将List转为int
int[][] newAns = new int[ans.size()][2];
for (int i = 0; i < ans.size(); i++) {
newAns[i][0] = ans.get(i)[0];
newAns[i][1] = ans.get(i)[1];
}

return newAns;
}
}

0828小红书

一对一

613eef2afc1cf1578da97a259b4a0a5e

注意:树

本题说了,这张无向图里面,任意两点之间有且仅有一条路径,

而且输入的时候,n-1个数字,ai代表ai到i-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
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
import java.util.*;

public class Main3 {
public static class TreeNode {
List<TreeNode> childs;
int val;

TreeNode(int val) {
this.val = val;
childs = new ArrayList<>();
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = Integer.parseInt(scanner.nextLine());
visited = new boolean[n + 1];

TreeNode[] nodes = new TreeNode[n + 1];
for (int i = 0; i < n + 1; i++) {
nodes[i] = new TreeNode(i);
}

for (int i = 0; i < n-1; i++) {
int temp = scanner.nextInt();
// 注意这里i+2,因为从0开始
nodes[temp].childs.add(nodes[i+2]);
}

TreeNode root = nodes[1];

dfs(root);

System.out.println(ans);
}

static int n = 0;
static int ans = 0;
static boolean[] visited;
public static void dfs(TreeNode node) {
// 如果该节点有子节点,并且没被访问过,那么可能能将该节点与子节点配对
if (!node.childs.isEmpty() && !visited[node.val]) {
// 先将子节点递归
for (int i = 0; i < node.childs.size(); i++) {
if (!node.childs.get(i).childs.isEmpty()) {
dfs(node.childs.get(i));
}
}

// 子节点递归完了,才轮到自己,与某个没有被配对的子节点配对即可,若没有就没有喽
for (int i = 0; i < node.childs.size(); i++) {
if (!visited[node.childs.get(i).val]) {
visited[node.childs.get(i).val] = true;
visited[node.val] = true;

ans += 1;

return;
}
}
}
}
}

0827美团

挑剔

a876de293c49ee36535cfcd4d8b329b1

考虑最好是用模拟,但是每次模拟搬动太多了。

所以想到了用queue + set。

由于数字是不重复的,而且每次的操作,都是讲编号m放到最前面,那么双端队列最前面放一个放一个就好

里面的不删除,最后从前往后输出的时候用set判断,输出过的就不再输出。

另一种思路:也可以每一次被操作的数字记录时间戳,然后按照时间戳从大到小。当然一开始是的输入不是。

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
import java.util.*;

public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
scanner.nextLine();
int[] indexs = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
int[] nums = IntStream.range(0, n).map(i -> i+1).toArray();

Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
queue.offerLast(i + 1);
}

for (int i = 0; i < m; i++) {
queue.offerFirst(indexs[i]);
}

Set<Integer> set = new HashSet<>();

int size = queue.size();
for (int i = 0; i < size; i++) {
int temp = queue.pollFirst();
if (!set.contains(temp)) {
System.out.print(temp + " ");
set.add(temp);
}
}
}
}

裁缝

dfs+回溯

891a22426ea09b7773569587fe1e0f2a

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
import java.util.*;

public class Main3 {
/**
* 一共要割m-1刀
* @param args
*/
static int n, m;
static String s;
static int[] kehu;
static String[] kehuStrs;
static int ans;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
scanner.nextLine();
s = scanner.nextLine();

kehu = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
kehuStrs = new String[m];
for (int i = 0; i < m; i++) {
kehuStrs[i] = scanner.nextLine();
}

dfsTrace(0, 0, new ArrayList<>());

System.out.println(ans);
}

/**
* 回溯 + dfs,curIndex表示该间隙割还是不割
*/
public static void dfsTrace(int preIndex, int curIndex, List<String> strs) {
if (strs.size() == m - 1 && curIndex <= n - 1) {
strs.add(s.substring(preIndex));

boolean[] visited = new boolean[m];
out: for (int j = 0; j < m; j++) {
for (int i = 0; i < m; i++) {
if (!visited[i] && strs.get(j).equals(kehuStrs[i])) {
visited[i] = true;
continue out;
}
}

strs.remove(strs.size() - 1);
return;
}

strs.remove(strs.size() - 1);
ans += 1;
return;
}

if (curIndex >= n - 1) {
return;
}

// 不割
dfsTrace(preIndex, curIndex + 1, strs);

// 割
strs.add(s.substring(preIndex, curIndex + 1));
dfsTrace(curIndex + 1, curIndex + 1, strs);
strs.remove(strs.size() - 1);
}
}

下雨

deb187f58597c0d0df70ea2e8289bbbe

掌握到感觉是有点牛的

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
import java.util.*;

// 未验证
public class Main4 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), b = scanner.nextInt();
scanner.nextLine();

int[] p = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
int[] t = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

if (p[0] > b) {
System.out.println(-1);
return;
}

// 注意,题目有两个限制,一个是电量限制,一个是要时间最小
// 所以可以在每一次时间,(看作背包),看看该最小电量能否满足,然后取最小时间
// 也就是说,在某个时间限制下,我先求能用到的最小电量,然后看能否满足。此处没有价值问题,感觉根背包稍微一点不一样?
// 但是这种朴素做法会超时,所以考虑把时间二分来做
// 注意,此处的机器人只能往右,而且是并行执行的,所以考虑从右往做算dp



int left = 1, right = Arrays.stream(t).sum();
int ans = 0;

while (left <= right) {
int mid = left + (right - left >> 1);

// 找到满足的最小的
if (check(mid, n, p, t, b)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}

// 最终状态right < left,left满足,right不满足
System.out.println(ans);
}

public static boolean check(int time, int n, int[] p, int[] t, int b) {
// 表示在某个固定时间下,收i~n件衣服的最少电量
// 所以dp[1]才是收所有衣服的最少电量
int[] dp = new int[n+2];

// 边界,注意t和p是从0开始的,而dp是从1开始的,不要搞混了
Arrays.fill(dp, Integer.MAX_VALUE);
dp[n+1] = 0;

// 以第i个,收到第j个,j是大于i的,由于从后往前,dp[j]已有最小电量,现在算dp[i]
// 就是说,dp[i]的最少电量,可以由机器人i往后一段时间到每个j来遍历的得到最小电量
for (int i = n; i >= 1; i--) {
// 注意此处j要从n+1,因为j不包括的,所以机器人i收到n,是要j在n+1
for (int j = n+1; j > i; j--) {
// 此处j是不包括的,因为dp[j]里面有j了
if ((j - i) * t[i-1] <= time) {
dp[i] = Math.min(dp[i], dp[j] + p[i-1]);
}
}
}

return dp[1] <= b;
}
}

0827京东

漂亮串

字符中,有两个red,其他的都是小写字母,组成不了red的,问字符串n中有多少个漂亮串。

用dp

1
2
3
抛砖引玉一个朴素易懂的DP:总的思路是做减法,用 所有长度为n的字符串数 减去 长度为n不含'red'的字符串数 和 长度为n有且仅有一个'red'的字符串数。维护一个 dp[2][N] 的二维数组, 第一个下标代表字符串中 'red'出现的次数,第二个下标代表字符串长度 于是dp[0][i] 即为 长度为 i 其中包含 0 个'red'的字符串个数(即不出现'red') 于是dp[1][i] 即为 长度为 i 其中包含 1 个'red'的字符串个数 最终结果就应该是很简单的 26^(N) - dp[0][N] - dp[1][N]
重头戏是状态转移防程:首先考虑 dp[0][i], 分 第 i 位不是'd' 和 第 i 位是'd' 两种情况考虑 如果第 i 位不是'd', 那前面 [0~i-1] 位只要不包含'red'就行,而第i位除'd'以外还有25种选择,dp[0][i-1] * 25 如果第 i 位是'd',那其前面两位不能是're', 考虑从 dp[0][i-1] 中剔除所有的 dp[0][i-3]'re'的情况,第i位只有'd'一种选择,(dp[0][i-1] - dp[0][i-3]) * 1 因此综合来看,dp[0][i] = dp[0][i-1] * 25 + (dp[0][i-1] - dp[0][i-3]) * 1 = dp[0][i-1] * 26 - dp[0][i-3]
其次考虑 dp[1][i], 也分 第 i 位不是'd' 和 第 i 位是'd' 两种情况考虑 如果第 i 位不是'd', 那前面 [0~i-1] 位需要包含一次'red',而第i位除'd'以外还有25种选择,dp[1][i-1] * 25 如果第 i 位是'd',那又有两种情况, “ 不包含'red' 的[0~i-3]+‘red’ ” 或者 “ 包含'red'的[0~i-3]+非're'+'d' ” “ 不包含'red'的[0~i-3]+‘red’ ”,非常简单,即 dp[0][i-3] * 1 “ 包含'red'的[0~i-3]+非're'+'d' ”的情况与之前类似,考虑从 dp[1][i-1] 中剔除所有的 dp[1][i-3]'re'的情况,第i位只有'd'一种选择,(dp[1][i-1] - dp[1][i-3]) * 1 因此综合来看,dp[1][i] = dp[1][i-1] * 25 + dp[0][i-3] + (dp[1][i-1] - dp[1][i-3]) * 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
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
ll dp[N][4];
void init(int n){
dp[0][0] = 1;
for(int i = 1; i <= n; i ++){
dp[i][0] = (dp[i - 1][0] * 25 % mod + dp[i - 1][1] * 24 % mod + dp[i - 1][2] * 24 % mod) % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
dp[i][2] = dp[i - 1][1];
}
}
int main()
{
int n;
cin >> n;
ll ans = 1;
for(int i = 1; i <= n; i ++){
ans = ans * 26 % mod;
}
init(n);
ans = (ans - (dp[n][0] + dp[n][1] + dp[n][2]) % mod + mod) % mod;
for(int i = 1; i <= n - 2; i ++){
ll left = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
ll right = (dp[n - i - 2][0] + dp[n - i - 2][1] + dp[n - i - 2][2]) % mod;
ans = (ans - left * right % mod + mod) % mod;
}
cout << ans << endl;
return 0;
}

0828小红书

一对一

yiduiyi

这是我自己做的。

这一题,一看n节点,n-1条边,是树,而且是有向的,直接建树就好。 使用邻接表。

然后两两配对,需要从叶子结点根父节点配对,所以是dfs先到最底下,把叶子和父亲配对,配对完就visited标识为给true,后面就不能配对了,以此类推。

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
// AC
import java.util.*;

public class Main3 {
public static class TreeNode {
List<TreeNode> childs;
int val;

TreeNode(int val) {
this.val = val;
childs = new ArrayList<>();
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = Integer.parseInt(scanner.nextLine());
visited = new boolean[n + 1];

TreeNode[] nodes = new TreeNode[n + 1];
for (int i = 0; i < n + 1; i++) {
nodes[i] = new TreeNode(i);
}

for (int i = 0; i < n-1; i++) {
int temp = scanner.nextInt();
// 注意这里i+2,因为从0开始
nodes[temp].childs.add(nodes[i+2]);
}

TreeNode root = nodes[1];

dfs(root);

System.out.println(ans);
}

static int n = 0;
static int ans = 0;
static boolean[] visited;
public static void dfs(TreeNode node) {
// 如果该节点有子节点,并且没被访问过,那么可能能将该节点与子节点配对
if (!node.childs.isEmpty() && !visited[node.val]) {
// 先将子节点递归
for (int i = 0; i < node.childs.size(); i++) {
if (!node.childs.get(i).childs.isEmpty()) {
dfs(node.childs.get(i));
}
}

// 子节点递归完了,才轮到自己,与某个没有被配对的子节点配对即可,若没有就没有喽
for (int i = 0; i < node.childs.size(); i++) {
if (!visited[node.childs.get(i).val]) {
visited[node.childs.get(i).val] = true;
visited[node.val] = true;

ans += 1;

return;
}
}
}
}
}

0830携程

rgb染色

首先建图(虽然此处n个节点,n-1条边,联通图,但是题目给的是无向图,所以不知道是哪里指向哪里的,所以还是建图,后面dfs的时候,在参数里面指定父节点,然后遍历子节点的时候取出父节点就好了)。

注意,数量问题,可以考虑每个节点挂以当前节点为根的总数据(dfs实现),下面圣诞树dp,也有类似的想法。

下面的代码是建树的,后面来不及改成图了。

232e872e9577eca706ff6f2c9081e920 88141f3cc2c8fae15bfdd636680b0acb
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
89
90
91
92
93
94
// 注意,只过了25%,感觉是建树的问题,因为无向,应该建图,建图的话需要找到入度为0
import java.util.*;

public class Main3 {

static int ans = 0;
public static class TreeNode {
List<TreeNode> childs;
int[] colors = new int[3];

TreeNode(char color) {
childs = new ArrayList<>();

if (color == 'r') { colors[0] = 1; }
else if (color == 'g') { colors[1] = 1; }
else { colors[2] = 1; }
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
String colors = scanner.nextLine();
int[] inDe = new int[n];

// 建树
TreeNode[] nodes = new TreeNode[n];
for (int i = 0; i < n; i++) {
nodes[i] = new TreeNode(colors.charAt(i));
}

for (int i = 0; i < n - 1; i++) {
int u = scanner.nextInt() - 1, v = scanner.nextInt() - 1;
if (inDe[v] > 0) {
int temp = u;
u = v;
v = temp;
}
nodes[u].childs.add(nodes[v]);
inDe[v] += 1;
}
TreeNode root = nodes[0];
for (int i = 0; i < n; i++) {
if (inDe[i] == 0) {
root = nodes[i];
}
}

dfs(root);
judge(root, root);

System.out.println(ans);
}


/**
* 得到以该节点为根的各个colors个数
* @param node
*/
public static void dfs(TreeNode node) {
if (node != null) {
for (TreeNode child : node.childs) {
dfs(child);
}

for (int i = 0; i < node.childs.size(); i++) {
for (int j = 0; j < 3; j++) {
node.colors[j] += node.childs.get(i).colors[j];
}
}
}
}

public static void judge(TreeNode node, TreeNode root) {
if (node != null) {
int[] allColors = root.colors;
// 断该子节点,及下面
for (TreeNode child : node.childs) {
int[] colors2 = child.colors;
boolean flag = true;
for (int i = 0; i < 3; i++) {
if (colors2[i] < 1 || allColors[i] - colors2[i] < 1) {
flag = false;
break;
}
}

ans = flag ? ans + 1 : ans;
judge(child, 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
import java.util.*;

public class Main4 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());

int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

int maxDist = 0;
int pos = -1;
for (int i = 0; i < n - 1; i++) {
if (Math.abs(nums[i + 1] - nums[i]) >= maxDist) {
pos = i;
maxDist = Math.abs(nums[i + 1] - nums[i]);
}
}

if (pos == 0) {
nums[pos] = nums[pos + 1];
} else if (pos == n - 2) {
nums[pos + 1] = nums[pos];
} else {
nums[pos] = (nums[pos - 1] + nums[pos + 1]) / 2;
}

maxDist = 0;
for (int i = 0; i < n - 1; i++) {
if (Math.abs(nums[i + 1] - nums[i]) > maxDist) {
maxDist = Math.abs(nums[i + 1] - nums[i]);
}
}

System.out.println(maxDist);
}
}

0831顺丰

猜数列游戏

每一个位置,二分二分查找

如果遍历1~n,每个取log2,相加,会超时

所以考虑数字范围,比如2^i ~ 2^(i+1)-1取i+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
import java.util.*;

public class Main1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());

if (n == 1) {
System.out.println(1);
return;
}

long ans = 0;
long bn = (long) (Math.log(n) / Math.log(2));

for (int i = 1; i < bn; i++) {
ans += (i + 1) * ((long)Math.pow(2, i+1) - (long)Math.pow(2, i));
}
ans += (n - (long)Math.pow(2, bn) + 1) * (bn + 1);


System.out.println(ans + 1);
}
}

圣诞树

CodeForces 274 B.Zero Tree(树形dp)

4174b0041bdc6bfc7d2e7f0a25762780

注意,这是一个无向图,但是题目说是,一定要包含节点1的子图,所以其实可以看作树,以1为根节点

这个题目其实就是给的树的结构,所以其实应该可以建树的。(下面的代码使用了邻接矩阵)。

但是有的题目如果给出n个节点,n-1条边保证联通图,但是这个时候其实不能建树,得建图。建图了之后,保证类似树的遍历方法,跟下面一样,传参数的时候传个父节点,判断下父节点不dfs就行了。

很好的一个例子是小红书的一对一,员工n个,员工关系n-1,保证联通。因为无向图,所以只能建树其实,而且树节点未知,考虑入度为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
import java.util.*;

public class Main2 {

static List<Long>[] g;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
int[] parents = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
yuanwangs = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
Main2.n = n;
inc = new long[n + 1];
dec = new long[n + 1];

g = new ArrayList[n+1];

for (int i = 0; i <= n; i++) {
g[i] = new ArrayList<>();
}

for (int i = 2; i <= n; i++) {
g[i].add((long)parents[i-2]);
g[parents[i-2]].add((long)i);
}

// 1 是父亲节点,0 其实null
shengdanshuDfs(1, 0);
System.out.println(inc[1] + dec[1]);
}

static int n;
static long[] inc, dec;
static int[] yuanwangs;
public static void shengdanshuDfs(long u, long fa) {
for (int i = 0; i < g[(int)u].size(); i++) {
long v = g[(int)u].get(i);
if (v == fa) { continue; }
shengdanshuDfs(v, u);

inc[(int)u] = Math.max(inc[(int)u], inc[(int)v]);
dec[(int)u] = Math.max(dec[(int)u], dec[(int)v]);
}

// 当前节点的值,根据子树的操作和操作了一下,如果还是不为0,那么需要将该节点在进行操作
// 下面如果当前愿望>0,那么减少次数要增加,否则增加次数要增加。
yuanwangs[(int)u-1] += inc[(int)u] - dec[(int)u];
if (yuanwangs[(int)u-1] > 0) {
dec[(int)u] += yuanwangs[(int)u-1];
} else {
inc[(int)u] -= yuanwangs[(int)u-1];
}
}
}

0831华为

14795393adb081e0452b0d4bbf245b41

字符串压缩替换

虽然是O(n),但是还是只有95%过了。

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
import java.util.*;

public class Main1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String senStr = scanner.nextLine();
String[] list = scanner.nextLine().toLowerCase().split(" ");

Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < list.length; i++) {
map.put(list[i], i);
}

int left = 0, right = -1;
StringBuilder ans = new StringBuilder();
char c;
int len = senStr.length();

while (right < senStr.length()) {
left = right + 1;
while (left < len && (senStr.charAt(left) == ',' || senStr.charAt(left) == '.'
|| senStr.charAt(left) == ' ')) {
// 找到下一个单词起点
ans.append(senStr.charAt(left));
left += 1;
}

if (left >= len) {
break;
}

if (senStr.charAt(left) == '\"') {
// 找到另外一个引号
ans.append(senStr.charAt(left));
left += 1;
while (senStr.charAt(left) != '\"') {
ans.append(senStr.charAt(left));
left += 1;
}

ans.append(senStr.charAt(left));
right = left;
continue;
}

right = left;
c = senStr.charAt(right);
while (right < len && c != ',' && c != '.' && c != '\"' && c != ' ') {
right += 1;
if (right < len) {
c = senStr.charAt(right);
}
}


String tempStr = senStr.substring(left, right);
if (map.containsKey(tempStr.toLowerCase())) {
ans.append(map.get(tempStr.toLowerCase()));
} else {
ans.append(tempStr);
}

if (right < len) {
ans.append(senStr.charAt(right));
}
}

System.out.println(ans.toString());
}
}

走迷宫(带有陷阱炸弹强)

115818bb996dedf990906a88a44574c9

注意下面的减枝,普通的减curTime>ans只能过45%,然后减枝改成当前时间+最快能到达>ans,就过了

减枝一般两种

第一种是记忆化搜索,第二种是就上面用的当前的加未来能到达的 > ans,这两种。

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
import java.util.*;

public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
Main2.n = n;
Main2.m = m;
scanner.nextLine();

int[][] matrix = new int[n][m];

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int val = scanner.nextInt();
matrix[i][j] = val;

if (val == 2) {
start[0] = i;
start[1] = j;
} else if (val == 3) {
end[0] = i;
end[1] = j;
}
}
}

dfsTrace(matrix, new boolean[n][m], 0, start);

System.out.println(ans);
}

static int n, m;
static int ans = Integer.MAX_VALUE;
static int[] start = new int[2], end = new int[2];
static int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public static void dfsTrace(int[][] matrix, boolean[][] visited, int curTime, int[] curLoc) {
int x = curLoc[0], y = curLoc[1];
if (x == end[0] && y == end[1]) {
ans = Math.min(ans, curTime);
return;
}

// 减枝
if ((Math.abs(x - end[0]) + Math.abs(y - end[1]) + curTime >= ans)) {
return;
}

visited[x][y] = true;

curTime += 1;
if (matrix[x][y] == 4) {
curTime += 2;
} else if (matrix[x][y] == 6) {
for (int i = 0; i < 4; i++) {
int newX = x + dirs[i][0], newY = y + dirs[i][1];
if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 1) {
// 墙被炸掉
matrix[newX][newY] = 9;
}
}
}

for (int i = 0; i < 4; i++) {
int newX = x + dirs[i][0], newY = y + dirs[i][1];
if (newX >= 0 && newX < n && newY >= 0 && newY < m && !visited[newX][newY] &&
(matrix[newX][newY] == 0 || matrix[newX][newY] == 4 || matrix[newX][newY] == 9
|| matrix[newX][newY] == 6 || matrix[newX][newY] == 3)) {

dfsTrace(matrix, visited, curTime, new int[]{newX, newY});
}
}


if (matrix[x][y] == 6) {
for (int i = 0; i < 4; i++) {
int newX = x + dirs[i][0], newY = y + dirs[i][1];
if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 9) {
// 炸掉的墙还原
matrix[newX][newY] = 1;
}
}
}
// visited还原
visited[x][y] = false;
}
}

充电桩问题

dee6201b3e8db11326f5d63a2572e272

动态规划,过了80%,注意,ans会是小数,然后答案是正数的话输出得整数。

然后没过的20%可能是,输入的waittimes有可能是double???

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
// 关于代码思路自己的理解,总的来说,感觉很像01背包问题
// 第一个维度 0~n+1代表充电桩,0代表起点,n+1代表终点
// 第二个维度代表剩下的里程数量,然后此处,利用前一个桩求本桩,并不是j-dst了,而是d+dst,因为历程数时间少的,不过由于是二位dp依赖i-1,所以j还是可以从j为0到后面。
// dpij表示的含义就是,到第i个充电桩,历程数目还剩j的情况下,最少的时间是多少,经典背包。

import java.util.*;

public class Main3 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int D = scanner.nextInt();
int N = scanner.nextInt();

int[] distances = new int[N + 2];
int[] times = new int[N + 2];

for (int i = 1; i <= N; i++) {
distances[i] = scanner.nextInt();
times[i] = scanner.nextInt();
}

double[][] dp = new double[N + 2][1001];

// 边界
for (int i = 0; i < N + 2; i++) {
Arrays.fill(dp[i], 0x3f3f3f3f);
}
dp[0][1000] = 0;

// 终点站
distances[N + 1] = D;

for (int i = 1; i <= N + 1; i++) {
// 开到第i个休息站,充电+等待
int cost = times[i] + 1;
int dst = distances[i] - distances[i - 1];
if (dst > 1000) {
System.out.println(-1);
return;
}

for (int j = 0; j <= 1000 - dst; j++) {
if (j + dst > 1000) {
// 无法到达
dp[i][j] = 0x3f3f3f3f;
} else {
// 更新不充电
dp[i][j] = Math.min(dp[i-1][j+dst] + dst * 1.0 / 100, dp[i][j]);
// 更新充电
dp[i][1000] = Math.min(dp[i][1000], dp[i-1][j+dst] + dst * 1.0 / 100 + cost);
}
}
}

double ans = 0x3f3f3f3f;
for (int i = 0; i < 1001; i++) {
ans = Math.min(ans, dp[N+1][i]);
}

if (ans == 0x3f3f3f3f) {
System.out.println(-1);
}else if (ans == (long)ans) {
System.out.println((long)ans);
} else {
System.out.println(ans);
}
}
}

0903美团笔试

0903搜狐畅游

0904飞哥网易互联网

树的权值因数和

65e015a613e797633c8ff4d5b98c0637

这里面,可以看出,说是两个节点之间有关联,但是是无向图,所以需要用邻接表建图,题目说了节点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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.*;

// 未验证,之前未优化过的,只有0。
public class Main4 {
public static class Node {
long val;
int bianhao;
long count;

Node(long val, int bianhao) {
this.val = val;
this.bianhao = bianhao;
count = 0;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

Node[] nodes = new Node[n + 1];
List<Node>[] g = new ArrayList[n + 1];
for (int i = 1; i < n + 1; i++) {
g[i] = new ArrayList<>();
nodes[i] = new Node(nums[i-1], i);
}

for (int i = 0; i < n - 1; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();

g[u].add(nodes[v]);
g[v].add(nodes[u]);
}

dfs(g, nodes[1],0);
System.out.println(nodes[1].count);
}

public static void dfs(List<Node>[] g, Node node, int father) {
// if (g[node.bianhao].size() == 0) {
// node.count = getYinZis(node.val);
// System.out.println("123");
// return;
// }
// 先算子节点
for (Node child: g[node.bianhao]) {
if (child.bianhao == father) {
continue;
}

dfs(g, child, node.bianhao);
}

Set<Long> set = new HashSet<>();
boolean one = false;
// 算出子树的乘积
for (Node child: g[node.bianhao]) {
if (child.bianhao == father) {
continue;
}

set.add(child.val);
if (child.val == 1) {
one = true;
}
// node.val *= child.val;
node.count = (node.count + child.count) % ((long)10e9 + 7);
}

// 不算那个全职的乘积,因为全职乘积的因数个数,其实也是全职因数个数的相加
// 子节点所有的因数*2,再加上自己的全职的因数个数
node.count = (node.count * 2 + getYinZis(node.val)) % ((long)10e9 + 7);
set.add(node.val);
if (node.val == 1) {
one = true;
}
// 若有1,因数个数需要-1
node.count -= one ? 1 : 0;
// 若有相同,因数个数需要剪掉(相同的个数-1)
// 父亲节点的话,没有父亲节点,所以size少1
if(node.bianhao == 1) {
node.count -= (g[node.bianhao].size() + 1 - set.size());
} else {
node.count -= (g[node.bianhao].size() - set.size());
}
node.count = (node.count) % ((long)10e9 + 7);

// 算出因数
// node.count = (node.count * 2 - + getYinZis(node.val)) % ((long)10e9 + 7);
}

public static long getYinZis(long num) {
long ans = 0;
for (long i = 1; i * i <= num; i++) {
if (num % i == 0) {
if (i * i == num) {
ans += 1;
} else {
ans += 2;
}
}
}

return ans % ((long)10e9 + 7);
}
}
/**
3
1 2 3
1 2
1 3
*/
// 8

数组每次减去k,找最大的最小

14cb68590125cd7cb99119d19f85b1ef

直接使用优先队列,每次减最大会超时,考虑二分取答案。

以下C++ 91%:

注意下面的l需要为-10e15

6211662284045_.pic

0904滴滴

莫队算法 (Mo’s Algorithm)

40C8E15977538415CAAE646ED73EB66E

以下是我的代码,91%。感觉可以将LR排序,然后另一个同维护个数即可。

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
// 过了91%,超时
import java.util.*;

public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = Integer.parseInt(scanner.nextLine());

// 读取三行,C++的话,可以跟下面的求L最小和R最大一起,便读取边判断大小。
int[] L = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
int[] R = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
int[] t = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

int minL = Arrays.stream(L).min().getAsInt();
int maxR = Arrays.stream(R).max().getAsInt();
int n = maxR - minL + 1;
int[] meiliVal = new int[n];

for (int i = 0; i < n; i++) {
int num = minL + i;
int ans = 0;

while (num != 0) {
int temp = num % 10;
ans ^= temp;
num /= 10;
}

meiliVal[i] = ans;
}

for (int i = 0; i < T; i++) {
int ans = 0;
for (int j = L[i]; j <= R[i]; j++) {
if (meiliVal[j - minL] == t[i]) {
ans += 1;
}
}

System.out.println(ans);
}
}
}

0908 腾讯音乐

二叉树中序和前序

35e4d7330683be7de9a39f3f656cadf7
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// 标准答案
import java.util.*;

public class Main2TechGuide {
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int val) {
this.val = val;
}
}

public static void main(String[] args) {
ArrayList<Integer> preOrder = new ArrayList<>();
ArrayList<Integer> inOrder = new ArrayList<>();
preOrder.add(1);
preOrder.add(1);
preOrder.add(2);
inOrder.add(1);
inOrder.add(2);
inOrder.add(1);
int n = inOrder.size();
List<TreeNode> ans = new Solution().getBinaryTrees(preOrder, inOrder);

for (TreeNode an : ans) {
cengxuBianli(an);
}
}

static TreeNode emptyNode = new TreeNode(-1);
public static void cengxuBianli(TreeNode root) {
// 层序遍历输出
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);

while (!queue.isEmpty()) {
int n = queue.size();
for (int i = 0; i <n; i++) {TreeNode node = queue.pollFirst();
System.out.print(node == emptyNode ? "#" : node.val);

if (node.left == null && node.right == null) {
continue;
}

if (node.left == null) {
queue.offerLast(emptyNode);
} else {
queue.offerLast(node.left);
}
if (node.right == null) {
queue.offerLast(emptyNode);
} else {
queue.offerLast(node.right);
}
}
}
System.out.println();
}

static class Solution {
public ArrayList<TreeNode> getBinaryTrees(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
// write code here
return buildTree(preOrder, 0, preOrder.size() - 1,
inOrder, 0, inOrder.size() - 1);

}

ArrayList<TreeNode> buildTree(ArrayList<Integer> preOrder, int preStart, int preEnd,
ArrayList<Integer> inOrder, int inStart, int inEnd) {
ArrayList<TreeNode> res = new ArrayList<>();
if (preStart > preEnd || inStart > inEnd) {
res.add(null);
return res;
}
int rootVal = preOrder.get(preStart);
ArrayList<Integer> indexs = new ArrayList<>();
for (int i = inStart; i <= inEnd; i++) {
if (inOrder.get(i) == rootVal) {
indexs.add(i);
}
}
for (Integer index : indexs) {
ArrayList<TreeNode> lefts = buildTree(preOrder, preStart + 1, preStart + index - inStart,
inOrder, inStart, index - 1);
ArrayList<TreeNode> rights = buildTree(preOrder, preStart + index - inStart + 1, preEnd,
inOrder, index + 1, inEnd);
// 我在想如果left中没有一个节点,但是right中有很多,那么right中的节点不是放不进去了吗??
// 所以此处会不会有问题呢???
// 揭开疑惑了,注意null进去的话也会被当成一个元素的,如果只是想下面一个赋值给别人,是没关系的。若遍历拿出来用,就会报错:NullPointerException
for (TreeNode left : lefts) {
for (TreeNode right : rights) {
TreeNode root = new TreeNode(rootVal);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
// vx公众号关注TechGuide 实时题库 闪电速递
}
}
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
// 我的答案,
// 注意null放入list可算作元素
// 下面的其实不需要深拷贝
import java.util.*;

public class Main2 {
private static class TreeNode implements Cloneable {
int val;
TreeNode left;
TreeNode right;

TreeNode(int val) {
this.val = val;
}

@Override
public TreeNode clone() {

TreeNode node = null;

try {
node = (TreeNode) super.clone();
if (this.left != null) {
node.left = this.left.clone();
}
if (this.right != null) {
node.right = this.right.clone();
}

} catch (CloneNotSupportedException e) {
e.printStackTrace();
}

return node;
}
}

public static TreeNode copy(TreeNode node) {
TreeNode cpNode = new TreeNode(node.val);

if (node.left != null) {
cpNode.left = copy(node.left);
}
if (node.right != null) {
cpNode.right = copy(node.right);
}

return cpNode;
}


public static void main(String[] args) {
List<Integer> preOrder = new ArrayList<>();
List<Integer> inOrder = new ArrayList<>();
preOrder.add(1);
preOrder.add(1);
preOrder.add(2);
inOrder.add(1);
inOrder.add(2);
inOrder.add(1);
int n = inOrder.size();
List<TreeNode> ans = dfs(preOrder, inOrder, 0, n-1, 0, n-1);

for (TreeNode an : ans) {
cengxuBianli(an);
}
}

static TreeNode emptyNode = new TreeNode(-1);
// public static void cengxuBianli(TreeNode root) {
// // 层序遍历输出
// Deque<TreeNode> queue = new ArrayDeque<>();
// queue.add(root);
//
// while (!queue.isEmpty()) {
// boolean flag = true;
//
// int n = queue.size();
// for (int i = 0; i <n; i++) {
// TreeNode node = queue.pollFirst();
// System.out.print(node == emptyNode ? "#" : node.val);
//
// if (node.left == null || node == emptyNode) {
// queue.offerLast(emptyNode);
// } else {
// flag = false;
// queue.offerLast(node.left);
// }
// if (node.right == null || node == emptyNode) {
// queue.offerLast(emptyNode);
// } else {
// flag = false;
// queue.offerLast(node.right);
// }
// }
// if (flag) {
// break;
// }
// }
// System.out.println();
// }

public static void cengxuBianli(TreeNode root) {
// 层序遍历输出
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);

while (!queue.isEmpty()) {
int n = queue.size();
for (int i = 0; i <n; i++) {
TreeNode node = queue.pollFirst();
System.out.print(node == emptyNode ? "#" : node.val);

if (node.left == null && node.right == null) {
continue;
}

if (node.left == null) {
queue.offerLast(emptyNode);
} else {
queue.offerLast(node.left);
}
if (node.right == null) {
queue.offerLast(emptyNode);
} else {
queue.offerLast(node.right);
}
}
}
System.out.println();
}

public static List<TreeNode> dfs(List<Integer> preOrder, List<Integer> inOrder, int pre_l, int pre_r, int in_l, int in_r) {
if (pre_l > pre_r && in_l > in_r) {
List<TreeNode> ans = new ArrayList<>();
ans.add(emptyNode);
return ans;
}

List<TreeNode> ans = new ArrayList<>();
// 找出先序遍历的根节点,由于这个找到了也是不停止的,所以算是找了所有的区间
for (int i = in_l; i <= in_r; i++) {
if (inOrder.get(i).equals(preOrder.get(pre_l))) {
// 可以先取出num的数值
int num = i - in_l;
List<TreeNode> node1 = dfs(preOrder, inOrder, pre_l + 1, pre_l + num, in_l, i - 1);
List<TreeNode> node2 = dfs(preOrder, inOrder, pre_l + num + 1, pre_r, i + 1, in_r);

for (int x = 0; x < node1.size(); x++) {
for (int y = 0; y < node2.size(); y++) {
TreeNode pnew = new TreeNode(preOrder.get(pre_l));

// // 注意此处的拷贝需需要神拷贝,自己写了一个copy函数
// pnew.left = node1.get(x) == emptyNode ? null : copy(node1.get(x));
// pnew.right = node2.get(y) == emptyNode ? null : copy(node2.get(y));;
// // 好吧,其实不用深拷贝也是对的,因为下面的节点的左右子树是不会再改变了的。
pnew.left = node1.get(x) == emptyNode ? null : node1.get(x);
pnew.right = node2.get(y) == emptyNode ? null : node2.get(y);;
// pnew.left = node1.get(x) == emptyNode ? null : node1.get(x).clone();
// pnew.right = node2.get(y) == emptyNode ? null : node2.get(y).clone();;
ans.add(pnew);
}
}
}
}

return ans;
}
}

二叉树权值

aa370b20dcdfa8614808a4765ba383ea
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
// 注意,这里面权值计算的时候用long,所有权值计算完,在取模,而不是每次dfs下面取,因为2x+1根直接取模是不一样的。

public int getTreeSum(TreeNode tree) {
// write code here
return (int) (traverse(tree) % ((Math.pow(10, 9) + 7)));
}

long traverse(TreeNode root) {
if (root == null) return 0;
long leftVal = traverse(root.left);
long rightVal = traverse(root.right);
return 1 + Math.max(leftVal, rightVal) * 2;
}

}

class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;
}
}
// vx公众号关注TechGuide 实时题库 闪电速递

0914小米

92. 反转链表 II

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
89
import java.util.*;

/**
* 7 1 2 3 4 5 6 7
* 3
* 6
*/

public class Main1XiaoMi {
static class ListNode<T> {
public T data;
public ListNode next;
}

static class Solution {

/* Write Code Here */
public ListNode<Integer> reverseBetween(ListNode<Integer> head, int left, int right) {
ListNode ans = head;
if (left == right) { return head; }

ListNode preLeftNode = null, preRight = null, cur = ans;

for (int i = 0; i < left - 2; i++) {
cur = cur.next;
}

preLeftNode = left == 1 ? null : cur;

cur = left == 1 ? cur : cur.next;

ListNode leftNode = cur;
ListNode tempNext = cur.next;

for (int i = left; i < right; i++) {
ListNode temp = tempNext.next;
tempNext.next = cur;
cur = tempNext;
tempNext = temp;
}

if (preLeftNode == null) { ans = cur; }
else { preLeftNode.next = cur; }
leftNode.next = tempNext;

return head;
}
}

public static void main(String[] args){
Scanner in = new Scanner(System.in);
ListNode<Integer> res = null;

int head_size = 0;
head_size = in.nextInt();
ListNode<Integer> head = null, head_curr = null;
for(int head_i = 0; head_i < head_size; head_i++) {
int head_item = in.nextInt();
ListNode<Integer> head_temp = new ListNode<Integer>();
head_temp.data = head_item;
head_temp.next = null;

if (head == null) {
head = head_curr = head_temp;
} else {
head_curr.next = head_temp;
head_curr = head_temp;
}
}
in.nextLine();
// if(in.hasNextLine()) {
// in.nextLine();
// }

int left;
left = Integer.parseInt(in.nextLine().trim());

int right;
right = Integer.parseInt(in.nextLine().trim());

res = new Solution().reverseBetween(head, left, right);

while (res != null) {
System.out.print(String.valueOf(res.data) + " ");
res = res.next;
}
System.out.println();
}
}

二叉搜索树与双向链表

题解 | #二叉搜索树与双向链表#

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
* 10 6 14 4 8 12 16
* w
*/

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Main10 {
private static class Node {
public int data;
public Node left;
public Node right;

public Node(int data) {
this.data = data;
}

public Node() {
}

public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}

private static class Solution {
/* Write Code Here */
Node start = null, pre = null;
public Node Convert(Node pRootOfTree) {
dfs(pRootOfTree);

return start;
}

public void dfs(Node node) {
if (node == null) {
return;
}

dfs(node.left);
if (pre == null) {
start = node;
}else {
pre.right = node;
}
node.left = pre;
pre = node;

dfs(node.right);
}
}

public static void main(String[] args){
Scanner in = new Scanner(System.in);
Node res = null;
List<Node> list = new ArrayList<>();

// while (in.hasNext()) {
while (in.hasNextInt()) {
int item = in.nextInt();
if (item == -1) {
list.add(null);
} else {
list.add(new Node(item));
}
}
int len = list.size();
int i = 0;
while (i <= (len - 2) / 2) {
if (2 * i + 1 < len && list.get(i) != null) {
list.get(i).left = list.get(2 * i + 1);
}
if (2 * i + 2 < len && list.get(i) != null) {
list.get(i).right = list.get(2 * i + 2);
}
i++;
}


res = new Solution().Convert(list.get(0));


if (res != null) {
while (res.right != null && res.data != -1) {
System.out.print(String.valueOf(res.data) + " ");
res = res.right;
}
System.out.print(res.data + " ");
while (res.left != null && res.data != -1) {
System.out.print(String.valueOf(res.data) + " ");
res = res.left;
}
System.out.print(res.data);
}
System.out.println();
}
}

0915奇安信

夏季优惠

蚂蚁走网格,吃食物

0915荣耀

输出环的问题

11141663236248_.pic 11151663236248_.pic 11161663236249_.pic

0918雷火

走迷宫啊

12101663498910_.pic

12111663498916_.pic

12121663498920_.pic

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/**
100 5
2 2
1 1 3 200
2 1 3 200
1 2 1 100 5 100
2 2 1 100 5 200
100 100

500


100 5
2 2
1 1 2 200
2 1 2 200
1 2 1 100 5 100
2 2 1 100 5 200
100 100

500
*/

// 注意,只是能过样例
// 而且注意,只能过5*5的,6*6的太大了还是,代码有问题??
import java.util.*;

public class Main4 {
// C是进入下一张地图给的额外的金币,D是恢复血量需要的金币
static int A, B, C, D;
static int grid = 5;
static int maxCeng = 10;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
A = scanner.nextInt();
B = scanner.nextInt();
int n = scanner.nextInt();
int m = scanner.nextInt();

// 因为有多张图,所以三层,最后一层是血量攻击力和金币
// 注意层数是从1开始的
// 注意坐标也是从[1, 1]开始的
int[][][][] g = new int[maxCeng + 1][grid + 1][grid + 1][3];
for (int i = 0; i < n; i++) {
g[scanner.nextInt()][scanner.nextInt()][scanner.nextInt()][2] = scanner.nextInt();
}
for (int i = 0; i < m; i++) {
int row = scanner.nextInt(), x = scanner.nextInt(), y = scanner.nextInt();
g[row][x][y][0] = scanner.nextInt();
g[row][x][y][1] = scanner.nextInt();
g[row][x][y][2] = scanner.nextInt();
}

C = scanner.nextInt();
D = scanner.nextInt();

for (int r = 1; r <= grid; r++) {
for (int c = 1; c <= grid; c++) {
boolean[][][] booleans = new boolean[maxCeng + 2][grid+1][grid+1];
booleans[1][r][c] = true;
int[] counts = new int[maxCeng + 2];
// 由于第一个被置为true,所以此处的要变为1
Arrays.fill(counts, 1);
path.add(new int[]{1, r, c});
// 注意,初始化的时候在第一层,当前点需要true,当前点需要计数成功,但是当前点的操作放到下一个dfs中去
dfs(g, new int[]{r, c}, A, 0, booleans, counts, 1);

path.remove(path.size() - 1);
}
}

System.out.println(ans);
}

static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static boolean chance = true;
static int ans = 0;
static int index = 0;
// 感觉其实深度回溯的东西,其实一个全局变量就行
// 所以如果说其实这里面的visitedCount和visited不加层数信息也可以,但是不加的话,我需要手动判断切换到这一层和上一层之间,所以还是加了比较好。
static List<int[]> path = new ArrayList<>();
public static void dfs(int[][][][] g, int[] cur, int remainA, int totalCoin, boolean[][][] visited,
int[] visitedCount, int ceng) {
// 回退条件
if (ceng > maxCeng) {
return;
}

// 这个节点的操作需要在这一层完成
int x = cur[0], y = cur[1];
int monA = g[ceng][x][y][0];
int monB = g[ceng][x][y][1];
int coin = g[ceng][x][y][2];

// 当前点的visited,count等状态已经在上一层添加了,但是操作需要在这一层
int status = 0;
// 无攻击力表示没有怪物,可以直接拿coin
int num = B == 0 ? 0 : (int)Math.ceil(monA * 1.0 / B);
// 能攻击成功
if (remainA > monB * num) {
status = 1;
} else if (chance && totalCoin >= D && remainA + A / 2 > monB * num) {
chance = false;
status = 2;
}

if (status == 0) {
return;
}

// 信息debug
// for (int[] ints : path) {
// System.out.print("[" + ints[0] + "," + ints[1] + "," + ints[2] + "] ");
// }
// System.out.println("{" + remainA + "," + (totalCoin + coin - (status == 2 ? D : 0)) + "} ");

ans = Math.max(ans, totalCoin + coin - (status == 2 ? D : 0));

// 判断条件,如果满足,可以去下一张地图
// 注意这个不能放在下面的for循环里面,因为
// 若当前层为36,那么这个访问完就全部访问完了grid * grid点都被访问后,其实下面的for里面的if都是不满足的,所以根本进不去
if (visitedCount[ceng] == grid * grid) {
ceng += 1;

for (int r = 1; r <= grid; r++) {
for (int c = 1; c <= grid; c++) {
path.add(new int[]{ceng, r, c});
visited[ceng][r][c] = true;
dfs(g, new int[]{r, c}, remainA - monB * num + (status == 2 ? A / 2 : 0), totalCoin + coin - (status == 2 ? D : 0) + C, visited, visitedCount, ceng);
path.remove(path.size() - 1);
}
}

ceng -= 1;
}

// 进入到本层的下一个点
for (int i = 0; i < 4; i++) {
int newX = dir[i][0] + x, newY = dir[i][1] + y;
if (newX >= 1 && newX <= grid && newY >= 1 && newY <= grid && !visited[ceng][newX][newY]) {
visited[ceng][newX][newY] = true;
visitedCount[ceng] += 1;
path.add(new int[]{ceng, newX, newY});

dfs(g, new int[]{newX, newY}, remainA - monB * num + (status == 2 ? A / 2 : 0), totalCoin + coin - (status == 2 ? D : 0), visited, visitedCount, ceng);

visitedCount[ceng] -= 1;
visited[ceng][newX][newY] = false;
path.remove(path.size()-1);
}
}

if (status == 2) {
chance = true;
}
}
}

随便放的几个

15. 三数之和

美团,合法的三元组

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
import java.util.*;

/**
* 合法三元组
* 判断,是否满足nums,i<j<k 并且 nums[i] = 3 * nums[j] - nums[k];
*/
public class ValidThreeTuple {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int n = Integer.parseInt(scanner.nextLine()); // 如果此处直接nextInt的话,需要后面再nextLint读取换行符
int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

Map<Integer, Integer> map = new HashMap<>();
map.put(nums[0], 1);

long ans = 0L; // 注意此处需要long

for (int j = 1; j < n; j++) {
for (int k = j+1; k < n; k++) {
int sum = 3 * nums[j] - nums[k];
ans += map.getOrDefault(sum, 0);
}

// j弄完,把j放入map,当作i使用
map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
}

System.out.println(ans);
}
}

890. 查找和替换模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 这个方法挺不错的,使用
class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> visited = new HashSet<Integer>();
Set<Integer> res = new HashSet<Integer>();
for (int num : nums) {
if (visited.contains(num - k)) {
res.add(num - k);
}
if (visited.contains(num + k)) {
res.add(num);
}
visited.add(num);
}
return res.size();
}
}

532. 数组中的 k-diff 数对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 方法一,用map存储nums-k和nums+k
class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> visited = new HashSet<Integer>();
Set<Integer> res = new HashSet<Integer>();
for (int num : nums) {
if (visited.contains(num - k)) {
res.add(num - k);
}
if (visited.contains(num + k)) {
res.add(num);
}
visited.add(num);
}
return res.size();
}
}

// 方法二:使用排序+双指针,两个指针是从left=0和right=left+1开始的

954. 二倍数对数组

特别注意treemap的ans比较中的问题,-1和1是等于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
class Solution {
public boolean canReorderDoubled(int[] arr) {
// Map<Integer, Integer> map = new TreeMap<>((a, b) -> Math.abs(a) - Math.abs(b));
// 特别注意,上面这个判断,Math.abs会影响treemap对key的判断的
// 因为本来-1和1,绝对值相减=0,会误认为是同一个元素值???
Map<Integer, Integer> map = new TreeMap<>((a,b)->Math.abs(a)==Math.abs(b) ? a-b : Math.abs(a)-Math.abs(b));

for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}

// 0只有跟自己对应
if (map.getOrDefault(0, 0) % 2 != 0) { return false; }
map.remove(0);

for (Integer key : map.keySet()) {
int value = map.getOrDefault(key, 0);
int value2 = map.getOrDefault(key * 2, 0);

if (value2 < value) { return false; }

// 此处map不能在添加新的元素,否则在for循环会有问题的
if (value2 != 0) {
map.put(key * 2, value2 - value);
}
}

return true;
}
}

Author: Jcwang

Permalink: http://example.com/2022/10/13/%E6%88%91%E7%9A%84%E9%83%A8%E5%88%86%E7%A7%8B%E6%8B%9B%E7%AC%94%E8%AF%95/