发表于 | 分类于

​ 最近和浩博讨论了下几道关于二分查找的题目。正好做一下总结，方便下一次能够快速手写出二分的算法。

​ 其实，二分查找，可以用下图简单表示流程。

​

阅读全文 »

发表于 | 分类于

Implement regular expression matching with support for '.' and '*'.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> '.' 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
>

​ 题意：正则匹配，判断p是否匹配s。其中’.’匹配任意单个字符，’*’匹配0个或多个的前一字符。

阅读全文 »

发表于 | 分类于

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

题意：给出一个数n，判断它最少可以由多少个完全平方数相加而成。

阅读全文 »

发表于 | 分类于

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

阅读全文 »

发表于 | 分类于

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.

  2. The array size will not exceed 200.

    阅读全文 »