小狗的 Map 设计
题目描述
现需要设计一个Map<key,val>，满足以下条件
Map 的容量是一个固定值 N，最多保存 N 个记录
当执行插入操作时， 首先查询该 key 是否存在：
- 如果存在：若 val > old_val 时，才更新 val
- 如果不存在：当 size < N 时候，保存该值，当 size == N 时，淘汰最早的记录，并加入新的 key 和 val
说明：当一条记录在时间 T被更新，那么该记录的更新时间变为 T。
输入
第一行包含该 Map 的最大容量 N
之后每一行包含一个 key 和一个 val ( key.length < 16, val 为 unsigned int)
输出
输出被淘汰的记录
样例输入
2
10_123_50_A0 1566918054
10_123_50_A1 1566918054
10_123_50_A1 1566918055
10_123_50_A3 1566918055
10_123_50_A4 1566918056
样例输入
10_123_50_A0 1566918054
10_123_50_A1 1566918055
思路
Map 正常申请就行，使用队列记下记录插入的顺序即可
编码
import java.util.Map;
import java.util.Queue;
import java.util.HashMap;
import java.util.Scanner;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
Map<String, Long> map = new HashMap<>();
Queue<String> queue = new LinkedList<>(); // 记录 Map记录插入的顺序
while(true) {
String key = scn.next();
long val = scn.nextLong();
if(map.containsKey(key)) {
if(map.get(key) < val) {
map.put(key, val);
queue.remove(key);
queue.add(key);
}
} else if(map.size() < n) {
map.put(key, val);
queue.add(key);
} else {
String firstKey = queue.poll();
System.out.println(firstKey + " " + map.get(firstKey));
map.remove(firstKey);
map.put(key, val);
queue.add(key);
}
}
}
}
小狗的服务器分发
题目描述
我们共有 n 台服务器，每个服务器可以向若干个子服务器传输数据，n 台服务器组成一个树状结构。
现在要将一份数据从 root 节点开始分发给所有服务器。
一次数据传输需要一个小时时间，一个节点可以同时对 k 个儿子节点进行传输
不同节点可以并行分发，问，全部分发完成，最短需要多少小时？
说明：服务器只有一个根节点并且编号为 0，服务器个数 <= 1e6，编号取值范围[0, 1e6)
【示例】
0
／＼
1 2
／＼
3 4
当 k = 1 时候，最优传输过程如下：
第一个小时：0 --> 1
第二个小时：1 --> 4 && 0 --> 2
第三个小时：1 --> 4
所以当 k = 1 时，全部分发完成最短需要 3 个小时
当 k = 2 时，最优传输过程如下：
第一个小时：0 --> 1 && 0 --> 2
第二个小时：1 --> 3 && 1 --> 4
所以当 k = 2时，全部分发完成最短需要 2 个小时
输入
第一行输入单次并发的最大节点个数 k，以及剩余输入的行数 n
接下来的 n 行，每一行第一个数表示后面的节点个数，第二个数为父节点编号，后面皆为子节点编号
输出
输出全部服务器分发完成，需要的最短时间
样例输入
1 2
3 0 1 2
2 1 3
样例输出
2
思路
题目未说明为二叉树，暂时未想到什么比较好的解法
于是模拟了一遍题目的给定操作。
大概思路时，自定义含有编号并且带儿子列表的类（儿子列表按照其儿子数量降序排列）
把儿子数量当作权值的原因：按照贪心思想，儿子越多，就可以在其后代传递时，其他儿子也可以传递以节省时间
然后定义一个 Queue，跑一遍即为传输一遍数据（List也可以）
定义 count 计数器，得到答案即可
注：因为可能在遍历 Queue 时候有涉及插入和删除，遍历可能会出问题
定义 tmpList 记录下队列现有元素，然后遍历 tmpList 同时又可以更新 Queue
另外下附假如只是二叉树的做法，当然按照题意应该是不太可能的。。。
编码
import java.util.*;
public class Main {
private static final TreeNode root = new TreeNode(0); // 定义好一定有的根服务器
private static class TreeNode implements Comparable<TreeNode> {
int val, weight, tag;
// val：服务器编号，weight：儿子数量，tag：用于标记遍历到哪个儿子
List<TreeNode> child;
TreeNode(int val) {
this.val = val;
weight = 1;
tag = 0;
child = null;
}
@Override
public int compareTo(TreeNode treeNode) { // 按儿子数量降序
return treeNode.weight - this.weight;
}
}
private static int insert(TreeNode treeNode, int parent, List<TreeNode> child) {
if(treeNode == null) return 0;
if(treeNode.val == parent) {
treeNode.child = child;
treeNode.weight += child.size();
return child.size();
}
int sum = 0;
if(treeNode.child != null) {
for(TreeNode nextNode : treeNode.child) {
int weight = insert(nextNode, parent, child);
sum += weight;
if(weight != 0) break;
}
}
treeNode.weight += sum;
return sum;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int k = scn.nextInt(), n = scn.nextInt();
for(int i = 0; i < n; ++i) {
int m = scn.nextInt(), parent = scn.nextInt();
List<TreeNode> child = new ArrayList<>();
for(int j = 1; j < m; ++j) {
child.add(new TreeNode(scn.nextInt()));
}
insert(root, parent, child);
}
Queue<TreeNode> queue = new LinkedList<>();
List<TreeNode> list = new LinkedList<>();
queue.add(root);
Collections.sort(root.child);
int count = 0;
while(!queue.isEmpty()) {
++count;
list.addAll(queue);
for(TreeNode treeNode : list) {
Collections.sort(treeNode.child);
for(int i = 0; i < k; ++i) {
if(treeNode.tag < treeNode.child.size()) {
TreeNode child = treeNode.child.get(treeNode.tag++);
if(child.child != null)
queue.add(treeNode);
}
if(treeNode.tag == treeNode.child.size()) {
queue.remove(treeNode);
break;
}
}
}
list.clear();
}
System.out.println(count);
}
}
假如只是二叉树的做法
import java.util.Scanner;
public class Main {
private static int maxDepth = 0, maxNode = 0;
public static final int maxLen = 1000001;
private static int[] tree = new int[maxLen];
private static void insert(int root, int parent, int leftChild, int rightChild, int depth) {
if(root != 1 && tree[root] == 0) return;
int leftNode = root<<1, rightNode = leftNode | 1;
if(root == parent) {
maxDepth = Math.max(depth+1, maxDepth);
maxNode = Math.max(leftChild, maxNode);
tree[leftNode] = leftChild;
tree[rightNode] = rightChild;
return;
}
insert(leftNode, parent, leftChild, rightChild, depth+1);
insert(rightNode, parent, leftChild, rightChild, depth+1);
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int k = scn.nextInt(), n = scn.nextInt();
for(int i = 0; i < n; ++i) {
int m = scn.nextInt(), parent = scn.nextInt(), leftChild = scn.nextInt(), rightChild;
rightChild = m == 3 ? scn.nextInt() : 0;
insert(1, parent, leftChild, rightChild, 1);
}
int ans = k == 1 && tree[maxNode|1] != 0 ? maxDepth+1 : maxDepth;
System.out.println(ans);
}
}
小狗的核子聚变
题目描述
请设计一个程序，在规定步数内，成功的使得一个原子核队列完全湮灭。
共 7 种原子核，排成一条直线队列，初始状态是稳定的。
只有 2 种情况会发生湮灭：
- 当插入一个原子核时，插入位置形成 3 个或以上的相同原子核，则其湮灭
- 发生湮灭后，两边碰撞产生连锁反应又形成 3 个以上的相同原子核，则其湮灭
注：只有相同的原子核插入，或碰撞才会湮灭，例如以下情况不会
ABBCCC (插入B 1) -> ACCC (进入稳定)
为了方面描述插入位置，假定队列长度为 n，编号从 0 到 n-1，共 n+1 个位置。
要求选手给出一个消去过程，将其所有原子核都湮灭，只需要不超过规定步数完成即可，不要求最优解
输入
第一行是一行字母，表示原子核初始序列
第二行是规定步数 m (m <= 100)
输出
若干行，每行包含一个字母和一个数字，表示将该字母插入某位置
样例输入
AAABBAAACCABDCAABC
样例输出
C 8
C 3
C 3
D 5
B 0
B 0
C 0
C 0
说明：合法输出不唯一，也不要去最优解，规定步数内即可。
思路
// TODO
编码