前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >JavaScript算法题总结 (四)堆/栈/队列

JavaScript算法题总结 (四)堆/栈/队列

作者头像
henu_Newxc03
发布2022-05-12 14:23:54
2560
发布2022-05-12 14:23:54
举报

BM42 用两个栈实现队列

在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
let stack1=[],stack2=[];
function push(node)
{
    // write code here
    stack1.push(node);
}
function pop()
{
    // write code here
    if(stack2.length==0){
        while(stack1.length!==0){
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop()
}
module.exports = {
    push : push,
    pop : pop
};

BM43 包含min函数的栈

在这里插入图片描述
在这里插入图片描述

BM43 包含min函数的栈

在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
let stack1=[];

function push(node)
{
    // write code here
    stack1.push(node);
}
function pop()
{
    // write code here
    stack1.pop();
}
function top()
{
    // write code here
    return stack1[stack1.length-1];
}
function min()
{
    // write code here
    let min=stack1[0];
    for(let i=1;i<stack1.length;i++){
        min=min>stack1[i]?stack1[i]:min
    }
    return min
}
module.exports = {
    push : push,
    pop : pop,
    top : top,
    min : min
};

BM44 有效括号序列

在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
/**
  * 
  * @param s string字符串 
  * @return bool布尔型
  */
function isValid( s ) {
    // write code here
    let stack=[];
    for(let i=0;i<s.length;i++){
        if(s[i]==='('||s[i]==='{'||s[i]==='['){
            stack.push(s[i]);
        }else{
            if(s[i]===')'&&stack.pop()==='('||
              s[i]===']'&&stack.pop()==='['||
              s[i]==='}'&&stack.pop()==='{'){
                continue;
            }else{
                return false;
            }
        }
    }
    if(stack.length!==0){
        return false
    }
    return true
    
}
module.exports = {
    isValid : isValid
};

BM46 最小的K个数

在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
function GetLeastNumbers_Solution(input, k)
{
  function swap(i,j){
    let temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
  }
  function percDown(index,N){
    let root = heap[index];
    
    let parent,child;
    //为root找到合适的位置
    for( parent=index; parent*2+1<N; parent=child){
      child = parent*2+1;
      //child为两个parent中值小的那个元素
      if(child+1<N && heap[child+1]>heap[child])
        child++;
      
      if( root > heap[child] )//找到了合适位置break
        break;
      else
        heap[parent] = heap[child];
    }
    
    heap[parent] = root;
  }
  
  let heap = input.slice(0,k);
  
  //前k个元素建立最大堆
  for(let i=Math.floor(k/2)-1; i>=0; i-- ){
    percDown(i,k);//第i个到第N个为最大堆
  }
  
  for(let i=k; i<input.length; i++){
    if(input[i]<heap[0]){
      heap[0] = input[i];//新的元素比大顶堆的第一个还小的话,替换大顶堆的第一个元素,重新建堆
      percDown(0,k);
    }
  }
  
  return heap;
}
module.exports = {
    GetLeastNumbers_Solution : GetLeastNumbers_Solution
};

BM47 寻找第K大

在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
/**
 * 
 * @param a int整型一维数组 
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
function findKth( a ,  n ,  K ) {
    // write code here
    if(a.length===0) return 0;
    return sortArray(a)[n-K]
}
function sortArray(nums){
    let len=nums.length;
    if(len===0) return nums;
    const midIndex=Math.floor(len/2);
    const midValue=nums.splice(midIndex,1)[0];
    const left=[];
    const right=[];
    for(let i=0;i<nums.length;i++){
        const n=nums[i];
        if(n<midValue) left.push(n);
        else right.push(n);
    }
    return sortArray(left).concat([midValue],sortArray(right))
}
module.exports = {
    findKth : findKth
};

BM48 数据流中的中位数

在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
let arr=[];
function Insert(num)
{
    // write code here
    let i=0;
    while(arr[i]<num) i++;
    arr.splice(i,0,num);
}
function GetMedian(){
	// write code here
     let index = Math.floor(  arr.length/2 )
  if(arr.length%2){//奇数
    return arr[index];
  }else{
    return ( arr[index] + arr[index-1] )/2 ;
  }
}
module.exports = {
    Insert : Insert,
    GetMedian : GetMedian
};

BM49 表达式求值

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • BM42 用两个栈实现队列
  • BM43 包含min函数的栈
  • BM43 包含min函数的栈
  • BM44 有效括号序列
  • BM46 最小的K个数
  • BM47 寻找第K大
  • BM48 数据流中的中位数
  • BM49 表达式求值
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档