数组,栈,队列

数组

对于数组并不陌生,下面来总结一下数组的方法。

image

以下是一些容易记错或者记混的常用方法

map

在一个坑爹面试题中见过

["1", "2", "3"].map(parseInt)

就拿这道题复习吧,先看一下通常 map 中的参数

var new_array = arr.map(function callback(currentValue[, index[, array]]) {
    // Return element for new_array
}[, thisArg])

可以看到需要传参 callback 和 thisArg,分别是生成新数组元素的函数,执行 callback 函数时 使用的 this 值。

其中 callback 接受三个参数,

currentValue:数组中正在处理的当前元素。

index:数组中正在处理的当前元素的索引。

array:map 方法被调用的数组。

再看一下 parseInt

parseInt(string, radix)
//string    必需。要被解析的字符串。
//radix
可选。表示要解析的数字的基数。该值介于 2 ~ 36 之间。

如果省略该参数或其值为 0,则数字将以 10 为基础来解析。如果它以 “0x” 或 “0X” 开头,将以 16 为基数。
如果该参数小于 2 或者大于 36,则 parseInt() 将返回 NaN。

结合起来,再根据

parseInt('1',0) = 1,
parseInt('2',1) = NaN,
parseInt('3',2) = NaN

就可以得出[1,NaN,NaN]的结果;

solice 和 split

array.splice(start[, deleteCount[, item1[, item2[, ...]]]])

splice 的作用是在数组的任意位置添加或删除元素。
其中第一个参数表示想要删除或插入的元素的索引值,第二个参数是删除元素的个数(添加则传入 0),第三个参数之后就是要添加到数组里的值。

array.slice(start,end)

slice() 方法返回一个从开始到结束(不包括结束)选择的数组的一部分浅拷贝到一个新数组对象。且原始数组不会被修改。

栈是遵循后进先出原则的集合

实现栈类

let Stack = (function () {
    const items = new WeakMap()
    class Stack {
        constructor() {
            items.set(this, [])
        }
        push(element) {
            let s = items.get(this)
            s.push(element)//注意,返回值是数组的长度
        }
        pop() {
            let s = items.get(this)
            let r = s.pop()
            return r
        }
        isEmpty () {
            let s = items.get(this);
            return s.length==0
        }
    }
    return Stack
})()

栈的应用-进制转化

function baseConverter(decNumber,base) {
    let remStack = new Stack(),rem,binaryString  = "",chars ="0123456789ABCDEF";
    while(decNumber>0){
        //余数入栈
        rem = decNumber%base
        //被除数取整
        decNumber = Math.floor(decNumber/base);
        remStack.push(rem);
    }
    while(!remStack.isEmpty()){
        binaryString+=chars[remStack.pop()]
    }
    return binaryString
}
let result = baseConverter(10,2)//1010
let result1 = baseConverter(105,16)//69

队列

队列是遵循先进先出的集合

实现队列类

let Queue = (function () {
    const items = new WeakMap()
    class Queue {
        constructor() {
            items.set(this, [])
        }
        enqueue(element) {
            let q = items.get(this)
            q.push(element)//注意,返回值是数组的长度
        }
        dequeue() {
            let q = items.get(this)
            let r = q.shift()
            return r
        }
        isEmpty () {
            let q = items.get(this);
            return q.length==0
        }
        size () {
            let q =items.get(this);
            return q.length
        }
    }
    return Queue
})()

队列的应用-击鼓传花

function hotPotato(nameList, num){
    let queue = new Queue()
    for(let i=0;i<nameList.length;i++){
      //所有玩家入队列
      queue.enqueue(nameList[i])
    }
    let eliminated = '';
    //当队列里还有1个以上的玩家
    while (queue.size()>1){
      //num个玩家排列到队列末尾
      for(let i=0;i<num;i++){
        queue.enqueue(queue.dequeue())
      }
      eliminated = queue.dequeue()
      console.log(eliminated + '淘汰')
    }
    return queue.dequeue()
}
let nameList = ['a', 'b', 'c', 'd']
hotPotato(nameList, 3)