文章目录
- 📋前言
- 🎯数组中重复的数字
- 📚题目内容
- ✅解答
- 🎯两数之和
- 📚题目内容
- ✅解答
- 🎯替换空格
- 📚题目内容
- ✅解答
- 🎯二维数组中的查找
- 📚题目内容
- ✅解答
- 📝最后
📋前言
这个系列的文章收纳的内容是来自于蓝桥云课的前端岗位笔面必刷题的内容，简介是：30天133题，本题单题目全部来自于近2年BAT等大厂前端笔面真题！因为部分题目是需要会员，所以该系列的文章内容并非完全全面（如果需要会员的题目，则从 leetcode 补充对应的题目，题目大概也是一样的考法）。文章中题目涉及的内容包括原题、答案和解析等等。
🎯数组中重复的数字
📚题目内容
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0 ～ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
题目给的测试用例里有以下限制：
2 <= n <= 14。
✅解答
初始提供代码
function findRepeatNumber(nums) {
// 补充代码
}
答案
function findRepeatNumber(nums) {
let hash = new Set()
for(let i=0;i<nums.length;i++){
if(hash.has(nums[i])){
return nums[i]
}
hash.add(nums[i])
}
}
函数 findRepeatNumber 接收一个数组 nums，并返回一个重复的数字。在循环中，我们使用 Set 的 has 方法来判断当前数字是否已经出现过，如果是，则直接返回该数字；否则，将该数字添加到 Set 中。
该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。
🎯两数之和
📚题目内容
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入： nums = [2,7,11,15], target = 9
输出： [0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
输入： nums = [3,2,4], target = 6
输出： [1,2]
输入： nums = [3,3], target = 6
输出： [0,1]
题目给的测试用例里有以下限制：
2 <= nums.length <= 4。2 <= nums[i] <= 11。6 <= target <= 10。- 只会存在一个有效答案。
✅解答
初始提供代码
function twoSum(nums, target) {
// 补充代码
}
答案
function twoSum(nums, target) {
for(let i=0;i<nums.length;i++){
for(let j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]===target){
return [i,j]
}
}
}
}
采用双 for 循环，暴力枚举的思想来实现。首先使用两个嵌套的循环来遍历整个 nums 数组，对于每对不同的下标 i 和 j（i < j），计算它们所对应的数之和，并判断是否等于目标值 target。如果相等，则直接返回这两个下标。
该函数的时间复杂度为 O(n^2)，因为需要进行两层循环嵌套，最多需要遍历 n(n-1)/2 个数对。空间复杂度为 O(1)，因为只需要使用常数个变量来存储结果。
另一种解法
function twoSum(nums, target) {
const hashmap = new Map();
for (let i = 0; i < nums.length; i++) {
const num2 = target - nums[i];
if (hashmap.has(num2)) {
return [hashmap.get(num2), i];
}
hashmap.set(nums[i], i);
}
}
该函数的实现中，首先创建了一个新的 Map 对象 hashmap，然后遍历整个 nums 数组。对于每个数字 nums[i]，计算出与目标值之差 num2 = target - nums[i]，然后在 hashmap 中查找是否存在满足条件的 num2，如果存在，则直接返回对应的下标；如果不存在，则将当前数字作为新的键，将下标作为对应的值，存储到 hashmap 中，以备下次查找时使用。
该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。
🎯替换空格
📚题目内容
请实现一个函数，把字符串 s 中的每个空格替换成 “%20”。
题目给的测试用例里有以下限制：
0 <= s.length <= 14。
✅解答
初始提供代码
function replaceSpace(s) {
// 补充代码。
}
答案
function replaceSpace(s) {
let result = "";
for (let i = 0; i < s.length; i++) {
if (s[i] === " ") {
result += "%20"
} else {
result += s[i]
}
}
return result
}
首先创建一个新的空字符串 result，然后遍历原始字符串 s 中的每个字符。对于每个字符，如果它是一个空格，则将 "%20" 添加到 result 中，否则直接将它添加到 result 中。
该函数的时间复杂度为 O(n)，其中 n 是原始字符串 s 的长度，因为需要遍历一遍输入的字符串。而空间复杂度也为 O(n)，因为最坏情况下，需要将每个空格都替换为 "%20"。
另一种解法
function replaceSpace (s) {
return s.replace(/\s/g,'%20')
}
使用 String 类型的 replace 方法和正则表达式对字符串 s 进行替换空格的处理，在这个实现中，我们通过正则表达式 /\s/g 匹配所有空格字符，并使用 "%20" 作为新的内容来替换它们。最终返回替换后的字符串即可。
该函数的时间复杂度同样为 O(n)，其中 n 是原始字符串 s 的长度，因为需要遍历一遍输入的字符串并进行替换操作。而空间复杂度也为 O(n)，因为在正则表达式匹配后会得到一个新的字符串对象，并且该字符串对象的长度可能比原始字符串更长，因此需要额外的空间来存储。
🎯二维数组中的查找
📚题目内容
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。示例：
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30],
];
给定 target = 5，返回 true。 给定 target = 20，返回 false。
题目给的测试用例里有以下限制：
0 <= n <= 5。0 <= m <= 5。。
✅解答
初始提供代码
function findNumberIn2DArray(matrix, target) {
// 补充代码。
}
答案
function findNumberIn2DArray(matrix, target) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
return false;
}
const m = matrix.length; // 行数
const n = matrix[0].length; // 列数
let row = 0; // 行指针，从第一行开始
let col = n - 1; // 列指针，从最后一列开始
while (row < m && col >= 0) {
if (matrix[row][col] === target) { // 找到了目标值
return true;
} else if (matrix[row][col] > target) { // 当前值比目标值大，向左移动列指针
col--;
} else { // 当前值比目标值小，向下移动行指针
row++;
}
}
return false; // 遍历完整个数组都没有找到目标值
}
该函数的实现中，首先通过检查输入矩阵是否为空来判断是否需要提前返回 false。然后，定义了两个指针 row 和 col ，分别用于表示当前搜索的行和列。由于矩阵中的每一行都已经按照升序排列，而每一列也已经按照升序排列，因此可以采用类似于二分查找的方法进行搜索。
具体来说，在每次迭代中，我们比较当前指针所在位置的元素与目标值的大小关系。我们可以从矩阵的右上角开始搜索，如果当前值等于 target，则直接返回 true 。如果当前值大于 target，则说明 target 可能出现在当前元素的左侧，因此需要将列指针向左移动一位 。反之，如果当前值小于 target ，则说明目标值可能出现在当前元素的下方，因此需要将行指针向下移动一位 。不断重复以上步骤，直到找到目标值或者搜索完整个数组。
该函数的时间复杂度为 O(m+n)，其中 m 和 n 分别表示矩阵的行数和列数。因为每次迭代可以将搜索范围缩小一行或者一列，最多需要进行 m+n 次迭代才能找到目标值（当目标值位于矩阵的右上角时）。而空间复杂度为 O(1)，因为只使用了常数级别的额外空间来存储指针和一些临时变量。
📝最后
感谢阅读到这，这就是 Day1 的全部内容了，文章内容中题目的答案都是通过检测的了，如果有疑问和争议的内容，可以评论区留言和私信我，收到消息第一时间解答和回复。
