手记

咱一起来刷一刷leetCode的题吧

leetCode有兴趣的可以去看看,我们直接上干货啦= =

第一道题 - 难度(★)

输入一个数组跟一个目标值,当数组中某两个数之和等于目标值,返回这两个数的索引(下标)注意这两个数不能相同。(如果内部有多对符合要求的输出一对即可)
最简单直观的方式就是来一个O(n²)的for循环嵌套对吧?

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

这个虽然简单,但是性能较差,能不能用O(n)的方式实现呢?怎么实现?

const handle = (nums, target) => {
    
    let map;
    
    for(let i = 0; i < nums.length; i ++) {
        
        map = target - nums[i];
        
        if(nums.indexOf(map) !== i && nums.includes(map)) {
            
            return [i, nums.indexOf(map)]
            
        }
        
    }
    
}


var twoSum = function(nums, target) {
    
    return handle(nums, target);
    
};

这种方式呢,虽说看似只有一个for循环,但indexOf,includes方法都是比较耗时的,因而也不建议用。从下图中也可以看出,该方法较第一种我们认为比较慢的方法还整整慢了接近4倍。
这里比较推荐的方式呢,就是采用一个较为cool的一种方式,利用对象的key-value来快速对应,类似于map映射。
那它的思想是怎样的?假设要从[2,7,9,11]中找出两个数和为9,先把第一个的数据存入对象{2: 0},这时候你思考下,目标值 - 数组每一项出来的是什么?如果说数组中的数据比如第2个是7,这个7,目标值 - 7是不是刚好是2?也就是说,如果这个对象里面有数值的和为9,那么目标值减去数组的每一项的这个值一定是对象中的某个key。对吧?
我们一起看看代码是怎样实现的吧。

const handle = (nums, target) => {
    
    let map = {},
        result = [];
    
    for(let i = 0; i < nums.length; i ++) {
        
        let firstNum = target - nums[i];
        
        typeof map[firstNum] != "undefined" ? result.push(map[firstNum], i) : map[nums[i]] = i;
        
    }
    return result;
    
}


var twoSum = function(nums, target) {
    
    return handle(nums, target);
    
};

而此时所花的时间呢?72ms,大大的提升了效率,对吧?

这种通过对象的key来快速定位的情况在算法中应用很广泛,因为你可能就直接少了一个维度的循环,对象怎么快速找到这个key的,你不用管,反正,是基于底层实现,类似于数据库或者es,查索引的方式是无比快速的。远比你写一个for循环快。

嗯好了,第一道题铺得有点开,后面简单点。

第二道题 - 难度(★★)

找出一个字符串中最长不重复片段,返回这个片段的长度。
看似不难,其实有坑。那要完成这个的思路又是怎样?在我个人看来,就是一个水漫金山的过程。
我们看看实现的代码是怎样哈:

var lengthOfLongestSubstring = function(s) {

    let map = {},
        current = 0,
        max = 0;
    
    for(let i = 0; i < s.length; i ++) {
          
        current = map[s[i]] >= current ? map[s[i]] + 1 : current;
        
        map[s[i]] = i;
        
        max = max > i - current + 1 ? max : i- current + 1;
        
    }
    
    return max;
}

当然这里其实解法有很多种,但是这种方式是O(n)的方式,会比较快,性能较好。如果有更好的思路欢迎提出讨论。

第三题 - 难度(★★★)

输入两个数组,找出这两个数组所有数的中位数。注意时间复杂度应该为O(log(m + n))
我们先不管要什么时间复杂度,我们是新手,我不会。呵呵。
那我们需要怎样的思路,来完成这个东西呢?
最简单的,不是查找中位数嘛,我合并这两个数组,给他们排序,再取最中间的那一个或两个对吧?是不是很简单?
说到排序,还记得我们之前说过的,各种排序吗?我们用个简单的快排来实现一下吧。(当然直接用sort方法也是好的)

const interchange = (arr, i, k) => [arr[i], arr[k]] = [arr[k], arr[i]];

const sort = (left, right, arr) => {
    
    let i = left,
        j = right,
        reference = arr[left];
    
    if(i >= j) return;
    
    while(i < j) {
        
        while(i < j && arr[j] >= reference) j --;
        
        while(i < j && arr[i] <= reference) i ++;

        arr[i] > arr[j] && interchange(arr, i, j);
        
        
    }
    
    interchange(arr, left, i);
    
    sort(left, i - 1, arr);
    sort(i + 1, right, arr);
}

var findMedianSortedArrays = function(nums1, nums2) {
    
    let arr = nums1.concat(nums2),
        len = arr.length;
    
    sort(0, len - 1, arr);
    
    return len%2 ? arr[Math.floor(len/2)] : (arr[len/2 - 1] + arr[len/2]) / 2;
    
};

这里个人觉得这种方法还是比较慢,有什么更好的方式多谢指教。

第四题 - 难度(★★)

找出一个字符串中最长的回文字符串。
首先呢什么是回文字符串?就是跟我们古时候的回文联一样的,正倒念都是一样,比如地满红花红满地 ,天连碧水碧连天。那我们怎么实现呢?
首先肯定是写一个逻辑判断是否是字符串对吧?再写一个逻辑查找过程是吧?
这个其实也是一个水漫金山的过程:
那又怎么查找?回文的字符串可能是"aba",也可能是"bb",或者是"abba",甚至就单单一个"a",我的实现思路是这样:长度超过2的情况下,如果最终的结果的长度是奇数,那就是会有i - k 跟 i + k是一样的对吧?一定是的?对吧?如果长度是偶数呢?那一定会存在着最中间有偶数个数是一样的,对吧?比如"abba",“abccba”,“abbbba”,只要找到最中央这两个数,再还是按照第一种的方式一步步往外漫,比如设置一个k值,慢慢一步步加,只要两侧是相等的,就加1,这样是不是就能找到我们所有的回文字符串?再对比每一个回文字符串的长度,拿出最长的是不是就可以了?当然,要更快的话还是跟上面的一样,存的这个中间量(result)比原来的长就更新,不长就不管
看看代码是怎样的哈:

const palindromic = str => str.split("").reverse().join("") === str ? true : false;

const handle = s => {
    let result = s[0];
    
    for(let i = 0; i < s.length; i ++) {    

        if(s[i - 1] === s[i + 1]) {         
            let k = 2;      
            while(s[i - k] === s[i + k]) {       
                k ++; 
            }
            result = result.length < (2 * k - 1) ? s.substr(i - (k - 1), 2 * k - 1) : result;
        }
        if(s[i] === s[i + 1]) {

            let k = 1;
            while(s[i - k] === s[i + 1 + k]) {
                k ++;
            } 
            result = result.length < 2 * k ? s.substr(i - (k - 1), 2 * k) : result;
        }
    }
    return result;
}
var longestPalindrome = function(s) {
    if(s === '' || s.length < 2 || palindromic(s)) return s;
    return handle(s);
};

这种方式应该算是较好的了,从结果上看的话,性能超过97.69%的同语言算法。

好啦,leetCode我就抛砖引玉到这里啦。比较好的一种提高我们思维模式的一个途径了。想去瞧瞧的,可以看这里leetCode

1人推荐
随时随地看视频
慕课网APP