碎碎念：
親愛的讀者：你好！我的名字叫昌龍 【Changlon】 —— 一個(gè)非科班程序員、一個(gè)致力于前端的開發(fā)者、一個(gè)熱愛生活且又時(shí)有憂郁的思考者。
如果我的文章能給你帶來一些收獲，你的點(diǎn)贊收藏將是對(duì)我莫大的鼓勵(lì)！
我的郵箱:thinker_changlon@163.com
我的Github: https://github.com/Changlon
程序員之進(jìn)大廠必刷算法題系列
數(shù)組
字符串
鏈表
棧
哈希
二叉樹
二分算法
分治算法(快排序)
動(dòng)態(tài)規(guī)劃
深度優(yōu)先，廣度優(yōu)先算法
遞歸，回溯算法
貪心算法
一、NC22 合并兩個(gè)有序的數(shù)組
描述 給出一個(gè)整數(shù)數(shù)組 A 和有序的整數(shù)數(shù)組B ，請(qǐng)將數(shù)組 B合并到數(shù)組 A中，變成一個(gè)有序的升序數(shù)組 注意：
1.可以假設(shè) A數(shù)組有足夠的空間存放 B數(shù)組的元素，A 和 B中初始的元素?cái)?shù)目分別為 m和 n，A的數(shù)組空間大小為 m n
2.不要返回合并的數(shù)組，返回是空的，將數(shù)組B 的數(shù)據(jù)合并到A里面就好了
3.A數(shù)組在[0,m-1]的范圍也是有序的
例1: A: [1,2,3,0,0,0]，m=3 B: [2,5,6]，n=3 合并過后A為: A: [1,2,2,3,5,6]
示例1
輸入：
[4,5,6],[1,2,3]
復(fù)制
返回值：
[1,2,3,4,5,6]
思路1: 首先將B數(shù)組中的數(shù)據(jù)拷貝到A的剩余空間中，然后對(duì)A數(shù)組使用sort排序，最后返回A。
function merge( A, m, B, n ) {
for(let i =m,j=0;i<m n; i, j) {
A[i] = B[j]
}
A.sort((a,b)=>a-b)
return A
}
那么如果面試官這時(shí)候提了一個(gè)不能使用原型或類庫(kù)函數(shù)的要求呢？我們不能使用sort庫(kù)函數(shù)或原型函數(shù)。
思路2:因?yàn)锳數(shù)組和B數(shù)組都是升序的，所以我們可以用雙指針來處理這道題。
初始化 m,n分別指向A和B的尾部。然后開始從尾部向前比較大小，誰(shuí)的值大就放到A數(shù)組的后面。接著只移動(dòng)那個(gè)較大的指針先前一個(gè)再繼續(xù)比較。如果B中的數(shù)都比A中的大，那么遍歷一遍正好都放滿A的剩余空間。如果B中的最小值比A中的最小值小，那么遍歷一遍過后n一定是大于0的，那就將B中前n個(gè)元素拷貝到A前n個(gè)位置中。
function merge(A,m,B,n) {
let len1 = A.length,len2 = B.length
if(len1==0) {
for(let n of B) A.push(n)
return A
}
if(len2==0) return A
while(m>0&&n>0) {
if(A[m-1]>=B[n-1]) {
A[m n-1] = A[m-1]
m--
}else{
A[m n-1] = B[n-1]
n--
}
}
//處理B中小于A最小數(shù)的數(shù)
if(n>0) {
for(let i =0;i<n; i) A[i] = B[i]
}
return A
}
二、NC41 最長(zhǎng)無(wú)重復(fù)子數(shù)組
描述 給定一個(gè)數(shù)組arr，返回arr的最長(zhǎng)無(wú)重復(fù)元素子數(shù)組的長(zhǎng)度，無(wú)重復(fù)指的是所有數(shù)字都不相同。
子數(shù)組是連續(xù)的，比如[1,3,5,7,9]的子數(shù)組有[1,3]，[3,5,7]等等，但是[1,3,7]不是子數(shù)組
示例1 輸入：
[2,3,4,5]
返回值： 4
說明： [2,3,4,5]是最長(zhǎng)子數(shù)組
示例2 輸入： [2,2,3,4,3]
返回值： 3
說明：[2,3,4]是最長(zhǎng)子數(shù)組
思路1： 定義一個(gè)隊(duì)列，遍歷數(shù)組依次將數(shù)據(jù)添加至隊(duì)列中，如果將要添加的內(nèi)容與在隊(duì)列中重復(fù)，則將重復(fù)的內(nèi)容以及重復(fù)前面的內(nèi)容循環(huán)出隊(duì)列。之后再向隊(duì)列中添加數(shù)據(jù)，接著比較是否是最長(zhǎng)不重復(fù)子數(shù)組。
function maxLength(arr) {
if(arr.length==0||arr.length==1) return arr.length
const queue = []
let max = 0
for(let c of arr) {
while(queue.includes(c)) {
queue.shift()
}
queue.push(c)
max = Math.max(max,queue.length)
}
return max
}
思路2: 使用雙指針，初始化i,j指針指向數(shù)組首地址，然后依次將i向后移動(dòng)，順便將每次移動(dòng)的值添加至一個(gè)map中。如果當(dāng)前i所在的位置中的值在map中重復(fù)，則將j向后移動(dòng)。
function maxLength_( arr ) {
if(arr.length==0||arr.length==1) return arr.length
const map = new Map()
let max = 0
for(let i=0,j=0;i<arr.length; i) {
if(map.has(arr[i])) {
//[3,3,2,1,3,3,3,1]對(duì)于這種情況
//當(dāng)i指向最后一個(gè)元素的時(shí)候因?yàn)?在之前出現(xiàn)過，
//所以j由理想的 j = 7 變成 j =3 這會(huì)影響max的值，
//所以需要加一個(gè)Math.max取j的最大值
j = Math.max(j,map.get(arr[i]) 1)
}
map.set(arr[i],i)
max = Math.max(max,i-j 1)
}
return max
}
三、NC61 兩數(shù)之和
描述 給出一個(gè)整數(shù)數(shù)組，請(qǐng)?jiān)跀?shù)組中找出兩個(gè)加起來等于目標(biāo)值的數(shù)， 你給出的函數(shù)twoSum
需要返回這兩個(gè)數(shù)字的下標(biāo)（index1，index2），需要滿足 index1 小于index2.。注意：下標(biāo)是從1開始的
假設(shè)給出的數(shù)組中只存在唯一解 例如： 給出的數(shù)組為 {20, 70, 110, 150},目標(biāo)值為90 輸出 index1=1, index2=2
示例1
輸入： [3,2,4],6
返回值： [2,3]
說明： 因?yàn)?2 4=6 ，而 2的下標(biāo)為2 ， 4的下標(biāo)為3 ，又因?yàn)?下標(biāo)2 < 下標(biāo)3 ，所以輸出[2,3]
思路: 維護(hù)一個(gè)哈希列表，遍歷numbers數(shù)組，每次遍歷存入哈希列表的key–>value是 （目標(biāo)值 - 當(dāng)前值）–> 下標(biāo)
已數(shù)組 [3,2,4]為列子,當(dāng)遍歷到2的時(shí)候哈希中存入了 3–>0,4–>1 當(dāng)遍歷到最后一個(gè)值時(shí)正好對(duì)應(yīng)哈希中存入的 4–>1 所以說最后遍歷的 下標(biāo)2和哈希列表中對(duì)應(yīng)4的下標(biāo)1這兩個(gè)對(duì)應(yīng)的值和為6即目標(biāo)值。
function twoSum( numbers , target ) {
const res = []
const map = new Map()
for(let i =0;i<numbers.length; i) {
if(map.has(numbers[i])){
let a = i 1
let b = map.get(numbers[i]) 1
res.push(a)
res.push(b)
break
}else{
map.set(target-numbers[i],i)
}
}
res.sort((a,b)=>a-b)
return res
}
四、NC38 螺旋矩陣
描述
給定一個(gè)m x n大小的矩陣（m行，n列），按螺旋的順序返回矩陣中的所有元素。
示例1
輸入： [[1,2,3],[4,5,6],[7,8,9]] 返回值： [1,2,3,6,9,8,7,4,5]
這道題主要調(diào)試需要費(fèi)點(diǎn)功夫，就是回型遍歷數(shù)組。只要能按照想法寫出來就可以。本人實(shí)現(xiàn)了一個(gè)簡(jiǎn)陋的算法如下。通過一個(gè)marked二維數(shù)組來判斷是否遍歷過。
function spiralOrder( matrix ) {
if(!matrix || matrix.length==0) return []
let i =0,j= 0
let r = matrix.length,c = matrix[0].length
const res = []
let marked = []
for(let a = 0;a<=r; a ){
marked[a] = []
for(let b = 0;b<=c; b) {
if(a==r||b==c) {
marked[a][b] = 1
}else {
marked[a][b] = 0
}
}
}
let flag = 0 // 0 右 1 下 2 左 3 上
while(res.length<r*c) {
res.push(matrix[i][j])
marked[i][j] = 1
if(j<=c&&flag==0) {//向右
if(marked[i][j 1]!=1) j
else {
i
flag =1
}
}else if(i<=r&&flag==1) { //向下
if(marked[i 1][j]!=1) i
else {
j--
flag = 2
}
}else if(j>=-1&&flag==2){//向左
if( typeof marked[i][j-1]!='undefined' && marked[i][j-1]!=1) j--
else {
i--
flag = 3
}
}else if(i>=-1&&flag ==3) { //向上
if(typeof marked[i-1][j]!='undefined' &&marked[i-1][j]!=1) i--
else {
j
flag = 0
}
}
}
return res
}
五、NC65 斐波那契數(shù)列
描述 大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0，第1項(xiàng)是1）。 n≤39
老生常談的題了。主要有兩種解決思路。
思路1: 遞歸
時(shí)間復(fù)雜度：O(2^n)
空間復(fù)雜度：遞歸棧的空間
function Fibonacci(n)
{
if(n==0||n==1) return n
return Fibonacci(n-1) Fibonacci(n-2)
}
第一種方法只對(duì)剛?cè)腴T的人來說比較簡(jiǎn)單一點(diǎn)，下面介紹一種動(dòng)態(tài)規(guī)劃的方法以及它的優(yōu)化。時(shí)間復(fù)雜度 O(n),空間復(fù)雜 O(1)
思路2:動(dòng)態(tài)規(guī)劃
//動(dòng)態(tài)規(guī)劃
function Fibonacci(n) {
let dp = []
dp[0] = 0
dp[1] = 1
for(let i =2;i<=n; i) {
dp[i] = dp[i-1] dp[i-2]
}
return dp[n]
}
//空間優(yōu)化
function Fibonacci(n)
{
if(n==0||n==1) return n
let a = 0
let b = 1
let c
for(let i =2;i<=n; i) {
c = a b
a = b
b = c
}
return c
}
六、NC18 順時(shí)針旋轉(zhuǎn)矩陣
描述 有一個(gè)NxN整數(shù)矩陣，請(qǐng)編寫一個(gè)算法，將矩陣順時(shí)針旋轉(zhuǎn)90度。
給定一個(gè)NxN的矩陣，和矩陣的階數(shù)N,請(qǐng)返回旋轉(zhuǎn)后的NxN矩陣,保證N小于等于300。
思路: 從底向上，從左向右遍歷傳過來的數(shù)組，然后將值一次輸入到一個(gè)新的順序遍歷的數(shù)組中。
function rotateMatrix(mat,n){
let ret = []
for(let i=0;i<n; i) ret[i] = []
for(let i =0;i<n; i) {
for(let j =n-1;j>=0;--j) {
let c = mat[j][i] ;
ret[i][n-j-1] = c;
}
}
return ret;
}
七、NC75 數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字
描述 一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字只出現(xiàn)一次，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
示例1
輸入：
[1,4,1,6]
返回值：
[4,6]
說明：
返回的結(jié)果中較小的數(shù)排在前面
思路1: 用一個(gè)Map來存取所有數(shù)字出現(xiàn)的次數(shù)
function FindNumsAppearOnce( array ) {
let v = []
let m = new Map()
for(let n of array) {
if(!m.get(n)) {
m.set(n,1)
}else{
m.set(n,2)
}
}
for(let n of array) {
if(m.get(n)==1) {
v.push(n)
}
}
if(v[0]>v[1]) return [v[1],v[0]]
return v
}
思路2: 位運(yùn)算 。
如果數(shù)組中只有一個(gè)出現(xiàn)一次的數(shù)，那遍歷數(shù)組做異或運(yùn)算就能求出那個(gè)出現(xiàn)一次的數(shù)?，F(xiàn)在要求的是出現(xiàn)兩次的數(shù)，如[a,3,3,b,2,2,1,1]我們要找得是a,b
那么大體思路就是 將原本的數(shù)組分成 [a,3,3…] ,[b,2,2…]這兩個(gè)數(shù)組分別做遍歷異或運(yùn)算最后得到的就是兩個(gè)只出現(xiàn)一次的數(shù)。
function FindNumsAppearOnce(array){
let t = 0
//t 相當(dāng)于 a ^ b
for(let i =0;i<array.length; i){
t = t^array[i]
}
let c = 1
//找到第一位a,b不相等的bit,用來做分組區(qū)分
while((t & c )==0) c<<=1
let a =0,b=0
for(let i = 0;i<array.length; i) {
if( (array[i] & c)==0) {
a = a^array[i]
}else {
b = b^array[i]
}
}
return a<b?[a,b]:[b,a]
}
八、NC77 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
描述
輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
示例1
輸入： [1,2,3,4] 返回值： [1,3,2,4]
示例2
輸入： [2,4,6,5,7]
返回值： [5,7,2,4,6]
最簡(jiǎn)單的辦法就是遍歷兩次數(shù)組，將奇數(shù)偶數(shù)分別填入copy空數(shù)組內(nèi)。
function reOrderArray( array ) {
let copy = []
for(let i =0;i<array.length; i) {
if(array[i]%2!=0) {
copy.push(array[i])
}
}
for(let i =0;i<array.length; i) {
if(array[i]%2==0) {
copy.push(array[i])
}
}
return copy
}
九、NC37 合并區(qū)間
描述 給出一組區(qū)間，請(qǐng)合并所有重疊的區(qū)間。 請(qǐng)保證合并后的區(qū)間按區(qū)間起點(diǎn)升序排列。
示例1
輸入： [[10,30],[20,60],[80,100],[150,180]]
返回值：
[[10,60],[80,100],[150,180]]
這道題的重點(diǎn)就是對(duì)區(qū)間的大小進(jìn)行判斷，我們要注意的是那些區(qū)間交叉的元素，并對(duì)這些交叉的元素進(jìn)行合并。直接貼出代碼。
function merge( intervals ) {
if(intervals.length==0) return intervals
//對(duì)區(qū)間排序
intervals.sort((a,b)=>{
return a.start - b.start
})
let res = []
res.push(intervals[0])
for(let i =1;i<intervals.length; i) {
let current = intervals[i]
let pre = res[res.length-1]
if(pre.end<current.start) {
res.push(current)
}else{
if(pre.end<current.end) {
let interval = new Interval(pre.start,current.end)
res.pop()
res.push(interval)
}
}
}
return res
}
十、NC95 數(shù)組中的最長(zhǎng)連續(xù)子序列
描述 給定無(wú)序數(shù)組arr，返回其中最長(zhǎng)的連續(xù)序列的長(zhǎng)度(要求值連續(xù)，位置可以不連續(xù),例如 3,4,5,6為連續(xù)的自然數(shù)）
示例1
輸入： [100,4,200,1,3,2] 返回值： 4
示例2
輸入： [1,1,1]
返回值： 1
思路: 這道題的意思就是找出給出數(shù)組中能排成連續(xù)的數(shù)如（1,2,3）最大的長(zhǎng)度能有多少？
那么我們可以用一個(gè)集合來保存數(shù)組中的所有數(shù)，然后遍歷數(shù)組，找到為連續(xù)數(shù)開頭的那個(gè)數(shù)就開始一個(gè)循環(huán) 1再判斷集合是否有這個(gè) 1的數(shù)，直到?jīng)]有我們記錄當(dāng)前連續(xù)數(shù)的長(zhǎng)度。
function MLS( arr ) {
if(arr.length==0||arr.length==1) return arr.length
let max = 1
let set = new Set()
for(let num of arr) {
set.add(num)
}
for(let num of arr) {
if(set.has(num-1)) continue
let start = num
while(set.has(start 1)) {
start
}
max = Math.max(max,start-num 1)
}
return max
}
OK，本算法系列的數(shù)組部分就精選了這10道題，有易有難。如果你看完之后覺得不錯(cuò)不要忘了給我點(diǎn)個(gè)贊哦！我一定會(huì)繼續(xù)認(rèn)真做好后面的章節(jié)！
由于本人技術(shù)水平有限，博客中難免出現(xiàn)的一些錯(cuò)誤，有紕漏之處懇請(qǐng)各位大佬不吝賜教！
|
