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);
}
})();
标签:function,arr,return,递归,前端,更新,算法,let,key
From: https://blog.csdn.net/franktaoge/article/details/142068704