leetcode算法题js版

一粒小麦

发布于 2019-07-18 16:49:00

8860

发布于 2019-07-18 16:49:00

文章被收录于专栏：一Li小麦一Li小麦

世之奇伟，瑰怪，非常之观常在于险远。如果不是为了更好的工作机会，我才懒得刷。

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解析

已经战胜 70.19 % 的 javascript 提交记录

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    for(let i=0;i<nums.length;i++){
        for(let j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                return [i,j]
            }
        }
    }
};

// console.log(twoSum([2, 7, 11, 15], 9))

2.两数相加

实现大数加法。

js的number类型有个最大值（安全值）。即2的53次方，为9007199254740992。如果超过这个值，那么js会出现不精确的问题。这个值为16位。

示例：

输入：148004249825564012 + 148004249825564019
输出：296008499651128031 （js计算是296008499651128060）

解析

思路是转字符串把小学做加法的过程写下来就可以。

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    l1=l1.split('')
    l2=l2.split('')  
    let arr1 = l1.length >= l2.length?l2:l1;
    let arr2 = arr1==l2 ? l1 : l2;
    let arr=[];
    let add=0;

    for (let i = arr1.length; i > 0; i--) {
        let a = (Number(arr1[i - 1])) + Number(arr2[arr2.length - (arr1.length - i) - 1])+ add
        add = a >= 10 ? 1 : 0;
        arr.push(Number(a.toString()[a.toString().length - 1]))
    }

    for (let i = arr2.length - arr1.length;i>0;i--){
        let a = Number(arr2[i - 1])+add;
        add=a>=10?1:0;
        arr.push(Number(a.toString()[a.toString().length - 1]));
    }

    if(add>0){
        arr.push(1)
    }

    return arr.reverse().join('');
};

console.log(addTwoNumbers('148004249825564012', '148004249825564019'), 148004249825564012 + 148004249825564019)

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 *最长子串 *的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解析

首先要找到数组中字符串的重复值。然后判断。

执行用时108 ms, 在JavaScript提交中击败了88.92% 的用户。主要是考虑执行过程中生成滑标。

var lengthOfLongestSubstring = function (s) {
    let count='';
    let arr=[];
    let len=s==''?0:1//判断空字符串返回0
    for(let i=0;i<s.length;i++){
        if(count.indexOf(s[i])!==-1){      
            arr.push(count);  
            count = count.substr(count.indexOf(s[i])+1)//关键
        }
        count += s[i]
        if(i==s.length-1){
            arr.push(count);  
        }
    }

    for (let j = 0; j < arr.length; j++) {

        if (arr[j].length > len) {
            len=arr[j].length
        }
    }
    return len
};

4. 寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解析

中位数（又称中值，英语：Median），统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。

对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。

var findMedianSortedArrays = function (nums1, nums2) {
    let result=0;
    let arr=nums1.concat(nums2).sort((a,b)=>{
        return b-a;
    })
    if(arr.length%2==1){
        result = arr[parseInt(arr.length / 2)]
    }else{
        let h = arr[(arr.length / 2)-1]
        let l = arr[(arr.length / 2)]
        result = (h + l) / 2
    }

    return result;
};

5.最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

解析

这种题是可能暴力破解的。

var longestPalindrome = function (s) {
    // 暴力破解

    if (s.length == 0 || s.length ==1){
        return s
    }

    let arr=[]

    for (let size = s.length ;size>0;size--){

        for(let i=0;i<s.length;i++){
            let _s=s;
            let str=_s.substring(i,i+size)

            let _str=str+str.split('').reverse().join('');
            let __str = str + s[i+size] + str.split('').reverse().join('');

            if (s.indexOf(_str) !== -1 ){
                arr.push(_str)
            }

            if (s.indexOf(__str) !== -1){
                arr.push(__str)
            }
        }
    }

    if(arr.length==0){
        return s[0]
    }else{

        let len=0
        for(let i=0;i<arr.length;i++){
            if(arr[len].length<arr[i].length){
                console.log(len)
                len=i
            }
        }

        return arr[len]
    }

};

但这段代码费内存了，可考虑这样

var longestPalindrome = function (s) {
    var temS = ['#'],
        subMidd = 0,
        subRightSide = 0,
        rightLen = [1]

    for (var i = 0, len = s.length; i < len; i++) {
        temS.push(s[i], '#')
    }

    for (i = 1, len = temS.length; i < len; i++) {
        if (i < subRightSide) {
            var j = 2 * subMidd - i
            if (rightLen[j] <= subRightSide - i) {
                rightLen[i] = rightLen[j]
            } else {
                rightLen[i] = subRightSide - i + 1
            }
        } else {
            rightLen[i] = 1
        }

        while (i - rightLen[i] >= 0 && i + rightLen[i] < len && temS[i - rightLen[i]] === temS[i + rightLen[i]]) {
            rightLen[i] += 1
        }

        if (rightLen[i] >= rightLen[subMidd]) {
            subRightSide = rightLen[i] + i - 1
            subMidd = i
        }
    }
    return s.slice((2 * subMidd - subRightSide) / 2, subRightSide / 2)
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-01-01，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自一Li小麦微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度