你的浏览器还没开启 Javascript 功能!

一道算法题引起的自省

前言

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

1570693232338.jpg

图为某文章所言,鄙人不才,论尾处反转时间复杂度有余,故,可用递归实现之

function printListFromTailToHead(head) {
    var arr = [];
    function func(node) {
        if(node === null){
            return;
        }
        // 先处理下一个节点
        func(node.next);
        // 再放入数组
        arr.push(node.val);
    }
    func(head);
    return arr;
}

最长公共前缀

1570693248339.jpg

鄙人杠上头了…


/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    // 一:尝试用正则来匹配,(失败)
    // 
    // const r = /^(\w+)\w*,?(\1\w*,?)*\2*$/;
    // const rs = strs.join(',').match(r);
    // if(rs === null || !rs[1]) {
    //     return '';
    // }
    // return rs[1];

    // 二:按照普通正确思路(成功,84ms)
    // 
    //     if(strs.length === 0) {
    //         return '';
    //     }
    //     if(strs.length === 1) {
    //         return strs[0];
    //     }

    //     let cindex = 0;
    //     let str = '';
    //     while(true){
    //         let c;
    //         for(let i = 0; i < strs.length; i++){
    //             const indexStr = strs[i];
    //             if(cindex >= indexStr.length) {
    //                 return str;
    //             }
    //             const indexChar = indexStr[cindex];
    //             if(c === void 0) {
    //                 c = indexChar;
    //             }else if(c !== indexChar) {
    //                return str; 
    //             }
    //         }
    //         cindex++;
    //         str += c;
    //     }

    // 三:尝试用字典树解决 (失败,暂时搁置,应该可以通过字典树解决)
    // 
    // function Node(c) {
    //     // 节点字符
    //     this.char = c;
    //     // 子节点数组
    //     this.subArray = [];
    // }
    // 
    // Node.prototype.addChar = function(char) {
    //     var hasSubNode = this.subArray.filter(c => c.char === char)[0];
    //     if(hasSubNode) {
    //         return hasSubNode;
    //     }
    //     var newSubNode = new Node(char);
    //     this.subArray.push(newSubNode);
    //     return newSubNode;
    // }
    // 
    // var head = new Node('');
    // var forEach = Array.prototype.forEach;
    // forEach.call(strs, (chars) => {
    //     var tempNode = head;
    //     if(chars === '') {
    //         tempNode = tempNode.addChar('');
    //     }else {
    //         forEach.call(chars, (c) => {
    //            tempNode = tempNode.addChar(c);
    //         });
    //     }
    // });
    // var s = '';
    // while(head !== null) {
    //     s += head.char;
    //     if(head.subArray.length === 1) {
    //         head = head.subArray[0];
    //     }else {
    //         break;
    //     }
    // }
    // return s;  

    // 四:尝试用动态规划 (通过,80ms)
    // 
    // dp[i] = 最大前缀(dp[i - 1], i);

    function func(s1, s2) {
        // 最大前缀只会越来越小
        var s3 = '';
        for(i = 0,l = s1.length; i < l; i++) {
            if(s1[i] !== s2[i]) {
                break;
            }
            s3 += s1[i];
        }
        return s3;
    }

    // 优化 不需要记录i,只用记录上一次的交集
    var dp_prev_str = strs[0];
    // 解决边界问题
    if(dp_prev_str === void 0 || dp_prev_str === '') {
        return '';
    }
    for(let i = 1; i < strs.length; i++) {
        // 状态转移
        dp_prev_str = func(dp_prev_str, strs[i]);
    }
    return dp_prev_str;
};

反省

如果我遇到一个问题,需要用算法的方式来解决,都是通过发散的思维来获取到当时使用哪种方法解决。
但是事后写到一半或者写完,反过来回想方法是错误抑或不是最好的。

所以,需要将常见的算法以及数据结构采取记忆,通过了解某类算法在那类场景最擅长解决,比如树,队列,链表等它们都有自己最适合的解决场景。
这样,将常见数据结构和算法熟悉之后,遇到问题时可以快速的采取正确的方向(后面可以优化,但至少方向不会有错),解决问题就事半功倍,而不是遇到问题直接就去套用当时的想法解决。

经验总结

  1. 遇到问题先确定场景,再考虑哪种算法方案适合
  2. 场景是复杂的,所以解决方案需要考虑多种数据结构和算法
  3. 数据结构和算法已经是沉淀好的精华,大多时候是利用而不是漫无目的创新
  4. 先解决问题,再考虑优化和发散性思维

当前目标

  1. 了解各类数据结构与算法,知道其使用的场景
  2. 利用已存在的数据结构和算法解决80%问题,再考虑优化和发散思维其它20%