首页 > 编程语言 >前端算法(持续更新)

前端算法(持续更新)

时间:2024-09-11 16:25:19浏览次数:11  
标签:function arr return 递归 前端 更新 算法 let key

1、最大的钻石

1楼到n楼的每层电梯口都放着一个钻石,钻石大小不一。你从电梯1楼到n楼,每层楼电梯门都会打开一次,只能拿一次钻石,问怎样才能最大的钻石?

解题思路:

这是一个经典的动态规划问题,可以使用贪心算法来解决。以下是解决这个问题的思路:

  • 定义问题

从 1 楼到 n 楼,每层楼电梯门都会打开一次,只能拿一次钻石,要找到最大的钻石。

  • 贪心算法思路

当在第 i 层楼时,如果当前钻石比之前看到的所有钻石都大,就选择当前钻石。
因为如果当前钻石是目前为止最大的,那么后面可能出现的钻石即使比当前钻石大,也不能选择了,因为只能拿一次钻石。而如果不选择当前最大的钻石,后面出现更大钻石的概率是不确定的,所以选择当前最大的钻石是一种贪心策略。

  • 具体实现步骤
  1. 初始化一个变量 max_diamond 为负无穷大,表示目前看到的最大钻石的大小。
  2. 从 1 楼开始,依次遍历每一层楼。
  3. 当到达第 i 层楼时,比较当前钻石的大小和 max_diamond 的大小。
  4. 如果当前钻石比 max_diamond 大,就更新 max_diamond 为当前钻石的大小。
  5. 最后,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、举例说明你对尾递归的理解,已经哪些应用场景

一、对尾递归的理解

尾递归是指一个函数在执行的最后一步调用自身的递归形式。在尾递归中,递归调用是函数执行的最后一个操作,并且在调用之后不需要再进行其他操作。这使得编译器或解释器可以对尾递归进行优化,将递归调用转换为循环,从而避免了传统递归可能导致的栈溢出问题。

例如,计算阶乘的函数可以用递归和尾递归两种方式实现:

  1. 传统递归实现阶乘:
function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

在这个传统递归实现中,每次递归调用都需要保存当前的状态到栈中,当 n 较大时,可能会导致栈溢出。复杂度为O(n)

  1. 尾递归实现阶乘:
function factorialTailRecursive(n, accumulator = 1) {
  if (n === 0) {
    return accumulator;
  }
  return factorialTailRecursive(n - 1, n * accumulator);
}

在尾递归版本中,每次递归调用时都将当前的部分结果(accumulator)传递给下一次调用,最后在 n 为 0 时返回结果。这样,编译器或解释器可以优化这种形式的递归,避免栈的不断增长。复杂度为O(1)

二、应用场景

  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,[]))
  1. 在函数式编程语言中,尾递归被广泛应用,因为函数式编程强调无副作用的纯函数和递归作为主要的控制结构。例如在 Haskell、Scheme 等语言中,尾递归是一种常见的编程模式。

  2. 深度优先搜索(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

相关文章

  • 前端常见算法题
    1、去除字符串中出现次数最少的字符,不改变原字符串的顺序实现删除字符串中出现次数最少的字符,若出现次数最少的字符有多个,则把出现次数最少的字符都删除。输出删除这些单词后的字符串,字符串中其它字符保持原来的顺序。“ababac”——“ababa”“aaabbbcceeff”——“aaa......
  • 前端面试(上)
    一:HTML篇1.HTML5新特性拖拽释放(Drapanddrop)API;语义化标签(headernavfooterarticle等);视频、音频(audio、video)API;画布(Canvas);地理(Geolocation)定位;存储(localStorage,sessionStorage);表单控件(date、time、email、url、search等);新的技术(多任务webworker、全双工通......
  • Web前端与物联网虚拟仿真系统对接读取与控制
    面对学生学习前端开发困难,教师难管理的问题,我们开发了一套Web前端开发实训平台。方便教师与学生进行网站的发布与浏览,平台具备在线CODE编辑器,直接输入代码完成前端开发代码的编写,系统自动生成预览的效果界面。该实训平台能与我们的物联网仿真系统联动,实现虚实结合。物联网......
  • 【大模型理论篇】ToB的大模型系统非常有必要引入搜索推荐算法能力(回顾BPR、W&D、ALS等
    1.背景和思考              上周2024上海外滩大会如约而至,各种大咖云集,多种观点思想碰撞,带来很多新的启发。我个人比较关注大模型和隐私计算相关的内容,因此重点听了相关老师带来的行业前沿进展和深度思考。有两位老师的观点,特别认同,一位是百川智能的王小川......
  • 代码随想录算法训练营Day1
    目录704.二分查找 27.移除元素977.有序数组的平方 704.二分查找 分类:左闭右闭、左闭右开Tips:1.循环条件:左闭右闭:左索引<=右索引左闭右开:左索引<右索引2.循环操作:处理元素>目标值:左闭右闭:右索引=折半索引-1左闭右开:右索引=折半索引classSolution{......
  • 互联网算法备案必要性+攻略全流程详解【附件+流程】
    一、算法备案的重要性算法备案是指相关企业或组织向有关部门提交其使用的算法的相关信息,以接受监管和审查。这一举措有助于确保算法的公正性、透明性和合法性,保护用户的权益,促进数字经济的健康发展。算法备案必要性强制性例如,在推荐系统中,如果算法存在偏见或歧视,可能会导致......
  • 前端权限开发——设计到实践(保姆级)
    主要思想:基于角色的访问控制(Role-BasedAccessControl,RBAC)可以結合roleX框架学习RoleX是一种基于角色的访问控制(RBAC)框架,它提供了一种灵活、可扩展的方式来管理用户对系统资源的访问权限。RoleX的架构和原理如下:1.角色模型:RoleX的核心是一个角色模型,它定义了角色、权......
  • 算法与数据结构——图的基础操作及图的遍历(广度优先与深度优先)
    图的实现基于邻接矩阵的实现给定一个顶点数量为n的无向图:初始化:传入n个顶点,初始化长度为n的顶点列表vertices,使用O(n)时间;初始化n*n大小的邻接矩阵adjMat,使用O(n2)时间。添加或删除边:直接在邻接矩阵中修改指定的边即可,使用O(1)时间。而由于是无向图,因此需要同时更新两个......
  • 【大数据】分布式存储压缩算法
    目录一、分布式存储压缩算法概述二、分布式存储压缩算法优缺点和改进2.1 分布式存储压缩算法优点2.2分布式存储压缩算法缺点2.3 分布式存储压缩算法改进三、分布式存储压缩算法实现3.1 分布式存储压缩算法C语言实现3.2 分布式存储压缩算法JAVA实现3.3 分布式存......
  • xaf-模型更新限制
    LimitationsTheXAFUIdoesnotreflectchangesmadeintheApplicationModelaftercontrolcreation.CustomizetheApplicationModelbeforethecontrolusedtodisplayatargetUIelementiscreatedandloaded.Accessthecontroldirectlytocustomizea......