Algorithm5

高频、未归纳

LRU缓存 最近最久未使用

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
class LRUCache {
// 打算使用双端链表和哈希表实现
// 双端链表尾部放最新的,头部就是最旧的
// 哈希表存的键存放key,值存放类

// 双端的
class LRULinkedNode {
int key;
int val;
LRULinkedNode pre;
LRULinkedNode next;

public LRULinkedNode() {}
public LRULinkedNode(int key, int val) {
this.key = key;
this.val = val;
}
}
LRULinkedNode head, tail;
int capacity;
Map<Integer, LRULinkedNode> map = new HashMap<>();

public LRUCache(int capacity) {
this.capacity = capacity;

head = new LRULinkedNode();
tail = new LRULinkedNode();

head.next = tail;
tail.pre = head;
}

public int get(int key) {
if (map.containsKey(key)) {
LRULinkedNode node = map.get(key);
moveToTail(node);
return node.val;
}

return -1;
}

public void put(int key, int value) {
if (map.containsKey(key)) { // 若已经存在,那么更改值,然后放到最后,使其最新
LRULinkedNode node = map.get(key);
node.val = value;
moveToTail(node);
} else {
LRULinkedNode newNode = new LRULinkedNode(key, value);
map.put(key, newNode);
addToTail(newNode);
}

if (capacity < map.size()) { // 需要去除最头部的
removeHead();
}
}

// 删除最旧的
public void removeHead() {
LRULinkedNode del = head.next;

head.next = head.next.next;
head.next.pre = head;

map.remove(del.key);
}

// 尾部是最新的
public void addToTail(LRULinkedNode newNode) {
LRULinkedNode pre = tail.pre;
pre.next = newNode;
newNode.pre = pre;
tail.pre = newNode;
newNode.next = tail;
}

// 已经存在,移动到最新的
public void moveToTail(LRULinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;

addToTail(node);
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

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);
}
}

建树、建图之类

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);
}
}

一些代码有关的问题

关于排序的问题

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
①①Queue<Integer> queue = new PriorityQueue<>((aa, bb) -> aa - bb);
①②Queue<Integer> queue1 = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return 0;
}
});
②②TreeMap<Integer, Integer> treeMap = new TreeMap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return 0;
}
});
③①TreeSet<Integer> treeSet = new TreeSet<>((aa, bb) -> aa - bb);


// 注意,用这个的一定是封装类型的,所以比如int[]这个就很麻烦,要么数组封装成Integer[],要么自己写个排序算法呗,或者排好后
// 但是对int[][]排序的时候是可以的。
public class MyComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return 0;
}
}

// 注意此处只能用Integer[]的数组,所以要先吧int[]转成Integer[]
Integer[] aa = new Integer[];
Arrays.sort(aa,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return (int)(o2-o1);
}
});

// 此处由于不是封装类型,所以直接先升序排序然后翻转,其他的封装类型还有之后的int[][]就是可以直接在Arrays.sort中去写Comparator了。
int[] temp = queue.pollFirst();
Arrays.sort(temp);
for (int i = 0; i < temp.length / 2; i++) {
int tempTemp = temp[i];
temp[i] = temp[temp.length - i - 1];
temp[temp.length - i - 1] = tempTemp;
}

// List的数组就没什么问题了
List<Integer> list = new ArrayList<>();
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return 0;
}
});




// 注意,由于都是int,所以从小到大只要a - b,从大到小只要b - a,如果是小数呢
// 就是说,如果要小于,那么整数a - b,也就是a < b时返回复数;大于,整数b - a,也就是a < b时返回整正数即可,不过确实是需要比较器的,此时稍微省略的写法了
Queue<Double> queue = new PriorityQueue<>((a, b) -> {
if (a.equals(b)) { return 0;}
else if (b > a) { return 1;} // return正数代表
return -1;
});

关于TreeSet和TreeMap

java集合方法之TreeSet.floor()和TreeSet.ceiling()

floor(E e) 方法返回在这个集合中小于或者等于给定元素的最大元素,如果不存在这样的元素,返回null.
ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素,如果不存在这样的元素,返回null.

lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素,如果不存在这样的元素,则返回 null。

注意:

1 声明的时候要用TreeSet,而不能用Set

2 取结果的时候用包装类型取,因为如果返回null,那么拆箱失败会nullpointexception

1
2
TreeSet<Integer> set = new TreeSet<>();
set.ceiling(23);

TreeSet的first()和last()

TreeMap中的floorKey()和ceilingKey()

ceilingKey(K key), 返回大于或等于给定键的最小键,如果没有这样的键,则null

floorKey(K key), 返回小于或等于给定键的最大键,如果没有这样的键,则null

注意:

1 声明的时候需要使用TreeMap,而不能只是Map

2 取结果的时候用包装类型取,因为如果返回null,那么拆箱失败会nullpointexception

1
2
3
TreeMap<Integer, Integer> map = new TreeMap<>();
map.ceilingKey(213);
Map.Entry<Integer, Integer> integerIntegerEntry = map.ceilingEntry(123);

Java8中Stream为什么要boxed

java8 中的 Collectors 全解析

Set对数组的去重问题

1
2
3
4
5
6
7
8
9
10
11
// 注意,HashSet对于int[]数组是无法去重的,对于Integer[]估计可以??没验证
// 但是对List<Integer>的一定是可以的,所以需要将int[]首先转换成List<Integer>
// 两种方法
// 注意:下面的temp是int[],所以第一种和第二种都是转换,但是第一种的Arrays.asList里面需要接收的是Integer[],所以我此处是写开了,但是对于temp个数很多的,只能用下面的了,或者先for循环把temp一个个的放入integer[]中去
set.add(Arrays.asList(temp[0], temp[1], temp[2], temp[3], temp[4]));
set.add(Arrays.stream(temp).boxed().collect(Collectors.toList())); // 注意是Collectors,而不是Collections

// boxed内部就是.mapToObj(Integer::valueOf, 0);,将intStrem转换成Stream<Integer>,而后可以collect

// 而我这个mapToInt是转成IntStream,后面只能toArray,而不能collect,注意区别
Arrays.stream(temp).mapToInt(Integer::valueOf).toArray();

Deque<int[]>中存放两次temp的,深浅拷贝问题

java中集合存储的元素,是对象的引用。

int[]这个数组也是对象的,所以说前面的Comparator的时候对int[]是不能排序的,对int[][]可以排序的,因为Comparator的时候里面的每一个元素是iny[],那么也就是对象了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//(1)如果是基本数据类型,则是value
//(2) 如果是复合数据类型,则是引用的地址;String b="a"; lists.add(b); b="bbb";最后输出还是a,
// 原因是存放的不是b,而是b第一次指向的地址,修改b=”bbb”后只是修改了b指向的地址。这里因为直接更换了b指向的地址了。
// 比如里面存放temp数组,然后temp数组的第一个值改变了,那么集合里存放的也会改变。但是如何此时temp = new int[n],那么temp这个东西,与集合里面的那个再也没有关系了。

// 所以我一开始将int[]存放进去,然后改这个数组的时候不想影响到集合里面的那个元素,那么存放的时候就是需要放queue.offerLast(temp.clone());

Deque<List<Integer>> deque = new ArrayDeque<>();
List<Integer> list = new ArrayList<>();
list.add(2);
deque.add(list);
list.set(0, 123);
System.out.println(deque.peekFirst().get(0));
// 无可厚非,这里面输出的是123还是改变的

// 这里重新new ArrayList(list)就可以了。 注意与int[]的区别,一个是clone,另外一个是new一个新的。
Deque<List<Integer>> deque = new ArrayDeque<>();
List<Integer> list = new ArrayList<>();
list.add(2);
deque.add(new ArrayList<>(list));
list.set(0, 123);
System.out.println(deque.peekFirst().get(0));

关于Scanner的next()和nextLine()的问题

  • next(),一定要读取到有效字符后才可以结束输入,对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符,next()方法会自动将其去掉,只有在输入有效字符之后,next()方法才将其后输入的空格键、Tab键或Enter键等视为分隔符或结束符。完整标记的前后是与分隔模式匹配的输入信息所以next()不能得到带空格的字符串。

  • nextLine(),遇到回车是才结束,所以可以得到带空格的字符串。

  • 在输入一个int类型的数字之后,如果后边采用nextLine的话,最后打印结果发现会少一个字符,原因是在你使用nextInt的时候后边有一个换行符,没有接受,前边的int变量只是接受了你输入的数值,所以在你继续输入nextLine之后,会自动读取还未读取的换行,所以会导致后边的结果有一列为空,所以此时你需要多输入一个NextLine把未接受的换行符接收到。

所以以后最好统一使用nextLine,但是如果前面nextInt读取了一个数字,那么需要先nextLine一下将换行符读取掉,然后在nextLine读取这一行字符串。

5
RBBRB

1
2
3
4
5
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();

sc.nextLine(); // 注意此处需要先读取换行符
String str = sc.nextLine();

但是如果要根据空格读取,那还是得用next()函数的

关于拷贝

1
2
3
4
5
6
7
8
9
char[] temp = Arrays.copyOfRange(chars, curIndex, i + 1);
Arrays.copyOf(chars, 2); // 表示chars中的0,1字符数组
curAns.add(new String(temp)); // cha[]转String,用String.value也可以

Arrays.fill(temp, '9');
Arrays.fill(temp, 0, 2, '9'); // temp中的0, 1变成'9'

String s = "132";
String substring = s.substring(0, 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
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
import java.util.*;
import java.util.stream.Collectors;

/**
* 注意,去重hash的写法
* Arrays降序排列的写法
* 存储int[的queue中放入int[]的话需要clone]
*/
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 < temp.length / 2; i++) {
int tempTemp = temp[i];
temp[i] = temp[temp.length - i - 1];
temp[temp.length - i - 1] = tempTemp;
}

// set.add(Arrays.asList(temp[0], temp[1], temp[2], temp[3], temp[4]));
set.add(Arrays.stream(temp).boxed().collect(Collectors.toList()));
}

System.out.print(a == set.size() ? "yes" : "no");
System.out.print(set.contains(Arrays.stream(scores).boxed().collect(Collectors.toList())) ? " yes" : " no");
}
}

Author: Jcwang

Permalink: http://example.com/2022/08/03/Algorithm5/