笔试算法复盘_华为0508笔试 时间轴上有n种周期出现的资源,每种资源有周期和偏移

请设计一种虚拟机解释器，能解析并执行以下虚拟指令。 虚拟机约定:32位整形寄存器:a0，a1....a31，共32个寄存器; 整个虚拟机只有寄存器和立即数参与计算。 规则集(dst一定为寄存器，src为寄存器或十进制正整数，运算结果存在负数场景):
1. MOV dst src 含义:dst= src
2. ADD dst src0 src1 含义:dst= src0 + src1
3. SUB dst src0 src1 含义:dst=src0-src1
4. MUL dst srco src1 含义:dst=src0*src1
5. DlV dst src0 src1 含义:dst=src0/src1(结果向下取整)
6. PRINT dst 含义:打印dst寄存器值 约束:不用考虑计算溢出(用例保证)，指令数最多100条，至少一条PRINT指令，寄存器保证先赋值再引用。不用考虑小数跟除0。

import java.util.HashMap;
import java.util.Scanner;
 
public class test {
    HashMap<String, Integer> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder stringBuilder = new StringBuilder();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            if (line.isEmpty()) {
                break;
            }
            stringBuilder.append(line).append("\n");
        }
        String[] split = stringBuilder.toString().split("\n");
        test test = new test();
        test.excuteCommand(split);
    }
 
    public void excuteCommand(String[] commands) {
        for(String command : commands) {
            String[] s = command.split(" ");
            String instruction = s[0];
            switch (instruction) {
                case "MOV":
                    map.put(s[1], parseIntPlus(s[2]));
                    break;
                case "ADD":
                    map.put(s[1], parseIntPlus(s[2]) + parseIntPlus(s[3]));
                    break;
                case "SUB":
                    map.put(s[1], parseIntPlus(s[2]) - parseIntPlus(s[3]));
                    break;
                case "MUL":
                    map.put(s[1], parseIntPlus(s[2]) * parseIntPlus(s[3]));
                    break;
                case "DIV":
                    map.put(s[1], parseIntPlus(s[2]) / parseIntPlus(s[3]));
                    break;
                case "PRINT":
                    System.out.println(map.get(s[1]));
                    break;
            }
        }
    }
 
    public Integer parseIntPlus(String s) {
        // 方法1
        try{
           return Integer.parseInt(s);
        } catch (Exception e) {
            return map.get(s);
        }
        // 方法2
//        if (s.matches("-?\\d+")) { // check if it's a number
//            return Integer.parseInt(s);
//        } else { // it's a register name
//            return map.getOrDefault(s, 0);
//        }
    }
}

 无线通信移动性需要在基站上配置邻区(本端基站的小区LocalCell与周边邻基站的小区NeighborCell映射)关系，为了能够加速无线算法的计算效率，设计一个邻区关系缓存表，用于快速的通过本小区LocalCell查询到邻小区NeighborCel。但是缓存表有一定的规格限制，因此到达规格并且需要插入新的数据时，需要删除邻区数据，选择删除邻区数据对象的策略为:1)使用次数最少的，2)如果1)返回有多个对象，则选择最久未使用的。 请设计并实现一个满足以上要求的数据结构和算法实现。 注:假设每个LocalCell至多只有一个NeighborCell。 输入：

1、首行以字符"capacity:"标识设置一个整数容量

2、以"write:"标识开始进行若干组[LocalCell,NeighborCel] 邻区数据的输入，每组数据为一行;如果"write:"已经存在的LocalCell数据，更新其对应的NeighborCell，并刷新使用时间和次数加1;如果某邻区数据被删除，缓存表不再保留其记录;

3、以"read:"标识进行一次读取LocalCell的使用操作，刷新使用时间和次数加1;

4、最后以"query:"标识查询输出操作，输入正整数LocalCell，查询NeighborCell;

输出：

每个查询输入正整数LocalCell对应NeighborCell，表示在邻区关系缓存表中的记录。

package com.hmdp.utils;
 
import java.sql.Time;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Timer;
 
class CachNode{
    int localCell;
    int neighborCell;
    long time;
    int cnt;
 
    public CachNode(int localCell, int neighborCell) {
        this.localCell = localCell;
        this.neighborCell = neighborCell;
        this.time = System.nanoTime();
        this.cnt = 1;
    }
}
 
class LRUCache{
    int capacity;
    HashMap<Integer, CachNode> map;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
    }
 
    public int get(int localCell) {
        CachNode node = map.get(localCell);
        if(node != null) return -1;
        node.cnt++;
        node.time = System.nanoTime();
        return node.neighborCell;
    }
 
    public void put(int localCell, int neighborCell){
        if(map.containsKey(localCell)) {
            CachNode node = map.get(localCell);
            node.cnt++;
            node.time = System.nanoTime();
            node.neighborCell = neighborCell;
            return;
        }
        if(map.size() >= capacity) {
            int minCnt = Integer.MAX_VALUE;
            long minTime = Long.MAX_VALUE;
            int removeNode = 0;
            for(CachNode node : map.values()) {
                if(node.cnt < minCnt || (node.cnt == minCnt && node.time < minTime)) {
                    minCnt = node.cnt;
                    minTime = node.time;
                    removeNode = node.localCell;
                }
            }
            map.remove(removeNode);
        }
        map.put(localCell, new CachNode(localCell, neighborCell));
    }
 
 
}
 
public class test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        LRUCache lruCache = null;
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.startsWith("capacity:")) {
                int capacity = Integer.parseInt(scanner.nextLine());
                lruCache = new LRUCache(capacity);
            } else if (line.startsWith("write:")) {
                int writeCount = Integer.parseInt(scanner.nextLine().trim());
                for (int i = 0; i < writeCount; i++) {
                    String[] parts = scanner.nextLine().trim().split(" ");
                    int localCell = Integer.parseInt(parts[0]);
                    int neighborCell = Integer.parseInt(parts[1]);
                    lruCache.put(localCell, neighborCell);
                }
            } else if (line.startsWith("read:")) {
                int localCell = Integer.parseInt(scanner.nextLine().trim());
                lruCache.get(localCell);
            } else if (line.startsWith("query:")) {
                int localCell = Integer.parseInt(scanner.nextLine().trim());
                int result = lruCache.get(localCell);
                System.out.println(result);
                return;
            }
        }
    }
}

时间轴上有N种周期出现的资源，每种资源Rx的都有自己的周期period x和偏置ofset x，且资源的period/offset对不重复。求可以包含所有种类资源点的最小窗口的起始位置以及长度，由于满足条件的窗口会有若干个，所以只需要返回起始位置最小的窗口。

说明: 1、资源在时间轴上周期出现，例如资源对应的period，offset分别为(10,3)，那么该资源在时间轴上的位置为3,13,23.…，时间轴的最大值不超过INT MAX;2、最小窗口需要满足每种资源至少包含一次，但是可以包含多次;3、窗口大小至少为1。

输入： 第一行为资源的种类数;N，取值范围[1，10]，第二行为N种资源对应的period和offset，period取值范围(0,512],ofset为小于对应period的自然数;

输出： 满足覆盖N种资源的最小窗口的起始位置以及长度(每个资源至少包含一次),以空格隔开。

package com.hmdp.utils;
 
import java.util.*;
 
 
public class test {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            // 读取资源的种类数
            int N = scanner.nextInt();
            // 读取每种资源的周期和偏置
            int[] periods = new int[N];
            int[] offsets = new int[N];
            for (int i = 0; i < N; i++) {
                periods[i] = scanner.nextInt();
                offsets[i] = scanner.nextInt();
            }
            // 找出包含所有资源的最小窗口
            int[] result = findMinWindow(N, periods, offsets);
            System.out.println(result[0] + " " + result[1]);
        }
 
        private static int[] findMinWindow(int N, int[] periods, int[] offsets) {
            List<int[]> points = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                int period = periods[i];
                int offset = offsets[i];
                for (int j = 0; j < N; j++) {
                    points.add(new int[]{offset + j * period, i});
                }
            }
 
            // 按位置排序
            Collections.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
 
            int[] count = new int[N];
            int distinctCount = 0;
            int left = 0;
            int minLength = Integer.MAX_VALUE;
            int minStart = 0;
 
            for (int right = 0; right < points.size(); right++) {
                int type = points.get(right)[1];
                if (count[type] == 0) {
                    distinctCount++;
                }
                count[type]++;
 
                while (distinctCount == N) {
                    int start = points.get(left)[0];
                    int end = points.get(right)[0];
                    int length = end - start + 1;
                    if (length < minLength) {
                        minLength = length;
                        minStart = start;
                    }
 
                    int leftType = points.get(left)[1];
                    count[leftType]--;
                    if (count[leftType] == 0) {
                        distinctCount--;
                    }
                    left++;
                }
            }
 
            return new int[]{minStart, minLength};
        }
    }