小黑盒是一家做游戏语音盒子的半游戏公司吧，福利待遇啥的也不错，薪资30-45K。他们的面试形式是牛客网视频面试，注意全程不能切屏。上来就是三道算法题，会就过，不会就挂。下面是我拿到的三道算法题。磕磕绊绊大概都实现了出来，也没运行，不知道能不能运行通过。
1.寻找两个正序数组的中位数
题目链接
题目
给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为O(log (m+n))。
示例
示例 1：
输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1,2,3] ，中位数 2
示例 2：
输入： nums1 = [1,2], nums2 = [3,4]
输出： 2.50000
解释： 合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
题解
使用双指针的方式，遍历两个数组。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
const len1 = nums1.length
const len2 = nums2.length
const merge = new Array(len1 + len2)
let i = 0, j = 0, k = 0;
while (i < len1 && j < len2) {
merge[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
}
while (i < len1) {
merge[k++] = nums1[i++];
}
while (j < len2) {
merge[k++] = nums2[j++];
}
const len = merge.length
return len % 2 == 0 ? (merge[len / 2] + merge[len / 2 - 1]) / 2 : merge[(len - 1) / 2];
};
// 测试用例
var nums1 = [1, 2];
var nums2 = [3, 4];
const result = findMedianSortedArrays(nums1, nums2)
console.log(result) // 2.5
2.分发糖果
题目链接
题目
n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。
示例
示例1：
输入： ratings = [1,0,2]
输出： 5
解释： 你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例2：
输入： ratings = [1,2,2]
输出： 4
解释： 你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
题解
采用贪心策略，从局部到全局，在每一次遍历中，只考虑一侧的大小关系并进行更新，进行从左到右和从右到左两次遍历后。
- 每个人至少有一个糖果，先建个数组初始化为1，每个孩子都分配一个糖果
- 第一次 从左往右遍历，若右边的评分比左边的高，则右边的糖果数改为左边的糖果数加 1
- 从右往左遍历，左边的评分比右边的高，且左边孩子当前的糖果数不大于右边的糖果数，则左边的糖果数更新为右边的糖果数加 1
/**
* @param {number[]} ratings
* @return {number}
*/
const candy =(ratings) => {
// 每个人先分配一个
let nums = new Array(ratings.length).fill(1);
// 从左往右
for(let i = 1 ; i < ratings.length; i++){
if(ratings[i] > ratings[i-1]){
nums[i] = nums[i-1] +1;
}
}
// 从右往左
for(let j = ratings.length - 1; j > 0; j--){
if (ratings[j] < ratings[j-1] && nums[j-1] <= nums[j]) {
nums[j-1] = nums[j] + 1;
}
}
// 求和
let sum = 0;
for(let i = 0; i < nums.length; i++){
sum += nums[i];
}
return sum;
}
// 测试用例
var ratings = [1, 0, 2]
const result = candy(ratings)
console.log(result) // 5
3.无重叠区间
题目链接
题目
给定一个区间的集合intervals，其中intervals[i] = [starti, endi]。返回需要移除区间的最小数量，使剩余区间互不重叠 。
示例
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
题解
这道题也是使用贪心的思想，子问题实际上就是区间两两之间的接触情况，这样逐步局部最优会最终到达全局最优。
第一步：我们要将二维数组按照第二个元素进行排序，为什么要选择第二个而不是第一个呢？因为区间第二个元素都是较大数，可以准确确定区间的范围。
第二步：从下标为1开始循环遍历二维数组，与它上一个区间进行比较，如果等于或者大于或者等于，则向后遍历，并且记录上一个区间的变量移至当前下标处。如果是小于，记录，但是上一个区间下标不动，直至循环结束
/**
* @param {number[][]} intervals
* @return {number}
*/
var eraseOverlapIntervals = function (intervals) {
if (intervals.length == 0 || intervals.length == 1) {
return 0
}
intervals.sort(function (a, b) {
return a[1] - b[1]
})
var pre = 0;//记录上一个节点
var removeNum = 0;
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= intervals[pre][1]) {
pre = i;//因为中途可能有删除的数组区间，直接++会将其算进结果内
} else {
removeNum++;
}
}
return removeNum
};
// 测试用例
var intervals = [ [1,2], [1,2], [1,2] ]
const result = eraseOverlapIntervals(intervals)
console.log(result)
没有感情的刷题机器。。。
如果你现在正在找工作，可以扫描下方的二维码进群，本群承诺没有任何交易，没有买卖，权当为了督促我自己，也为了找到志同道合的道友一起渡劫。如果二维码过期请添加我个人WX：xiumubai01。
