Leetcode做题笔记

Posted on 三 08 七月 2015 in 编码

Two Sum

  • The return numbers in vector should be increasely order.

Longest Substring Without Repeating Characters

  • Record the position of every characters so far.

Median of Two Sorted Arrays

  • Use the method of findKth
  • The start index should add to k

Longest Palindromic Substring

  • Use Manacher algorithm.reference
  • Time complexity O(N): the inner loop will take at most a total of N steps in the whole process. Why? Every step of outter loop, the mx(=id+len[id]) will be the most right index before this iteration and the inner loop will start checking charachers at position mx. Then update the mx. So the inner Loop will check every characher once.

Reverse Integer

  • Use the type of unsigned int to contain the abs(x), sign be the sign of x.
  • Use res to represent the reverse result so far and res = res * 10 + digit.
  • When the res is bigger than 214748364 and there is digit which do not reverse yet, it will be overflow. If the reverse is overflow, the reverse of digits exclude the fast digit of x must bigger than ((2 << 31) - 1) >> 1. Because if x have nine digits, then the most significant digit should be 1 or 2.

String to Integer (atoi)

  • The atoi reference
  • Use int isspace(int c) to check if character is a white-space and bool isdigit(char) to check if character is decimal digit.
  • And according to the problem, it requires that if the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned. But the atoi in standard library does not have this requirement.

Palindrome Number

  • The negative integer is not a palindrome.

Regular Expression Matching

  • DP, O(n * m)
  • f[i][j] = f[i-1][j-1] && match(s[j], p[i]), if p[i] != '*' && p[i+1] != '*'.
  • f[i][j] = f[i][j-1] || f[i-1][j-1] && match(s[j], p[i]), if p[i+1] == '*'.
  • f[i][j] = f[i-1][j], if p[i] == '*'.

Container With Most Water

  • Reference lccycc
  • assume that 0..i-1 and j+1..n-1 have all find their best match
  • assume height[i] < height[j]
  • if i match some k, i<k<j
  • answer = (k-i) * min(height[i], height[k]) <= (k-i) * height[i] < (j-i) * height[i];
  • so the best match of i is j. for k < i or k > j, they have find their best match. so no need to concern.

Implement strStr()

  • kmp
  • if the needle is empty string, should return 0.

Substring with Concatenation of All Words

  • O(len * n / len * len) = O(n * len), n is the length of s, m is the number of words, len is the length of word.
  • The straightforward thought is that we can scan every m * len long string start form each position in s and see if all the strings in words have been appeared only once using map data structure.
  • How to pick every m * len long string? Pick a start position in [0, len-1] and get the m * len start with it. When we have a m * len long string and the range is [i, j], then we can get another m * len long string by removing the [i, i+len-1] chars and append [j+1, j+len] chars.

Longest Valid Parentheses

  • First push -1 into stack.
  • Then Scan the s, when the char scaned now is ( then push the index into stack. When the char is ), pop the top element if the number of element in stack is more than one or change the top element to be the index now if the stack only contains one element, and calculate the i - top which is one of the candidates of the longest length.

Multiply Strings

  • Leading zero should be removed.

Leetcode