恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
现有一个硬件加速器资源，可以通过100000个通道对其下发任务。要求设计一种通道资源管理方案，满足：
某个用户需输入-1时。此时资源管理方案分配未使用的最小通道号给用户 当某个用户输入有效的通道号时，此时资源管理方案回收对应通道，允许之后重新分配。
计算经过一段时间后，下次用户申请时，所申请到的通道号，如无未使用的通道，输出-1。
输入以数组的方式传入历史申请释放情况，分为两行
第一行为数组大小，用例保证输入的数组大小为有效输入次数，小于等于500000次
第二行为数组元素，每个元素以“空格”区分每次申请释放操作，用例保证输入的通道号均为有效通道号[0,99999]。
下一次申请操作将会申请到的通道号
8
-1 -1 -1 2 -1 0 -1 -1
4
用deque模拟通道资源队列，对于输入-1，直接弹出队列头部元素；有效通道号的话就通过二分插入维护有序队列。最终结果就是 输出下一次申请操作将会申请到的通道号，就可啦。
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] ops = new int[n];
for (int i = 0; i < n; i++) {
ops[i] = scanner.nextInt();
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < 100000; i++) {
q.offer(i);
}
for (int op : ops) {
if (op == -1) {
q.poll();
} else {
q.add(op);
q = new ArrayDeque<>(q.subList(0, q.size()));
}
}
if (!q.isEmpty()) {
System.out.println(q.peek());
} else {
System.out.println(-1);
}
}
}
// vx公众号关注TechGuide，代码可能需要少量调试。
#include <iostream>
#include <deque>
#include <algorithm>
int main() {
int n;
std::cin >> n;
std::deque<int> q;
for (int i = 0; i < 100000; i++) {
q.push_back(i);
}
for (int i = 0; i < n; i++) {
int op;
std::cin >> op;
if (op == -1) {
q.pop_front();
} else {
q.push_back(op);
std::sort(q.begin(), q.end());
}
}
if (!q.empty()) {
std::cout << q.front() << std::endl;
} else {
std::cout << -1 << std::endl;
}
return 0;
}
// vx公众号关注TechGuide，代码可能需要少量调试。
某通信设备经过长时间运行产生了大量文件目录与文件名称不同的日志文件，维护人员使用设备命令生成了一种特定格式的文件路径列表。
请编写程序帮助维护人员根据匹配规则从该文件路径列表中快速查找符合要求的日志文件或目录路径。
输入数据第一行为文件匹配规则字符串，包含大小写英文字符、“/“、"”，其中“/“为文件路径中的目录分割符，"“标识匹配任意名称的文件名或者目录名，1<=长度<=2048;
输入数据从第二行开始为文件列表，包含大小写英文字符、空格， 英文字符表示文件名或目录名，英文字符串前的四个空格缩进标识文件目录结构，1<=每行长度<=1024，总计不超过30000行;
输出格式: 符合匹配规则的文件完整路径，文件路径中使用”/“分割目录。
如果存在多个结果，请使用多行输出，输出的顺序与输入的顺序相同。
如果不存在匹配的结果，则输出: NOT FOUND
/path1/file1
file0
path1
file1
/path1/file1
输入的第一行为文件匹配规则，匹配完整路径为“/path1/file1”的文件。
输入的第二行及后续行为文件列表，其中每行开头的四个空格为目录缩进
转换成完整的文件路径列表如下所示
/fileo
/path1
/path1/file1
根据题意，输出匹配结果为”/path1/file1”
简单模拟。遍历文件列表，匹配规则来筛选出符合条件的文件路径。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String source = scanner.nextLine();
List<String> fileList = new ArrayList<>();
while (scanner.hasNext()) {
fileList.add(scanner.nextLine());
}
String[] sources = source.substring(1).split("/");
int pre = -1;
List<String> currentPath = new ArrayList<>();
for (String file : fileList) {
int cnt = file.trim().split(" ").length - 1;
if (cnt <= pre && !currentPath.isEmpty()) {
System.out.println("/" + String.join("/", currentPath));
currentPath = new ArrayList<>(currentPath.subList(0, cnt));
currentPath.add(file.trim());
} else {
if (cnt < sources.length && (sources[cnt].equals(file.trim()) || sources[cnt].equals("*"))) {
currentPath.add(file.trim());
}
}
pre = cnt;
}
System.out.println("/" + String.join("/", currentPath));
}
}
// vx公众号关注TechGuide，代码可能需要少量调试。
#include <iostream>
#include <vector>
#include <sstream>
int main() {
std::string source;
std::getline(std::cin, source);
std::vector<std::string> fileList;
std::string line;
while (std::getline(std::cin, line)) {
fileList.push_back(line);
}
std::vector<std::string> sources;
std::istringstream sourceStream(source.substr(1));
std::string sourcePart;
while (std::getline(sourceStream, sourcePart, '/')) {
sources.push_back(sourcePart);
}
int pre = -1;
std::vector<std::string> currentPath;
for (const std::string& file : fileList) {
int cnt = file.find_first_not_of(' ') / 4;
if (cnt <= pre && !currentPath.empty()) {
std::cout << "/" << currentPath[0];
for (int i = 1; i < cnt; ++i) {
std::cout << "/" << currentPath[i];
}
std::cout << std::endl;
currentPath.resize(cnt);
currentPath.push_back(file);
} else {
if (cnt < sources.size() && (sources[cnt] == file || sources[cnt] == "*")) {
currentPath.push_back(file);
}
}
pre = cnt;
}
std::cout << "/" << currentPath[0];
for (int i = 1; i < currentPath.size(); ++i) {
std::cout << "/" << currentPath[i];
}
std::cout << std::endl;
return 0;
}
// vx公众号关注TechGuide，代码可能需要少量调试。
二叉查找树，是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉查找树。
给定一个数n，表示值由1到n的节点构造成二叉查找树，问对应能构造的高度小于等于k的不同二叉查找树的个数，根节点的高度为1。0< n < 36，0< k< 36.
树的节点个数n，树的高度k，用空格分割。
不同二叉查找树的个数。
3 2
1
递归即可，实现不难，需要理解思想。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
Map<String, Integer> cache = new HashMap<>();
System.out.println(dfs(1, n, k, cache));
}
private static int dfs(int l, int r, int lvl, Map<String, Integer> cache) {
if (l > r) return 1;
if (lvl == 1) {
if (l == r) return 1;
return 0;
}
if (l == r) return 1;
String key = l + "_" + r + "_" + lvl;
if (cache.containsKey(key)) {
return cache.get(key);
}
int ans = 0;
for (int root = l; root <= r; root++) {
ans += dfs(l, root - 1, lvl - 1, cache) * dfs(root + 1, r, lvl - 1, cache);
}
cache.put(key, ans);
return ans;
}
}
// vx公众号关注TechGuide，代码可能需要少量调试。
#include <iostream>
#include <unordered_map>
std::unordered_map<std::string, int> cache;
int dfs(int l, int r, int lvl) {
if (l > r) return 1;
if (lvl == 1) {
if (l == r) return 1;
return 0;
}
if (l == r) return 1;
std::string key = std::to_string(l) + "_" + std::to_string(r) + "_" + std::to_string(lvl);
if (cache.find(key) != cache.end()) {
return cache[key];
}
int ans = 0;
for (int root = l; root <= r; root++) {
ans += dfs(l, root - 1, lvl - 1) * dfs(root + 1, r, lvl - 1);
}
cache[key] = ans;
return ans;
}
int main() {
int n, k;
std::cin >> n >> k;
std::cout << dfs(1, n, k) << std::endl;
return 0;
}
// vx公众号关注TechGuide，代码可能需要少量调试。