add 006 007 009 016 017 018 022 023 024 027

zongyanqi · zongyanqi · commit c9eee2f5ca8c · 2017-12-19T20:32:28.000+08:00
diff --git a/006-ZigZag-Conversion.js b/006-ZigZag-Conversion.js
@@ -0,0 +1,47 @@
+/**
+ *
+ * https://leetcode.com/problems/zigzag-conversion/description/
+ * Difficulty:Medium
+ *
+ * The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:
+ * (you may want to display this pattern in a fixed font for better legibility)
+ *
+ * P   A   H   N
+ * A P L S I I G
+ * Y   I   R
+ * And then read line by line: "PAHNAPLSIIGYIR"
+ * Write the code that will take a string and make this conversion given a number of rows:
+ * string convert(string text, int nRows);
+ * convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
+ *
+ */
+
+/**
+ * @param {string} s
+ * @param {number} numRows
+ * @return {string}
+ */
+var convert = function (s, numRows) {
+
+    var arr = [];
+    for (var i = 0; i < numRows; i++) {
+        arr[i] = [];
+    }
+
+    var cnt = 0;
+    var len = s.length;
+
+    while (cnt < len) {
+        for (var i = 0; i < arr.length && cnt < len; i++) {
+            arr[i].push(s[cnt++]);
+        }
+        for (var i = numRows - 2; i >= 1 && cnt < len; i--) {
+            arr[i].push(s[cnt++]);
+        }
+    }
+    // console.log(arr);
+
+    return arr.map(arr => arr.join('')).join('')
+};
+
+console.log(convert('PAYPALISHIRING', 3));
diff --git a/007-Reverse-Integer.js b/007-Reverse-Integer.js
@@ -0,0 +1,49 @@
+/**
+ * https://leetcode.com/problems/reverse-integer/description/
+ * Difficulty:Easy
+ *
+ * Given a 32-bit signed integer, reverse digits of an integer.
+ *
+ * Example 1:
+ * Input: 123
+ * Output:  321
+ * Example 2:
+ * Input: -123
+ * Output: -321
+ * Example 3:
+ * Input: 120
+ * Output: 21
+ * Note:
+ * Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range.
+ * For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
+ */
+
+/**
+ * @param {number} x
+ * @return {number}
+ */
+var reverse = function (x) {
+
+    var sign = x >= 0 ? -1 : 1;
+    x = Math.abs(x);
+
+    var sum = 0;
+    while (x) {
+        sum = sum * 10 + x % 10;
+        x = Math.floor(x / 10);
+    }
+    var ret = sign * -1 * sum;
+    var max = Math.pow(2, 31) - 1;
+    var min = -Math.pow(2, 31);
+    if (ret > max) return 0;
+    if (ret < min) return 0;
+    return ret;
+};
+
+console.log(reverse(123) === 321);
+console.log(reverse(-123) === -321);
+console.log(reverse(120) === 21);
+console.log(reverse(1534236469) === 0);
+console.log(reverse(-2147483412), reverse(-2147483412) === -2143847412);
+console.log(reverse(-2147483648), reverse(-2147483648) === 0);
+
diff --git a/009-Palindrome-Number.js b/009-Palindrome-Number.js
@@ -0,0 +1,31 @@
+/**
+ * https://leetcode.com/problems/palindrome-number/description/
+ * Difficulty:Easy
+ *
+ * Determine whether an integer is a palindrome. Do this without extra space.
+ */
+
+/**
+ * @param {number} x
+ * @return {boolean}
+ */
+var isPalindrome = function (x) {
+    if (x < 0) return false;
+    var t = x;
+    x = Math.abs(x);
+    var p = 0;
+    while (x) {
+        p = p * 10 + x % 10;
+        x = Math.floor(x / 10);
+    }
+    // console.log(x, p);
+    return t === p;
+};
+
+console.log(isPalindrome(-1) === false);
+console.log(isPalindrome(0) === true);
+console.log(isPalindrome(123) === false);
+console.log(isPalindrome(12321) === true);
+console.log(isPalindrome(1221) === true);
+console.log(isPalindrome(2222) === true);
+
diff --git a/016-3Sum-Closest.js b/016-3Sum-Closest.js
@@ -0,0 +1,42 @@
+/**
+ * https://leetcode.com/problems/3sum-closest/description/
+ * Difficulty:Medium
+ *
+ * Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.
+ * Return the sum of the three integers. You may assume that each input would have exactly one solution.
+ * For example, given array S = {-1 2 1 -4}, and target = 1.
+ * The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
+ *
+ */
+
+/**
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number}
+ */
+var threeSumClosest = function (nums, target) {
+
+    var ans = nums[0] + nums[1] + nums[2];
+    var len = nums.length;
+
+    nums.sort((a, b) => a < b ? -1 : (a > b) ? 1 : 0);
+
+    for (var i = 0; i < len - 2; i++) {
+        var j = i + 1;
+        var k = len - 1;
+
+        while (j < k) {
+            var sum = nums[i] + nums[j] + nums[k];
+            if (sum === target) return sum;
+            if (sum > target) k--;
+            if (sum < target) j++;
+            if (Math.abs(target - sum) < Math.abs(target - ans)) {
+                ans = sum;
+            }
+        }
+    }
+    return ans;
+
+};
+
+console.log(threeSumClosest([-1, 2, 1, -4], 1));
diff --git a/017-Letter-Combinations-of-a-Phone-Number.js b/017-Letter-Combinations-of-a-Phone-Number.js
@@ -0,0 +1,44 @@
+/**
+ *
+ * https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
+ * Difficulty:Medium
+ *
+ * Given a digit string, return all possible letter combinations that the number could represent.
+ *
+ * A mapping of digit to letters (just like on the telephone buttons) is given below.
+ *
+ * Input:Digit string "23"
+ * Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
+ *
+ * Note:
+ * Although the above answer is in lexicographical order, your answer could be in any order you want.
+ *
+ */
+
+/**
+ * @param {string} digits
+ * @return {string[]}
+ */
+var letterCombinations = function (digits) {
+
+    if (!digits.length) return [];
+
+    var ans = [''];
+    var map = ['0', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
+
+    for (var i = 0; i < digits.length; i++) {
+        var str = map[digits[i]];
+        var tmp = [];
+        for (var j = 0; j < ans.length; j++) {
+            var t = ans[j];
+            for (var k = 0; k < str.length; k++) {
+                tmp.push(t + str[k]);
+            }
+        }
+        ans = tmp;
+    }
+
+    return ans;
+};
+
+console.log(letterCombinations('23'));
diff --git a/018-4Sum.js b/018-4Sum.js
@@ -0,0 +1,51 @@
+/**
+ * https://leetcode.com/problems/4sum/description/
+ * Difficulty:Medium
+ *
+ * Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
+ * Note: The solution set must not contain duplicate quadruplets.
+ * For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
+ * A solution set is:
+ * [
+ * [-1,  0, 0, 1],
+ * [-2, -1, 1, 2],
+ * [-2,  0, 0, 2]
+ ]
+ */
+
+/**
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number[][]}
+ */
+var fourSum = function (nums, target) {
+    var len = nums.length;
+    if (len < 4) return [];
+    nums.sort((a, b) => a < b ? -1 : a > b ? 1 : 0);
+    // console.log(nums);
+    var ans = [];
+    for (var i = 0; i < len - 3; i++) {
+
+        for (var j = i + 1; j < len - 2; j++) {
+            var k = j + 1;
+            var l = len - 1;
+
+            while (k < l) {
+                var sum = nums[i] + nums[j] + nums[k] + nums[l];
+                if (sum === target) {
+                    ans.push([nums[i], nums[j], nums[k], nums[l]]);
+                    while (nums[l--] === nums[l] && nums[k++] === nums[k] && k < l);
+                }
+                else if (sum < target) while (nums[k++] === nums[k] && k < l);
+                else  while (nums[l--] === nums[l] && k < l);
+            }
+            while (nums[j] === nums[j + 1]) j++;
+        }
+        while (nums[i] === nums[i + 1]) i++;
+
+    }
+    return ans;
+
+};
+
+console.log(fourSum([-5, -4, -2, -2, -2, -1, 0, 0, 1], -9));
diff --git a/022-Generate-Parentheses.js b/022-Generate-Parentheses.js
@@ -0,0 +1,37 @@
+/**
+ * https://leetcode.com/problems/generate-parentheses/description/
+ * Difficulty:Medium
+ *
+ * Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
+ * For example, given n = 3, a solution set is:
+ * [
+ *   "((()))",
+ *   "(()())",
+ *   "(())()",
+ *   "()(())",
+ *   "()()()"
+ * ]
+ */
+
+/**
+ * @param {number} n
+ * @return {string[]}
+ */
+var generateParenthesis = function (n) {
+
+    var ans = [];
+    helper(ans, '', 0, 0, n);
+    return ans;
+};
+
+function helper(ans, str, left, right, n) {
+    if (right === n) ans.push(str);
+    if (left < n) {
+        helper(ans, str + '(', left + 1, right, n);
+    }
+    if (right < left) {
+        helper(ans, str + ')', left, right + 1, n);
+    }
+}
+
+console.log(generateParenthesis(3));
diff --git a/023-Merge-k-Sorted-Lists.js b/023-Merge-k-Sorted-Lists.js
@@ -0,0 +1,84 @@
+/**
+ * https://leetcode.com/problems/merge-k-sorted-lists/description/
+ * Difficulty:Hard
+ *
+ * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
+ */
+
+
+//Definition for singly-linked list.
+function ListNode(val) {
+    this.val = val;
+    this.next = null;
+}
+
+/**
+ * @param {ListNode[]} lists
+ * @return {ListNode}
+ */
+var mergeKLists = function (lists) {
+    return lists.reduce((a, b) => merge2lists(a, b), null)
+};
+
+function merge2lists(a, b) {
+    if (!a && !b) return null;
+    if (!a) return b;
+    if (!b) return a;
+    var h;
+    if (a.val < b.val) {
+        h = a;
+        a = a.next;
+    } else {
+        h = b;
+        b = b.next;
+    }
+    var t = h;
+
+    while (a && b) {
+        if (a.val < b.val) {
+            t.next = a;
+            t = t.next;
+            a = a.next;
+        } else {
+            t.next = b;
+            t = t.next;
+            b = b.next;
+        }
+    }
+    if (a) t.next = a;
+    if (b) t.next = b;
+    return h;
+
+}
+
+var a = {
+    val: 1,
+    next: {
+        val: 4,
+        next: {
+            val: 7,
+            next: null
+        }
+    }
+}
+var b = {
+    val: 2,
+    next: {
+        val: 8,
+        next: {
+            val: 9,
+            next: null
+        }
+    }
+}
+
+var c = {
+    val: 3,
+    next: {
+        val: 10,
+        next: null
+    }
+}
+
+// console.log(merge2lists(a, b));
+console.log(mergeKLists([a, b, c]))
diff --git a/024-Swap-Nodes-in-Pairs.js b/024-Swap-Nodes-in-Pairs.js
diff --git a/027-Remove-Element.js b/027-Remove-Element.js
