25 – 09 – 15 (补于 25 – 09 – 20)
初等数论其实是
今日份题面
给你一个整数数组
nums。请你对数组执行下述操作：
- 从
nums中找出 任意 两个 相邻 的 非互质 数。- 如果不存在这样的数，终止 这一过程。
- 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
- 只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于
108。
这题其实考察的就是一个公式，
$$\text{GCD}(x, y)\times\text{LCM}(x, y)=x\times y$$
所以实现起来就很简单了：
class Solution {
private int gcd(int m, int n) {
return (n == 0) ? m : gcd(n, m % n);
}
private int lcm(int m, int n) {
return m / gcd(m, n) * n; // 防溢出处理
}
public List<Integer> replaceNonCoprimes(int[] nums) {
Stack<Integer> stack = new Stack<>();
for (int num : nums) {
int current = num;
while (!stack.isEmpty()) {
int top = stack.peek();
int g = gcd(current, top);
if (g == 1) break; // 共质，不做处理
stack.pop(); // 否则移出当前元素进行处理
current = lcm(current, top); // 以最小公倍数回填
}
stack.push(current);
}
List<Integer> result = new ArrayList<>(stack);
return result;
}
}
以上
25 – 09 – 16 (补于 25 – 09 – 21)
异言盯帧，鉴定为这周LeetCode开的是设计模式
今日份题面：
设计一个数字容器系统，可以实现以下功能：
- 在系统中给定下标处 插入 或者 替换 一个数字。
- 返回 系统中给定数字的最小下标。
请你实现一个
NumberContainers类：
NumberContainers()初始化数字容器系统。void change(int index, int number)在下标index处填入number。如果该下标index处已经有数字了，那么用number替换该数字。int find(int number)返回给定数字number在系统中的最小下标。如果系统中没有number，那么返回-1。
考虑维护 num2loc 和 loc2num 两个映射表进行双选。不过需要注意，位置对数字唯一但数字对位置不唯一，所以 num2loc 可以开一个 TreeSet 作为 Value 同时满足多位置和最小两个行为。另外位置上数字更新时注意同时 Remove 掉num2loc 中 TreeSet 里的元素
给出个人实现如下：
class NumberContainers {
HashMap<Integer, TreeSet<Integer>> num2loc;
HashMap<Integer, Integer> loc2num;
public NumberContainers() {
this.num2loc = new HashMap<>();
this.loc2num = new HashMap<>();
}
public void change(int index, int number) {
if (!loc2num.containsKey(index)) {
// 新增键值对
loc2num.put(index, number);
// 同步更新 num2loc
if (!num2loc.containsKey(number)) {
TreeSet<Integer> curElementLocs = new TreeSet<>();
curElementLocs.add(index);
num2loc.put(number, curElementLocs);
} else {
TreeSet<Integer> curElementLocs = num2loc.get(number);
curElementLocs.add(index);
}
} else {
// 替换当前数字
int replacedNum = loc2num.get(index);
loc2num.put(index, number);
// 从旧数字的位置集合中移除当前index
TreeSet<Integer> oldLocs = num2loc.get(replacedNum);
oldLocs.remove(index);
if (oldLocs.isEmpty()) {
num2loc.remove(replacedNum);
}
// 添加到新数字的位置集合
if (!num2loc.containsKey(number)) {
TreeSet<Integer> newLocs = new TreeSet<>();
newLocs.add(index);
num2loc.put(number, newLocs);
} else {
TreeSet<Integer> newLocs = num2loc.get(number);
newLocs.add(index);
}
}
}
public int find(int number) {
return num2loc.containsKey(number) && !num2loc.get(number).isEmpty()
? num2loc.get(number).first()
: -1;
}
}
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers obj = new NumberContainers();
* obj.change(index,number);
* int param_2 = obj.find(number);
*/
我都不敢想纯 C 战士写这题得多得劲(
以上
25 – 09 – 17 (补于 25 – 09 – 23)
什么业务需求(
今日份题面
一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。
请你设计一个
TaskManager类：
TaskManager(vector<vector<int>>& tasks)初始化任务管理器，初始化的数组格式为[userId, taskId, priority]，表示给userId添加一个优先级为priority的任务taskId。void add(int userId, int taskId, int priority)表示给用户userId添加一个优先级为priority的任务taskId，输入 保证taskId不在系统中。void edit(int taskId, int newPriority)更新已经存在的任务taskId的优先级为newPriority。输入 保证taskId存在于系统中。void rmv(int taskId)从系统中删除任务taskId。输入 保证taskId存在于系统中。int execTop()执行所有用户的任务中优先级 最高 的任务，如果有多个任务优先级相同且都为 最高 ，执行taskId最大的一个任务。执行完任务后，taskId从系统中 删除 。同时请你返回这个任务所属的用户userId。如果不存在任何任务，返回 -1 。注意 ，一个用户可能被安排多个任务。
其实从 OO 的角度出发，这题比较严谨的做法是设计一个 Task 类对输入参数进行对象化然后操纵这个类进行相关任务
class Task implements Comparable<Task>{
public int userId;
public int taskId;
public int priority;
public Task(){
this.userId = -1;
this.taskId = -1;
this.priority = -1;
}
public Task(int userId, int taskId, int priority){
this.userId = userId;
this.taskId = taskId;
this.priority = priority;
}
@Override
public int compareTo(Task other){
return this.priority == other.priority ? other.taskId - this.taskId : other.priority - this.priority;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Task task = (Task) o;
return taskId == task.taskId;
}
@Override
public int hashCode() {
return Objects.hash(taskId);
}
}
然后你就发现空时双爆了(
所以还是老老实实用数组替代吧。注意到 TaskId 唯一，这就意味着我们可以使用 HashMap 储存相关任务并做到 $O(1)$ 查询以及删除，同时由于部分任务要求优先级，所以考虑开一个自定义顺序 Heap 对任务进行维护，数据结构有了实现起来就很简单了
class TaskManager {
private Map<Integer, int[]> taskInfo;
private PriorityQueue<int[]> heap;
public TaskManager(List<List<Integer>> tasks) {
taskInfo = new HashMap<>();
heap = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) {
return b[0] - a[0];
}
return b[1] - a[1];
});
for (List<Integer> task : tasks) {
int userId = task.get(0), taskId = task.get(1), priority = task.get(2);
taskInfo.put(taskId, new int[]{priority, userId});
heap.offer(new int[]{priority, taskId});
}
}
public void add(int userId, int taskId, int priority) {
taskInfo.put(taskId, new int[]{priority, userId});
heap.offer(new int[]{priority, taskId});
}
public void edit(int taskId, int newPriority) {
if (taskInfo.containsKey(taskId)) {
taskInfo.get(taskId)[0] = newPriority;
heap.offer(new int[]{newPriority, taskId});
}
}
public void rmv(int taskId) {
taskInfo.remove(taskId);
}
public int execTop() {
while (!heap.isEmpty()) {
int[] task = heap.poll();
int priority = task[0], taskId = task[1];
if (taskInfo.containsKey(taskId) && taskInfo.get(taskId)[0] == priority) {
int userId = taskInfo.get(taskId)[1];
taskInfo.remove(taskId);
return userId;
}
}
return -1;
}
}
注意到这块其实是用了一个 LazyTag 的小技巧，我们在 Remove 时只对 HashMap 进行移除操作，对 Heap 的操作是在涉及到 Heap 时临时对堆顶进行排查的。
虽然是另一种意义上的 Mem Leak，不过只要力大就能砖飞(´-ω-｀)
以上
25 – 09 – 18 (补于 25 – 09 – 24)
别拦着我，我觉得我能开发出 Excel！
今日份题面
电子表格是一个网格，它有 26 列（从
'A'到'Z'）和指定数量的rows。每个单元格可以存储一个 0 到 105 之间的整数值。请你实现一个
Spreadsheet类：
Spreadsheet(int rows)初始化一个具有 26 列（从'A'到'Z'）和指定行数的电子表格。所有单元格最初的值都为 0 。void setCell(String cell, int value)设置指定单元格的值。单元格引用以"AX"的格式提供（例如，"A1"，"B10"），其中字母表示列（从'A'到'Z'），数字表示从 1 开始的行号。void resetCell(String cell)重置指定单元格的值为 0 。int getValue(String formula)计算一个公式的值，格式为"=X+Y"，其中X和Y要么 是单元格引用，要么非负整数，返回计算的和。注意： 如果
getValue引用一个未通过setCell明确设置的单元格，则该单元格的值默认为 0 。
题目的思路是很明确的，行列对应的单元格值唯一，那么必然是 Map 映射最为方便，但偏偏我在这个时候犯蠢，明明引用是唯一的可以直接作为键，我还离散化了一下之后再设置键值对
class Spreadsheet {
private final static int COLS = 26;
private int rows;
private HashMap<Integer, Integer> fills = new HashMap<>();
// 愚蠢的离散化
private int rc2index(int curRow, char curCol) {
return curRow * COLS + (curCol - 'A');
}
private int[] extractRowAndColumn(String cell) {
char colChar = cell.charAt(0);
String rowStr = cell.substring(1);
int row = Integer.parseInt(rowStr);
return new int[] { row, colChar };
}
private int getCell(String cell) {
int[] coordinates = extractRowAndColumn(cell);
int index = rc2index(coordinates[0], (char) coordinates[1]);
return fills.getOrDefault(index, 0);
}
public Spreadsheet(int rows) {
this.rows = rows;
}
public void setCell(String cell, int value) {
int[] coordinates = extractRowAndColumn(cell);
int index = rc2index(coordinates[0], (char) coordinates[1]);
fills.put(index, value);
}
public void resetCell(String cell) {
int[] coordinates = extractRowAndColumn(cell);
int index = rc2index(coordinates[0], (char) coordinates[1]);
fills.put(index, 0); // 直接设置为0，无需检查是否存在
}
public int getValue(String formula) {
String[] elements = formula.substring(1).split("\\+"); // 跳过开头的"="，然后按"+"分割
int res = 0;
for (String element : elements) {
if (element.matches("\\d+")) {
// 如果元素是整数
res += Integer.parseInt(element);
} else {
// 否则视为单元格引用
res += getCell(element);
}
}
return res;
}
}
至于其他的，注意一下查找引用时是不是大写字母开头就行了。上述版本过于繁琐，参考一下 0xf3 佬的简洁实现：
class Spreadsheet {
private final Map<String, Integer> data = new HashMap<>();
public Spreadsheet(int rows) {
}
public void setCell(String cell, int value) {
data.put(cell, value);
}
public void resetCell(String cell) {
data.remove(cell);
}
public int getValue(String formula) {
int ans = 0;
for (String cell : formula.substring(1).split("\\+")) {
if (Character.isUpperCase(cell.charAt(0))) {
ans += data.getOrDefault(cell, 0);
} else {
ans += Integer.parseInt(cell);
}
}
return ans;
}
}
自愧不如啊自愧不如
以上
发表回复