摘要：先去空白，去掉空白之后取第一個(gè)字符，判斷正負(fù)符號(hào)，若是英文直接返回，若數(shù)字則不取。回文數(shù)題目描述判斷一個(gè)整數(shù)是否是回文數(shù)。回文數(shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。

一直以來，前端開發(fā)的知識(shí)儲(chǔ)備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認(rèn)為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。
因此，我作為一名前端菜雞，打算做一個(gè)專欄，就是關(guān)于用JavaScript來解答算法題，會(huì)持續(xù)跟新，希望大家督促。同時(shí)，本人才疏學(xué)淺，文章內(nèi)容可能有錯(cuò)誤的地方，希望各位大神指出，謝謝。
no more bb, show me the code!

題目均來自樂扣（leetcode）

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。

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

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

這題不難，遍歷nums，用targer減去當(dāng)前元素，得到的元素如果在數(shù)組中，那就完事了。不過要注意統(tǒng)一元素不能用兩次

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]
};

給出兩個(gè)?非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照?逆序?的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ)?一位?數(shù)字。
如果，我們將這兩個(gè)數(shù)相加起來，則會(huì)返回一個(gè)新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0?開頭。

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

這題不難，不過稍微有點(diǎn)復(fù)雜，涉及到了鏈表，同時(shí)考擦了js大數(shù)的運(yùn)算情況。
先遍歷兩個(gè)鏈表獲得對(duì)應(yīng)的數(shù)字，然后相加，最后反推算出結(jié)果對(duì)應(yīng)的鏈表即可。

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;
};

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長子串 的長度。

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。

輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是?"wke"，所以其長度為 3。

請(qǐng)注意，你的答案必須是 子串 的長度，"pwke"?是一個(gè)子序列，不是子串。

維護(hù)一個(gè)數(shù)組用于存放無重復(fù)子串，遍歷輸入的字符串，若當(dāng)前字符不在無重復(fù)數(shù)組中，則添加，否則，無重復(fù)數(shù)組清空，并push當(dāng)前字符。
同時(shí)要維護(hù)另外一個(gè)最長無重復(fù)子串的數(shù)組。

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;
};

給定兩個(gè)大小為 m 和 n 的有序數(shù)組?nums1 和?nums2。

請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為?O(log(m + n))。

你可以假設(shè)?nums1?和?nums2?不會(huì)同時(shí)為空。

nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0

nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5

將兩個(gè)數(shù)組合并然后排序，之后獲取中位數(shù)即可。問題在于限定時(shí)間復(fù)雜度為?O(log(m + n))的情況下，如何排序呢？
我們這里直接使用sort()方法，該方法底層原理是將多個(gè)排序集于一體，根據(jù)數(shù)組的長度不同選擇不同的排序方法，加上V8引擎的優(yōu)化，綜合來說時(shí)間復(fù)雜度是能滿足的。
好像有點(diǎn)偷雞摸狗的感覺。。。
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]
    }
};

給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。

輸入: "cbbd"
輸出: "bb"

這題要用動(dòng)態(tài)規(guī)劃來做，先是判斷出所有長度為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，即左下標(biāo)到右下標(biāo)的距離
        for(let i = 0; i + k < s.length; i++){
            let j = i + k;
            // i為子串開始的左下標(biāo)，j為子串開始的右下標(biāo)
            if(k == 0){
                // 當(dāng)子串長度為1時(shí)，必定是回文
                dp[i][j] = true;
            }
            else if(k <= 2){
                // 當(dāng)子串長度為2時(shí)，兩字符相同則符合回文，長度為3，首位字符相同則符合回文
                if(s[i] == s[j]){
                    dp[i][j] = true;
                }
                else{
                    dp[i][j] = false;
                }
            }
            else{
                // 當(dāng)子串長度超過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;
};

將一個(gè)給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進(jìn)行?Z 字形排列。
比如輸入字符串為 "LEETCODEISHIRING"?行數(shù)為 3 時(shí)，排列如下：

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

之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個(gè)新的字符串，比如："LCIRETOESIIGEDHN"。
請(qǐng)你實(shí)現(xiàn)這個(gè)將字符串進(jìn)行指定行數(shù)變換的函數(shù)：
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

這題目的結(jié)構(gòu)有點(diǎn)怪，但也是有規(guī)律可循的，我們發(fā)現(xiàn)這個(gè)”Z“的字符順序是這樣子的：垂直向下，斜向上，然后再垂直向下。
那其實(shí)我們可以直接將該結(jié)構(gòu)簡化為一個(gè)二維數(shù)組，去掉中間的空格，再一行一行地遍歷就能獲取到答案了。
如：

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;
};

給出一個(gè) 32 位的有符號(hào)整數(shù)，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。
注意:
假設(shè)我們的環(huán)境只能存儲(chǔ)得下 32 位的有符號(hào)整數(shù)，則其數(shù)值范圍為?[?231,? 231?? 1]。請(qǐng)根據(jù)這個(gè)假設(shè)，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 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
    }
};

請(qǐng)你來實(shí)現(xiàn)一個(gè)?atoi?函數(shù)，使其能將字符串轉(zhuǎn)換成整數(shù)。

首先，該函數(shù)會(huì)根據(jù)需要丟棄無用的開頭空格字符，直到尋找到第一個(gè)非空格的字符為止。
當(dāng)我們尋找到的第一個(gè)非空字符為正或者負(fù)號(hào)時(shí)，則將該符號(hào)與之后面盡可能多的連續(xù)數(shù)字組合起來，作為該整數(shù)的正負(fù)號(hào)；假如第一個(gè)非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來，形成整數(shù)。
該字符串除了有效的整數(shù)部分之后也可能會(huì)存在多余的字符，這些字符可以被忽略，它們對(duì)于函數(shù)不應(yīng)該造成影響。

注意：假如該字符串中的第一個(gè)非空格字符不是一個(gè)有效整數(shù)字符、字符串為空或字符串僅包含空白字符時(shí)，則你的函數(shù)不需要進(jìn)行轉(zhuǎn)換。
在任何情況下，若函數(shù)不能進(jìn)行有效的轉(zhuǎn)換時(shí)，請(qǐng)返回 0。

說明：
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位大小的有符號(hào)整數(shù)，那么其數(shù)值范圍為?[?231,? 231?? 1]。如果數(shù)值超過這個(gè)范圍，qing返回 ?INT_MAX (231?? 1) 或?INT_MIN (?231) 。

題目很長是吧，沒關(guān)系，我們直接看示例。

輸入: "42"
輸出: 42

輸入: " -42"
輸出: -42
解釋: 第一個(gè)非空白字符為 "-", 它是一個(gè)負(fù)號(hào)。
? 我們盡可能將負(fù)號(hào)與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來，最后得到 -42 。

輸入: "4193 with words"
輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 "3" ，因?yàn)樗南乱粋€(gè)字符不為數(shù)字。

輸入: "words and 987"
輸出: 0
解釋: 第一個(gè)非空字符是 "w", 但它不是數(shù)字或正、負(fù)號(hào)。
因此無法執(zhí)行有效的轉(zhuǎn)換。

輸入: "-91283472332"
輸出: -2147483648
解釋: 數(shù)字 "-91283472332" 超過 32 位有符號(hào)整數(shù)范圍。
因此返回 INT_MIN (?231) 。

這題不難，但是有很多坑。首先我們采取ASCII編碼的方式來判斷字符為數(shù)字還是英文還是別的。
先去空白，去掉空白之后取第一個(gè)字符，判斷正負(fù)符號(hào)，若是英文直接返回0，若數(shù)字則不取。
從第二個(gè)字符開始遍歷，若不是數(shù)字則退出循環(huán)。
最后還要考慮溢出情況。

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)
    }
};

判斷一個(gè)整數(shù)是否是回文數(shù)。回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。

輸入: 121
輸出: true

輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。因此它不是一個(gè)回文數(shù)。

輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個(gè)回文數(shù)

這題比較簡單，反轉(zhuǎn)對(duì)比即可

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

給你一個(gè)字符串?s?和一個(gè)字符規(guī)律?p，請(qǐng)你來實(shí)現(xiàn)一個(gè)支持 "."?和?"*"?的正則表達(dá)式匹配。

"." 匹配任意單個(gè)字符
"*" 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
所謂匹配，是要涵蓋?整個(gè)?字符串?s的，而不是部分字符串。

說明:
s?可能為空，且只包含從?a-z?的小寫字母。
p?可能為空，且只包含從?a-z?的小寫字母，以及字符?.?和?*。

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個(gè)字符串。

輸入:
s = "aa"
p = "a*"
輸出: true
解釋:?因?yàn)?"*" 代表可以匹配零個(gè)或多個(gè)前面的那一個(gè)元素, 在這里前面的元素就是 "a"。因此，字符串 "aa" 可被視為 "a" 重復(fù)了一次。

輸入:
s = "ab"
p = ".*"
輸出: true
解釋:?"." 表示可匹配零個(gè)或多個(gè)（""）任意字符（"."）。

輸入:
s = "aab"
p = "cab"
輸出: true
解釋:?因?yàn)?"*" 表示零個(gè)或多個(gè)，這里 "c" 為 0 個(gè), "a" 被重復(fù)一次。因此可以匹配字符串 "aab"。

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

這題稍微有點(diǎn)復(fù)雜，我們采用了遞歸方法將兩個(gè)字符串對(duì)比，每次只對(duì)比一個(gè)字符。
將當(dāng)前遞歸p的下一個(gè)字符是否為*進(jìn)行分類比較：
①p的下一個(gè)字符是*
若s和p的當(dāng)前字符相同或者p的當(dāng)前字符為.，則結(jié)果就取決于：

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

若p的最后兩個(gè)字符為.*就返回true
若不符合上面兩種情況就將取決于

isMatch(s,p.slice(2))

②p的下一個(gè)字符不為*
這種情況就簡單了
若s和p的當(dāng)前字符相同或者p的當(dāng)前字符為.，返回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），做法不唯一，甚至可能還有所錯(cuò)誤，希望各位大神指出，弟弟虛心學(xué)習(xí)。