JS算法(一)

待我称王封你为后i 2022-05-20 03:57 155阅读 0赞

## 一些简单的JS算法 ##

*  判断回文数

function isPlalindrom(str){ 
        return str == str.split('').reverse().join('')
    }

*  去掉重复值(数组)

function uniqueue(arr){ 
        let hashTable = {}
        let data = []
        for (let i=0; i<arr.length;i++){
            if (!hashTable[arr[i]]){
                hashTable[arr[i]] = true
                data.push(arr[i])
            }
        }
        return data
    }

*  找出字符串中出现次数最多的字母

// str 有个方法，可以和数组一样把字符一个个取出来, str.charAt(i)
    function mostOccur(str){ 
        let hashTable = {}
        for(let i=0;i<str.length;i++){
            if (!hashTable[str.charAt(i)]){
                hashTable[str.charAt(i)] = 1
            } else {
                hashTable[str.charAt(i)] += 1
            }
        }
        let max = 1
        let maxCode = ''
        for (let key in hashTable) {
            if (hashTable[key] > max){
                max = hashTable[key]
                maxCode = key
            }
        }
        return maxCode
    }

*  冒泡排序(有待解决)

*  快排

// 数组方法
    function quickSort(arr) { 
        if (arr.length <= 1) return arr
        let rightArr = []
        let leftArr = []
        let middle = Math.floor(arr.length / 2)
        let key = arr.splice(middle, 1)[0]
        for (let i=0;i<arr.length;i++) {
            if (arr[i] > key) {
                rightArr.push(arr[i])
            } else {
                leftArr.push(arr[i])
            }
        }
        return [].concat(quickSort(leftArr), [key], quickSort(rightArr))
    }
    
    function sortHelp(arr, low, high) { 
        let i = low, j = hight
        let e = arr[low]
        while(i < j) {
            while(i < j && arr[j] >= e) j--
            if (i < j) arr[i++] = arr[j]
            while (i < j && arr[i] <= e) i++
            if (i <j ) arr[j--] = arr[i]
        }
        arr[i] = e
        if (low < i -1) sortHelp(arr, low, i -1)
        if (i + 1 < high) sort(arr, i+1, high)
        return arr
    }
    
    function quickSort(arr){ 
        sortHelp(arr, 0, arr.length-1)
    }

*  不借助临时变量，交换

function swap(a, b){ 
        b = b - a
        a = a + b
        b = a - b
        return [a, b]
    }
    function swap1(a, b) { 
        [a, b ] = [b, a]
        return [a, b]
    }

*  斐波那契数列

function fibonacci(n) { 
        let fibArr = []
        let i = 0
        while(i < n){
            if (i <= 1) {
                fibArr.push(i)
            } else {
                fibArr.push(fibArr[i-1] + fibArr[i-2])
            }
            i += 1
        }
        return fibArr
    }
    function* es6Fibonacci(n) { 
        let [pre, cur] = [0, 1]
        for(;;){
            [pre, cur] = [cur, pre + cur]
            yield cur
        }
    }
    // 这里要区分一下 for...in 和 for...of
    // 推荐在循环对象属性的时候，使用for...in,在遍历数组的时候的时候使用for...of。
    // for...in循环出的是key，for...of循环出的是value

*  求数组最大，最小值

function maxMin(arr) { 
        let max = Math.max.apply(null, arr)
        let min = Math.min(...arr)
        return max -min
    }

*  随机生成指定长度的字符串

function randomString(n) { 
        let str = 'abcdefghijklmnopqrstuvwxyz9876543210'
        let temp = ''
        let len = str.length
        for (let i = 0; i< n; i++) {
            temp += str.charAt(Math.floor(Math.random() * len))
            // Math.floor 返回小于或等于某一个给定数字的最大整数
        }
        return temp
    }

*  验证是否为数组

function isArray(obj) { 
        console.log(Object.prototype.toString.call(obj))
        return Object.prototype.toString.call(obj) == '[object Array]'
    }

*  二叉查找树

function Node(data, left, right){ 
        this.data = data
        this.left = left
        this.right = right
        this.show = show
    }
    
    function show(){ 
        return this.data
    }
    
    function BST(){ 
        this.root = null
        this.insert = insert
        this.getMax = getMax
        this.getMin = getMin
        this.find = find
    }
    
    function insert(data){ 
        var n = new Node(data, null, null)
        if (this.node == null) {
            this.root = n
        } else {
            var current = this.root
            var parent
            while(true) {
                parent = current
                if (data < current.data) {
                    current = current.left
                    if(current == null) {
                        parent.left = n
                        break
                    }
                } else {
                    current = current.right
                    if (current == null) {
                        parent.right = n
                    }
                }
            }
        }
    }