第一题-设计有序流

问题

n(id, value) 对,其中 id1n 之间的一个整数,value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流,以 任意 顺序获取 n(id, value) 对,并在多次调用时按id递增的顺序返回一些值。

实现 OrderedStream 类:

  • OrderedStream(int n) 构造一个能接收 n 个值的流,并将当前指针ptr设为 1 。
  • String[] insert(int id, String value) 向流中存储新的 (id, value)对。存储后:
    • 如果流存储有 id = ptr(id, value) 对,则找出从id = ptr开始的 最长id连续递增序列 ,并按顺序返回与这些id关联的值的列表。然后,将 ptr 更新为最后那个 id + 1
    • 否则,返回一个空列表。

示例

输入

["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]

输出

[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

解释

OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc"),返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa"),返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb"),返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee"),返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd"),返回 ["ddddd", "eeeee"]

思路

本问题唯一难点即是读懂题目要求,按照题目所说实现逻辑即可。这里采用哈希表来记录(id, value)键值对。

代码

class OrderedStream {
    int n = 0;
    int ptr = 0;
    Map<Integer, String> map = new HashMap<>();
    public OrderedStream(int n) {
        this.ptr = 1;
        this.n = n;
    }
    
    public List<String> insert(int id, String value) {
        List<String> res = new LinkedList<>();
        map.put(id, value);
        if(ptr == id){
            for(int i = id; i < n + 1; i++){
                if(map.containsKey(i)){
                    res.add(map.get(i));
                }else{
                    ptr = i;
                    break;
                }
            }
        }
        return res;
    }
}

第二题-确定两个字符串是否接近

问题

如果可以使用以下操作从一个字符串得到另一个字符串,则认为两个字符串 接近 :

  • 操作 1:交换任意两个现有字符。
    • 例如,abcde -> aecdb
  • 操作 2:将一个现有字符的每次出现转换为另一个现有字符,并对另一个字符执行相同的操作。
    • 例如,aacabb -> bbcbaa(所有 a 转化为 b ,而所有的 b 转换为 a ) 你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串,word1word2。如果word1word2接近 ,就返回 true;否则,返回false

示例1

输入word1 = "abc", word2 = "bca" 输出true 解释

  • 2 次操作从word1获得word2
    1. 执行操作 1:“abc” -> “acb
    2. 执行操作 1:"acb" -> “bca

示例2

输入word1 = "a", word2 = "aa" 输出false 解释: 不管执行多少次操作,都无法从 word1得到word2,反之亦然。

思路

根据题目中的两种变换,不难找到规律:只要满足word1word2中字母出现的频率和字母的种类相同即可互相转化,反之则不可。

代码

class Solution {
    public boolean closeStrings(String word1, String word2) {
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();
        for (char c : word1.toCharArray()) {
            if (map1.containsKey(c)) {
                map1.put(c, map1.get(c) + 1);
            } else {
                map1.put(c, 1);
            }
        }
        for (char c : word2.toCharArray()) {
            if (map2.containsKey(c)) {
                map2.put(c, map2.get(c) + 1);
            } else {
                map2.put(c, 1);
            }
        }
        Integer[] v1 = map1.values().toArray(new Integer[0]);
        Integer[] v2 = map2.values().toArray(new Integer[0]);
        if (map1.keySet().size() != map2.keySet().size() || !map1.keySet().containsAll(map2.keySet())) {
            return false;
        }
        int len1 = v1.length;
        int len2 = v2.length;
        if (len1 != len2) {
            return false;
        }
        Arrays.sort(v1);
        Arrays.sort(v2);
        for (int i = 0; i < len1; i++) {
            if (!v1[i].equals(v2[i])) {
                return false;
            }
        }
        return true;
    }
}

第三题-将x减到0的最小操作数

问题

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要修改数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1

示例1

输入nums = [1,1,4,2,3], x = 5
输出2

示例2

输入nums = [5,6,7,8,9], x = 4 输出-1

示例3

输入nums = [3,2,20,1,1,3], x = 10 输出5

思路

采用滑动窗口的方式扫描数组,首先确定最大的窗口大小(这里是SUM(nums) - x),之后从最左侧开始使用右指针扩大窗口,左指针缩小窗口,当窗口值大于最大窗口大小时,移动左指针缩小窗口并检测是否满足题目中x恰好减到0的条件(窗口大小值刚好等于最大窗口大小),如果满足则与当前结果值进行比较,取最小值即可。

代码

class Solution {
    public int minOperations(int[] nums, int x) {
        int maxSum = 0;
        for (int num : nums) {
            maxSum += num;
        }
        maxSum -= x;
        if (maxSum == 0) {
            return nums.length;
        }
        int count = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int curSum = 0;
        while (right < nums.length) {
            curSum += nums[right];
            if (curSum > maxSum) {
                while (left < right && curSum > maxSum) {
                    curSum -= nums[left];
                    left++;
                }
            }
            if (curSum == maxSum) {
                count = Math.min(count, left + nums.length - 1 - right);
            }
            right++;
        }
        return count == Integer.MAX_VALUE ? -1 : count;
    }
}

总结

总体上来看,题目本身并不难,目标也只是做出前三题即可。也遇到了一些小问题,比如说在第二题中,没有注意将Object数组转为Integer数组,导致之后的equals方法出错,第三题也只是没想好最优解就直接用递归去莽,导致结果超时,这些以后都需要注意。