算法题目整理分析--字典序 和 字典序最大子序列

平时算法问题处理的不多。看到 字典序有点眼生。研究一下。

字典序:就是按照字典中出现的先后顺序进行排序

参考 字典序算法详解

计算 abc的最大字典序,流程就是:abc > acb > bac > bca > cab > cba

要求下一种排列既要比原排列大,又不能有第三种排列位于他俩之间。即下一种排列为大于原排列的最小排列

字典序排序

js 的sort,默认就是字典排序。

    function dictionarySort(str) {
        var result = checkStr(str)

        // 检查字符
        function checkStr(str) {
            var newStr = str
            var isPlain = checkIsPlain(str)
            if (isPlain instanceof Array) {
                newStr = changeStr(str, isPlain)
            }

            if (isPlain instanceof Array) {
                return checkStr(newStr)
            } else {
                return str
            }

        }

        // 检查是否需要重新排列
        function checkIsPlain(str) {
            var isPlain = true
            var toBreak = false
            for (var i = str.length - 1; i >=0; i--) {
                if (toBreak) {
                    break
                }
                for (var j = i - 1; j >=0; j--){
                    if (str[j] < str[i]) {
                        isPlain = [j, i]
                        toBreak = true
                        break
                    }
                }
            }
            return isPlain
        }
        // 交换字符位置
        function changeStr(str, position) {
            var arr = str.split('')
            var s = str.charAt(position[0])
            var e = str.charAt(position[1])
            arr[position[0]] = e
            arr[position[1]] = s
            return arr.join('')
        }
        return result

    }


    console.log(dictionarySort('ababba'))

字典序最大子序列

子序列:对于字符串a和b,如果移除字符串a中的一些字母(可以全部移除,也可以一个都不移除)就能够得到字符串b,则b为a的子序列。例如,‘heo'为'hello'的子序列,’le'不是。

思路就是从后往前递归,遇到小于最后的,就删掉。这样可以保持第一位是最大的字母。

function maxDictionaryStr(str) {
    var result = check(str)

    function check(str) {
        var res = str.split('')
        var isPlain = true
        for (var i = str.length - 1; i >= 0; i--) {
            if (!isPlain) {
                break
            }
            var originStr = str.charAt(i)
            for (var j = i - 1; j >= 0; j--) {
                var targetStr = str.charAt(j)
                if (targetStr < originStr) {
                    res.splice(j, 1)
                    isPlain = false
                    break
                }
            }
        }
        if (isPlain) {
            return res.join('')
        } else {
            return check(res.join(''))
        }
    }
    return result
}
console.log(maxDictionaryStr('test'))
console.log(maxDictionaryStr('ababba'))
console.log(maxDictionaryStr('abbcbccacbbcbaaba'))

随机浏览