前端算法(持续更新)
1、最大的钻石
1楼到n楼的每层电梯口都放着一个钻石，钻石大小不一。你从电梯1楼到n楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能最大的钻石？
解题思路：
这是一个经典的动态规划问题，可以使用贪心算法来解决。以下是解决这个问题的思路：
- 定义问题
从 1 楼到 n 楼，每层楼电梯门都会打开一次，只能拿一次钻石，要找到最大的钻石。
- 贪心算法思路
当在第 i 层楼时，如果当前钻石比之前看到的所有钻石都大，就选择当前钻石。
因为如果当前钻石是目前为止最大的，那么后面可能出现的钻石即使比当前钻石大，也不能选择了，因为只能拿一次钻石。而如果不选择当前最大的钻石，后面出现更大钻石的概率是不确定的，所以选择当前最大的钻石是一种贪心策略。
- 具体实现步骤
- 初始化一个变量 max_diamond 为负无穷大，表示目前看到的最大钻石的大小。
- 从 1 楼开始，依次遍历每一层楼。
- 当到达第 i 层楼时，比较当前钻石的大小和 max_diamond 的大小。
- 如果当前钻石比 max_diamond 大，就更新 max_diamond 为当前钻石的大小。
- 最后，max_diamond 就是能拿到的最大钻石的大小。
代码实例
function maxDiamonds(n) {
let num = -Infinity;
for (let i = 0; i < n; i++) {
num = Math.max(num, Math.floor(Math.random(i) * 100));
}
return num;
}
let n = 100;
console.log(maxDiamonds(n));
提示
题中包含一个隐藏条件：随机放置。说有的分析都是基于随机放置给出的。换句话说，如果放置钻石是人为干预的大小，那么本题所有分析都不成立。
2、举例说明你对尾递归的理解，已经哪些应用场景
一、对尾递归的理解
尾递归是指一个函数在执行的最后一步调用自身的递归形式。在尾递归中，递归调用是函数执行的最后一个操作，并且在调用之后不需要再进行其他操作。这使得编译器或解释器可以对尾递归进行优化，将递归调用转换为循环，从而避免了传统递归可能导致的栈溢出问题。
例如，计算阶乘的函数可以用递归和尾递归两种方式实现：
- 传统递归实现阶乘：
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
}
在这个传统递归实现中，每次递归调用都需要保存当前的状态到栈中，当 n 较大时，可能会导致栈溢出。复杂度为O(n)
- 尾递归实现阶乘：
function factorialTailRecursive(n, accumulator = 1) {
if (n === 0) {
return accumulator;
}
return factorialTailRecursive(n - 1, n * accumulator);
}
在尾递归版本中，每次递归调用时都将当前的部分结果（accumulator）传递给下一次调用，最后在 n 为 0 时返回结果。这样，编译器或解释器可以优化这种形式的递归，避免栈的不断增长。复杂度为O(1)
二、应用场景
- 一些数学计算和算法问题中，如果可以将问题分解为相似的子问题并且可以用尾递归形式解决，就可以使用尾递归。例如，计算斐波那契数列、求解汉诺塔问题等。
- 数组求和
function sumArray(arr, total = 0) {
if (arr.length === 0) {
return total;
}
return sumArray(arr, total + arr.pop());
}
const array = [1, 2, 3, 4, 5];
const result = sumArray(array);
console.log(result); // 15
- 计算斐波那契数列
function factorial(n, start=1, total=1) {
if (n <= 2) {
return start;
}
return factorial(n - 1, total, start + total);
}
- 数组扁平化
let arr = [1, [2, [3, [4, [5]]]]];
function flat(arr=[],result=[]) {
arr.forEach(item=>{
if(Array.isArray(item)){
result = result.concat(flat(item,[]));
}else{
result.push(item);
}
})
return result;
}
console.log(flat(arr,[]))
-
在函数式编程语言中，尾递归被广泛应用，因为函数式编程强调无副作用的纯函数和递归作为主要的控制结构。例如在 Haskell、Scheme 等语言中，尾递归是一种常见的编程模式。
-
深度优先搜索（DFS）和广度优先搜索（BFS）算法实现中，如果需要递归遍历图或树结构，可以考虑使用尾递归优化，特别是在处理大规模数据时，以避免栈溢出。
3、去除字符串中出现次数最少的字符，不改变原字符串的顺序
实现删除字符串中出现次数最少的字符，如果出现最少的字符有多个，则把出现次数最少的字符都删除。输出删除这些单词后的字符串，字符串中的顺序保持不变
function removeLeastFrequent(str) {
// 创建对象，保存key为字符，value为出现次数
let obj = {};
for (let i = 0; i < str.length; i++) {
if (obj[str[i]]) {
obj[str[i]]++;
} else {
obj[str[i]] = 1;
}
}
// 找出出现次数最少的次数
let minCount = Math.min(...Object.values(obj));
// 删除对象obj中value为minCount的key
for (let key in obj) {
if (obj[key] === minCount) {
delete obj[key];
}
}
// 遍历原字符串，将出现次数最少的字符删除
let result = '';
for (let i = 0; i < str.length; i++) {
if (obj[str[i]]) {
result += str[i];
}
}
return result;
}
console.log(removeLeastFrequent('aaabbbccddeeff'));
4、手写快速排序
以下是用 JavaScript 实现快速排序的代码：
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
// 设置数组的中位数middle，pivot是middle为索引的值
let middle = Math.floor(arr.length / 2);
let pivot = arr[middle];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
// 如果是中位数，跳过
if (i === middle) {
continue
}
// 把小于中位数的放到左边，大于的放进右边
let item = arr[i];
if (item < pivot) {
left.push(item);
} else {
right.push(item);
}
}
// 左右分别递归转为更小的颗粒度
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));
}
快速排序的基本思想是：选择一个基准值（这里选择数组的第一个元素作为基准值），将数组分为两部分，小于基准值的元素放在左边，大于等于基准值的元素放在右边。然后对左右两部分分别递归地进行快速排序，最后将左、基准值、右三部分合并起来。
快速排序的时间复杂度在平均情况下为 O ( n l o g n ) O(n log n) O(nlogn)，但在最坏情况下（例如数组已经有序时）为 O ( n 2 ) O(n^2) O(n2)。空间复杂度在平均情况下为 O ( l o g n ) O(log n) O(logn)（递归调用栈的深度），最坏情况下为 O ( n ) O(n) O(n)。
5、洗牌算法
洗牌算法是将原数组打散，使得原数组在新数组中的位置等概率相等，也叫乱序算法
function shuffle(arr) {
let len = arr.length;
for (let i = len - 1; i >= 0; i--) {
let randomIndex = Math.floor(Math.random() * (i + 1));
[arr[i], arr[randomIndex]] = [arr[randomIndex], arr[i]];
}
return arr;
}
6、手写一个LRU函数
class LRU {
constructor(capacity) {
// 缓存的最大容量
this.capacity = capacity;
// 缓存的数据
this.cache = new Map();
}
// 获取缓存数据
get(key) {
// 如果缓存中没有该数据，则返回false
if (this.cache.has(key)) {
// 将缓存中的数据删除，再重新插入，保证最近使用的数据在最后
let val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
return false;
}
put(key, value) {
// 如果缓存中有该数据，则删除，再重新插入
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// 另一种写法：this.cache.delete([...this.cache.keys()][0]);
this.cache.delete(this.cache.keys().next().value);
}
this.cache.set(key, value);
}
}
7、判断回文串
function isPalindrome(s) {
if (typeof s !== 'string') return false;
return s === s.split('').reverse().join('');
}
8、写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
牛客网的答题格式：
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function () {
// Write your code here
let a = await readline();
let b = await readline();
a = a.toLocaleLowerCase()
b = b.toLocaleLowerCase()
console.log(a.split(b).length-1)
}()
9、输入一个字符串，请按长度为8拆分每个输入字符串并进行输出；长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
function fun8(str) {
let len = str.length;
if(len===8){
console.log(str)
} else if(len<8){
console.log(padEnd(str))
} else {
let list = str.split('');
let newList = [];
while(list.length>0){
if(list.length<8){
let end = list.splice(0,list.length);
newList.push(padEnd(end));
} else {
newList.push(list.splice(0,8).join(''));
}
}
for(let i in newList){
console.log(newList[i])
}
}
function padEnd(msg){
let n = 8-msg.length;
let end = "0".repeat(n);
return msg+end;
}
}
10、质数因子
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）
function getZhiYinZi(str){
let num = parseInt(str);
let list = [];
let i = 2;
while (i * i <= num) {
while (num % i === 0) {
list.push(i);
num /= i;
}
i++;
}
if (num > 1) {
list.push(num);
}
console.log(list.join(' '));
}
11、写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
async function hexToDecimal() {
while (line = await readline()) {
let hexNumber = line;
console.log(parseInt(hexNumber, 16));
}
}
hexToDecimal();
12、合并表记录
数据表记录包含表索引index和数值value（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照index值升序进行输出。
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
let n = await readline();
let sets = new Map();
while (n > 0) {
n--;
let arr = await readline();
let list = arr.split(' ');
let key = parseInt(list[0]),
value = parseInt(list[1]);
if (sets.has(key)) {
let lastValue = sets.get(key);
sets.set(key, lastValue + value);
} else {
sets.set(key, value);
}
}
// 根据key排序
const sortedMapByKey = new Map([...sets].sort((a, b) => a[0]-b[0]));
for (const [key, value] of sortedMapByKey) {
console.log(key, value);
}
})();
13、相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
function getIntersectionNode(headA, headB) {
let lenA = 0, lenB = 0;
let pa = headA;
let pb = headB;
while(pa){
lenA++;
pa = pa.next;
}
while(pb){
lenA++;
pb = pb.next;
}
pa = headA;
pb = headB;
if(lenA>lenB){
let diff = lenA - lenB;
while(diff>0){
diff--;
pa = pa.next;
}
} else (lenB>lenA){
let diff = lenB - lenA;
while(diff>0){
diff--;
pb = pb.next;
}
}
while(pa && pb){
if(pa === pb){
return pa
}
pa = pa.next;
pb = pb.next;
}
return null;
}
首先通过两个while循环分别计算headA和headB链表的长度lenA和lenB。
然后重新将pa指向headA，pb指向headB。根据lenA和lenB的大小关系，让较长的链表先走|lenA - lenB|步。
最后通过一个while循环让两个链表同时走，当pa和pb相等时，说明找到了相交节点，返回这个节点；如果循环结束都没有找到相等的节点，说明两个链表不相交，返回null。