# 数据结构与算法
lastUpdated: 2023-8-10
# 如何分析时间复杂度?
当问题规模即要处理的数据增长时，基本操作要重复执行的次数必定也会增长，那么我们关心地是这个执行次数以什么样的数量级增长。
我们用大O表示法表示一下常见的时间复杂度量级：
常数阶O(1) 线性阶O(n) 对数阶O(logn) 线性对数阶O(nlogn) 平方阶O(n²)
当然还有指数阶和阶乘阶这种非常极端的复杂度量级，我们就不讨论了。
O(1) 传说中的常数阶的复杂度，这种复杂度无论数据规模n如何增长，计算时间是不变的。
举一个简单的例子：
const increment = n => n++
不管n如何增长，都不会影响到这个函数的计算时间，因此这个代码的时间复杂度都是O(1)。
O(n) 线性复杂度，随着数据规模n的增长，计算时间也会随着n线性增长。
典型的O(n)的例子就是线性查找。
const linearSearch = (arr, target) => {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i
}
}
return -1
}
线性查找的时间消化与输入的数组数量n成一个线性比例，随着n规模的增大，时间也会线性增长。
O(logn) 对数复杂度，随着问题规模n的增长，计算时间也会随着n对数级增长。
典型的例子是二分查找法。
function binarySearch(arr, target) {
let max = arr.length - 1
let min = 0
while (min <= max) {
let mid = Math.floor((max + min) / 2)
if (target < arr[mid]) {
max = mid - 1
} else if (target > arr[mid]) {
min = mid + 1
} else {
return mid
}
return -1
}
}
在二分查找法的代码中，通过while循环，成 2 倍数的缩减搜索范围，也就是说需要经过 log2^n 次即可跳出循环。
事实上在实际项目中，O(logn)是一个非常好的时间复杂度，比如当n=100的数据规模时，二分查找只需要7次，线性查找需要100次，这对于计算机而言差距不大，但是当有10亿的数据规模的时候，二分查找依然只需要30次，而线性查找需要惊人的10亿次，O(logn)时间复杂度的算法随着数据规模的增大，它的优势就越明显。
O(nlogn) 线性对数复杂度，随着数据规模n的增长，计算时间也会随着n呈线性对数级增长。
这其中典型代表就是归并排序，我们会在对应小节详细分析它的复杂度。
const mergeSort = array => {
const len = array.length
if (len < 2) {
return array
}
const mid = Math.floor(len / 2)
const first = array.slice(0, mid)
const last = array.slice(mid)
return merge(mergeSort(fist), mergeSort(last))
function merge(left, right) {
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
}
O(n²) 平方级复杂度，典型情况是当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了，代表应用是冒泡排序算法。
function bubleSort(arra){
var temp;
for(var i=0;i<arra.length;i++){
for(var j=0;j<arra.length-i-1;j++){
if(arra[j]>arra[j+1]){
temp=arra[j];
arra[j]=arra[j+1];
arra[j+1]=temp;
}
}
};
return arra;
}
# 排序算法
排序算法有很多种,我们只讲最具代表性的几种算法： 冒泡排序、希尔排序、归并排序、快速排序
排序算法主体内容采用的是十大经典排序算法总结（JavaScript描述）,更详细的内容可以移步,因为作者的内容与教科书上的内容有较大冲突,因此我们重写了快速排序部分的内容,以教科书为准,因此建议重点读一下本文的快速排序部分.
# 冒泡排序（Bubble Sort）
实现思路:
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
实现:
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
var temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
https://blog.csdn.net/weixin_42181512/article/details/131033606 改进1: 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
function bubbleSort2(arr) {
console.time('改进后冒泡排序耗时');
var i = arr.length-1; //初始时,最后位置保持不变
while ( i> 0) {
var pos= 0; //每趟开始时,无记录交换
for (var j= 0; j< i; j++)
if (arr[j]> arr[j+1]) {
pos= j; //记录交换的位置
var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
}
i= pos; //为下一趟排序作准备
}
console.timeEnd('改进后冒泡排序耗时');
return arr;
}
改进2: 传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
function bubbleSort3(arr3) {
var low = 0;
var high= arr.length-1; //设置变量的初始值
var tmp,j;
console.time('2.改进后冒泡排序耗时');
while (low < high) {
for (j= low; j< high; ++j) //正向冒泡,找到最大者
if (arr[j]> arr[j+1]) {
tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
}
--high; //修改high值, 前移一位
for (j=high; j>low; --j) //反向冒泡,找到最小者
if (arr[j]<arr[j-1]) {
tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
}
++low; //修改low值,后移一位
}
console.timeEnd('2.改进后冒泡排序耗时');
return arr3;
}
动画:
# 希尔排序(Shell Sort）
1959年Shell发明； 第一个突破O(n^2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序
算法简介 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。
算法描述和实现 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 按增量序列个数k，对序列进行k 趟排序； 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 Javascript代码实现：
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
console.time('希尔排序耗时:');
while(gap < len/5) { //动态定义间隔序列
gap =gap*5+1;
}
for (gap; gap > 0; gap = Math.floor(gap/5)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
console.timeEnd('希尔排序耗时:');
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
希尔排序图示（图片来源网络）：
算法分析 最佳情况：T(n) = O(nlog2 n)
最坏情况：T(n) = O(nlog2 n)
平均情况：T(n) =O(nlog n)
# 归并排序（Merge Sort）
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
算法简介 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述和实现 具体算法描述如下：
把长度为n的输入序列分成两个长度为n/2的子序列； 对这两个子序列分别采用归并排序； 将两个排序好的子序列合并成一个最终的排序序列。 Javscript代码实现:
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
console.time('归并排序耗时');
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
console.timeEnd('归并排序耗时');
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
归并排序进行相关说明分析
https://zhuanlan.zhihu.com/p/124356219 归并排序动图演示:
这里写图片描述
算法分析 最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
# 快速排序（Quick Sort）
算法简介
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述和实现
1.从数组中选择中间一项作为主元；
2.创建两个指针，左边一个指向数组的第一项，右边指向数组最后一项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素。然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程是的比主元小的值都排在了主元之前，而比主元大的值都排在了主元之后，这一步叫划分操作。
3.接着，算法对划分的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组以完全排序。
// 快速排序
const quickSort = (function() {
// 默认状态下的比较函数
function compare(a, b) {
if (a === b) {
return 0
}
return a < b ? -1 : 1
}
function swap(array, a, b) {
[array[a], array[b]] = [array[b], array[a]]
}
// 分治函数
function partition(array, left, right) {
// 用index取中间值而非splice
const pivot = array[Math.floor((right + left) / 2)]
let i = left
let j = right
while (i <= j) {
while (compare(array[i], pivot) === -1) {
i++
}
while (compare(array[j], pivot) === 1) {
j--
}
if (i <= j) {
swap(array, i, j)
i++
j--
}
}
return i
}
// 快排函数
function quick(array, left, right) {
let index
if (array.length > 1) {
index = partition(array, left, right)
if (left < index - 1) {
quick(array, left, index - 1)
}
if (index < right) {
quick(array, index, right)
}
}
return array
}
return function quickSort(array) {
return quick(array, 0, array.length - 1)
}
})()
const quickSort = arr => {
if ( toString.call(arr) !== '[object Array]' || arr.length <= 1 ) {
return arr
}
const pivotIndex = Math.floor(arr.length / 2)
const pivot = arr.splice(pivotIndex, 1)[0]
const leftArr = []
const rightArr = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
leftArr.push(arr[i])
} else {
rightArr.push(arr[i])
}
}
// return quickSort(leftArr).concat([pivot], quickSort(rightArr))
return [ ...quickSort(leftArr), pivot, ...quickSort(rightArr) ]
}
算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
# 查找算法
# 二分查找法
算法简介
折半查找算法要求查找表的数据是线性结构存储，还要求查找表中的顺序是由小到大排序（由大到小排序）
算法思路及实现
首先设两个指针，low和height，表示最低索引和最高索引
然后取中间位置索引middle，判断middle处的值是否与所要查找的数相同，相同则结束查找，middle处的值比所要查找的值小就把low设为middle+1，如果middle处的值比所要查找的值大就把height设为middle-1
然后再新区间继续查到，直到找到或者low>height找不到所要查找的值结束查找
// 非递归方式
function binarySearch(arr, target) {
let max = arr.length - 1
let min = 0
while (min <= max) {
let mid = Math.floor((max + min) / 2)
if (target < arr[mid]) {
max = mid - 1
} else if (target > arr[mid]) {
min = mid + 1
} else {
return mid
}
}
return -1
}
// 递归方式
function binarySearch(arr,findVal,leftIndex,rightIndex) {
if(leftIndex>rightIndex){
return -1;
}
var midIndex=Math.floor((leftIndex+rightIndex)/2);
var midVal=arr[midIndex];
if(midVal>findVal){
return binarySearch(arr,findVal,leftIndex,midIndex-1);
}else if(midVal<findVal){
return binarySearch(arr,findVal,midIndex+1,rightIndex);
}else{
return midIndex;
}
}
算法分析
最佳情况：T(n) = O(logn) 最差情况：T(n) = O(logn) 平均情况：T(n) = O(logn)
# 线性查找
算法简介及实现
线性查找很简单,只需要进行简单的遍历即可.
const linearSearch = (arr, target) => {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i
}
}
return -1
}
算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n) 平均情况：T(n) = O(n)
# 算法案例总结
# 5只鸡5天下5个鸡蛋，几只鸡100天可以下100个鸡蛋
答案：5
详细分析如下：
设一只鸡平均一天生x个蛋， 根据条件5只鸡5天生了5只蛋，可知5x5=5，解方程可知，x=0.2； 根据问题，100天内要100个蛋，设需要y只鸡，可列方程1000.2y=100，解方程可知，y=5， 因此，需要5只鸡。
# 正方形队列，一行一列共19个人，问总共多少人**
答案：100
# 1000杯水，1杯是毒药，给你小白鼠，小白鼠一次只能喝一杯，怎么最快可以找到毒药。
答案：最快就是1000只一起喝，死的就是。小白鼠数量最少就是二分查找
# 一只青蛙一次可以跳上1级台阶,也可以跳上2级.求该青蛙跳上一个n级的台阶总共有多少种跳法
答案：青蛙每一次跳跃只有两种选择:一是再跳1级阶梯到达第n级阶梯,此时小青蛙处于第n-1级阶梯;或者再跳2级阶梯到达第n级阶梯,此时小青蛙处于n-2级阶梯。
于是,n级阶梯的跳法总是依赖于前n-1级阶梯的跳法总数f(n-1)和前n-2级阶梯的跳法总数f(n-2).因为只有两种可能性,所以,f(n)=f(n-1)+f(n-2); 递推公式f(n)=f(n-1)+f(n-2):很熟悉,就是斐波那契数列求和 验证一下,青蛙1级有1种跳法,2级有2种跳法,3级有3种跳法,4级有5种跳法.... 使用两种方式来求,递归算法和非递归算法 代码如下
// 递归算法
// 缺点:太占空间,效率低下,计算到n时,总要依赖前一个n-1再算一遍
function JumpFloor1(n) {
if (n < 0) {
return 0;
} else if (n == 0 || n == 1 || n == 2) {
return n;
}
return JumpFloor1(n - 1) + JumpFloor1(n - 2);
}
// 递归优化
// 记忆函数
let memoizer = function(fn) {
let memo = [];
return function(n) {
if(memo[n] === undefined) {
memo[n] = fn(n)
}
return memo[n]
}
}
let fn = memoizer((n)=> {
if(n === 0) return 0;
if(n === 1 || n === 2) return 1;
return fn(n - 2) + fn(n - 1);
})
// 非递归算法
// 时间复杂度O(n)
// 空间复杂度O(1)
function JumpFloor1(n) {
if (n < 0) {
return 0;
}
if (n == 0 || n == 1 || n == 2) {
return n;
}
let f1 = 1;
let f2 = 2;
let result = 0;
for (let i = 3; i <= n; i++) {
result = f1 + f2;
f1 = f2;
f2 = result;
}
return result;
}
// for循环+解构赋值
let fn = (n) => {
let n1 = 1,n2 = 1,sum = 0;
for(let i=2;i<n;i++) {
[n1,n2] = [n2,n1+n2]
}
return n2;
}
# 有十瓶药，其中有一瓶是假药，每一瓶都有100颗药，真药每一颗10G，假药每一颗9G，有一个小称，只称一次，如何找到假药
答案：将10瓶药编好号，第1号取一粒，第2号取2粒，第三号取3粒....第10号取10粒，用天秤称得重量为x，用550-x得出的结果是那瓶假药
# 有十瓶药，其中有两瓶是假药，每一瓶都有100颗药，真药每一颗10G，假药每一颗9G，有一个小称，只称一次，如何找到假药
答案：制作瓶贴号：1、11、23、37、43、51、67、71、83、91分别随机贴在各瓶药瓶上,并按瓶贴的数字从各瓶药中取出相应数量的药片,并进行称重,按照每片药片都是10G来算,取出的药片总重应为以上数字相加=466克,又知,取出的药片中,每取出一片9克重的药片会使取出药片的总重减轻1克,故将实际466克-实际取出药片重量=取出药片数量,以上所给出的数字两两相加所得数值皆为唯一,故可知较轻的药片是从哪两个药瓶里取出的,举例若实际重量为432克,则共有466-432=34片重9克的药片被取出,由取出药片数可知有唯一11+23=34故贴有11与23标签的瓶内的两瓶药较轻,当然,瓶贴的数字也可由其他数组组成,关键是保证每两个数字相加的和在数组中唯一,故我所取的都为质数,且相差数值较大。
# 如果你有两个桶，一个装的是红色的颜料，另一个装的是蓝色的颜料。你从蓝色颜料桶里舀一杯，倒入红色颜料桶，再从红色颜料桶里舀一杯倒入蓝颜料桶。两个桶中红蓝颜料的比例哪个更高？通过算术的方式来证明这一点
答案：假设桶各有10L颜料，满瓢为1L，那么第一次操作后。蓝桶有9L，100%纯度，红桶有11L，10/11纯度。第二次操作后，蓝桶有10L，9+（1/11）/9+1=90.91%纯度。红桶有10L，10/11=90.91%，所以是一样多的。
# 复原IP地址（递归）JS
给定⼀个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间⽤ '.' 分隔。
⽰例:
输⼊: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
var restoreIpAddresses = function (str) {
// 保存所有符合条件的IP地址
let res = [];
// 递归函数
let search = (cur, sub) => {
// 如果剩下的位数超过12位，就说明是非法的
if (sub.length > 12) return
// 边界条件，已经分完一种情况了，就将它push到res中
if (cur.length === 4 && cur.join("") === str) {
res.push(cur.join('.'))
} else {
// 还没分完。正常处理情况
// 如果剩下的数字不到3个了，就按照剩下的循环；否则按照三位循环
for (let i = 0, len = Math.min(3, sub.length), tmp; i < len; i++) {
// 取出从0开始，i+1长度的子串，也就是1~len的子串
tmp = sub.substr(0, i + 1)
// 对取出的子串验证是否合法
if (tmp - 256 < 0) { // 小于255合法
// 将这个合法的数字格式化（去掉前面的0），递归调用，进行下一次
search(cur.concat([tmp * 1]), sub.substr(i + 1))
}
}
}
}
// 第一次调用
search([], str)
return res
};
console.log(restoreIpAddresses("25525511135"))
# Nim 游戏桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
/\*\*
\* @param {number} n
\* @return {boolean}
\*/
var canWinNim = function(n) {
return n % 4 === 0 ? false : true
};
n = 4 false n = 1 true n = 2 true
# 灯泡开关
初始时有 n 个灯泡处于关闭状态。
对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。
第 1 轮，每个灯泡切换一次开关。即，打开所有的灯泡。
第 2 轮，每两个灯泡切换一次开关。 即，每两个灯泡关闭一个。
第 3 轮，每三个灯泡切换一次开关。
第 i 轮，每 i 个灯泡切换一次开关。 而第 n 轮，你只切换最后一个灯泡的开关。
找出 n 轮后有多少个亮着的灯泡。
var bulbSwitch = function(n) {
return Math.floor(Math.sqrt(n))
};
# 在LR字符串中交换相邻字符
在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。
/\*\*
\* @param {string} start
\* @param {string} end
\* @return {boolean}
\*/
var canTransform = function(start, end) {
let copyStart = start,copyEnd = end;
if(copyStart.replace(/X/g,'') !== copyEnd.replace(/X/g,'')) {
return false;
}
let p1 = p2 = 0;
while(p1 < start.length && p2 < end.length) {
while(start\[p1\] === 'X') {
p1++
}
while(end\[p2\] === 'X') {
p2++
}
if (start[p1] !== end[p2]) {
return false
} else {
if ((start[p1] === 'L' && p1 p2)) {
return false
}
}
p1++;
p2++;
}
return true
};
# 移动石子直到连续
三枚石子放置在数轴上，位置分别为 a，b，c。
每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答 案：answer = [minimum_moves, maximum_moves]
/\*\*
\* @param {number} a
\* @param {number} b
\* @param {number} c
\* @return {number\[\]}
\*/
var numMovesStones = function(a, b, c) {
let temp = [a,b,c];
temp.sort((a,b)=>a-b);
if(temp[1]-temp[0]==1 && temp[2]-temp[1]==1) return [0,0];
let min=0;
let max=0;
if(temp[1]-temp[0]==1 || temp[2]-temp[1]==1 || temp[1]-temp[0]==2 || temp[2]- temp[1]==2) min=1;
else min =2;
max = getSteps(temp[0],temp[1])+getSteps(temp[1],temp[2]);
return [min,max];
};
var getSteps = function(a,b){
if(b-a-1>0) return b-a-1;
else return 0;
};
# 飞机座位分配概率
有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
剩下的乘客将会：
如果他们自己的座位还空着，就坐到自己的座位上，
当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？
/\*\*
\* @param {number} n
\* @return {number}
\*/
var nthPersonGetsNthSeat = function(n) {
return n === 1 ? 1 : 0.5
};
# 所有蚂蚁掉下来前的最后一刻
有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。
而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻### 解题思路 蚂蚁都一样，相撞即为穿过，所以只需要找到向右爬行的蚂蚁中起始位置距离终点最远的 和向左爬行的蚂蚁中起始位置距离板子起点最远的距离，比较大的那个，返回即可
/**
* @param {number} n
* @param {number[]} left
* @param {number[]} right
* @return {number}
*/
var getLastMoment = function(n, left, right) {
return Math.max(
n - Math.min(...right), // 向右爬行距离最远的
Math.max(...left) // 向左爬行距离最远的
);
};
BFS 模拟过程
/\*\*
\* @param {number} n
\* @param {number\[\]} left
\* @param {number\[\]} right
\* @return {number}
\*/
var getLastMoment = function(n, left, right) {
let sec = 0;
// 模拟蚂蚁爬行的过程
while (true) {
let l = left.length,
r = right.length;
for (let i = 0; i < l; i++) {
left[i] -= 1;
if (left[i] < 0) {
left.splice(i, 1);
i--;
l--;
}
}
for (let i = 0; i < r; i++) {
right[i] += 1;
if (right[i] > n) {
right.splice(i, 1);
i--;
r--;
}
}
if (left.length === 0 && right.length === 0) break;
sec++;
}
return sec;
};
1+2+...+n
1+2+...+n=n(1+n)/2
function addNum(n) {
let result = 0;
for(let i=0;i<n.length;i++) {
result += n[i]
}
return result;
}
# 字符串相关实现
# 解析 URL Params 为对象
let url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';
parseParam(url)
/* 结果
{ user: 'anonymous',
id: [ 123, 456 ], // 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
city: '北京', // 中文需解码
enabled: true, // 未指定值得 key 约定为 true
}
*/
function parseParam(url) {
const paramsStr = /.+\?(.+)$/.exec(url)[1]; // 将 ? 后面的字符串取出来
const paramsArr = paramsStr.split('&'); // 将字符串以 & 分割后存到数组中
let paramsObj = {};
// 将 params 存到对象中
paramsArr.forEach(param => {
if (/=/.test(param)) { // 处理有 value 的参数
let [key, val] = param.split('='); // 分割 key 和 value
val = decodeURIComponent(val); // 解码
val = /^\d+$/.test(val) ? parseFloat(val) : val; // 判断是否转为数字
if (paramsObj.hasOwnProperty(key)) { // 如果对象有 key，则添加一个值
paramsObj[key] = [].concat(paramsObj[key], val);
} else { // 如果对象没有这个 key，创建 key 并设置值
paramsObj[key] = val;
}
} else { // 处理没有 value 的参数
paramsObj[param] = true;
}
})
return paramsObj;
}
# 模板引擎实现
let template = '我是{{name}}，年龄{{age}}，性别{{sex}}';
let data = {
name: '姓名',
age: 18
}
render(template, data); // 我是姓名，年龄18，性别undefined
function render(template, data) {
const reg = /\{\{(\w+)\}\}/; // 模板字符串正则
if (reg.test(template)) { // 判断模板里是否有模板字符串
const name = reg.exec(template)[1]; // 查找当前模板里第一个模板字符串的字段
template = template.replace(reg, data[name]); // 将第一个模板字符串渲染
return render(template, data); // 递归的渲染并返回渲染后的结构
}
return template; // 如果模板没有模板字符串直接返回
}
# 转化为驼峰命名
var s1 = "get-element-by-id"
// 转化为 getElementById
var f = function(s) {
return s.replace(/-\w/g, function(x) {
return x.slice(1).toUpperCase();
})
}
# 查找字符串中出现最多的字符和个数
例: abbcccddddd -> 字符最多的是d，出现了5次
let str = "abcabcabcbbccccc";
let num = 0;
let char = '';
// 使其按照一定的次序排列
str = str.split('').sort().join('');
// "aaabbbbbcccccccc"
// 定义正则表达式
let re = /(\w)\1+/g;
str.replace(re,($0,$1) => {
if(num < $0.length){
num = $0.length;
char = $1;
}
});
console.log(`字符最多的是${char}，出现了${num}次`);
let findStr = (str) => {
let num = 0, char = '',result = {};
let strArr = str.split('').sort().join('');
let reg = /(\w)\1+/g;
strArr.replace(reg, ($1, $2) => {
if (num < $1.length) {
num = $1.length
char = $2
}
})
result[char] = num
return result
}
# 找出字符串中连续出现最多的字符和个数
let findStr = (str) => {
let num = 0, char = '',result = {};
// let strArr = str.split('').sort().join('');
let reg = /(\w)\1+/g;
str.replace(reg, ($1, $2) => {
if (num < $1.length) {
num = $1.length
char = $2
}
})
result[char] = num
return result
}
let findStr2 = (str) => {
const arr = str.match(/(\w)\1\*/g); // str.match(/(.)\\1+/g);
const maxLen = Math.max(...arr.map(s => s.length));
const result = arr.reduce((pre, curr) => {
if (curr.length === maxLen) {
pre[curr[0]] = curr.length;
}
return pre;
}, {});
return result
}
# 字符串查找
请使用最基本的遍历来实现判断字符串 a 是否被包含在字符串 b 中，并返回第一次出现的位置（找不到返回 -1）。
a='34';b='1234567'; // 返回 2
a='35';b='1234567'; // 返回 -1
a='355';b='12354355'; // 返回 5
isContain(a,b);
function isContain(a, b) {
for (let i in b) {
if (a[0] === b[i]) {
let tmp = true;
for (let j in a) {
if (a[j] !== b[~~i + ~~j]) {
tmp = false;
}
}
if (tmp) {
return i;
}
}
}
return -1;
}
# 实现千位分隔符
// 保留三位小数
parseToMoney(1234.56); // return '1,234.56'
parseToMoney(123456789); // return '123,456,789'
parseToMoney(1087654.321); // return '1,087,654.321'
function parseToMoney(num) {
num = parseFloat(num.toFixed(3));
let [integer, decimal] = String.prototype.split.call(num, '.');
integer = integer.replace(/\d(?=(\d{3})+$)/g, '$&,');
return integer + (decimal ? '.' + decimal : '');
}
# 正则表达式(运用了正则的前向声明和反前向声明):
function parseToMoney(str){
// 仅仅对位置进行匹配
let re = /(?=(?!\b)(\d{3})+$)/g;
return str.replace(re,',');
}
# 金额转换 分->元 保留2位小数 并每隔3位用逗号分开 1,234.56
function caseMoney(val) {
const str = val.toFixed(2) + ''
const intSum = str.substring(0, str.indexOf('.')).replace(/\\B(?=(?:\\d{3})+$)/g, ',') //取到整数部分
const dot = str.substring(str.length, str.indexOf('.')) //取到小数部分搜索
const ret = intSum + dot
return ret
}
# 判断是否是电话号码
function isPhone(tel) {
var regx = /^1[34578]\d{9}$/;
return regx.test(tel);
}
# 验证是否是邮箱
function isEmail(email) {
var regx = /^([a-zA-Z0-9_\-])+@([a-zA-Z0-9_\-])+(\.[a-zA-Z0-9_\-])+$/;
return regx.test(email);
}
# 验证是否是身份证
function isCardNo(number) {
var regx = /(^\d{15}$)|(^\d{18}$)|(^\d{17}(\d|X|x)$)/;
return regx.test(number);
}
参考:
前端面试遇到的算法题
# 无重复字符的最长子串
/\*\*
\* @param {string} s
\* @return {number}
\*/
var lengthOfLongestSubstring = function (s) {
var strSet = new Set();
var left = 0;
var right = 0;
var ans = 0;
while (right < s.length) {
if (left > 0) {
strSet.delete(s[left - 1]);
}
while (right < s.length && !strSet.has(s[right])) {
strSet.add(s[right]);
right++;
}
ans = Math.max(ans, strSet.size);
left++;
}
return ans;
};
var lengthOfLongestSubstring2 = function(s) {
let res = 0,temp = [],i = 0;
while(i<s.length) {
if(temp.indexOf(s[i]) === -1) {
temp.push(s[i])
} else {
temp.shift();
continue;
}
res = Math.max(res,temp.length)
i ++
}
return res;
};
console.log(lengthOfLongestSubstring('abcabcbb'))
# 使用JS将手机号进行加密中间四位变成*号
// 正则
var phone= 15845621523; //获取到的电话信息
phone= "" + phone;
var reg=/(\d{3})\d{4}(\d{4})/; //正则表达式
var phone= phone.replace(reg, "$1****$2")
console.log(phone);
// 使用split，splice，join 方法来进行电话号码加密
var phone= 15845625621;
phone= "" + phone;
var ary = phone.split("");
ary.splice(3,4,"****");
var phone=ary.join("");
console.log(phone);
// 使用substr方法进行电话号码加密
var phone =15865234562;
phone = "" + phone;
var phone= phone.substr(0,3) + "****" + phone.substr(7)
console.log(phone);
# js 判断回文字符串
// 判断一个字符串是不是回文字符串
function isPalindrome(str) {
var str1 = str.split('').reverse().join('');
return str1===str;
}
// 优化
function isPalindrome2(str) {
var len = str.length
var middle = parseInt(len / 2)
for (var i = 0; i < middle; i++) {
if (str[i] != str[len - i - 1]) {
return false
}
}
return true
}
//判断字符串中的所有回文字符串
function palindromeStr(str) {
var temp = '';
var result=[];
for(var i=0;i<str.length;i++){
temp = '';
for(var j=i;j<str.length;j++){
temp+=str.charAt(j);
if(isPalindrome2(temp) && result.indexOf(temp) == -1){
result.push(temp);
}
}
}
return result;
}
// 判断字符串中的最长回文字符串
function palindromeLongestStr(str) {
var temp = '';
var longestStr='';
for(var i=0;i<str.length;i++){
temp = '';
for(var j=i;j<str.length;j++){
temp+=str.charAt(j);
if(isPalindrome2(temp) && longestStr.length<temp.length){
longestStr=temp;
}
}
}
return longestStr;
}