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的keyfor (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) {// 如果缓存中没有该数据，则返回falseif (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 herelet 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。
