算法面试-持续更新
面试题
1. 两数之和
真题描述: 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
示例:
给定 nums = [2, 7, 11, 15»], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
几乎所有的两数之和问题都可以转换为求差问题
1 | const twoSum = function(nums, target) { |
2. 合并两个有序数组
真题描述:给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
解题思路:采用双指针法,首先用p1(指针1) 指向 nums1 的开头,p2(指针2)指向num2的开头。
用 p1 对应的值和 p2 进行比较,将最小的值放入都输出数组中。每次比较,移动对应的 p1 或者 p2:
![image](/2023/02/08/%E7%AE%97%E6%B3%95%E9%9D%A2%E8%AF%95/1.png)
假设我们一开始执行的是:merge([1,2,3,0,0,0], 3, [2,5,6], 3),那么:
1
2
3
4
5
6
7
while (count1 < m && count2 < n) {
if (nums1[count1] > nums2[count2]) {
nums1.push(nums2[count2++]);
} else {
nums1.push(nums1[count1++]);
}
}
经过 while 的遍历之后,我们把基本能添加的值,都添加进 nums1 了。
然后,我们再进行一次判断,是 nums1 没有遍历完还是 nums2 没有遍历完,如果没遍历完,那么就从那位开始,把剩下的通过 slice() 切割出来后,再通过解构赋值,将其 push() 到 nums1 即可:
1 | if (count1 < m) { |
最后,我们通过 nums1.splice(0, len) 将 nums1 原本的内容删掉,就可以获得最终结果了。
1 | /** |
3.
已知每个服务启动都需要一定时间,且每个服务可能依赖其他的服务启动。现给定一个n*n的二维数组arr,
arr[i][i]表示i服务启动需要的时间,arr[i][j]表示i服务是否依赖j服务,如果为1表示依赖,
0表示不依赖。当服务依赖的服务彼此之间没有依赖关系时,这些服务可以并行启动。
题目保证服务之间不存在循环依赖关系,求服务k(1<=k<=n)启动需要的时间。