JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。

一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。
因此，我作为一名前端菜鸡，打算做一个专栏，就是关于用JavaScript来解答算法题，会持续跟新，希望大家督促。同时，本人才疏学浅，文章内容可能有错误的地方，希望各位大神指出，谢谢。
no more bb, show me the code!

题目均来自乐扣（leetcode）

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

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

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

这题不难，遍历nums，用targer减去当前元素，得到的元素如果在数组中，那就完事了。不过要注意统一元素不能用两次

var twoSum = function(nums, target) {
    let idx1, idx2;
    nums.forEach((ele, index) => {
        let tempIdx = nums.indexOf(target - ele);
        if(tempIdx !== -1 && tempIdx !== index){
            idx1 = index;
            idx2 = tempIdx;
        }
    });
    return [idx1, idx2]
};

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

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

这题不难，不过稍微有点复杂，涉及到了链表，同时考擦了js大数的运算情况。
先遍历两个链表获得对应的数字，然后相加，最后反推算出结果对应的链表即可。

function ListNode(val) {
      this.val = val;
      this.next = null;
    return {
        val: this.val,
        next: null
    }
}

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

var addTwoNumbers = function(l1, l2) {
    let num1 = "", num2 = "", cur;
    cur = l1;

    while(cur){
        num1 += cur.val.toString();
        cur = cur.next;
    }
    cur = l2;
    while(cur){
        num2 += cur.val.toString();
        cur = cur.next;
    }
    num1 = num1.split("").reverse().join("");
    num2 = num2.split("").reverse().join("");
    
    let total;
    if(num1.length > 21 || num2.length > 21){
        total = addBigNumber(num1, num2)
    }
    else{
        total = Number(num1) + Number(num2)
    }

    total = total.toLocaleString().toString().split("").reverse().join("").replace(/,/g, "")
    console.log(num1, num2, total)
    
    let l3 = ListNode(total[0]);
    cur = l3;
    for(let i = 1; i < total.length; i++){
        let node = ListNode(total[i]);
        cur.next = node;
        cur = node;
    }

    return l3;
};

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

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

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

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

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

维护一个数组用于存放无重复子串，遍历输入的字符串，若当前字符不在无重复数组中，则添加，否则，无重复数组清空，并push当前字符。
同时要维护另外一个最长无重复子串的数组。

var lengthOfLongestSubstring = function(s) {
    let max = 0, maxArr = [], oldArr= [];
    s.split("").forEach((ele, index) => {
        if(maxArr.indexOf(ele) === -1){
            maxArr.push(ele)
            if(maxArr.length > max){
                max = maxArr.length;
            }
        }
        else{
            maxArr = [ele]
            let tempItem = oldArr.pop();
            while(tempItem != ele){
                maxArr.unshift(tempItem)
                tempItem = oldArr.pop();
            }
        }
        oldArr = [...maxArr]
    })
    return max;
};

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

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

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

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

将两个数组合并然后排序，之后获取中位数即可。问题在于限定时间复杂度为 O(log(m + n))的情况下，如何排序呢？
我们这里直接使用sort()方法，该方法底层原理是将多个排序集于一体，根据数组的长度不同选择不同的排序方法，加上V8引擎的优化，综合来说时间复杂度是能满足的。
好像有点偷鸡摸狗的感觉。。。
sort方法的源码：Array API源码，从710行开始看吧

var findMedianSortedArrays = function(nums1, nums2) {
    let num = nums1.concat(nums2);
    num = num.sort((a, b) => a - b);
    let mid = Math.floor(num.length / 2);
    if (num.length % 2 === 0) {
        return (num[mid-1] + num[mid])/2
    } else {
        return num[mid]
    }
};

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

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

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

这题要用动态规划来做，先是判断出所有长度为1,2,3的子串是否回文。
长度为1，必定回文。
长度为2或者3，取决于首位字符是否相同。
长度大于3，取决于该子串去掉首位字符之后是否回文，并且首位字符是否相同。
核心在于 dp[i][j] == dp[i+1][j-1] && s[i] === s[j]

var longestPalindrome = function(s) {
    let dp = [];
    for(let i = 0; i < s.length; i++){
        dp[i] = [];
    }

    let max = -1, str = "";
    for(let k = 0; k < s.length; k++){
        // k为所遍历的子串长度 - 1，即左下标到右下标的距离
        for(let i = 0; i + k < s.length; i++){
            let j = i + k;
            // i为子串开始的左下标，j为子串开始的右下标
            if(k == 0){
                // 当子串长度为1时，必定是回文
                dp[i][j] = true;
            }
            else if(k <= 2){
                // 当子串长度为2时，两字符相同则符合回文，长度为3，首位字符相同则符合回文
                if(s[i] == s[j]){
                    dp[i][j] = true;
                }
                else{
                    dp[i][j] = false;
                }
            }
            else{
                // 当子串长度超过3，取决于去掉头尾之后的子串是否回文并且首位字符是否相同
                if(dp[i+1][j-1] && (s[i] == s[j])){
                    dp[i][j] = true;
                }
                else{
                    dp[i][j] = false;
                }
            }

            if(dp[i][j] && k > max){
                max = k;
                str = s.substring(i, j + 1)
            }
        }
    }

    return str;
};

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

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

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

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

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

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

这题目的结构有点怪，但也是有规律可循的，我们发现这个”Z“的字符顺序是这样子的：垂直向下，斜向上，然后再垂直向下。
那其实我们可以直接将该结构简化为一个二维数组，去掉中间的空格，再一行一行地遍历就能获取到答案了。
如：

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

可以变成

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

接着再一行一行读，拼成字符串，便可。

var convert = function(s, numRows) {
    if(numRows == 1){
        return s;
    }

    let arr = [], direction = "down", line = 0, str = "";
    for(let i = 0; i < numRows; i++){
        arr[i] = [];
    }

    for(let i = 0; i < s.length; i++){
        arr[line].push(s[i]);

        if(line == 0){
            line++;
            direction = "down"
        }
        else if(line == numRows - 1){
            line--;
            direction = "up"
        }
        else{
            if(direction == "down"){
                line++;
            }
            else if(direction = "up"){
                line--;
            }
        }
    }

    for(let i = 0; i < numRows; i++){
        str += arr[i].join("");
    }

    return str;
};

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

输入: 123
输出: 321

输入: -123
输出: -321

输入: 120
输出: 21

这题就很简单了，不过要考虑好边缘溢出情况即可。

var MAX = Math.pow(2, 31) - 1
var MIN = -1 * Math.pow(2, 31)

var reverse = function(x) {
    let str = x.toString().split(""), symbolFlag = false;
    if(str[0] == "-"){
        symbolFlag = true;
        str.shift();
    }

    str = str.reverse();

    if(symbolFlag){
        str.unshift("-");
    }
    let num = Number(str.join(""))
    if(num < MIN || num > MAX){
        return 0
    }
    else{
        return num
    }
};

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，qing返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

题目很长是吧，没关系，我们直接看示例。

输入: "42"
输出: 42

输入: " -42"
输出: -42
解释: 第一个非空白字符为 "-", 它是一个负号。
  我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 "3" ，因为它的下一个字符不为数字。

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 "w", 但它不是数字或正、负号。
因此无法执行有效的转换。

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

这题不难，但是有很多坑。首先我们采取ASCII编码的方式来判断字符为数字还是英文还是别的。
先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回0，若数字则不取。
从第二个字符开始遍历，若不是数字则退出循环。
最后还要考虑溢出情况。

const MIN = -1 * Math.pow(2, 31);
const MAX = Math.pow(2, 31) - 1;

var myAtoi = function(str) {
    str = str.trim();
    let result = "", symbol = "";
    let idx = 0;

    if(str.charCodeAt(0) === 45){
        idx++;
        symbol = "-";
    }
    else if(str.charCodeAt(0) === 43){
        idx++;
    }
    else if(str.charCodeAt(0) < 48 || str.charCodeAt(0) > 57){
        return 0;
    }

    for(let i = idx; i < str.length; i++){
        if(str.charCodeAt(i) === 46){
            break;
        }
        else if(str.charCodeAt(i) >= 48 && str.charCodeAt(i) <= 57){
            result += str[i];
        }
        else{
            break
        }
    }

    result = symbol.toString() + result.toString();

    if(Number(result) !== Number(result)){
        return 0;
    }
    else if(Number(result) < MIN){
        return MIN;
    }
    else if(Number(result) > MAX){
        return MAX;
    }
    else{
        return Number(result)
    }
};

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

输入: 121
输出: true

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数

这题比较简单，反转对比即可

var isPalindrome = function(x) {
    let y = x.toString().split("").reverse().join("");
    return x == y
};

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 "." 和 "*" 的正则表达式匹配。

"." 匹配任意单个字符
"*" 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 "*" 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 "a"。因此，字符串 "aa" 可被视为 "a" 重复了一次。

输入:
s = "ab"
p = ".*"
输出: true
解释: "." 表示可匹配零个或多个（""）任意字符（"."）。

输入:
s = "aab"
p = "cab"
输出: true
解释: 因为 "*" 表示零个或多个，这里 "c" 为 0 个, "a" 被重复一次。因此可以匹配字符串 "aab"。

输入:
s = "mississippi"
p = "misisp*."
输出: false

这题稍微有点复杂，我们采用了递归方法将两个字符串对比，每次只对比一个字符。
将当前递归p的下一个字符是否为*进行分类比较：
①p的下一个字符是*
若s和p的当前字符相同或者p的当前字符为.，则结果就取决于：

isMatch(s.slice(1), p) || isMatch(s.slice(1), p.slice(2)) || isMatch(s, p.slice(2))

若p的最后两个字符为.*就返回true
若不符合上面两种情况就将取决于

isMatch(s,p.slice(2))

②p的下一个字符不为*
这种情况就简单了
若s和p的当前字符相同或者p的当前字符为.，返回true
否则返回false

var isMatch = function(s, p) {
    if(s.length === 0 && p.length === 0){
        return true;
    }
    if(s.length !== 0 && p.length === 0){
        return false;
    }

    let str = s[0], pattern = p[0];
    let isNextStart = p[1] === "*";

    if(isNextStart){
        if(str && (str === pattern || pattern === ".")){
            return isMatch(s.slice(1), p) || isMatch(s.slice(1), p.slice(2)) || isMatch(s, p.slice(2))
        }
        else if(pattern === "." && p.slice(2).length === 0){
            return true
        }
        else{
            return isMatch(s,p.slice(2));
        }
    }
    else{
        if(str && (str === pattern || pattern === ".")){
            return isMatch(s.slice(1), p.slice(1))
        }
        else{
            return false;
        }
    }
};

本文所有题目均来自乐扣（leetcode），做法不唯一，甚至可能还有所错误，希望各位大神指出，弟弟虚心学习。