---

📋前言

這個系列的文章收納的內(nèi)容是來自于藍橋云課的前端崗位筆面必刷題的內(nèi)容，簡介是：30天133題，本題單題目全部來自于近2年BAT等大廠前端筆面真題！因為部分題目是需要會員，所以該系列的文章內(nèi)容并非完全全面（如果需要會員的題目，則從 leetcode 補充對應(yīng)的題目，題目大概也是一樣的考法）。文章中題目涉及的內(nèi)容包括原題、答案和解析等等。

---

🎯數(shù)組中重復(fù)的數(shù)字

📚題目內(nèi)容

找出數(shù)組中重復(fù)的數(shù)字。

在一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0 ～ n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字重復(fù)了，也不知道每個數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。

輸入：[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])}
}

函數(shù) findRepeatNumber 接收一個數(shù)組 nums，并返回一個重復(fù)的數(shù)字。在循環(huán)中，我們使用 Set 的 has 方法來判斷當前數(shù)字是否已經(jīng)出現(xiàn)過，如果是，則直接返回該數(shù)字；否則，將該數(shù)字添加到 Set 中。

該算法的時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(n)。

---

🎯兩數(shù)之和

📚題目內(nèi)容

給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標值 target，請你在該數(shù)組中找出和為目標值 target 的那兩個整數(shù)，并返回它們的數(shù)組下標。

你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。

你可以按任意順序返回答案。

輸入： 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 循環(huán)，暴力枚舉的思想來實現(xiàn)。首先使用兩個嵌套的循環(huán)來遍歷整個 nums 數(shù)組，對于每對不同的下標 i 和 j（i < j），計算它們所對應(yīng)的數(shù)之和，并判斷是否等于目標值 target。如果相等，則直接返回這兩個下標。

該函數(shù)的時間復(fù)雜度為 O(n^2)，因為需要進行兩層循環(huán)嵌套，最多需要遍歷 n(n-1)/2 個數(shù)對?？臻g復(fù)雜度為 O(1)，因為只需要使用常數(shù)個變量來存儲結(jié)果。

另一種解法

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);}
}

該函數(shù)的實現(xiàn)中，首先創(chuàng)建了一個新的 Map 對象 hashmap，然后遍歷整個 nums 數(shù)組。對于每個數(shù)字 nums[i]，計算出與目標值之差 num2 = target - nums[i]，然后在 hashmap 中查找是否存在滿足條件的 num2，如果存在，則直接返回對應(yīng)的下標；如果不存在，則將當前數(shù)字作為新的鍵，將下標作為對應(yīng)的值，存儲到 hashmap 中，以備下次查找時使用。

該算法的時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(n)。

---

🎯替換空格

📚題目內(nèi)容

請實現(xiàn)一個函數(shù)，把字符串 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
}

首先創(chuàng)建一個新的空字符串 result，然后遍歷原始字符串 s 中的每個字符。對于每個字符，如果它是一個空格，則將 "%20" 添加到 result 中，否則直接將它添加到 result 中。

該函數(shù)的時間復(fù)雜度為 O(n)，其中 n 是原始字符串 s 的長度，因為需要遍歷一遍輸入的字符串。而空間復(fù)雜度也為 O(n)，因為最壞情況下，需要將每個空格都替換為 "%20"。

另一種解法

function replaceSpace (s) {return s.replace(/\s/g,'%20')
}

使用 String 類型的 replace 方法和正則表達式對字符串 s 進行替換空格的處理，在這個實現(xiàn)中，我們通過正則表達式 /\s/g 匹配所有空格字符，并使用 "%20" 作為新的內(nèi)容來替換它們。最終返回替換后的字符串即可。

該函數(shù)的時間復(fù)雜度同樣為 O(n)，其中 n 是原始字符串 s 的長度，因為需要遍歷一遍輸入的字符串并進行替換操作。而空間復(fù)雜度也為 O(n)，因為在正則表達式匹配后會得到一個新的字符串對象，并且該字符串對象的長度可能比原始字符串更長，因此需要額外的空間來存儲。

---

🎯二維數(shù)組中的查找

📚題目內(nèi)容

在一個 n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個高效的函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。示例：

現(xiàn)有矩陣 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; // 行數(shù)const n = matrix[0].length; // 列數(shù)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; // 遍歷完整個數(shù)組都沒有找到目標值
}

該函數(shù)的實現(xiàn)中，首先通過檢查輸入矩陣是否為空來判斷是否需要提前返回 false。然后，定義了兩個指針 row 和 col ，分別用于表示當前搜索的行和列。由于矩陣中的每一行都已經(jīng)按照升序排列，而每一列也已經(jīng)按照升序排列，因此可以采用類似于二分查找的方法進行搜索。

具體來說，在每次迭代中，我們比較當前指針所在位置的元素與目標值的大小關(guān)系。我們可以從矩陣的右上角開始搜索，如果當前值等于 target，則直接返回 true 。如果當前值大于 target，則說明 target 可能出現(xiàn)在當前元素的左側(cè)，因此需要將列指針向左移動一位 。反之，如果當前值小于 target ，則說明目標值可能出現(xiàn)在當前元素的下方，因此需要將行指針向下移動一位 。不斷重復(fù)以上步驟，直到找到目標值或者搜索完整個數(shù)組。

該函數(shù)的時間復(fù)雜度為 O(m+n)，其中 m 和 n 分別表示矩陣的行數(shù)和列數(shù)。因為每次迭代可以將搜索范圍縮小一行或者一列，最多需要進行 m+n 次迭代才能找到目標值（當目標值位于矩陣的右上角時）。而空間復(fù)雜度為 O(1)，因為只使用了常數(shù)級別的額外空間來存儲指針和一些臨時變量。

---

📝最后

感謝閱讀到這，這就是 Day1 的全部內(nèi)容了，文章內(nèi)容中題目的答案都是通過檢測的了，如果有疑問和爭議的內(nèi)容，可以評論區(qū)留言和私信我，收到消息第一時間解答和回復(fù)。