分类：每日一题

题目

首先还是最原始的自己思考解决方法。。

思路就是，遍历+校验是否有重复+递归，效率低下，惨不忍睹。不过是自己思考的。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // 子串是相连的
    // 子序列是不相连
    if(s == ''){
        return 0;
    }
    var maxLength=1;
    var k = 0;
    for(var i=0;i<s.length;i++){
        var tempMax = 1;
        var tempList = [s[i]];
        k = i;
        function checkRepeat(list,value){
            for(var item of list){
                if(item == value){
                    return true;
                }
            }
            return false;
        }
        function checkNext(){
            k = k+1;
            if(s[k]){
                if(checkRepeat(tempList,s[k])){
                    // 有重复
                    if(tempMax>maxLength){
                        maxLength=tempMax;
                    }
                }else{
                    // 无重复
                    tempList.push(s[k]);
                    tempMax++;
                    if(tempMax>maxLength){
                        maxLength=tempMax;
                    }
                    checkNext()
                }
            }
        }
        checkNext();
    }
    return maxLength;
};

然后是标准答案是使用滑动窗口。

其实这个应该是链表直接加就行了。。我开始想错了，然后搞笑的玩意来了。把我给气笑了。

测试用例有个

[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1] [5,6,4]

JS存的表示为

对于过长的数字，JS显示为1E+30.。。。牛逼。

function sumStrings(a,b){
  var res='', c=0;
  a = a.split('');
  b = b.split('');
  while (a.length || b.length || c){
      c += ~~a.pop() + ~~b.pop();
      res = c % 10 + res;
      c = c>9;
  }
  return res.replace(/^0+/,'');
 
}

https://www.jianshu.com/p/c373943f0e9e js大数相加问题

JS处理大数相加，一般引用BigNumber.js。。查了下核心代码，加法的计算如下。

 // adds two positive BigNumbers
    BigNumber._add = function(a, b) {
        var index;
        var remainder = 0;
        var length = Math.max(a.number.length, b.number.length);

        for (index = 0; index < length || remainder > 0; index++) {
            a.number[index] = (remainder += (a.number[index] || 0) + (b.number[index] || 0)) % 10;
            remainder = Math.floor(remainder / 10);
        }

        return a.number;
    };

a.number = []，是个数组 array : [3,2,1], [‘+’,3,2,1], [‘-‘,3,2,1]。所以说，我存储的结构必须改变为数组。

原来的思路PASS。

完成版本。。。效率惨不忍睹。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var numListA = [];
    var numListB = [];
    var resultArr = [];
    getListNodeArr(numListA,l1);
    getListNodeArr(numListB,l2);
    console.log(numListA)
    resultArr = add(numListA,numListB)
    console.log(resultArr)
    return array2ListNode(resultArr)

    function array2ListNode(arr){
        var line = arr.map((i,j)=>{
            return new ListNode(i)   
        })
        for(var j = 0;j<= line.length; j++){
            line[j+1] && (line[j].next = line[j+1])
        }
        return line[0]
    }
    function getListNodeArr(listArr,listNode){
        if(listNode.next!=null){
            listArr.push(listNode.val)
            getListNodeArr(listArr,listNode.next)
        }else{
            listArr.push(listNode.val)
        }
    }
    function add(listA,listB){
        var index;
        var remainder = 0;
        var length = Math.max(listA.length, listB.length);

        for (index = 0; index < length || remainder > 0; index++) {
            listA[index] = (remainder += (listA[index] || 0) + (listB[index] || 0)) % 10;
            remainder = Math.floor(remainder / 10);
        }
        return listA;
    }
};

好吧，看了官方解法。

很简单，逆序保证了，低位对齐。然后进一位，记录.

var addTwoNumbers = function(l1, l2) {
    var result = temp = new ListNode(0)
    while(l1 || l2){
        var sum = (l1 && l1.val || 0) + (l2 && l2.val || 0) + ( temp.val || 0 )
        var carry = parseInt(sum / 10)
        l1 = l1 && l1.next
        l2 = l2 && l2.next
        temp.val = (sum % 10)
        if(l1 || l2 ||carry){
            temp.next = new ListNode(carry)
        }
        temp = temp.next
    }
    return result
};

貌似标准答案也没有快很多，空间占用也挺多的.

气死个人。。一晚上，没什么提速。感觉leetcode有问题。

C语言真的强。。算法是一样的。

惊了，java只要2ms，wtf

TwoSum

速度有点慢。。再优化下。不过解题思考只花了5分钟。。

var twoSum = function(nums, target) {
    if(nums==null ||nums.length==0 || target == null){
        return;
    }
    var curpos = 0;
    while(curpos<=nums.length){
        if(curpos == nums.length){
            return;
        }
        for(var i=(curpos+1);i<nums.length;i++){
            if(nums[curpos]+nums[i] == target){
                return [curpos,i]
            }
        }
        curpos++
    }
};

Ok,68ms…增加一倍速度。。有点欢乐。真不道如何比这个还快。

执行用时 :68 ms, 在所有 JavaScript 提交中击败了81.18%的用户

//Hash表解法。应该是所有语言的标准解法，60 ms

很奇怪的是，

var twoSum = function(nums, target) {
    let numsObj = {}
    for (let i = 0; i < nums.length; i++) {
        let current = nums[i]
        let match = target - current
        if (match in numsObj) {
            return [i, numsObj[match]]
        }
        numsObj[current] = i
    }
};

经过测试。。每次提交结果都不同。见鬼了这玩意

所以测试用例是随机生成的。这个速度如果是简单的题目，也是看运气。