第一题-设计有序流
问题
有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，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 ） 你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串，word1和word2。如果word1和word2接近 ，就返回 true；否则，返回false。
示例 1
输入：word1 = "abc", word2 = "bca"
输出：true
解释：
- 2 次操作从
word1获得word2。- 执行操作 1：“abc” -> “acb”
- 执行操作 1："acb" -> “bca”
示例 2
输入：word1 = "a", word2 = "aa"
输出：false
解释： 不管执行多少次操作，都无法从 word1得到word2，反之亦然。
思路
根据题目中的两种变换，不难找到规律：只要满足word1和word2中字母出现的频率和字母的种类相同即可互相转化，反之则不可。
代码
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方法出错，第三题也只是没想好最优解就直接用递归去莽，导致结果超时，这些以后都需要注意。