Leetcode 题解

这是一份不定期更新的笔记。封面 pid:77734148

1.两数之和

原题
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

输入： nums = [2, 7, 11, 15], target = 9
输出： [0,1]

var twoSum = function(nums, target) {
    let map ={};
    // nums某个数=>该数的下标
    for(let i in nums){
        //for num in nums，在map中检查是有 num 的差值，有就返回
        if(!isNaN(map[target-nums[i]]))return [i,map[target-nums[i]]];
        //录入num
        map[nums[i]] = i;
    }
};

2.两数相加

原题
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

/**
 * 节点定义
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
var addTwoNumbers = function(l1, l2) {
    let x,y,tmp,c=0,ret = new ListNode(0);
    let cur = ret;
    while(l1||l2){
        //如果到尽头了，当做0
        x = l1?l1.val:0;
        y = l2?l2.val:0;
        tmp = x + y + c;
        c = tmp>=10?1:0;
        cur.next = new ListNode(tmp%10);
        cur = cur.next;
        //先到尾的就维持为 null
        l1 && (l1 = l1.next);
        l2 && (l2 = l2.next);
    }
    //最后还有进位就再加一位
    c && (cur.next = new ListNode(c))
    return ret.next;
};

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

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

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

var lengthOfLongestSubstring = function(s) {
    let p1,p2,max=0,i1,i2,map={};//使用hashmap查重
    i1 = i2 = p1 = p2 = 0;
    while(p2<s.length){
        //p1,p2组成移动窗口，维护一个无重复字符的窗口
        //后指针p2尽量往后移
        if(!map[s[p2]]){
            map[s[p2]] = 1;
            p2++;
        }
        //p2后移出现重复，前指针p1后移直到重复消除
        else{
            delete map[s[p1]];
            p1++;
        }
        if(p2-p1>max){
            //i1,i2记录最长子串的起始点，max记录其长度
            i1 = p1;
            i2 = p2;
            max = p2 - p1
        }
    }
    //因为p2++的存在，max是默认加一的
    return max
};

5.最长回文子串

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

输入: "babad"
输出: "bab"/"aba"

var longestPalindrome = function(s) {
    //中心扩展算法
    if(!s)return '';
    let [left,right,len,maxStart,maxLen] = [0,0,1,0,0];
    for(let i=0;i<s.length;i++){
        left = i - 1;
        right = i + 1;
        //i指向中心，首先从中心向两边扩展，寻找最长重复串
        while(left>=0&&s[i]==s[left]){
            len++;
            left--;
        }
        while(right<s.length&&s[i]==s[right]){
            len++;
            right++;
        }
        //最长重复串的基础再向两边（等长）扩展，要求两边相等
        while(left>=0 && right<s.length && s[left]==s[right]){
            len += 2;
            left--;right++;
        }
        //有更长的回文，记录其开始点和长度
        if(len>maxLen){
            maxLen = len;
            maxStart = left+1;
        }
        //中心下移，len重置
        len = 1;
    }
    return s.substr(maxStart,maxLen);
};

6.Z 字形变换

原题
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。请实现这个将字符串进行指定行数变换的函数

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

var convert = function(s, numRows) {
    //从上往下扫描算法
    //排除空串、长度不大于行数的串、行数为1的情况
    if(!s)return '';
    if(numRows==1||s.length<=numRows)return s;
    //分别是取值下标、s长度、返回结果
    let [ind,len,res] = [0,s.length,''];
    //最长间隔
    let maxInterval = 2*(numRows-1);
    //最长间隔分成前后两个小间隔
    let front,back;
    //从上到下逐行填充
    for(let i=0;i<numRows;i++){
        ind = i;
        front = maxInterval - i*2;
        back = i*2;
        res += s[ind];
        while(ind<len){
            //前后间隔中不为0的那个，作为步幅加到当前下标并取值（如果没超出索引范围）
            if(front){
                ind+=front;
                ind<len && (res+=s[ind]);
            }
            if(back){
                ind+=back;
                ind<len && (res+=s[ind]);
            }
        }
    }
    return res;
};

7.整数反转

原题
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。假设数值范围为 [−231, 231 − 1]，如果反转后整数溢出那么就返回 0。

输入: 123/-123/120
输出: 321/-321/21

var reverse = function(x) {
    let ret = 0;
    while(x!=0){
        if(ret > 214748364 || ret < -214748364)
            return 0;
        ret = ret*10 + x%10;
        x = x>0?Math.floor(x/10):Math.ceil(x/10);
    }
    return ret;
};

8.字符串转换整数

原题
根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

• 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
• 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
• 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换，返回 0

输入: "42"/"- 42"/"www114"/"114www"
输出: 42/-42/0/114

//最简正则
var myAtoi = function(str) {
    let ret = /^[+-]?\d+/.exec(str.trim());
    if(ret===null)return 0;
    return Math.min(Math.max(parseInt(ret[0]),-2147483648),2147483647);
};

11.盛最多水的容器

原题
给定若干个非负整数列 an，对应坐标（n,an），对n个坐标作垂线，相邻两条垂线间隔为1，任两条垂线和横坐标能能组成一个u型容器，先求该容器的最大容量（满足木桶原理）

输入：[1,8,6,2,5,4,8,3,7]
输出：49

var maxArea = function(height) {
    //前后双指针解法
    let [p1,p2,ret,tmp] = [0,height.length-1,0,0];
    while(p1!=p2){
        //计算面积并保留大值
        tmp = Math.min(height[p1],height[p2]) * (p2-p1);
        if(tmp>ret)
            ret = tmp;
        //值小的指针往另外的方向移动
        height[p1]>height[p2]?p2--:p1++;
    }
    return ret;
};