add 010, 019, 162, 167, 202, 347, 561, 647, 654, 718

zongyanqi · zongyanqi · commit f518057fc52c · 2017-12-03T19:35:59.000+08:00
diff --git a/010-Regular-Expression-Matching.js b/010-Regular-Expression-Matching.js
@@ -0,0 +1,56 @@
+/**
+ * https://leetcode.com/problems/regular-expression-matching/description/
+ * Difficulty:Hard
+ *
+ * implement regular expression matching with support for '.' and '*'.
+ *
+ * '.' Matches any single character.
+ * '*' Matches zero or more of the preceding element.
+ * The matching should cover the entire input string (not partial).
+ *
+ * The function prototype should be:
+ * bool isMatch(const char *s, const char *p)
+ *
+ * Some examples:
+ * isMatch("aa","a") → false
+ * isMatch("aa","aa") → true
+ * isMatch("aaa","aa") → false
+ * isMatch("aa", "a*") → true
+ * isMatch("aa", ".*") → true
+ * isMatch("ab", ".*") → true
+ * isMatch("aab", "c*a*b") → true
+ */
+
+/**
+ * @param {string} s
+ * @param {string} p
+ * @return {boolean}
+ */
+var isMatch = function (s, p) {
+
+    var dp = [];
+    var m = s.length;
+    var n = p.length;
+
+    for (var i = 0; i <= m; i++) {
+        dp.push(new Array(n + 1).fill(false));
+    }
+    dp[0][0] = true;
+
+    for (var i = 0; i <= m; i++) {
+        for (var j = 1; j <= n; j++) {
+            if (p[j - 1] === '*') {
+                dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] === p[j - 2] || p[j - 2] === '.') && dp[i - 1][j]);
+            } else {
+                dp[i][j] = i > 0 && dp[i - 1][j - 1] &&
+                    (s[i - 1] === p[j - 1] || p[j - 1] === '.');
+            }
+        }
+    }
+
+    // console.log(dp);
+    return dp[m][n];
+};
+
+console.log(isMatch("aab", "c*a*b"));
+console.log(isMatch("aasdfasdfasdfasdfas", "aasdf.*asdf.*asdf.*asdf.*s"));
diff --git a/019-Remove-Nth-Node-From-End-of-List.js b/019-Remove-Nth-Node-From-End-of-List.js
@@ -0,0 +1,61 @@
+/**
+ * https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
+ * Difficulty:Medium
+ *
+ * Given a linked list, remove the nth node from the end of list and return its head.
+ *
+ * For example,
+ *  Given linked list: 1->2->3->4->5, and n = 2.
+ *  After removing the second node from the end, the linked list becomes 1->2->3->5.
+ *
+ * Note:
+ *  Given n will always be valid.
+ *  Try to do this in one pass.
+ *
+ */
+
+
+// Definition for singly-linked list.
+function ListNode(val) {
+    this.val = val;
+    this.next = null;
+}
+
+/**
+ * @param {ListNode} head
+ * @param {number} n
+ * @return {ListNode}
+ */
+var removeNthFromEnd = function (head, n) {
+    if (!head) return head;
+    var len = 0;
+    var tail = head;
+    while (tail) {
+        tail = tail.next;
+        len++;
+    }
+    if (len === n) {
+        return head.next;
+    }
+
+    len = len - n - 1;
+    tail = head;
+    while (len) {
+        tail = tail.next;
+        len--;
+    }
+    tail.next = tail.next.next;
+    return head;
+};
+
+var a = new ListNode(1);
+var b = new ListNode(2);
+var c = new ListNode(3);
+var d = new ListNode(4);
+// var e = new ListNode(5);
+a.next = b;
+b.next = c;
+c.next = d;
+// d.next = e;
+
+console.log(removeNthFromEnd(a, 2));
diff --git a/162-Find-Peak-Element.js b/162-Find-Peak-Element.js
@@ -10,35 +10,22 @@
  */
 
 /**
+ *
  * @param {number[]} nums
  * @return {number}
  */
 var findPeakElement = function (nums) {
-    if (nums.length === 1) return 0;
-    nums.unshift(nums[0] - 1);
-    nums.push(nums[nums.length - 1] - 1);
-    var i = 1;
-    var j = nums.length - 2;
-    while (i < j) {
-        var half = Math.floor((i + j ) / 2);
-        // console.log(i, j, half, nums[half]);
-        if (isPeak(nums, half)) return half - 1;
-        if (i === half) return j - 1;
-
-        if (nums[half - 1] > nums[half]) j = half;
-        else i = half;
+    for (var i = 1; i < nums.length; i++) {
+        if (nums[i - 1] > nums[i]) return i - 1;
     }
-    return 0;
+    return nums.length - 1;
 };
 
-function isPeak(nums, i) {
-    var a = nums[i - 1];
-    var b = nums[i];
-    var c = nums[i + 1];
-    return b > a && b > c;
-}
+// ================================================
 
 /**
+ * 二分查找
+ *
  * @param {number[]} nums
  * @return {number}
  */
@@ -53,6 +40,9 @@ var findPeakElement = function (nums) {
     }
     return l;
 };
+
+// ================================================
+
 console.log(findPeakElement([3, 2, 1]), 0);
-console.log(findPeakElement([1, 2, 3]), 2);
+console.log(findPeakElement([1, 2, 3, 1]), 2);
 console.log(findPeakElement([1, 3, 2]), 1);
diff --git a/167-Two-Sum-II-Input-array-is-sorted.js b/167-Two-Sum-II-Input-array-is-sorted.js
@@ -2,9 +2,14 @@
  * https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
  * Difficulty:Easy
  *
- * Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
- * The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
+ * Given an array of integers that is already sorted in ascending order,
+ * find two numbers such that they add up to a specific target number.
+ * The function twoSum should return indices of the two numbers such that they add up to the target,
+ * where index1 must be less than index2.
+ *
+ * Please note that your returned answers (both index1 and index2) are not zero-based.
  * You may assume that each input would have exactly one solution and you may not use the same element twice.
+ *
  * Input: numbers=[2, 7, 11, 15], target=9
  * Output: index1=1, index2=2
  *
@@ -19,9 +24,29 @@ var twoSum = function (numbers, target) {
 
     for (var i = 0; i < numbers.length - 1; i++) {
         for (var j = i + 1; j < numbers.length; j++) {
-            if (numbers[i] + numbers[j] == target) return [i + 1, j + 1];
+            if (numbers[i] + numbers[j] === target) return [i + 1, j + 1];
         }
     }
 };
 
-console.log(twoSum([2, 7, 11, 15], 9))
+// ==========================================
+
+/**
+ * 双指针
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number[]}
+ */
+var twoSum = function (nums, target) {
+
+    var lo = 0;
+    var hi = nums.length - 1;
+
+    while (nums[lo] + nums[hi] !== target) {
+        if (nums[lo] + nums[hi] > target) hi--;
+        else lo++;
+    }
+    return [lo + 1, hi + 1];
+};
+
+console.log(twoSum([2, 7, 11, 15], 9));
diff --git a/202-Happy-Number.js b/202-Happy-Number.js
@@ -22,20 +22,25 @@
  */
 var isHappy = function (n) {
 
-    var num = n;
-    var results = [];
+    var results = [n];
+
     while (true) {
-        var digits = ('' + num).split('');
-        var newN = squareSumOfDigits(digits);
-        if (newN === 1) return true;
-        if (results.indexOf(newN) > -1) return false;
-        results.push(newN);
-        num = newN;
+        n = squareSumOfDigits(n);
+        // console.log(n);
+        if (n === 1) return true;
+        if (results.indexOf(n) > -1) return false;
+        results.push(n);
     }
 };
 
-function squareSumOfDigits(digits) {
-    return digits.reduce((sum, d) => sum += d * d, 0);
+function squareSumOfDigits(n) {
+    var sum = 0, tmp;
+    while (n) {
+        tmp = n % 10;
+        sum += tmp * tmp;
+        n = Math.floor(n / 10);
+    }
+    return sum;
 }
 
 console.log(isHappy(1));
diff --git a/347-Top-K-Frequent-Elements.js b/347-Top-K-Frequent-Elements.js
@@ -0,0 +1,37 @@
+/**
+ * https://leetcode.com/problems/top-k-frequent-elements/description/
+ * Difficulty:Medium
+ *
+ * Given a non-empty array of integers, return the k most frequent elements.
+ *
+ * For example,
+ * Given [1,1,1,2,2,3] and k = 2, return [1,2].
+ *
+ * Note:
+ * You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
+ * Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
+ *
+ */
+
+/**
+ * @param {number[]} nums
+ * @param {number} k
+ * @return {number[]}
+ */
+var topKFrequent = function (nums, k) {
+    var map = {};
+    for (var i = 0; i < nums.length; i++) {
+        map[nums[i]] = map[nums[i]] ? map[nums[i]] + 1 : 1;
+    }
+
+    var keys = Object.keys(map);
+    keys.sort((a, b) => {
+        if (map[a] > map[b]) return -1;
+        if (map[a] < map[b]) return 1;
+        return 0;
+    });
+    // console.log(map, keys);
+    return keys.slice(0, k).map(a => parseInt(a));
+};
+
+console.log(topKFrequent([1, 1, 1, 2, 2, 3, 4], 2));
diff --git a/561-Array-Partition-I.js b/561-Array-Partition-I.js
@@ -0,0 +1,38 @@
+/**
+ * https://leetcode.com/problems/array-partition-i/description/
+ * Difficulty:Easy
+ *
+ * Given an array of 2n integers, your task is to group these integers into n pairs of integer,
+ * say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
+ *
+ * Example 1:
+ * Input: [1,4,3,2]
+ * Output: 4
+ * Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
+ *
+ * Note:
+ * n is a positive integer, which is in the range of [1, 10000].
+ * All the integers in the array will be in the range of [-10000, 10000].
+ */
+
+/**
+ * @param {number[]} nums
+ * @return {number}
+ */
+var arrayPairSum = function (nums) {
+    nums.sort((a, b) => {
+        if (a < b) return -1;
+        if (a > b) return 1;
+        return 0;
+    });
+
+    // console.log(nums);
+    var sum = 0;
+    for (var i = 0; i < nums.length / 2; i++) {
+        sum += nums[2 * i];
+    }
+
+    return sum;
+};
+
+console.log(arrayPairSum([1, 4, 3, 2]));
diff --git a/647-Palindromic-Substrings.js b/647-Palindromic-Substrings.js
@@ -0,0 +1,53 @@
+/**
+ * https://leetcode.com/problems/palindromic-substrings/description/
+ * Difficulty:Medium
+ *
+ *
+ * Given a string, your task is to count how many palindromic substrings in this string.
+ *
+ * The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
+ *
+ * Example 1:
+ *  Input: "abc"
+ *  Output: 3
+ *  Explanation: Three palindromic strings: "a", "b", "c".
+ *
+ * Example 2:
+ *  Input: "aaa"
+ *  Output: 6
+ *  Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
+ *
+ * Note:
+ *  The input string length won't exceed 1000.
+ */
+
+/**
+ * @param {string} s
+ * @return {number}
+ */
+var countSubstrings = function (s) {
+
+    var dp = [];
+    var n = s.length;
+    for (var i = 0; i < n; i++) {
+        dp.push(new Array(n).fill(false));
+        // dp[i][i] = 1;
+    }
+    var cnt = 0;
+    for (var i = n - 1; i >= 0; i--) {
+        for (var j = i; j < n; j++) {
+            if (i === j) dp[i][j] = true;
+            else {
+                dp[i][j] = s[i] === s[j] ? (i + 1 >= j - 1 || dp[i + 1][j - 1]) : 0;
+            }
+            if (dp[i][j]) cnt++;
+        }
+    }
+    // console.log(dp);
+
+    return cnt;
+
+};
+
+// console.log(countSubstrings('abc'));
+console.log(countSubstrings('aaaaa'));
diff --git a/654-Maximum-Binary-Tree.js b/654-Maximum-Binary-Tree.js
diff --git a/718-Maximum-Length-of–Repeated-Subarray.js b/718-Maximum-Length-of–Repeated-Subarray.js
