算法学习记录（二十七）

问：

1. 有效的括号
2. 数组中第K个大的元素
3. 全排列
4. 最长回文子串

解：

1. 栈解法

function isValid(s) {
    const stack = []
    const hashMap = new Map([['}', '{'],[']', '['],[')', '(']])
    const hashSet = new Set(['{', '[', '('])
    for (let i of s) {
        if (hashSet.has(i)) {
            stack.push(i)
            continue
        }
        if (stack.pop() !== hashMap.get(i)) {
            return false
        }
    }
    return !stack.length
}
复制代码

2. 堆排，可以只排K个元素

function findKthLargest(nums, k) {
    let heapSize = 0
    for (let i = 0; i<nums.length;i++) {
        heapInsert(i)
        heapSize += 1
    }
    while (k) {
        [nums[0], nums[heapSize - 1]] = [nums[heapSize - 1], nums[0]]
        heapSize -= 1
        k -= 1
        heapFy(0, heapSize)
    }
    function heapFy(i, heapSize) {
        const leftIdx = 2 * i + 1
        const rightIdx = leftIdx + 1
        let target = i
        if (leftIdx < heapSize && nums[leftIdx] > nums[target]) target = leftIdx
        if (rightIdx < heapSize && nums[rightIdx] > nums[target]) target = rightIdx
        if (target !== i) {
            [nums[i], nums[target]] = [nums[target], nums[i]]
            heapFy(target, heapSize)
        }
    }
    function heapInsert(i) {
        const father = Math.floor((i - 1) / 2)
        if (nums[father] < nums[i]) {
            [nums[father], nums[i]] = [nums[i], nums[father]];
            i = father
            heapInsert(i)
        }
    }
    return nums[heapSize]
}
复制代码

3. 从第0位数开始递归，对于当前位来说，后面的每一位数都有可能来到当前位置，所以遍历并且交换位置，然后递归下去。在本轮递归结束后把位置交换回来。

function permute(arr) {
    const res = []
    function getRes (idx, curArr) {
        const temp = curArr.slice()
        if (idx === curArr.length) {
            res.push(curArr)
            return
        }
        for (let i = idx; i < curArr.length; i++) {
            [temp[idx], temp[i]] = [temp[i], temp[idx]]
            getRes(idx + 1, temp);
            [temp[idx], temp[i]] = [temp[i], temp[idx]]
        }
    }
    getRes(0, arr)
    return res
}
复制代码

function Manacher(str) {
    str = handleStr(str)
    let center = -1
    let mostRight = -1
    let max = {
        length: 1,
        idx: 0
    }
    const allInfo = []
    // 1、若 i 越过 mostRight。暴力扩充
    // 2、若 i 没越过 mostRight，判断:i 和  mostRight的距离，是否大于 i'(i 关于中心的对称点) 的回文半径  ①：若大于,i'的回文半径就是i的回文半径； ②：若小于，i到mostRight的距离就是i的回文半径  ③：若等于：i暴力扩
    for (let i = 0; i < str.length ; i++) {
        // 减少上述逻辑判断，直接拿到对应的回文半径，无论怎么样都暴力扩
        allInfo[i] = i < mostRight ? Math.min(mostRight - i, allInfo[2 * center  - i]) : 1
        // 暴力扩充
        while (i - allInfo[i] > -1 && i + allInfo[i] < str.length) {
            if (str[allInfo[i] + i] === str[i- allInfo[i]]) {
                allInfo[i]++
            } else {
                break
            }
        }
        // 扩充完毕，判断边界
        if (mostRight < i + allInfo[i]) {
            mostRight = i + allInfo[i]
            center = i
        }
        // 找到最大回文直径，以及它所在的下标
        if (max.length < allInfo[i]) {
            max.length = allInfo[i]
            max.idx = i
        }
    }
    return str.slice(max.idx - max.length + 1, max.idx + max.length - 1).replace(/#/g, '')

    function handleStr(str) {
        const strArr = str.split('')
        strArr.push('')
        strArr.unshift('')
        return strArr.join('#')
    }
}
复制代码