3. Longest-Substring-Without-Repeating-Characters

说明

最基本的思路是，遍历字符串，计算以每个字符开头的无重复子串长度，但是这样做的复杂度会很大，无法通过最后一个用例（这个题目的最后一个用例是用来测试算法的时间复杂度的）。

线性复杂度的算法思想描述如下：

遍历字符串，每次计算以当前字符结尾的最长不重复子串的length，遍历完成时，就得到了整个字符串的最长不重复子串。遍历时，将每个遇到的字符及其index以key：value形式存入一个hash中，我们每遇到一个字符，从hash中取寻找，判断之前是否遇见过，如果遇见过，那以当前字符结尾的最长不重复子串的开头字符的index的最小值就是最近一次遇到的这个字符的index。那么是不是说，最近一次遇到的这个字符的index就是开头了呢？不一定，因为我们要保证两个这两个相同的字符之间没有重复字符。如何保证这一点呢？这需要我们维护一个 名叫 start 的变量，每次发现一个字符之前遇到过，那就将start更新为 之前遇到的字符index。

代码

  1. /** 
  2.  * @param {string} s 
  3.  * @return {number} 
  4.  */  
  5. var lengthOfLongestSubstring = function(s) {  
  6.     var hash = { };  
  7.     var start = -1;  
  8.     var max = 0;  
  9.     var dis = 0;  
  10.     for (var i = 0; i < s.length; i++) {  
  11.         if (hash[s[i]] === undefined) {  
  12.             dis = i - start;  
  13.         }  
  14.         else {  
  15.             if (hash[s[i]] > start) {  
  16.                 dis = i - hash[s[i]];  
  17.                 start = hash[s[i]];  
  18.             }  
  19.             else {  
  20.                 dis = i - start;  
  21.             }  
  22.         }  
  23.         hash[s[i]] = i;  
  24.         max = (dis > max) ? dis : max;  
  25.     }  
  26.     return max;  
  27. };

4. Median-of-Two-Sorted-Arrays

说明：

先将两个数组归并，然后找出中间值

代码：

  1. /** 
  2.  * @param {number[]} nums1 
  3.  * @param {number[]} nums2 
  4.  * @return {number} 
  5.  */  
  6. var findMedianSortedArrays = function(nums1, nums2) {  
  7.     var arr = [];  
  8.     var i = 0;  
  9.     var j = 0;  
  10.     var k = 0;  
  11.     var mid;  
  12.     while (i < nums1.length && j < nums2.length) {  
  13.         if (nums1[i] < nums2[j]) {  
  14.             arr.push(nums1[i++]);  
  15.         }  
  16.         else {  
  17.             arr.push(nums2[j++]);  
  18.         }  
  19.     }  
  22.     if (i < nums1.length) {  
  23.         for (k = i; k < nums1.length; k++) {  
  24.             arr.push(nums1[k]);  
  25.         }  
  26.     }  
  27.     if (j < nums2.length) {  
  28.         for (k = j; k < nums2.length; k++) {  
  29.             arr.push(nums2[k]);  
  30.         }  
  31.     }  
  34.     if (arr.length % 2 === 0) {  
  35.         mid = (arr.length / 2) - 1;  
  36.         return (arr[mid] + arr[mid + 1]) / 2;  
  37.     }  
  38.     else {  
  39.         mid = (arr.length + 1) / 2 - 1;  
  40.         return arr[mid];  
  41.     }  
  42. };

5. longest-palindromic-substring

说明

最长回文串，考虑到长度为奇数的回文串和长度为偶数的回文串。

代码

  1. var longestPalindrome = function(s) {  
  3.     var max = 0;  
  4.     var mark = {  
  5.         i: 0,  
  6.         j: 0  
  7.     };  
  8.     var result = '';  
  10.     var getOddLength = function (s, index) {  
  11.         var i = index;  
  12.         var j = index;  
  13.         while (i >= 0 && j < s.length) {  
  14.             if (s[i] === s[j]) {  
  15.                 i--;  
  16.                 j++;  
  17.             }  
  18.             else {  
  19.                 break;  
  20.             }  
  21.         }  
  22.         return j - i + 1;  
  23.     };  
  24.     var getEvenLength = function (s, index) {  
  25.         if (index >= s.length ) {  
  26.             return 0;  
  27.         }  
  28.         var i = index;  
  29.         var j = index + 1;  
  30.         while (i >= 0 && j < s.length) {  
  31.             if (s[i] === s[j]) {  
  32.                 i--;  
  33.                 j++;  
  34.             }  
  35.             else {  
  36.                 break;  
  37.             }  
  38.         }  
  39.         return j - i + 1;  
  40.     };  
  41.     var getResult = function (mark, s) {  
  42.         var i = mark.i;  
  43.         var j = mark.j;  
  44.         var str = '';  
  45.         while (i >= 0 && j < s.length) {  
  46.             if (s[i] === s[j]) {  
  47.                 str = s[i] + str;  
  48.                 if (i !== j) {  
  49.                     str = str + s[j];  
  50.                 }  
  51.                 i--;  
  52.                 j++;  
  53.             }  
  54.             else {  
  55.                 break;  
  56.             }  
  57.         }  
  58.         return str;  
  59.     };  
  60.     for (var i = 0; i < s.length; i++) {  
  61.         var l1 = getOddLength(s, i);  
  62.         var l2 = getEvenLength(s, i);  
  63.         if (l1 > max) {  
  64.             max = l1;  
  65.             mark.i = i;  
  66.             mark.j = i;  
  67.         }  
  68.         if (l2 > max) {  
  69.             max = l2;  
  70.             mark.i = i;  
  71.             mark.j = i + 1;  
  72.         }  
  73.     }  
  74.     return getResult(mark, s);  
  75. };

6. ZigZag-Conversion

说明：

首先要弄清zigzag模式的概念，在博客http://blog.csdn.net/zhouworld16/article/details/14121477中，有很清晰的介绍。

根据题意，可以知道，若要得到正确的结果，只需要将输入的字符串按照zigzag模式分配给给定数目（numRows）的数组，然后再讲每个字符串拼接起来即可。

代码：

  1. /** 
  2.  * @param {string} s 
  3.  * @param {number} numRows 
  4.  * @return {string} 
  5.  */  
  6. var convert = function(s, numRows) {  
  7.     var result = '';  
  8.     var arr = [ ];  
  9.     var down = true;  
  10.     var index = 0;  
  11.     var row = 0;  
  12.     var i;  
  13.     // 创建长度为numRows的数组  
  14.     for (i = 0; i < numRows; i++) {  
  15.         arr.push('');  
  16.     }  
  17.     // 为数组分配字符  
  18.     while (index < s.length) {  
  19.         arr[row] += s[index];  
  20.         if (down) {  
  21.             if (row < numRows - 1) {  
  22.                 row++;  
  23.                 if (row === numRows - 1) {  
  24.                     down = false;  
  25.                 }  
  26.             }  
  27.         }  
  28.         else {  
  29.             if (row > 0) {  
  30.                 row--;  
  31.                 if (row === 0) {  
  32.                     down = true;  
  33.                 }  
  34.             }  
  35.         }  
  36.         index ++;  
  37.     }  
  38.     // 将数组中的字符串拼接得到结果  
  39.     for (i = 0; i < arr.length; i++) {  
  40.         result += arr[i];  
  41.     }  
  43.     return result;  
  44. };

11. Container-With-Most-Water.md

说明：

  1. 题目是：给定n个非负整数 a1, a2..., ai..., an，表示在点(i, ai)处的点。现在根据这个整数序列画出n条线段，每个线段的两个端点分别为(i, 0)和(i, ai)。要求是从这n条线段中找出两条，使得这两条直线与x轴围成的容器所能容纳的水最多。
  3. 题目说是找出两条线段围成的容器中容纳水最多的那个，其实就是找出两条线段，使得（这两条线段之间的水平距离） * （两条线段中较短的那条） 值最大。
  5. 很容易想到的思路就是暴力穷举法，遍历每个点，计算 这个点对应的线段和其他所有线段围成的容器容量 中最大的值，记为maxi，求出最大的maxi，就是题目要求的结果。代码如下：

暴力穷举代码：

  1. /** 
  2.  * @param {number[]} height 
  3.  * @return {number} 
  4.  */  
  5. var maxArea = function (height) {  
  6.     // 计算两点围成的容器的容量  
  7.     var getArea = function (i, j) {  
  8.         var h = height[i] < height[j] ? height[i] : height[j];  
  9.         return h * (j - i);  
  10.     };  
  11.     var max = 0;  
  12.     // 遍历求解  
  13.     for (var i = 0; i < height.length; i++) {  
  14.         for (var j = i + 1; j < height.length; j ++) {  
  15.             var area = getArea(i, j, height[i], height[j])  
  16.             if (area > max) {  
  17.                 max = area;  
  18.             }  
  19.         }  
  20.     }  
  21.     return max;  
  22. };
  1. 很明显这个的复杂度是n^2。这个代码不能通过leetcode测试时间性能的测试用例。那么我们需要优化一下。如果我们希望能使一个算法的时间性能提升上去，即减少执行时间，可以从两个方面入手，第一是使用问题中的一些规则，减少算法的操作；第二是我们在算法过程中记录一些信息，在后续的执行过程中直接使用信息而不用再次计算。第二种思路的典型代表就是动态规划的思想。
  2. 我们这里使用第一种思路，规则就是：如果在点j处的线段是从点到点j之间的线段中最长的，那么，点i到点j之间的所有可能的容器中容量最大的就是点i处的线段和点j处的线段所围成的容器（原因是既然j处的线段是从i到j之间最长的，那么i到j之间的线段和i围成的容器的长和宽都不可能比j更大，因此j处的线段和i所围成容器一定是容量最大的）。根据这个规则，我们要记录两个信息：一个是正序 从下标为0到下标为i之间的线段中最长线段的下标，另一个是逆序 从下标为height.length -1 到下标为i之间的线段中最长的线段的下标。用这两个信息，当遍历到i时，如果i处的线段不是从0到i之间最大的，就可以不作任何操作（因为根据上面的规则，这时 i和其后任何线段围成的容器 都不会比 i之前那个比它长的线段和任何线段围成的容器的容量更大）；而从i到其后最大的线段之间的容器容量也不必计算（因为它们和i围成的容器容量不会比i后最大的线段更大）。代码如下：
  1. var maxArea = function (height) {  
  2.     // 计算两点围成的容器的容量  
  3.     var getArea = function (i, j) {  
  4.         var h = height[i] < height[j] ? height[i] : height[j];  
  5.         return h * (j - i);  
  6.     };  
  7.     var max;  
  8.     var temp;  
  9.     // 记录从0到i的最大height的下标  
  10.     var preMax = [ ];  
  11.     // 记录从heiht.length-1到i的最大height的下标  
  12.     var postMax = [ ];  
  13.     var i, j;  
  14.     // temp在这里保存从0到i的最大height  
  15.     temp = 0;  
  16.     for (i = 0; i < height.length; i++) {  
  17.         if (height[i] > temp) {  
  18.             temp = height[i];  
  19.             preMax.push(i);  
  20.         }  
  21.         else {  
  22.             preMax.push(preMax[i - 1]);  
  23.         }  
  24.     }  
  25.     // temp在这里保存从heiht.length-1的最大height  
  26.     temp = 0;  
  27.     for (i = height.length - 1; i >= 0; i--) {  
  28.         if (height[i] > temp) {  
  29.             temp = height[i];  
  30.             postMax.unshift(i);  
  31.         }  
  32.         else {  
  33.             postMax.unshift(postMax[0]);  
  34.         }  
  35.     }  
  36.     max = 0;  
  37.     // 遍历height数组，求容量最大值  
  38.     for (i = 0; i < height.length; i++) {  
  39.         if (preMax[i] === i) {  
  40.             var area = getArea(i, postMax[i]);  
  41.             if (max < area) {  
  42.                 max = area;  
  43.             }  
  44.             for (j = postMax[i] + 1; j < height.length; j++) {  
  45.                 area = getArea(i, j);  
  46.                 if (max < area) {  
  47.                     max = area;  
  48.                 }  
  49.             }  
  50.         }  
  51.     }  
  52.     return max;  
  53. };

这样就可以accept了。

12. Integer-to-Roman.md

说明：

  1. 该题目要求是将一个整数转换为一个罗马数字，所以首先要搞清楚罗马数字的规则。

罗马数字的规则：

  1. 罗马数字和阿拉伯数字一样，都是十进制的，所以我们只要把每一位的数字拼凑到一起就可以了。但是有一点需要注意的是，罗马数字不同于阿拉伯数字，它的每一位数字表示方法不同，比如，对于阿拉伯数字，五用 ‘5’来表示，而五十只需要把 '5'放在十位就行了：‘50’，因为有0占位，因此不会有任何歧义。但是罗马数字没有占位机制，因此各个位的表示方法不同，如五用罗马数字表示为 ‘V’，五十则为 ‘X’。
  3. 虽然罗马数字每一个位对应的数字符号不同，但是表示的方法都是一样的，都是通过表示‘1’的符号和表示‘5’的符号组合而成。表示方法如下：假设某一位表示‘1’的符号为A，表示‘5’的符号为B，则 0，1，2，3，4，5，6，7，8，9分别为     ‘’（空字符），A, AA, AAA, AB(可以这么理解，A位于B左侧相当于B-A，A位于B右侧相当于B+A), B, BA, BAA, BAAA, AC(C是更高一位的‘1’，相当于10 - 1)。
  5. 根据上面的叙述，我们只需要知道每一位表示 ‘1’和 ‘5’的符号，就可以按照上述规则拼凑起罗马数字了。
  7. 值得注意的是，题目中说明输入整数从1 ~ 3999 ，因此只需要知道个位到千位的表示符号即可。

代码：

  1. /** 
  2.  * @param {number} num 
  3.  * @return {string} 
  4.  */  
  5. var intToRoman = function(num) {  
  6.     var result = '';  
  7.     var temp;  
  8.     var list = [  
  9.         {  
  10.             one: 'I',  
  11.             five: 'V'  
  12.         },  
  13.         {  
  14.             one: 'X',  
  15.             five: 'L'  
  16.         },  
  17.         {  
  18.             one: 'C',  
  19.             five: 'D'  
  20.         },  
  21.         {  
  22.             one: 'M'  
  23.         }  
  24.     ];  
  26.     var map = function (integer, cur, next) {  
  27.         var one = cur.one;  
  28.         var five = cur.five;  
  29.         var ten = next && next.one;  
  30.         switch (integer) {  
  31.             case 0:  
  32.                 return '';  
  33.             case 1:  
  34.                 return one;  
  35.             case 2:  
  36.                 return one + one;  
  37.             case 3:  
  38.                 return one + one + one;  
  39.             case 4:  
  40.                 return one + five;  
  41.             case 5:   
  42.                 return five;  
  43.             case 6:  
  44.                 return five + one;  
  45.             case 7:  
  46.                 return five + one + one;  
  47.             case 8:  
  48.                 return five + one + one + one;  
  49.             case 9:  
  50.                 return one + ten;  
  51.         }  
  52.     };  
  53.     while (num) {  
  54.         temp = num % 10;  
  55.         result = map(temp, list[0], list[1]) + result;  
  56.         list.shift();  
  57.         num = Math.floor(num / 10);  
  58.     }  
  60.     return result;  
  62. };

13. Roman-to-Integer.md

说明：

  1. 题目要求将罗马数字转为阿拉伯数字。思路是从个位开始，匹配各个位的数字，一直到最高位为止。需要注意两点，第一是要移除已经匹配完的数字，防止在匹配更高位数字时产生歧义。第二是在匹配的时候，为防止歧义，应遵循一定顺序，比如应先匹配4，6，7，8然后再匹配5。

代码：

  1. /** 
  2.  * @param {string} s 
  3.  * @return {number} 
  4.  */  
  5. var romanToInt = function(s) {  
  6.     var num = 0;  
  7.     var list = [  
  8.         {  
  9.             grade: 1,  
  10.             one: 'I',  
  11.             five: 'V'  
  12.         },  
  13.         {  
  14.             grade: 10,  
  15.             one: 'X',  
  16.             five: 'L'  
  17.         },  
  18.         {  
  19.             grade: 100,  
  20.             one: 'C',  
  21.             five: 'D'  
  22.         },  
  23.         {  
  24.             grade: 1000,  
  25.             one: 'M'  
  26.         }  
  27.     ];  
  29.     var map = function (cur, next) {  
  30.         var result = 0;  
  31.         var one = cur.one;  
  32.         var five = cur.five;  
  33.         var ten = next && next.one;  
  35.         var nine = ten ? (one + ten) : 'doomliu';  
  37.         var fiveIndex = s.indexOf(five);  
  38.         var oneIndex = s.indexOf(one);  
  39.         var nineIndex = s.indexOf(nine);  
  40.         if (nineIndex !== -1) {  
  41.             s = s.slice(0, nineIndex);  
  42.             result = 9;  
  43.         }  
  44.         else if (fiveIndex !== -1) {  
  45.             var preIndex = postIndex = fiveIndex;  
  46.             while (preIndex >= 0 && (s[--preIndex] === one)) { }  
  47.             while (postIndex <= s.length - 1 && (s[++postIndex] === one)) { }  
  48.             s = s.slice(0, preIndex + 1);  
  49.             result = 5 + ((postIndex - 1) + (preIndex + 1) - 2 * fiveIndex);  
  50.         }  
  51.         else if (oneIndex !== -1) {  
  52.             var postIndex = oneIndex;  
  53.             while (postIndex <= s.length - 1 && s[++postIndex] === one) { }  
  54.             s = s.slice(0, oneIndex);  
  55.             result = (postIndex - 1) - oneIndex + 1;  
  56.         }  
  58.         result *= cur.grade;  
  59.         return result;  
  60.     };  
  62.     while (list.length) {  
  63.         num += map(list[0], list[1]);  
  64.         list.shift();  
  65.     }  
  67.     return num;  
  69. };

134. Gas-Station.md

代码

  1. /** 
  2.  * @param {number[]} gas 
  3.  * @param {number[]} cost 
  4.  * @return {number} 
  5.  */  
  6. var canCompleteCircuit = function(gas, cost) {  
  7.     var arr = [];  
  8.     var curSum = 0;  
  9.     var positiveSum = 0;  
  10.     var positiveIndex = 0;  
  11.     var index = gas.length - 1;  
  12.     gas.forEach((item, index) => {  
  13.         arr.push(item - cost[index])  
  14.     });  
  15.     while (index >= 0) {  
  16.         if (arr[index] < 0) {  
  17.             curSum = arr[index--];  
  18.             while (curSum < 0 && index >= 0) {  
  19.                 curSum += arr[index--];  
  20.             }  
  21.             if (index < 0) {  
  22.                 if (curSum + positiveSum >= 0) {  
  23.                     return positiveIndex  
  24.                 }  
  25.                 else {  
  26.                     return -1  
  27.                 }  
  28.             }  
  29.             else {  
  30.                 positiveSum += curSum;  
  31.                 positiveIndex = index + 1;  
  32.                 curSum = 0;  
  33.             }  
  34.         }  
  35.         else {  
  36.             while (arr[index] >= 0 && index >= 0) {  
  37.                 positiveSum += arr[index];  
  38.                 positiveIndex = index--;  
  39.             }  
  40.             if (index < 0) {  
  41.                 return 0  
  42.             }  
  43.         }  
  44.     }  
  45.     return -1  
  46. };

14. Longest-Common-Prefix.md

说明：

  1. 题目要求找出一个字符串数组中的所有字符串的最长前缀。

代码：

  1. /** 
  2.  * @param {string[]} strs 
  3.  * @return {string} 
  4.  */  
  5. var longestCommonPrefix = function (strs) {  
  6.     var result = '';  
  7.     var  breakFlag = false;  
  8.     var curStr = '';  
  9.     var i = j = 0;  
  10.     if (!strs.length) {  
  11.         return result;  
  12.     }  
  13.     while (true) {  
  14.         if (i > strs[0].length - 1) {  
  15.             break;  
  16.         }  
  17.         curStr = strs[0][i];  
  18.         for (j = 0; j < strs.length; j++) {  
  19.             if (strs[j][i] !== curStr || i > strs[j].length - 1) {  
  20.                 breakFlag = true;  
  21.                 break;  
  22.             }  
  23.             else if (j === strs.length - 1) {  
  24.                 result += strs[j][i];  
  25.             }  
  26.         }  
  27.         if (breakFlag) {  
  28.             break;  
  29.         }  
  30.         i++;  
  31.     }  
  33.     return result;  
  34. };

15. 3sum.md

说明

  1. 题目是，给定一个数组（nums），返回一个数组（假定为result），result的每个元素都是一个数组（假定为ele），ele长度为3，其中的3个元素不重复地取自nums，并且这3个元素之和为0。result中的各数组要保证3元素组合不重复。
  3. 首先最容易想到的方法是暴力遍历，用一个3重循环求取结果，再去重即可。这样复杂度为n^3。
  5. 可以从多个角度进行优化
  7. 第一，先把输入参数nums升序排序，这样可以在遍历的过程中判断两数之和是否大于0，如果大于0可以不用再向后遍历，这就减少了一定的计算量；
  9. 第二，可以给nums去重，保证每个元素最多只有3个重复；
  11. 第三，可以先把nums中每个元素存到一个hash里，key就是这个元素的值，value是这个元素最后出现的下标，遍历的时候，只需要两重遍历即可；

代码

  1. /** 
  2.  * @param {number[]} nums 
  3.  * @return {number[][]} 
  4.  */  
  5. var threeSum = function(nums) {  
  6.     var resultHash = {};  
  7.     var numsHash = {};  
  8.     var result = [];  
  10.     var newNums = [];  
  11.     var newNumsHash = {};  
  13.     // nums去重  
  14.     nums.forEach(function (item, index) {  
  15.         if (newNumsHash[item] !== 3) {  
  16.             newNums.push(item);  
  17.             if (newNumsHash[item]) {  
  18.                 newNumsHash[item]++;  
  19.             }  
  20.             else {  
  21.                 newNumsHash[item] = 1;  
  22.             }  
  23.         }  
  24.     });  
  26.     // 排序  
  27.     var list = newNums.sort(function (a, b) {  
  28.         return a - b;  
  29.     });  
  31.     // 将nums转成hash  
  32.     for (var i = 0; i < list.length; i++) {  
  33.         numsHash[list[i]] = i + 1;  
  34.     }  
  36.     // 两重遍历确定两个数，第三个数在numsHash里找  
  37.     for (var j = 0; j < list.length; j++) {  
  38.         for (var k = j + 1; k < list.length; k++) {  
  39.             var target = -(list[j] + list[k]);  
  40.             // 因为数组是升序排好序的，所以如果两数之和大于0，再加上后面的肯定不为0  
  41.             if (target < 0) {  
  42.                 break;  
  43.             }  
  45.             if (numsHash[target]  
  46.                 && (numsHash[target] - 1) !== j  
  47.                 && (numsHash[target] - 1) !== k  
  48.             ) {  
  49.                 var arr = [list[j], list[k], target];  
  50.                 var resultHashKey = arr.sort().join('_');  
  51.                 if (!resultHash[resultHashKey]) {  
  52.                     result.push(arr);  
  53.                     resultHash[resultHashKey] = true;  
  54.                 }  
  55.             }  
  56.         }  
  57.     }  
  58.     return result;  
  59. };

16. 3Sum-Closest.md

说明

  1. 题目是，给定一个数组，和一个目标值，找出数组中的3个数，这3个数之和离目标值最近。
  3. 可以直接想出的方法就是三重循环遍历。为了减少计算，需要先对数组进行排序，然后根据遍历中当前3个元素之和与目标值的关系判定是否需要继续向后遍历。

代码

  1. /** 
  2.  * @param {number[]} nums 
  3.  * @param {number} target 
  4.  * @return {number} 
  5.  */  
  6. var threeSumClosest = function(nums, target) {  
  7.     var list = nums.sort(function (a, b) {  
  8.         return a - b;  
  9.     });  
  11.     var distance = Math.abs((list[0] + list[1] + list[2]) - target);  
  12.     var tempSum;  
  14.     for (var i = 0; i < list.length; i++) {  
  15.         for (var j = i + 1; j < list.length; j++) {  
  16.             for (var k = j + 1; k < list.length; k++) {  
  17.                 if (Math.abs(list[i] + list[j] + list[k] - target) > distance) {  
  18.                     if ((list[i] + list[j] + list[k] - target) > 0) {  
  19.                         break;  
  20.                     }  
  21.                 }  
  22.                 else {  
  23.                     distance = Math.abs(list[i] + list[j] + list[k] - target);  
  24.                     tempSum = list[i] + list[j] + list[k];  
  25.                 }  
  26.             }  
  27.         }  
  28.     }  
  29.     return tempSum;  
  30. };

17. Letter-Combinations-of-a-Phone-Number.md

说明

  1. 当我们使用手机的9键键盘时，每个按键对应多个字母，我们按下几个键后，对应多种可能的字母组合。题目要求根据输入的数字求出所有可能的字母组合。这个题就是简单的递归题目，和字符全排列类似。

代码

  1. /** 
  2.  * @param {string} digits 
  3.  * @return {string[]} 
  4.  */  
  5. var letterCombinations = function(digits) {  
  6.     const map = {  
  7.         '2': ['a', 'b', 'c'],  
  8.         '3': ['d', 'e', 'f'],  
  9.         '4': ['g', 'h', 'i'],  
  10.         '5': ['j', 'k', 'l'],  
  11.         '6': ['m', 'n', 'o'],  
  12.         '7': ['p', 'q', 'r', 's'],  
  13.         '8': ['t', 'u', 'v'],  
  14.         '9': ['w', 'x', 'y', 'z']  
  15.     };  
  16.     var result = [];  
  17.     const it = (prefix, seq, result) => {  
  18.         if (seq.length === 0) {  
  19.             return;  
  20.         }  
  21.         else if (seq.length === 1) {  
  22.             map[seq[0]].forEach((item, index) => {  
  23.                 result.push(prefix + item);  
  24.             });  
  25.             return;  
  26.         }  
  27.         else {  
  28.             map[seq[0]].forEach((item, index) => {  
  29.                 it(prefix + item, seq.slice(1), result);  
  30.             });  
  31.         }  
  32.     }  
  34.     it('', digits, result);  
  36.     return result;  
  37. };

19. Remove-Nth-Node-From-End-of-List.md

说明

  1. 题目要求删除链表倒数第n个节点。
  3. 这是个典型的双指针问题，先让前指针走n步，然后两个指针一起走，直到前指针走到链表末尾，最后删掉后指针指向的节点即可。
  5. 值得注意的是，这里的头指针不是一个指向第一个节点的节点，它就是第一个节点。

代码

  1. /** 
  2.  * Definition for singly-linked list. 
  3.  * function ListNode(val) { 
  4.  *     this.val = val; 
  5.  *     this.next = null; 
  6.  * } 
  7.  */  
  8. /** 
  9.  * @param {ListNode} head 
  10.  * @param {number} n 
  11.  * @return {ListNode} 
  12.  */  
  13. var removeNthFromEnd = function(head, n) {  
  14.     var h = new ListNode(0);  
  15.     h.next = head;  
  16.     var i = h, j = h;  
  17.     for (var k = 0; k < n; k++) {  
  18.         j = j.next;  
  19.     }  
  20.     while (j.next) {  
  21.         i = i.next;  
  22.         j = j.next;  
  23.     }  
  24.     i.next = i.next.next;  
  25.     return h.next;  
  26. };

20. Valid-Parentheses.md

说明

  1. 题目要求判断一个括号序列是否合法。
  3. 这是一个典型的栈问题。

代码

  1. /** 
  2.  * @param {string} s 
  3.  * @return {boolean} 
  4.  */  
  5. var isValid = function(s) {  
  6.     var stack = [];  
  7.     var match = {  
  8.         ')': '(',  
  9.         ']': '[',  
  10.         '}': '{',  
  11.     };   
  12.     for (var i = 0; i < s.length; i++) {  
  13.         if (stack.length > 0 && match[s[i]] === stack[stack.length - 1]) {  
  14.             stack.pop();  
  15.         }  
  16.         else {  
  17.             stack.push(s[i]);  
  18.         }  
  19.     }  
  20.     if (stack.length === 0) {  
  21.         return true;      
  22.     }  
  23.     return false  
  24. };

21. Merge-Two-Sorted-Lists.md

说明

  1. 合并两个列表，这里list使用的是链表结构

代码

  1. // Definition for singly-linked list.  
  2. function ListNode(val) {  
  3.     this.val = val;  
  4.     this.next = null;  
  5. }  
  7. /** 
  8.  * @param {ListNode} l1 
  9.  * @param {ListNode} l2 
  10.  * @return {ListNode} 
  11.  */  
  12. var mergeTwoLists = function(l1, l2) {  
  13.     var i = l1;  
  14.     var j = l2;  
  15.     var h1 = h2 = new ListNode();  
  16.     while (i && j) {  
  17.         if (i.val < j.val) {  
  18.             h2.next = i;  
  19.             h2 = h2.next;  
  20.             i = i.next;  
  21.         }  
  22.         else {  
  23.             h2.next = j;  
  24.             h2 = h2.next;  
  25.             j = j.next;  
  26.         }  
  27.     }  
  28.     if (i) {  
  29.         while (i) {  
  30.             h2.next = i;  
  31.             h2 = h2.next;  
  32.             i = i.next;  
  33.         }  
  34.     }  
  35.     if (j) {  
  36.         while (j) {  
  37.             h2.next = j;  
  38.             h2 = h2.next;  
  39.             j = j.next;  
  40.         }  
  41.     }  
  42.     return h1.next;  
  43. };

22. Generate-Parentheses.md

说明：

  1. 题目要求找出n个括号所能组成的所有合法括号序列，所谓合法括号序列，指的是从左到右遍历序列，任意位置都满足，左括号的个数大于等于右括号的个数。

代码：

  1. /** 
  2.  * @param {number} n 
  3.  * @return {string[]} 
  4.  */  
  5. var generateParenthesis = function(n) {  
  6.     var stack = [];  
  7.     var result = [];  
  8.     var curLeft = 0;  
  9.     var curRight = 0;  
  10.     function getEnd(n) {  
  11.         var result = ''  
  12.         for (var i = 0; i < n; i++) {  
  13.             result += '()';  
  14.         }  
  15.         return result;  
  16.     }  
  17.     var end = getEnd(n);  
  18.     function reachEnd() {  
  19.         return stack.join('') == end;  
  20.     }  
  21.     function init() {  
  22.         for (var i = 0; i < n; i++) {  
  23.             stack.push('(')  
  24.         }  
  25.         for (var i = 0; i < n; i++) {  
  26.             stack.push(')')  
  27.         }  
  28.         result.push(stack.join(''));  
  29.     }  
  30.     init();  
  31.     while (!reachEnd()) {  
  32.         // 出栈  
  33.         while (true) {  
  34.             var ele = stack.pop();  
  35.             if (ele == '(') {  
  36.                 curLeft++  
  37.                 if (curLeft < curRight) {  
  38.                     break;  
  39.                 }  
  40.             }  
  41.             else {  
  42.                 curRight++  
  43.             }  
  44.         }  
  45.         // 入栈  
  46.         while (curRight) {  
  47.             stack.push(')');  
  48.             curRight--;  
  49.             while (curLeft) {  
  50.                 stack.push('(')  
  51.                 curLeft--  
  52.             }  
  53.             while (curRight) {  
  54.                 stack.push(')')  
  55.                 curRight--  
  56.             }  
  57.         }  
  58.         result.push(stack.join(''))  
  59.     }  
  60.     return result  
  61. };

6. ZigZag-Conversion.md

说明：

首先要弄清zigzag模式的概念，在博客http://blog.csdn.net/zhouworld16/article/details/14121477中，有很清晰的介绍。

根据题意，可以知道，若要得到正确的结果，只需要将输入的字符串按照zigzag模式分配给给定数目（numRows）的数组，然后再讲每个字符串拼接起来即可。

代码：

  1. /** 
  2.  * @param {string} s 
  3.  * @param {number} numRows 
  4.  * @return {string} 
  5.  */  
  6. var convert = function(s, numRows) {  
  7.     var result = '';  
  8.     var arr = [ ];  
  9.     var down = true;  
  10.     var index = 0;  
  11.     var row = 0;  
  12.     var i;  
  13.     // 创建长度为numRows的数组  
  14.     for (i = 0; i < numRows; i++) {  
  15.         arr.push('');  
  16.     }  
  17.     // 为数组分配字符  
  18.     while (index < s.length) {  
  19.         arr[row] += s[index];  
  20.         if (down) {  
  21.             if (row < numRows - 1) {  
  22.                 row++;  
  23.                 if (row === numRows - 1) {  
  24.                     down = false;  
  25.                 }  
  26.             }  
  27.         }  
  28.         else {  
  29.             if (row > 0) {  
  30.                 row--;  
  31.                 if (row === 0) {  
  32.                     down = true;  
  33.                 }  
  34.             }  
  35.         }  
  36.         index ++;  
  37.     }  
  38.     // 将数组中的字符串拼接得到结果  
  39.     for (i = 0; i < arr.length; i++) {  
  40.         result += arr[i];  
  41.     }  
  43.     return result;  
  44. };

7. Reverse-Integer.md

说明：

32位有符号整数的范围就是-2^31 ~ 2^31。

该题目有个细节要注意，就是不仅输入的数32位溢出时要返回0。而且翻转后的数32位溢出时也要返回0。

代码：

  1. /** 
  2.  * @param {number} x 
  3.  * @return {number} 
  4.  */  
  5. var reverse = function(x) {  
  6.     var result = 0;  
  7.     if (Math.abs(x) >= 2147483648) {  
  8.         result = 0;  
  9.     }  
  10.     else {  
  11.         if (x >= 0) {  
  12.             result = +(('' + x).split('').reverse().join(''));  
  13.         }  
  14.         else {  
  15.             result = -(('' + -x).split('').reverse().join(''))  
  16.         }  
  17.     }  
  18.     if (Math.abs(result) >= 2147483648) {  
  19.         result = 0;  
  20.     }  
  21.     return result;  
  22. };

9. Palindrome-Number.md

说明

判断一个数字是否具有回文特性，不允许使用额外存储空间

思路是，先将改数转换为一个字符串，然后一次比较头尾两个字符是否相等，然后掐头去尾。如果一直相等直到只剩下0个字符或者1个字符，那么可以断定改数为回文数

代码

  1. var isPalindrome = function(x) {  
  2.     x = '' + x;  
  3.     while (x !== '') {  
  4.         if (x[0] === x[x.length - 1] && x.length >= 2) {  
  5.             x = x.slice(1, x.length - 1).slice(0, x.length - 2);  
  6.         }  
  7.         else {  
  8.             break;  
  9.         }  
  10.     }  
  12.     if (x.length <= 1) {  
  13.         return true;  
  14.     }  
  15.     return false;  
  16. };