前言
1.2021年已过半，“金九银十”笔试即将要开始,整理一些算法题一起学习。
2.我统一使用JavaScript(V8/Node)解答,都已经调试通过。
3.一起加油！一起进步！
1.排序
以下两个函数是排序中会用到的通用函数，就不一一写了
function checkArray(array) {
if (!array || array.length <= 2) return }
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}
2.时间复杂度
通常使用最差的时间复杂度来衡量一个算法的好坏。
常数时间 O(1) 代表这个操作和数据量没关系，是一个固定时间的操作，比如说四则运算。
对于一个算法来说，可能会计算出如下操作次数 aN + 1 ， N 代表数据量。那么该算法的时间复杂度就是 O(N)。因为我们在计算时间复杂度的时候，数据量通常是非常大的，这时候低阶项和常数项可以忽略不计。
当然可能会出现两个算法都是 O(N) 的时间复杂度，那么对比两个算法的好坏就要通过对比低阶项和常数项了。
3.位运算
位运算在算法中很有用，速度可以比四则运算快很多。
在学习位运算之前应该知道十进制如何转二进制，二进制如何转十进制。这里说明下简单的计算方式
- 十进制 33 可以看成是 32 + 1 ，并且 33 应该是六位二进制的（因为 33 近似 32 ，而 32 是 2
的五次方，所以是六位），那么 十进制 33 就是 100001 ，只要是 2 的次方，那么就是 1否则都为 0 - 那么二进制 100001 同理，首位是 2^5 ，末位是 2^0 ，相加得出 33
4.左移 <<
10 << 1 // -> 20
左移就是将二进制全部往左移动， 10 在二进制中表示为 1010 ，左移一位后变成 10100 ，转换为十进制也就是 20，所以基本可以把左移看成以下公式 a * (2 ^ b)
5.算数右移 >>
10 >> 1 // -> 5
算数右移就是将二进制全部往右移动并去除多余的右边， 10 在二进制中表示为 1010 ，右移一位后变成 101 ，转换为十进制也就是 5，所以基本可以把右移看成以下公式 int v = a / (2 ^ b)
右移很好用，比如可以用在二分算法中取中间值
13 >> 1 // -> 6
6.最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 动态规划
res = cur = nums[0]
for i in range(1, len(nums)):
cur = max(nums[i], cur + nums[i])
res = max(res, cur)
return res
动态规划。时间复杂度O(n), 空间复杂度 O(1)。
7.链表
面试题：反转单向链表
题目需要将一个单向链表反转。思路很简单，使用三个变量分别表示当前节点和当前节点的前后节点，虽然这题很简单，但是却是一道面试常考题
以下是实现该算法的代码
var reverseList = function(head)
{
// 判断下变量边界问题
if (!head || !head.next) return head
// 初始设置为空，因为第一个节点反转后就是尾部，尾部节点指向 null
let pre = null
let current = head
let next
// 判断当前节点是否为空
// 不为空就先获取当前节点的下一节点
// 然后把当前节点的 next 设为上一个节点
// 然后把 current 设为下一个节点，pre 设为当前节点
while(current) {
next = current.next
current.next = pre
pre = current
current = next
}
return pre
};
8.二叉树的先序，中序，后序遍历
先序遍历表示先访问根节点，然后访问左节点，最后访问右节点。
中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。
后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。
9.递归实现
递归实现相当简单，代码如下
function TreeNode(val)
{
this.val = val;
this.left = this.right = null;
}
var traversal = function(root) {
if (root)
{
// 先序
console.log(root);
traversal(root.left);
// 中序
// console.log(root);
traversal(root.right);
// 后序
// console.log(root);
}
};
10.树的深度
面试题：树的最大深度（题目需要求出一颗二叉树的最大深度）
以下是算法实现
var maxDepth = function(root)
{
if (!root) return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};
11.动态规划
动态规划背后的基本思想非常简单。就是将一个问题拆分为子问题，一般来说这些子问题都是非常相似的，那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。
一旦得出每个子问题的解，就存储该结果以便下次使用。
12.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
以下是实现该算法的代码
function mergeTwoLists(l1, l2) {
if (l1 = null && l2 == null) {
return null;
}
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
使用递归完成迭代
13.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
//反转链表
function reverseList(head){
//1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面
//（在这里我们存的节点的值，而不是存的整个节点，这样是可以节约内存的）
let arr=[];//arr用于存储链表的节点的值
let p=head;//p用于遍历链表
while(p){
arr.push(p.val);
p=p.next;
}
//2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转
//（我们没有考虑新建一个链表，而是用了原来的链表，可以节约创建新链表的时间和内存）
p=head;
while(p){
p.val=arr.pop();
p=p.next;
}
return head;
}
1、遍历链表，把链表里面的每个节点的值都拿下来，存在数组里面
2、再次遍历链表，将数组里面的值倒序的赋值给每一个节点的val域就实现了链表的反转
14.二分查找算法（建立在已经排好序的情况下）
function binarySearch(arr, data) {
var end = arr.length - 1,
start = 0;
while (start <= end) {
var middle = Math.floor((start + end) / 2);
if (arr[middle] > data) {
end = middle - 1;
} else if (arr[middle] < data) {
start = middle + 1;
} else {
return middle;
}
}
return -1;
}
var arr = [1, 2, 3, 4, 5, 6];
console.log(binarySearch(arr, 2));
15.斐波那契数列
相信大家都不陌生,在高中数学中都有接触过,斐波那契数列以如下被以递推的方法定义：
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
实现过程
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。
以下是实现该算法的代码
/**
* @param {number} N
* @return {number}
*/
var fib = function(N) {
if (N<2) return N;
var frist = 0;
var second = 1;
for (var i=2;i<=N;i++) {
second = frist + second;
frist = second - frist;
}
return second;
};
for循环，用两个变量保存前两项斐波那契数即可。并且变量交换时也无需临时变量,空间复杂度O(N)
16.找出下列正数组的最大差值
输入 [10,5,11,7,8,9]
输出 6
这是通过一道题目去测试对于基本的数组的最大值的查找，很明显我们知道，最大差值肯定是一个数组中最大值与最小值的差。
function getMaxProfit(arr) {
var minPrice = arr[0];
var maxProfit = 0;
for (var i = 0; i < arr.length; i++) {
var currentPrice = arr[i];
minPrice = Math.min(minPrice, currentPrice);
var potentialProfit = currentPrice - minPrice;
maxProfit = Math.max(maxProfit, potentialProfit);
}
return maxProfit;
}
17.随机生成指定长度的字符串
实现一个算法，随机生成指制定长度的字符窜。
以下是实现算法的代码
比如给定 长度 8 输出 4ldkfg9j
function randomString(n) {
let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
let tmp = '',
i = 0,
l = str.length;
for (i = 0; i < n; i++) {
tmp += str.charAt(Math.floor(Math.random() * l));
}
return tmp;
}
module.exports = randomString;
18.找到任意两个数字的最大和
找到两个最大的数并返回它们的和。
function topSum(arr){
if(arr.length<2) return null;
var first,second;
if(arr[0]>arr[1]){
first = arr[0];
second=arr[1];
}else{
first = arr[1];
second=arr[0];
}
for(var i=2;i<arr.length;i++){
if(arr[i]>first){
second = first;
first = arr[i];
}else if(arr[i]>second){
second = arr[i];
}
}
return first+second;
}
19.去掉一组整型数组重复的值
比如输入: [1,13,24,11,11,14,1,2]
输出: [1,13,24,11,14,2]
需要去掉重复的11 和 1 这两个元素。
这道问题出现在诸多的前端面试题中，主要考察个人对Object的使用，利用key来进行筛选。
/**
* unique an array
**/
let unique = function(arr) {
let hashTable = {};
let data = [];
for(let i=0,l=arr.length;i<l;i++) {
if(!hashTable[arr[i]]) {
hashTable[arr[i]] = true;
data.push(arr[i]);
}
}
return data
}
module.exports = unique;
20.替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.
则经过替换之后的字符串为We%20Are%20Happy
解题思路：利用简单的正则获取空格,并且替换成%20即可。
部分正则规则:/g 匹配所有符合条件的元素.
\d：表示数字 ^：表示开头 $：表示结尾 +：匹配多个
例如: ^\d+$ 匹配的字符串只能是数字
let readline = require('readline');
let rl = readline.createInterface({
input:process.stdin,
output:process.stdout
})
rl.on('line',function(input){
// let result = deal(input);
let result = input.trim().replace(/ /g,'%20'); //replace(获取值,替换值)
console.log(result);
return result;
})
21.实现一个函数，判断输入是不是回文字符串
function isPlalindrome(input) {
if (typeof input !== 'string') return false;
return input.split('').reverse().join('') === input;
}
22.腾讯：数组扁平化、去重、排序
面试题
已知如下数组：var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组
let arr =[[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]
function newArray ( ) {
while(arr.some(Array.isArray)){
arr = [].concat(...arr)
}
arr = [...new Set(arr)].sort((a,b)=>{
return a-b
})
return arr
}
newArray()
console.log(arr);
23.编写一个函数计算多个数组的交集
要求：输出结果中的每个元素一定是唯一的
const getIntersection = (...arrs) => {
return Array.from(new Set(arrs.reduce((total, arr) => {
return arr.filter(item => total.includes(item));
})));
}
24.选择排序
选择排序是从数组的开头开始，将第一个元素和其他元素作比较，检查完所有的元素后，最小的放在第一个位置，接下来再开始从第二个元素开始，重复以上一直到最后。
很简单嘛：外层循环从0开始到length-1， 然后内层比较，最小的放开头
function selectSort(arr) {
var len = arr.length;
for(let i = 0 ;i < len - 1; i++) {
for(let j = i ; j<len; j++) {
if(arr[j] < arr[i]) {
[arr[i],arr[j]] = [arr[j],arr[i]];
}
}
}
return arr
}
- 外层循环的i表示第几轮，arr[i]就表示当前轮次最靠前(小)的位置；
- 内层从i开始，依次往后数，找到比开头小的，互换位置即可
25.爬楼梯问题
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？
分析： 这个问题要倒过来看，要到达n级楼梯，只有两种方式，从（n-1）级 或 （n-2）级到达的。所以可以用递推的思想去想这题，假设有一个数组s[n], 那么s[1] = 1（由于一开始就在第一级，只有一种方法）， s[2] = 1（只能从s[1]上去 没有其他方法）。
那么就可以推出s[3] ~ s[n]了。
下面继续模拟一下， s[3] = s[1] + s[2]， 因为只能从第一级跨两步， 或者第二级跨一步。
function cStairs(n) {
if(n === 1 || n === 2) {
return 1;
} else {
return cStairs(n-1) + cStairs(n-2)
}
}
没错，其实就是斐波纳契数列
26.栈实现队列
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。
示例：
let queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
解题思路
既然栈是先进后出, 要想得到先进先出的效果，我们不妨用两个栈。
当进行push操作时，push 到 stack1，而进行pop和peek的操作时，我们通过stack2。
当然这其中有一个特殊情况，就是stack2是空，如何来进行pop和peek? 很简单，把stack1中的元素依次 pop 并推入stack2中，然后正常地操作 stack2即可，如下图所示:
这就能保证先入先出的效果了。
以下是实现该算法的代码
var MyQueue = function() {
this.stack1 = [];
this.stack2 = [];
};
MyQueue.prototype.push = function(x) {
this.stack1.push(x);
};
// 将 stack1 的元素转移到 stack2
MyQueue.prototype.transform = function() {
while(this.stack1.length) {
this.stack2.push(this.stack1.pop());
}
}
MyQueue.prototype.pop = function() {
if(!this.stack2.length) this.transform();
return this.stack2.pop();
};
MyQueue.prototype.peek = function() {
if(!this.stack2.length) this.transform();
return this.stack2[this.stack2.length - 1];
};
MyQueue.prototype.empty = function() {
return !this.stack1.length && !this.stack2.length;
};
27.队列实现栈
和上一题的效果刚好相反，用队列先进先出的方式来实现先进后出的效果。
解题思路
以上面的队列为例，push 操作好说，直接从在队列末尾推入。但 pop 和 peek 呢？
回到我们的目标，我们的目标是拿到队尾的值，也就是3。这就好办了，我们让前面的元素统统出队，只留队尾元素即可，剩下的元素让另外一个队列保存。
代码实现
var MyStack = function() {
this.queue1 = [];
this.queue2 = [];
};
MyStack.prototype.push = function(x) {
if(!this.queue2.length) this.queue1.push(x);
else {
// queue2 已经有值
this.queue2.push(x);
// 旧的栈顶移到 queue1 中
this.queue1.push(this.queue2.shift());
}
};
MyStack.prototype.transform = function() {
while(this.queue1.length !== 1) {
this.queue2.push(this.queue1.shift())
}
// queue2 保存了前面的元素
// 让 queue1 和 queue2 交换
// 现在queue1 包含前面的元素，queue2 里面就只包含队尾的元素
let tmp = this.queue1;
this.queue1 = this.queue2;
this.queue2 = tmp;
}
MyStack.prototype.pop = function() {
if(!this.queue2.length) this.transform();
return this.queue2.shift();
};
MyStack.prototype.top = function() {
if(!this.queue2.length) this.transform();
return this.queue2[0];
};
MyStack.prototype.empty = function() {
return !this.queue1.length && !this.queue2.length;
};
实现过程中，值得注意的一点是，queue1 始终保存前面的元素，queue2 始终保存队尾元素（即栈顶元素 ）。
但是当 push 的时候有一个陷阱，就是当queue2已经有元素的时候，不能将新值 push 到 queue1，因为此时的栈顶元素应该更新。此时对于新的值来说，应先 push 到 queue2， 然后将旧的栈顶从queue2出队，推入 queue1，这样就实现了更新栈顶的操作。
28.双指针问题
最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
解题思路： 先按照升序排序，然后分别从左往右依次选择一个基础点 i（0 <= i <= nums.length - 3），在基础点的右侧用双指针去不断的找最小的差值。
假设基础点是 i，初始化的时候，双指针分别是：
- left：i + 1，基础点右边一位。
- right: nums.length - 1 数组最后一位。
然后求此时的和，如果和大于 target，那么可以把右指针左移一位，去试试更小一点的值，反之则把左指针右移。
在这个过程中，不断更新全局的最小差值 min，和此时记录下来的和 res。最后返回 res 即可。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
let threeSumClosest = function (nums, target) {
let n = nums.length
if (n === 3) {
return getSum(nums)
}
// 先升序排序 此为解题的前置条件
nums.sort((a, b) => a - b)
let min = Infinity // 和 target 的最小差
let res
// 从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个
for (let i = 0; i <= nums.length - 3; i++) {
let basic = nums[i]
let left = i + 1 // 左指针先从 i 右侧的第一位开始尝试
let right = n - 1 // 右指针先从数组最后一项开始尝试
while (left < right) {
let sum = basic + nums[left] + nums[right] // 三数求和
// 更新最小差
let diff = Math.abs(sum - target)
if (diff < min) {
min = diff
res = sum
}
if (sum < target) {
// 求出的和如果小于目标值的话 可以尝试把左指针右移 扩大值
left++
} else if (sum > target) {
// 反之则右指针左移
right--
} else {
// 相等的话 差就为0 一定是答案
return sum
}
}
}
return res
}
function getSum(nums) {
return nums.reduce((total, cur) => total + cur, 0)
}
