初级程序员进大厂必刷的100道算法题

叁歲伎倆 2022-10-10 15:52 202阅读 0赞

> ##### 碎碎念： #####
> 
> 亲爱的读者：你好！我的名字叫昌龙 【Changlon】 —— 一个非科班程序员、一个致力于前端的开发者、一个热爱生活且又时有忧郁的思考者。
> 
> 如果我的文章能给你带来一些收获，你的点赞收藏将是对我莫大的鼓励！
> 
> 我的邮箱:thinker\_changlon@163.com
> 
> 我的Github: [https://github.com/Changlon][https_github.com_Changlon]

**程序员之进大厂必刷算法题系列**  
数组  
字符串  
链表  
栈  
哈希  
二叉树  
二分算法  
分治算法(快排序)  
动态规划  
深度优先，广度优先算法  
递归，回溯算法  
贪心算法

### 文章目录 ###

*  一、NC22 合并两个有序的数组
 *  二、NC41 最长无重复子数组
 *  三、NC61 两数之和
 *  四、NC38 螺旋矩阵
 *  五、NC65 斐波那契数列
 *  六、NC18 顺时针旋转矩阵
 *  七、NC75 数组中只出现一次的两个数字
 *  八、NC77 调整数组顺序使奇数位于偶数前面
 *  九、NC37 合并区间
 *  十、NC95 数组中的最长连续子序列

# 一、NC22 合并两个有序的数组 #

> 描述 给出一个整数数组 A 和有序的整数数组B ，请将数组 B合并到数组 A中，变成一个有序的升序数组 注意：  
> 1.可以假设 A数组有足够的空间存放 B数组的元素，A 和 B中初始的元素数目分别为 m和 n，A的数组空间大小为 m+n  
> 2.不要返回合并的数组，返回是空的，将数组B 的数据合并到A里面就好了  
> 3.A数组在\[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\]  
> 复制  
> 返回值：  
> \[1,2,3,4,5,6\]

思路1: 首先将B数组中的数据拷贝到A的剩余空间中，然后对A数组使用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
    }

那么如果面试官这时候提了一个不能使用原型或类库函数的要求呢？我们不能使用sort库函数或原型函数。

思路2:因为A数组和B数组都是升序的，所以我们可以用双指针来处理这道题。  
初始化 m,n分别指向A和B的尾部。然后开始从尾部向前比较大小，谁的值大就放到A数组的后面。接着只移动那个较大的指针先前一个再继续比较。如果B中的数都比A中的大，那么遍历一遍正好都放满A的剩余空间。如果B中的最小值比A中的最小值小，那么遍历一遍过后n一定是大于0的，那就将B中前n个元素拷贝到A前n个位置中。

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最小数的数
    		if(n>0) { 
    			for(let i =0;i<n;++i) A[i] = B[i] 
    		}
    		
    		return A
    }

# 二、NC41 最长无重复子数组 #

> 描述 给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。  
> 子数组是连续的，比如\[1,3,5,7,9\]的子数组有\[1,3\]，\[3,5,7\]等等，但是\[1,3,7\]不是子数组  
>   
>   
> 示例1 输入：  
> \[2,3,4,5\]  
> 返回值： 4  
> 说明： \[2,3,4,5\]是最长子数组  
>   
>   
> 示例2 输入： \[2,2,3,4,3\]  
> 返回值： 3  
> 说明：\[2,3,4\]是最长子数组

思路1： 定义一个队列，遍历数组依次将数据添加至队列中，如果将要添加的内容与在队列中重复，则将重复的内容以及重复前面的内容循环出队列。之后再向队列中添加数据，接着比较是否是最长不重复子数组。

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指针指向数组首地址，然后依次将i向后移动，顺便将每次移动的值添加至一个map中。如果当前i所在的位置中的值在map中重复，则将j向后移动。

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]对于这种情况
    			//当i指向最后一个元素的时候因为1在之前出现过，
    			//所以j由理想的 j = 7 变成 j =3 这会影响max的值，
    			//所以需要加一个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 两数之和 #

> 描述 给出一个整数数组，请在数组中找出两个加起来等于目标值的数， 你给出的函数twoSum  
> 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的  
> 假设给出的数组中只存在唯一解 例如： 给出的数组为 \{20, 70, 110, 150\},目标值为90 输出 index1=1, index2=2

示例1

> 输入： \[3,2,4\],6
> 
> 返回值： \[2,3\]
> 
> 说明： 因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以输出\[2,3\]

思路: 维护一个哈希列表，遍历numbers数组，每次遍历存入哈希列表的key–>value是 （目标值 - 当前值）–> 下标  
已数组 \[3,2,4\]为列子,当遍历到2的时候哈希中存入了 3–>0,4–>1 当遍历到最后一个值时正好对应哈希中存入的 4–>1 所以说最后遍历的 下标2和哈希列表中对应4的下标1这两个对应的值和为6即目标值。

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 螺旋矩阵 #

> 描述  
> 给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

示例1

> 输入： \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\] 返回值： \[1,2,3,6,9,8,7,4,5\]

这道题主要调试需要费点功夫，就是回型遍历数组。只要能按照想法写出来就可以。本人实现了一个简陋的算法如下。通过一个marked二维数组来判断是否遍历过。

# 五、NC65 斐波那契数列 #

> 描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。 n≤39

老生常谈的题了。主要有两种解决思路。  
思路1: 递归  
时间复杂度：O(2^n)  
空间复杂度：递归栈的空间

function Fibonacci(n)
    { 
        if(n==0||n==1) return n 
    	return Fibonacci(n-1) + Fibonacci(n-2) 
    }

第一种方法只对刚入门的人来说比较简单一点，下面介绍一种动态规划的方法以及它的优化。时间复杂度 O(n),空间复杂 O(1)  
思路2:动态规划

//动态规划
    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]
    }
    
    //空间优化
    
    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 顺时针旋转矩阵 #

> 描述 有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。
> 
> 给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于300。

思路: 从底向上，从左向右遍历传过来的数组，然后将值一次输入到一个新的顺序遍历的数组中。

# 七、NC75 数组中只出现一次的两个数字 #

> 描述 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

示例1

> 输入：  
> \[1,4,1,6\]  
> 返回值：  
> \[4,6\]  
> 说明：  
> 返回的结果中较小的数排在前面

思路1: 用一个Map来存取所有数字出现的次数

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: 位运算 。  
如果数组中只有一个出现一次的数，那遍历数组做异或运算就能求出那个出现一次的数。现在要求的是出现两次的数，如\[a,3,3,b,2,2,1,1\]我们要找得是a,b  
那么大体思路就是 将原本的数组分成 \[a,3,3…\] ,\[b,2,2…\]这两个数组分别做遍历异或运算最后得到的就是两个只出现一次的数。

# 八、NC77 调整数组顺序使奇数位于偶数前面 #

> 描述  
> 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

示例1

> 输入： \[1,2,3,4\] 返回值： \[1,3,2,4\]

示例2

> 输入： \[2,4,6,5,7\]
> 
> 返回值： \[5,7,2,4,6\]

最简单的办法就是遍历两次数组，将奇数偶数分别填入copy空数组内。

# 九、NC37 合并区间 #

> 描述 给出一组区间，请合并所有重叠的区间。 请保证合并后的区间按区间起点升序排列。

示例1

> 输入： \[\[10,30\],\[20,60\],\[80,100\],\[150,180\]\]  
> 返回值：  
> \[\[10,60\],\[80,100\],\[150,180\]\]

这道题的重点就是对区间的大小进行判断，我们要注意的是那些区间交叉的元素，并对这些交叉的元素进行合并。直接贴出代码。

function merge( intervals ) { 
    
        if(intervals.length==0) return intervals
    	//对区间排序
    	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 数组中的最长连续子序列 #

> 描述 给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

示例1

> 输入： \[100,4,200,1,3,2\] 返回值： 4

示例2

> 输入： \[1,1,1\]
> 
> 返回值： 1

思路: 这道题的意思就是找出给出数组中能排成连续的数如（1,2,3）最大的长度能有多少？  
那么我们可以用一个集合来保存数组中的所有数，然后遍历数组，找到为连续数开头的那个数就开始一个循环+1再判断集合是否有这个+1的数，直到没有我们记录当前连续数的长度。

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，本算法系列的数组部分就精选了这10道题，有易有难。如果你看完之后觉得不错不要忘了给我点个赞哦！我一定会继续认真做好后面的章节！

--------------------

**由于本人技术水平有限，博客中难免出现的一些错误，有纰漏之处恳请各位大佬不吝赐教！**

[https_github.com_Changlon]: https://github.com/Changlon