leetcode刷题日记

32.Longest Valid Parentheses

  • 难度：hard
  • 代码语言：JavaScript
  • 时间：17-10-17

题目描述

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

相当于说，要从一个由括号组成的字符串中，找到一个最长的正确匹配的子字符串的长度。

解题思路

  1. 遍历整个字符串，通过堆栈的方式，每次遍历到'('，把下标压入栈中，每次遍历到')'，从栈中弹出栈顶，并在链表中，把弹出的栈顶指向当前节点。

  2. 这样可以得到一个链表，相当于记录了一个字符串中，左右括号的匹配情况，比如下面这个字符串，’))(()())(()‘

  3. 通过遍历这个链表，就能找到最长的子字符串

    /**
     * @param {string} s
     * @return {number}
     */
    var longestValidParentheses = function (s) {
        var longest = 0
        var stack = [], match = []
        for (var j = 0; j < s.length; j++) {
            if (s[j] == '(') {
                stack.push(j)
            } else {
                var begin = stack.pop()
                var end = j
                if(begin != undefined){
                    match[begin] = end
                    match[end] = -1
                }
            }
        }
        var i = 0, length = 0, begin = 0, end = 0
        while(i < match.length){
            while(match[i] == undefined && i < match.length){
                i++
            }
            if(match[i] == -1){
                if(match[i+1] == undefined){
                    end = i
                    length = end - begin + 1
                    if( length > longest){
                        longest = length
                    }
                    i++
                } else {
                    i = match[i+1]
                }
            } else {
                begin = i
                i = match[i]
            }
        }
        return longest
    };

    ​

Substring with Concatenation of All Words

  • 难度：hard
  • 代码语言：JavaScript
  • 时间：17-10-15

题目描述

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

解题思路

我的解题思路很简单，因为words中的每个单词的长度（length）是固定的，所以只要每length长度，对s进行扫描就行了，扫描到的单词刚好在words里面就把它记录下来即可。这样做的时间复杂度是O(N*M)，N是s的长度，M是words的个数。

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
*/
var findSubstring = function (s, words) {
  var wordLength = words[0].length
  var wordsDict = {}
  words.forEach((d, i, a) => {
    if (wordsDict[d] == undefined) {
      wordsDict[d] = {
        seq: [],
        index: 0
      }
    }
    wordsDict[d].seq.push(i)
  })
  var result = []
  var record = {}
  for (var i = 0; i < s.length; i++) {
    var maxJ = i + words.length * wordLength - wordLength
    if (maxJ > s.length) {
      break
    }
    var wordsSequence = []
    var tobeCleared = []
    for (var j = i; j <= maxJ; j += wordLength) {
      var thisWord = s.slice(j, j + wordLength)
      if (wordsDict[thisWord] != undefined) {
        var index = wordsDict[thisWord].index
        tobeCleared.push(thisWord)
        if (index < wordsDict[thisWord].seq.length) {
          wordsSequence.push(wordsDict[thisWord].seq[index])
          wordsDict[thisWord].index++
        } else {
          break
        }
      } else {
        break
      }
    }
    tobeCleared.forEach((d) => {
      wordsDict[d].index = 0
    })
    if (wordsSequence.length == words.length) {
      result.push(i)
    }
  }
  return result
};

Container With Most Water

  • 难度：Medium
  • 代码语言：JavaScript
  • 时间：16-11-12

    题目描述

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

解题思路

  1. 最简单的，当然就是穷举算法，当然算法复杂度是$O(n^2)$，具体而言，应该是n+(n-1)+(n-2)+…+1这个虽然可取，但是肯定不是我们这么优秀的人的追求啊，在此也不再赘述

  2. 在穷举算法的基础上，进行减支，当然，减支最好的结果就是降低时间复杂度了，当然如果能稍微提点速也是不错的，以下的这个思路就帮我通过了leetcode的测试：

    • 首先需要明白的是，我们的穷举算法中的循环是这个样子的，每次确定水桶左边的一条边，再往后找出右边的那条边

      for(var i = 0; i < height.length; i++)
      	for(var j = i; j < height.length; j++)

    • 第二条原则，两个水桶，公用其中一条边，那么如果其中一个水桶，底又宽，另外一条边又比较长，那肯定这个桶容得下的水比较多，至少不少。举个例子，如下图，a和c组成的水桶肯定比b和c组成的水桶容的水更多。

    • 基于上面两条，既然我们是从左往右遍历的，那么发现b比a短的那一瞬间，我们就应该抛弃b的这种情况。所以边往下遍历的时候，找出已经遍历过的那些边中最长的，那些比最长边要小的，并且在最长边右边的就不考虑了……

    • 代码如下：

      var maxArea = function(height) {
          var maxArea = 0, maxHeight = 0
          for(var i = 0; i < height.length; i++){
          	if(height[i] > maxHeight){ // 比较是否比已经遍历过的最长边还要长
          		maxHeight = height[i]
          		for(var j = i; j < height.length; j++){
          		var h = (j - i) * Math.min(height[i], height[j])
      	    		if(h > maxArea)
      	    			maxArea = h
      	    	}
          	}
          }
          return maxArea
      };

  3. 最终的理想——$O(n)$，在原来的基础上，我们需要再明确一个原则：当某条线作为矩形（水桶）的边时能构造出的最大的矩形，比另外一个矩形面积还要小的时候，那它肯定不是最大的。当然这条原则显而易见，但是在某种场景下有很大用途。

    • 如下图，四条线的高度按从大到小排序为：c>d>b>a。

      明显的是，当a作为水桶的一边时，和d组合才能达到最大容量；

      那么如果b&d组成的面积（蓝色部分）大于a&d组成的面积（黄色部分），那么a这条边就可以排除了，因为a作为矩形的一条边时能产生的最大面积都已经小于b的某种情况了。

    • 根据上面这条原理，我们可以设计出一种，从前往后，从后往前同时进行的算法。

    • b比a短时完全无需考虑了，当b>a时，检查一下b和d构成的面积是否大于当前的最大面积，如果是的话就将b&d的面积设置为最大面积，之后继续往后遍历，直到找到第一条比d还高的边，这就不符合上面提到的那种情况了

    • 于是我们从后往前开始，从d开始往前遍历寻找，这其实除了方向不一样以外，和上面的算法是一样的。

    • 事实证明，这种算法是正确的，附上代码：

      var maxArea = function(height) {
          var maxArea = -1, maxHeight = [-1, -1], i = 0, j = height.length - 1
          while(i < j){
      	    for(; i < j ;){
      	    	if(height[i] > maxHeight[0]){
      	    		if(height[i] > height[j])
      	    			break
      	    		maxHeight[0] = height[i]
      	    		var area = Math.min(maxHeight[0], height[j]) * (j - i)
      	    		if(area > maxArea)
      	    			maxArea = area
      	    	}
      	    	i++
      	    }
      	    for(; j > i;){
      	    	if(height[j] > maxHeight[1]){
      	    		if(height[i] < height[j])
      	    			break
      	    		maxHeight[1] = height[j]
      	    		var area = Math.min(maxHeight[1], height[i]) * (j - i)
      	    		if(area > maxArea)
      	    			maxArea = area
      	    	}
      	    	j--
      	    }
          }
          return maxArea
      };

      ​

Regular Expression Matching

  • 难度：Hard
  • 代码语言：JavaScript
  • 时间：16-11-08

题目描述

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

解题思路

  1. 递归解法：

    • 如果p的第二位不是*，那么说明s的第一位一定要匹配p的第一位，那么从p的第二位和s的第二位开始再执行这个函数（进行递归），否则返回false
    • 如果p的第二位是*，需要一个循环，将s.substring(0), s.substring(1), s.substring(2)...与p去掉头两个进行match（递归），直到s.substring(i)的第一个字符和p的第一个字符不一样；举个例子：s是aaabcd，p是a*bcd，那么，要将aabcd和bcd比较，不符合的话，再对abcd和bcd比较…
    • 这种解法的算法复杂度，似乎在最差情况下会达到$O(n^2)$

  2. 其他解法：

    暂时还在想..

代码

/**
 * [isMatch 递归写法]
 * @param  {[type]}  s [description]
 * @param  {[type]}  p [description]
 * @return {Boolean}   [description]
 */
var isMatch = function(s, p) {
	// "acccdfaaac", "ac*.*aa*ac"
	if(p.length == 0 && s.length == 0)
		return true
	if(p.length == 1){
		if(s.length != 1)
			return false
		else
			return (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0))
	}
	if(p.charAt(1) != '*'){
		if(s.length == 0){
			return false
		}
		else
			return ((p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p.substring(1)))
	}
	else{
		var i = 0
		for(; (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.') && i < s.length; i++){
			if(isMatch(s.substring(i), p.substring(2)))
				return true
		}
		return isMatch(s.substring(i), p.substring(2))
	}
};

Median of Two Sorted Arrays

  • 难度：Hard
  • 代码语言：JavaScript
  • 时间：16-09-30

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解题思路

一开始以为是归并排序的一个小小的应用而已，但一直不明白：O(log (m+n))的时间复杂度怎么达到……后来才明白这个题的恐怖之处就在于此，结题方案是利用二分查找类似的方法，来找到这个值，具体算法比较难写，先挖个坑，后面填上，贴上一个别人的解决方案：

代码

时间复杂度为O(M+N)的算法：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  var length1 = nums1.length, length2 = nums2.length;
  var flag = 0, median = Math.floor((length1 + length2) / 2) + 1;
  var i = 0, j = 0;
  var mergeArr = [];
  if((length1 + length2) % 2 === 0)//flag = 1 : even
    flag = 1;
  for(let k = 0; k < median; k++){
    if((i < length1 && j < length2 && nums1[i] < nums2[j]) || j >= length2){
        mergeArr[k] = nums1[i];
        i++;
    }
    else{
        mergeArr[k] = nums2[j];
        j++;
    }
  }
  if(flag === 1)
    return (mergeArr[median-1] + mergeArr[median-2])/2;
  else
    return mergeArr[median-1];
};

时间复杂度为O(log(m+n))的算法：
先挖坑：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
};

结果

81.90%……玛德其实这个什么卵用都没有！因为即便这么差的算法也能跑这么快？今天以后就不贴了 ZZ；

Longest Substring Without Repeating Characters

  • 难度：Medium
  • 代码语言：JavaScript
  • 时间：16-09-29

题目描述

Given a string, find the length of the longest substring without repeating characters.
Examples:

  • Given "abcabcbb", the answer is "abc", which the length is 3.
  • Given "bbbbb", the answer is "b", with the length of 1.
  • Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

PS:最后要求返回的是子字符串的长度，而不是子字符串。

解题思路

这题一眼就能看出来，最快的算法肯定是O(N)。在这个算法当中，有一步是必须的：

  • 发现一个字符是否有重复：利用类似哈希表的一个数据结构就能在O(1)时间内发现。

举个例子来说明：
假设字符串是："abvdfrhvmcvxdcgtew"

  • 不断向下遍历，并且在一个数组（类似哈希表）里面存入已发现的字符最大的下标，假设该数组叫：charMaxSub,当遍历到第二个v之前，就已经存储了：

    charMaxSub = {
      a: 0,
      b: 1,
      d: 3,
      f: 4,
      h: 6,
      r: 5,
      v: 2
    }

  • 当找到重复字符v时，就会发现，在charMaxSub里面已经存了v，所以这个时候就会产生第一个没有重复字符的最长子字符串："abvdfrh"。此刻应该把charMaxSub.v更新为新的下标。

  • 此时，继续往后遍历，再发现新的没有重复的子字符串，也只能是从第一个v后面产生的，所以，可以把第一个v后面的第一个字符，也就是下标为3的这个当做数组的开始。
  • 继续重复以上的环节，一直往后遍历，直到对比出最长的没有重复字符的子字符串。

代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  var charMaxSub = [];//用来存放字符串中每个字符的最大下标
  var initSub = 0; //随着字符串的遍历，最新的没有重复的子字符串的起始位置
  var maxLength = 0, temp = 0;
  for(let i = 0; i < s.length; i++){
    if(charMaxSub[s[i]] >= initSub){//!== undefined){
      temp = i - initSub;
      maxLength = temp > maxLength ? temp : maxLength;
      temp = charMaxSub[s[i]]+1;
      initSub = temp > initSub ? temp : initSub;
    }
    charMaxSub[s[i]] = i;
  }
  if(s.length-initSub > maxLength)
    maxLength = s.length - initSub;
  return maxLength
};

结果

Your runtime beats 43.41% of javascript submissions.

Add Two Numbers

  • 难度：Medium
  • 代码语言：JavaScript
  • 时间：16-09-28

题目描述

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解题思路

其实就是一般性的加法运算，就很简单，就是个位和个位相加，向前进位。但是你不能先把两个链表先分别整理成整数，也就是不能把(2 -> 4 -> 3)搞成342，因为可能链表比较长的时候就会比较大，会有case通不过……
这题竟然是medium，值得吐槽……

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var nextNode1 = l1, nextNode2 = l2;
    var addVal1 = 0, addVal2 = 0, sum = 0, carryOver = 0;
    var resNode = new ListNode(0);
    var resNodeList = resNode;
    while(resNodeList !== null){
      if(nextNode1 === null){
        addVal1 = 0;
      }
      else{
        addVal1 = nextNode1.val;
        nextNode1 = nextNode1.next;
      }
      if(nextNode2 === null){
        addVal2 = 0;
      }
      else{
        addVal2 = nextNode2.val;
        nextNode2 = nextNode2.next;
      }
      sum = addVal1 + addVal2 + carryOver;
      if(sum >= 10){
        carryOver = 1;
        sum %= 10;
      }
      else
        carryOver = 0;
      resNodeList.val = sum;
      if(nextNode1 === null && nextNode2 === null && carryOver === 0)
        resNodeList.next = null;
      else{
        resNodeList.next = {};
      }
      resNodeList = resNodeList.next;
    }
    return resNode;
};

结果

这种算法的效率beats了46.06%的提交者

Two Sum

  • 难度：easy
  • 代码语言：JavaScript
  • 时间：16-09-27

题目描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

解题思路

这道题最终的思路就是找到一个时间复杂度为O(N)的算法。

  1. 一次遍历下去，假设下标为i，每次用target减去数组中对应的那个值nums[i]，把差存放在一个新的数组中；
  2. 遍历的同时，去看看存储差值的那个数组里是否已经包含了当前这个nums[i]，如果包含的话，就相当于找到了这一对的值；
  3. 所以目标是把每次寻找的时间复杂度降低到O(1)，这样总体复杂度也就降低到了O[N]。

具体就看代码吧，很简单。

代码

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
  var diff = [];
  for(let i = 0; i < nums.length; i++){
	if(diff[nums[i]] !== undefined){
	  return [diff[nums[i]], i];
	}
	diff[target - nums[i]] = i;
  }
};

结果

37.Sudoku Solver

  • 难度：hard
  • 代码语言：JavaScript
  • 时间：18-04-09

题目描述

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

也就是找数独的解，而且保证输入的数独是有唯一解的

解题思路

其实就是个回溯。但是首先可以进行两个预处理。

  1. 先建立一个set，包含1-9的元素，然后去遍历每一个待填充的格子所在行、所在列和所在的九宫格，从set中删掉那些这些行、列和九宫格里已经填好的元素，得到的最终的set作为该单元格的可能解，假如这个可能解只有一个，那么刚好可以直接填入。
  2. 经历第一步后，每个待填充的单元格都会有它的可能解了。但可能，某个单元格包含的可能解，该单元格同行的那些待填充的单元格都不包含，那么只能它来填充这个可能解了，于是乎该单元格也被确定下来。同列和同九宫格的那些也一样。
  3. 在这两个基础上，再进行深度优先搜索的回溯，就会快很多。
var getPossible = function (i, j, board) {
    let result = new Set(['1', '2', '3', '4', '5', '6', '7', '8', '9'])
    board.forEach(function (row) {
        result.delete(row[j])
    })
    board[i].forEach(function (ele) {
        result.delete(ele)
    })
    var x = Math.floor(i / 3) * 3,
        y = Math.floor(j / 3) * 3
    for (var dx = 0; dx < 3; dx++) {
        for (var dy = 0; dy < 3; dy++) {
            var ele = board[x + dx][y + dy]
            result.delete(ele)
        }
    }
    
    if (result.size == 1) {
        board[i][j] = [...result][0]
        board.blankCount--
        if (board.blankCount != 0) {
            return update(i, j, board)
        } else {
            return 0
        }
    } else if (result.size > 1) {
        board[i][j] = result
        return 1
    } else {
        return -1
    }
}
var testPossible = function (i, j, board) {
    var ele = [...board[i][j]]
    for (var t = 0; t < ele.length; t++) {
        possible = ele[t]
        let deepCopy = board.map(function (row, i) {
            return row.map(function (ele, j) {
                return ele
            })
        })
        deepCopy[i][j] = possible
        deepCopy.blankCount = board.blankCount - 1
        var state = update(i, j, deepCopy)
        if (state == 0) {
            deepCopy.forEach(function (row, i) {
                row.forEach(function (ele, j) {
                    board[i][j] = ele
                })
            })
            return true
        } else if (state == 1) {
            var ii = -1,
                jj = -1
            if (deepCopy.some(function (row, i) {
                    return row.some(function (ele, j) {
                        if (ele instanceof Object) {
                            ii = i
                            jj = j
                            return true
                        }
                    })
                })) {
                if(testPossible(ii, jj, deepCopy)){
                    deepCopy.forEach(function (row, i) {
                        row.forEach(function (ele, j) {
                            board[i][j] = ele
                        })
                    })
                    return true
                }
            }
        }
    }
    return false
}
var update = function (x, y, board) {
    var state = 1
    board.forEach(function (row, i) {
        var j = y
        if ((row[j] instanceof Object) || row[j] == '.') {
            state = getPossible(i, j, board)
            if (state == 0) {
                return 0
            } else if (state == -1) {
                return -1
            }
        }
    })
    var i = x
    board[i].forEach(function (ele, j, row) {
        if ((ele instanceof Object) || ele == '.') {
            state = getPossible(i, j, board)
            if (state == 0) {
                return 0
            } else if (state == -1) {
                return -1
            }
        }
    })
    x = Math.floor(x / 3) * 3, y = Math.floor(y / 3) * 3
    for (var dx = 0; dx < 3; dx++) {
        for (var dy = 0; dy < 3; dy++) {
            i = x + dx
            j = y + dy
            var ele = board[i][j]
            if ((ele instanceof Object) || ele == '.') {
                state = getPossible(i, j, board)
                if (state == 0) {
                    return 0
                } else if (state == -1) {
                    return -1
                }
            }
        }
    }
    return state
}
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
    board.blankCount = 0
    board.forEach(function (row, j) {
        row.forEach(function (ele, i) {
            if (ele == '.') {
                board.blankCount++
            }
        })
    })
    var count = 0
    var state = 1
    board.forEach(function (row, i) {
        row.forEach(function (ele, j) {
            if ((ele instanceof Object) || ele == '.') {
                console.log(i, j, count++)
                state = getPossible(i, j, board)
            }
        })
    })
    board.forEach(function (row, i) {
        var record = [[],[],[],[],[],[],[],[],[],[]]
        row.forEach((ele, j) => {
            if(ele instanceof Object){
                ele.forEach(e => {
                    record[e].push([i, j])
                })
            }
        })
        record.forEach((r, t) => {
            if(r.length == 1){
                board[r[0][0]][r[0][1]] = '' + t
                board.blankCount--
                var state = update(r[0][0], r[0][1], board)
                if(state == 0){
                    return
                }
            }
        })
    })
    for(var j = 0; j < board[0].length; j++){
        var record = [[],[],[],[],[],[],[],[],[],[]]
        for(var i = 0; i < board.length; i++){
            var ele = board[i][j]
            if(ele instanceof Object){
                ele.forEach(e => {
                    record[e].push([i, j])
                })
            }
        }
        record.forEach((r, t) => {
            if(r.length == 1){
                board[r[0][0]][r[0][1]] = '' + t
                board.blankCount--
                var state = update(r[0][0], r[0][1], board)
                if(state == 0){
                    return
                }
            }
        })
    }
    for(x = 0; x < 9; x += 3){
        for(y = 0; y < 9; y += 3){
            var record = [[],[],[],[],[],[],[],[],[],[]]
            for (var dx = 0; dx < 3; dx++) {
                for (var dy = 0; dy < 3; dy++) {
                    var i = x + dx, j = y + dy
                    var ele = board[i][j]
                    if(ele instanceof Object){
                        ele.forEach(e => {
                            record[e].push([i, j])
                        })
                    }
                }
            }
            record.forEach((r, t) => {
                if(r.length == 1){
                    board[r[0][0]][r[0][1]] = '' + t
                    board.blankCount--
                    var state = update(r[0][0], r[0][1], board)
                    if(state == 0){
                        return
                    }
                }
            })
        }
    }
    var ii = -1,
        jj = -1
    if (board.some(function (row, i) {
            return row.some(function (ele, j) {
                if (ele instanceof Object) {
                    ii = i
                    jj = j
                    return true
                }
            })
        })) {
            testPossible(ii, jj, board)
    }
};

39.Combination Sum

  • 难度：Medium
  • 代码语言：JavaScript
  • 时间：18-04-10

题目描述

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is: 

[
  [7],
  [2, 2, 3]
]

给定目标7，要从候选的数组里面选出不同的组合，使得和为7

解题思路

简单想，其实是一个递归，最简单的递归思路如下：

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    let candidateSet = new Set(candidates)
    let result = []
    candidates.forEach(candidate => {
        let times = 1
        candidateSet.delete(candidate)
        while (times * candidate <= target) {
            let thisResult = []
            for (let i = 0; i < times; i++) {
                thisResult.push(candidate)
            }
            if (target == times * candidate) {
                result.push(thisResult)
            } else {
                combinationSum([...candidateSet], target - times * candidate).forEach(solution => {
                    result.push(thisResult.concat(solution))
                })
            }
            times++
        }
    })
    return result
};

上述的解法比较简洁，因为应用了set的特性，但是JavaScript中，set的构建和解构是非常耗时的，我们希望转换成数组的形式：

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    return _combinationSum(candidates, 0, target)
};
function _combinationSum(candidates, start, target){
    let result = []
    for(let k = start; k < candidates.length; k++){
        let candidate = candidates[k]
        let times = 1
        while (times * candidate <= target) {
            let thisResult = []
            for (let i = 0; i < times; i++) {
                thisResult.push(candidate)
            }
            if (target == times * candidate) {
                result.push(thisResult)
            } else {
                let iteResult = _combinationSum(candidates, k + 1, target - times * candidate)
                iteResult.forEach(solution => {
                    result.push(thisResult.concat(solution))
                })
            }
            times++
        }
    }
    return result
}

41.First Missing Positive

  • 难度：hard
  • 代码语言：JavaScript
  • 时间：18-04-11

题目描述

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

就是找最小的没有在数组中出现的正数。但难点在于如何用O(n)的时间和常数的空间。

解题思路

  1. 看到这种题，自然而然第一想法就是去排序，然后遍历就OK。但难点在于O(n)的排序算法

  2. 一般的排序算法，最快也得要O(n*logn)，比如快排。当然也有一种trick，利用散列，用O(n)的效率就能将它们散列好（具体代码可以看下方），但从中去遍历的效率就和最大值成正比了，况且这种排序方法的空间并不是一个常数空间，需要在遍历数组的时候，不断扩大。

    // 简单的排序，效率是常数的，O(max(array))，这里是简单实现，最终结果是不包含重复值的
    var hashSort = function(array) {
        let sortedArray = array.reduce((result, num) => {
            result[num] = true
            return result
        }, [])
        return sortedArray.filter(num => !isNaN(num))
    }

  3. 但是还好，我们是找最小缺失的正整数，所以这个正整数一定不会大于数组的长度！

  4. 当明白了以上这一点之后，也就解决了非常数空间的问题了，于是解决方案如下，效率也极为高效：

    /**
     * @param {number[]} nums
     * @return {number}
     */
    var firstMissingPositive = function (nums) {
        let record = []
        for (let i = 0; i < nums.length; i++) {
            let num = nums[i]
            if (num > 0 && num <= nums.length) {
                record[num] = true
            }
        }
        var i = 1
        for (; i < record.length; i++) {
            if (!record[i]) {
                return i
            }
        }
        return i
    };

42.Trapping Rain Water

  • 难度：hard
  • 代码语言：JavaScript
  • 时间：18-04-11

题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

就是给你一堆黑色的条状图，然后下雨，算出能装满的雨水量。

解题思路

  1. 假如我们从左往右进行遍历，能装雨水的地方，一定是某根柱子和它右边的第一根不比它矮的柱子之间的部分。于是我们寻找这样的组合即可。
  2. 但有可能这根柱子右边没有比它高的柱子了，那么从左往右的遍历方法就失效了。故而我们要从右往左再遍历一遍。直到所有的柱子都遍历完。
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let leftIndex = 0, rightIndex = height.length - 1;
    let trapping = 0
    let range = [leftIndex, rightIndex]
    while(leftIndex < rightIndex){
        range = scanLeft(leftIndex, rightIndex, height)
        if(range[1] != -1){
            leftIndex = range[1]
            trapping += calTrapping(range[0], range[1], height)
        }
        range = scanRight(leftIndex, rightIndex, height)
        if(range[0] != -1){
            rightIndex = range[0]
            trapping += calTrapping(range[0], range[1], height)
        }
    }
    return trapping
};
function calTrapping(left, right, height){
    let maxHeight = Math.min(height[left], height[right])
    let result = 0
    for(let i = left; i <= right; i++){
        if(height[i] < maxHeight){
            result += (maxHeight - height[i])
        }
    }
    return result
}
function scanLeft(left, right, height){
    let leftHeight = height[left]
    for(let i = left + 1; i <= right; i++){
        if(height[i] >= leftHeight){
            return [left, i]
        }
    }
    return [left, -1]
}
function scanRight(left, right, height){
    let rightHeight = height[right]
    for(let i = right - 1; i >= left; i--){
        if(height[i] >= rightHeight){
            return [i, right]
        }
    }
    return [-1, right]
}

44. Wildcard Matching

  • 难度：hard
  • 代码语言：JavaScript
  • 时间：18-04-14

题目描述

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

问题可以简单表述为正则匹配，*表示匹配0或多个任意字符，?表示匹配1个任意字符。字符只包含a-z。

解题思路

  1. 我的思路是，在正则表达式中，*是一个很特殊的存在，因为它可以匹配[0, Inifinity]个任意字符，所以要特殊对待。
  2. 我专门写了一个findFromS函数方便调用，用来查找某个字符串str在输入的s中的所有位置，能够处理?的情况，效率应该是$O(len(s) * len(str))$。
  3. 首先我们来看头和尾，如果正则表达式的头和尾都不是*，那么就需要看看能不能和字符串s的头尾相吻合，如果吻合则p和s都去掉头尾。
  4. 对于p的中间的部分，我们可以用*来分割它们，则会得到一个序列，我们只要去s中寻找，是否有这样的序列即可。
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  	// 预处理，将多个*合并成一个
    var newp = ''
    for (let i = 0; i < p.length; i++) {
        newp += p[i]
        if (p[i] == '*') {
            i--
            while (p[i + 1] == '*') {
                i++
            }
        }
    }
    p = newp
    let result = []
    // head
    let head = ''
    for (let i = 0; i < p.length && p[i] != '*'; i++) {
        head += p[i]
    }
    let headInfo
    if (head.length) {
        headInfo = findFromS(s, head)[0]
        if (!headInfo || headInfo[0] != 0) {
            return false
        }
        p = p.slice(headInfo[1])
        s = s.slice(headInfo[0] + headInfo[1])
    }
    // tail
    let tail = ''
    for (let i = p.length - 1; i >= 0 && p[i] != '*'; i--) {
        tail = p[i] + tail
    }
    let tailInfo
    if (tail.length) {
        tailInfo = findFromS(s, tail).pop()
        if (!tailInfo || tailInfo[0] + tailInfo[1] != s.length) {
            return false
        }
        p = p.slice(0, p.length - tailInfo[1])
        s = s.slice(0, tailInfo[0])
    }
    if (!p.length && s.length) {
        return false
    }
    let spliteP = p.split('*').filter(s => s.length)
    if (spliteP.length == 0) {
        return true
    }
    return !spliteP.map(str => findFromS(s, str)).some(element => {
        if (element.length == 0) {
            return true
        } else {
            if (result.length == 0) {
                result.push(element[0])
                return false
            } else {
                return !element.some(e => {
                    if (e[0] >= (result[result.length - 1][0] + result[result.length - 1][1])) {
                        result.push(e)
                        return true
                    }
                })
            }
        }
    })
    // return _isMatch(s, p, 0, 0)
};
function findFromS(s, str, init = 0) {
    let length = str.length
    let result = []
    for (let i = init; i < s.length; i++) {
        let state = true
        if (i > s.length - str.length) {
            state = false
        } else {
            for (let k = 0; k < str.length; k++) {
                if (s[i + k] != str[k] && str[k] != '?') {
                    state = false
                }
            }
        }
        if (state) {
            result.push([i, length])
        }
    }
    return result
}

49. Group Anagrams

  • 难度：Medium
  • 代码语言：JavaScript
  • 时间：18-05-08

题目描述

  • Given an array of strings, group anagrams together.

    Example:

    Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
    Output:
    [
      ["ate","eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]

    Note:

    • All inputs will be in lowercase.
    • The order of your output does not matter.

    ​

找到Anagrams，具体什么叫Anagrams应该在例子中说明的比较清楚。

解题思路

这题思路其实不难，但一直有个瓶颈，关于如何将一个字符串，hash成为一个数字的问题。看了最佳答案，它的hash方法值得学习：

const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
    37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
    97, 101
] // 26 primes
const alphaToInteger = x => x.charCodeAt(0) - 97
const alphaToPrime = x => primes[alphaToInteger(x)]
const hashStr = (s) => {
    let hash = 1
    for (let i = 0; i < s.length; i++) {
        hash *= alphaToPrime(s[i])
    }
    return hash
}

用反证法证明其有效性：

假设存在四个质数：$a,b,c,d$，使得$a\times b=c\times d$，显然，这是不可能的，因为如果成立，$a$和$b$就是$c \times d$的公约数，而显然$c \times d$的公约质数只有$c $和$d$，所以不存在$a \times b = c \times d$。

故而不同的质数相乘，一定会得到不一样的解，也就解决了hash过程中collision的问题。