问题描述

给定一个二叉树的前序遍历序列（preorder），由这个给定的序列推测原二叉树是否存在。#表示NULL。

Example 1

给定序列："9,3,4,#,#,1,#,#,2,#,6,#,#"，则可构造如下的二叉树：

1
2
3
4
5
6
7

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

所以返回True;

Example 2

给定序列"9,#,#,1", 则不存在这样一颗二叉树。

问题描述

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.

问题描述

K-Sum问题可以描述为，给定一个未排序且可重复的整数array以及一个target，求是否存在K个array中的整数，使得它们的和为target。找出所有的组合，并且不能重复，每个组合数字按升序排列。

4Sum的问题描述

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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.
  For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

问题描述

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

问题描述

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
“112358“ is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
“199100199“ is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

问题描述

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

思路

这题是个典型的动归问题 ，由于求的是子序列的最大乘积 ，所以要注意0和负数的情况。

动归中要保持两个量，一个是最大的正数积，一个是最小负数积（最小负数积用来保证遇到下个负数是能获得最大的正数积）。遇到0时，两个数都置为0。

more >>