leetcode刷题日记

作者 Jackie Anxis 日期 2016-11-12
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的第一个字符不一样;举个例子:saaabcdpa*bcd,那么,要将aabcdbcd比较,不符合的话,再对abcdbcd比较…
    • 这种解法的算法复杂度,似乎在最差情况下会达到$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;
}
};

结果