大疆笔试 8.14 后端B卷 AC代码
1.存在重复元素
LeetCode 219原题
可以用map记录最新的下标
也可以使用set来控制滑动窗口
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (i > k) {
set.remove(nums[i - k - 1]);
}
if (!set.add(nums[i])) {
return true;
}
}
return false;
} 2. 表现良好的时间段LeetCode 1124原题
前缀和+单调栈
public int longestWPI(int[] hours) {
int[] arr = new int[hours.length];
for (int i = 0; i < arr.length; i++) {
if (hours[i] > 8) {
arr[i] = 1;
}
else {
arr[i] = -1;
}
}
int[] pres = new int[arr.length + 1];
int sum = 0;
int result = 0;
for (int i = 0; i < arr.length; i++) {
pres[i] = sum;
sum += arr[i];
}
pres[pres.length - 1] = sum;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < pres.length; i++) {
if (stack.isEmpty() || pres[stack.peek()] > pres[i]) {
stack.push(i);
}
}
for (int i = pres.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && pres[stack.peek()] < pres[i]) {
int temp = stack.pop();
result = Math.max(result, i - temp);
}
}
return result;
} ps：为啥后端题目选择题还有前端题目啊