likes
comments
collection
share

使用JavaScript实现根据baseUrl和字典排序后的查询参数列表queryParamsList生成完整URL

作者站长头像
站长
· 阅读数 91

前言

通过ES6类封装一个功能：给出一个代表网址 host 的字符串 base_url，和代表查询参数的列表 query_params_list，返回带查询参数的完整 URL。查询参数要进行字典排序再拼接成完整的URL。

题目描述

题目链接lintcode网站

给出一个代表网址 host 的字符串 base_url，和代表查询参数的列表 query_params_list，你需要返回带查询参数的完整 URL。 查询参数列表由一些包含两个元素的数组组成，数组第一个元素代表参数，数组第二个元素代表该参数对应的值。 现在需要你拼接两个部分得到完整的 URL。base_url 和查询参数字符串之间使用 ? 拼接，在查询参数的参数和值之间通过 = 拼接，各个查询参数之间使用 & 拼接。查询参数需要根据字典序排序。

查询参数列表 query_params_list 长度在 100100 以内。数据中不会包含特殊的需要转义的字符。

样例

样例1

输入：

"https://www.lintcode.com/problem"
[["typeId","2"]]

输出：

"https://www.lintcode.com/problem?typeId=2"

样例2

输入：

"https://translate.google.cn/"
[["sl","en"],["tl","zh-CN"],["text","Hello"],["op","translate"]]

输出：

"https://translate.google.cn/?op=translate&sl=en&text=Hello&tl=zh-CN"

解释：

参数需要按照字典序拼接，所以需要先拼接 op 部分，然后是 sl 部分，接着是 text 部分，最后才是 tl 部分。

样例3

输入：

"https://www.baidu.com/s"
[["wd","LintCode"],["rsv_spt","1"],["rsv_iqid","0xa1238d24000254d9"],["issp","1"],["f","8"],["rsv_bp","1"],["rsv_idx","2"],["ie","utf-8"],["tn","baiduhome_pg"],["rsv_enter","1"],["rsv_dl","tb"],["rsv_sug3","8"],["rsv_sug1","8"],["rsv_sug7","100"],["rsv_sug2","0"],["rsv_btype","i"],["inputT","2389"],["rsv_sug4","2389"]

输出：

"https://www.baidu.com/s?f=8&ie=utf-8&inputT=2389&issp=1&rsv_bp=1&rsv_btype=i&rsv_dl=tb&rsv_enter=1&rsv_idx=2&rsv_iqid=0xa1238d24000254d9&rsv_spt=1&rsv_sug1=8&rsv_sug2=0&rsv_sug3=8&rsv_sug4=2389&rsv_sug7=100&tn=baiduhome_pg&wd=LintCode"

样例4

输入：

"https://www.baidu.com/s"
[["",""]]

输出：

"https://www.baidu.com/s?="

解题思路

同步lintcode解题思路

根据baseUrl和查询参数列表queryParamsList，来生成完整的URL，且查询参数需按照字典排序。首先做功能拆分，两部分：（1）不考虑排序，生成完整URL；（2）对queryParamsList进行字典排序。主要分三步：

  • （1）getWholeUl(baseUrl, queryParamsList)：不考虑查询参数列表的字典排序情况下（将queryParamsList视作普通列表，无需排序），生成完整的URL；
  • （2）getDictionarySorting(queryParamsList)： 对queryParamsList进行字典排序；
  • （3）getWholeUl(baseUrl, getDictionarySorting(queryParamsList))：将字典排序后的queryParamsList再传入getWholeUl，生成完整的URL。

方法getWholeUl(baseUrl, queryParamsList)实现较为简单，就是给url拼接参数，与第一个参数的拼接要加上前缀 ? ，参数之间的拼接使用符号 &，拼接完成返回即可。

字典排序较为复杂，首先说明下两个字符的字典排序比较：给定两个个字符串strA和strB，先比较第一个字符，比较的是在字典中的位置：

  • 如果getLetterIndexByStr(strA[0])大于getLetterIndexByStr(strB[0])（这里将获取字符在字典中位置逻辑抽离出来即方法getLetterIndexByStr(str)），表示后者小，往前排；
  • 如果getLetterIndexByStr(strA[0])小于getLetterIndexByStr(strB[0])，表示前者小；
  • 如果两者相等，则继续比较下一个字符，直到最后一个字符（并不是说每次都要比较到最后一个字符，取两个字符串长度的最小值，便是这两个字符最多比较次数）。

这里我使用了使用了三层for循环来实现数组的字典排序，创建一个新数组targetList来存储排序后的值。核心逻辑：每次都从剩下的数组中找到最小的字典排序对应的值。然后将该值加入到新的数组targetList里，再将该值从原list删除，继续从剩下的值里找最小的。最后将字典排序后的数组targetList返回。

export class Solution {
    // 26个字母+数字+特殊字符
    letterList = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","_","0","1","2","3","4","5","6","7","8","9"]
    /**
     * 获取字符在26字母列表的位置(索引+1)
     * @param {String} str 字符
     */
    getLetterIndexByStr(str) {
        return !str ? 0 : this.letterList.indexOf(str[0].toLowerCase())+1
    }
    /**
     * 按照二维数组的第一个项做字典排序
     * @param {Array} list 二维数组
     * @return 字典排序后的二维数组
     */
    getDictionarySorting(list=[]) {
        const len = list.length
        if (!len) return []
        if (len === 1) return list
        let targetList = []
        for (let m = 0; m < len; m++) {
            let minIdx = 0 // 每次最小都是从0开始
            const curListLen = list.length
            if (curListLen === 1) {
                targetList.push(list[minIdx])
                break
            }
            // 找当前list里字典最小值
            for (let i = 1, j = curListLen; i < j; i++) {
                const preMinStr = list[minIdx][0]
                const curStr = list[i][0]
                const preMinLetterIndex = this.getLetterIndexByStr(preMinStr)
                const curLetterIndex = this.getLetterIndexByStr(curStr)
                // 从第0字符比较开始
                // 如果第一个字符, 前面记录的最小值的第一个字符大于当前字符串的第一个字符, 就需要change最小值的下标
                // 如果两者关系是前者小于后者, 则不需改变
                // 如果两者相同,则需要比较后面的字符
                if (preMinLetterIndex > curLetterIndex) {
                    minIdx = i
                } else if (preMinLetterIndex < curLetterIndex) {
                    continue
                } else if (preMinLetterIndex === curLetterIndex) {
                    // 如果两者相等, 再去比较下一个字符, 就是要确定谁是最小的
                    if (list[minIdx][0].length === 1) {
                        continue
                    } else if (curStr.length === 1) {
                        minIdx = i
                    } else {
                        // 比较后面的字符 minIdx 和 i
                        const minLen = Math.min(list[minIdx][0].length, curStr.length) // 记录这两个字符串的最小长度, 表示这两个字符串最多的比较次数
                        // 因为上面已比较了第一个字符,所以从第二个字符开始继续比较
                        let hasBreak = false
                        for (let k = 1; k < minLen; k++) {
                            const preMinLetterIndex = this.getLetterIndexByStr(preMinStr[k])
                            const curLetterIndex = this.getLetterIndexByStr(curStr[k])
                            // console.log('第'+k+"字符比较：", preMinLetterIndex, curLetterIndex)
                            // 如果前者大于后者, 则需change最小值小标,并且结束循环
                            // 如果前者小于后者, 则不许change最小值下标
                            // 如果相同,则继续下个字符的比较,直到结束都相同,则
                            if (preMinLetterIndex > curLetterIndex) {
                                minIdx = i
                                hasBreak = true
                                break
                            } else if (preMinLetterIndex < curLetterIndex) {
                                hasBreak = true
                                break
                            }
                        }
                        // 如果后面的字符比较到minLen都相同, 则比较两者的长度
                        // 如果前者的长度要大于后者, 则更改最小值小标
                        if (!hasBreak && list[minIdx][0].length > curStr.length) {
                            minIdx = i
                        }
                    }
                }
            }
            targetList.push(list[minIdx])
            list.splice(minIdx, 1)
        }
        return targetList
    }
    /**
     * 获取完整的URL
     * @param {*} baseUrl 
     * @param {*} queryParamsList
     * @return 完整的url
     */
    getWholeUl(baseUrl, queryParamsList) {
        if (!baseUrl) return ""
        const queryLen = queryParamsList.length
        if (!queryLen) return baseUrl
        baseUrl += "?"
        for (let i = 0, j = queryLen; i < j; i++) {
            const curQuery = queryParamsList[i]
            baseUrl += curQuery[0] + "=" + curQuery[1]
            if (i < queryLen - 1) {
                baseUrl += "&"
            }
        }
        return baseUrl
    }
    /**
     * @param baseUrl: the string of base_url
     * @param queryParamsList: sequence of two-element tuples by query_params
     * @return: return a url query string
     */
    urlencode(baseUrl, queryParamsList) {
        return this.getWholeUl(baseUrl, this.getDictionarySorting(queryParamsList))
    }
}

测试

import {Solution} from "./Solution"
const solution = new Solution()
const testCase = [
    ["https://www.lintcode.com/problem", [["typeId","2"]]],
    ["https://translate.google.cn/", [["tl","zh-CN"],["text","Hello"],["ta", "77"]]],
    ["https://translate.google.cn/", [["sl","en"],["tl","zh-CN"],["text","Hello"],["op","translate"]]],
    ["https://www.baidu.com/s", [["rsvbtype","i"],["","2389"]]],
    ["https://www.baidu.com/s", [["wd","LintCode"],["rsv_spt","1"],["rsv_iqid","0xa1238d24000254d9"],["issp","1"],["f","8"],["rsv_bp","1"],["rsv_idx","2"],["ie","utf-8"],["tn","baiduhome_pg"],["rsv_enter","1"],["rsv_dl","tb"],["rsv_sug3","8"],["rsv_sug1","8"],["rsv_sug7","100"],["rsv_sug2","0"],["rsv_btype","i"],["inputT","2389"],["rsv_sug4","2389"]]]
]
const idx = 5
console.log(solution.urlencode(testCase[idx][0], testCase[idx][1]))

其打印结果如下：

使用JavaScript实现根据baseUrl和字典排序后的查询参数列表queryParamsList生成完整URL

优化一：抽离两个字符串字典排序判断逻辑，增加递归调用

同步lintcode优化解题思路，优化：增加静态属性和方法控制

上面第二个for循环里面的逻辑是为了判断两个字符串的字典排序值大小，将这部分判断两个字符串的字典排序逻辑抽离出来即方法judgeTwoStrDictionarySort(preMinStr, curStr)。因为在比较两个字符串时，如果第一个字符相同，则比较下一个字符，而下一个字符的比较逻辑通第一个字符，所以将字符串切割掉第一个字符依然是一个字符串，故可继续调用judgeTwoStrDictionarySort(preMinStr.slice(1), curStr.slice(1))即递归调用，其代码如下：

 /**
 * 两个字符串preMinStr和curStr字典值比较
 * 如果前者小于等于后者,则返回true,否则返回false
 * @param {String} preMinStr 
 * @param {String} curStr 
 * @return Boolean
 */
judgeTwoStrDictionarySort(preMinStr, curStr) {
    // 如果比较到preMinStr为空或preMinStr和curStr都为空,即一模一样,则无需change
    if (!preMinStr.length) return true
    // 如果preMinStr非空,而curStr为空,则需change
    if (!curStr.length) return false
    // 如果两者都存在
    const preMinLetterIndex = this.getLetterIndexByStr(preMinStr), 
        curLetterIndex = this.getLetterIndexByStr(curStr)
    // 从第0字符比较开始
    // 如果第一个字符, 前面记录的最小值的第一个字符大于当前字符串的第一个字符, 就需要change最小值的下标
    // 如果两者关系是前者小于后者, 则不需改变
    // 如果两者相同,再去比较后面的字符(递归调用)
    return preMinLetterIndex > curLetterIndex 
        ? false
        : preMinLetterIndex < curLetterIndex 
            ? true 
            : this.judgeTwoStrDictionarySort(preMinStr.slice(1), curStr.slice(1))
}

同步修改getDictionarySorting()（第二次for循环的内容），但是可以继续抽离功能（getMinIxFromList()方法，接收一个数组，返回该数组中最小字典值），如下：

/**
 * 寻找list里最小字典值的索引
 * 如果数组长度为0，则返回-1
 * @param {*} list 
 * @returns 
 */
 static getMinIxFromList(list=[]) {
    let minIdx = 0
    const curListLen = list.length
    if (curListLen === 1) return minIdx
    for (let i = 1, j = curListLen; i < j; i++) {
        const preMinStr = list[minIdx][0]
        const curStr = list[i][0]
        if (!this.judgeTwoStrDictionarySort(preMinStr, curStr)) {
            minIdx = i
        }
    }
    return minIdx
}
/**
 * 按照二维数组的第一个项做字典排序
 * @param {Array} list 二维数组
 * @return 字典排序后的二维数组
 */
 static getDictionarySorting(list=[]) {
    // list = list.filter(item=> item && item[0]) // 过滤空的查询参数
    const len = list.length
    if (!len) return []
    if (len === 1) return list
    let targetList = []
    while(list.length) {
        const minIdx = this.getMinIxFromList(list) // 获取数组list中字典值最小的索引
        if (minIdx < 0) {
            break
        } else {
            targetList.push(list[minIdx])
            list.splice(minIdx, 1)
        }
    }
    return targetList
}

提交结果

使用JavaScript实现根据baseUrl和字典排序后的查询参数列表queryParamsList生成完整URL

strA.localeCompare(strB)改进

localeCompare()方法提供的比较字符串(数字、符号、字母类)的方法，考虑了默认的本地排序规则。对于文字排序的时候是比较有用的，例如后台对人员名称的升降序等等。修改方法getDictionarySorting部分代码如下：

// 后面百度发现, String原型上有个方法localeCompare,便可以实现方法judgeTwoStrDictionarySort的功能
// 如果string小于target，则localeCompare()返回小于0的数
// 如果大于,则返回大于0的数
// 如果相等,则返回0
if (preMinStr.localeCompare(curStr) > 0) {
    minIdx = i
}

提交结果

使用JavaScript实现根据baseUrl和字典排序后的查询参数列表queryParamsList生成完整URL

会发现，使用strA.localeCompare(strB)增加了消耗时间和空间消耗： 101 ms时间消耗，8.11 MB空间消耗，您的提交打败了84.37 %的提交。前面使用自己写的方法judgeTwoStrDictionarySort：85ms 时间消耗，7.78 MB空间消耗。

优化二：增加static，辅助属性和方法不被继承

同步lintcode优化解题思路

给类里的属性和方法增加static关键字，表示不被类的实例所继承，都会在类的本身constructor下挂着，打印类的实例，结果如下：

使用JavaScript实现根据baseUrl和字典排序后的查询参数列表queryParamsList生成完整URL

在类里公共方法和静态方法/属性的访问方式：

  • 公共方法里访问静态方法或静态属性的方式：通过this.constructor；
  • 静态方法里的this指向的是类本身即constructor；

完整代码（加上注释，95行）如下：

export class Solution {
    // 26个字母+数字+特殊字符
    static letterList = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","_","0","1","2","3","4","5","6","7","8","9"]
    /**
     * 获取字符在26字母列表的位置(索引+1)
     * @param {String} str 字符
     */
    static getLetterIndexByStr(str) {
        return !str ? 0 : this.letterList.indexOf(str[0].toLowerCase())+1
    }
    /**
     * preMinStr和curStr字典排序值比较(如果前者小于等于后者,则返回true;否则返回false)
     * @param {*} preMinStr 
     * @param {*} curStr 
     */
     static judgeTwoStrDictionarySort(preMinStr, curStr) {
        if (!preMinStr.length) return true
        if (!curStr.length) return false
        const preMinLetterIndex = this.getLetterIndexByStr(preMinStr)
        const curLetterIndex = this.getLetterIndexByStr(curStr)
        return preMinLetterIndex > curLetterIndex 
            ? false
            : preMinLetterIndex < curLetterIndex 
                ? true 
                : this.judgeTwoStrDictionarySort(preMinStr.slice(1), curStr.slice(1))
    }
    /**
     * 获取list里最小字典排序值的下标(如果数组长度为0，则返回-1)
     * @param {*} list 
     * @returns 
     */
    static getMinIxFromList(list=[]) {
        const curListLen = list.length
        if (!curListLen) return -1
        let minIdx = 0
        if (curListLen === 1) return minIdx
        for (let i = 1, j = curListLen; i < j; i++) {
            const preMinStr = list[minIdx][0]
            const curStr = list[i][0]
            if (!this.judgeTwoStrDictionarySort(preMinStr, curStr)) {
                minIdx = i
            }
        }
        return minIdx
    }
    /**
     * 按照二维数组的第一个项做字典排序
     * @param {Array} list 二维数组
     * @return 字典排序后的二维数组
     */
     static getDictionarySorting(list=[]) {
        // 过滤空的查询参数
        // list = list.filter(item=> item && item[0])
        const len = list.length
        if (!len) return []
        if (len === 1) return list
        let targetList = []
        while(list.length) {
            if (!list.length) break
            const minIdx = this.getMinIxFromList(list)
            if (minIdx < 0) break
            targetList.push(list[minIdx])
            list.splice(minIdx, 1)
        }
        return targetList
    }
    /**
     * 获取完整的URL
     * @param {*} baseUrl 
     * @param {*} queryParamsList
     * @return 完整的url
     */
     static getWholeUl(baseUrl, queryParamsList) {
        if (!baseUrl) return ""
        const queryLen = queryParamsList.length
        if (!queryLen) return baseUrl
        baseUrl += "?"
        for (let i = 0, j = queryLen; i < j; i++) {
            const curQuery = queryParamsList[i]
            baseUrl += curQuery[0] + "=" + curQuery[1]
            if (i < queryLen - 1) {
                baseUrl += "&"
            }
        }
        return baseUrl
    }
    /**
     * @param baseUrl: the string of base_url
     * @param queryParamsList: sequence of two-element tuples by query_params
     * @return: return a url query string
     */
    urlencode(baseUrl, queryParamsList) {
        return this.constructor.getWholeUl(baseUrl, this.constructor.getDictionarySorting(queryParamsList))
    }
}

总结

面对一个简单OR复杂的逻辑，首先要做的便是以结果为导向，对功能拆分（最好将流程图画出来，能更好的帮助梳理思路）；其次：功能的具体实现（代码健壮性、可维护性等）；然后：测试；最后：优化。

使用JavaScript实现根据baseUrl和字典排序后的查询参数列表queryParamsList生成完整URL

参考

es6 阮一峰，类的静态属性、静态方法

转载自:https://juejin.cn/post/7259372449834549305
评论
请登录