2014/09/15

posted in OJ题解

LeetCode: Remove Nth Node From End of List

题目
分析
代码

题目

https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/

分析

两个指针，第一个指针先走n步，然后两个指针一起走，直到第一个指针走到结尾处，此时第二个指针即为要删除的结点的上一个结点。
特别要注意的一点是，如果要删除的结点是第一个结点，要特别的处理一下，因为第二个指针无法指向第一个结点的上一个结点。

代码

class Solution
{
public:
	ListNode *removeNthFromEnd(ListNode *head, int n)
	{
		ListNode *l, *r;

		l = head;
		r = head;
		for (int i = 0; i < n; i++)
			r = r->next;

		if (r == NULL)
		{
			ListNode *t = head;
			head = head->next;
			delete t;
		}
		else
		{
			while (r->next != NULL)
			{
				l = l->next;
				r = r->next;
			}
			ListNode *t = l->next;
			l->next = t->next;
			delete(t);
		}
		return head;
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39289759

2014/09/14

posted in OJ题解

LeetCode: Letter Combinations of a Phone Number

题目：
分析：
代码：

题目：

https://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/

分析：

DFS

代码：

class Solution
{
public:
	vector<string> letterCombinations(string digits)
	{
		string solution;
		dfs(digits, 0, solution);

		return res;
	}
	void dfs(string &digits, int index, string &solution)
	{
		if (index == digits.size())
		{
			res.push_back(solution);
			return;
		}
		else
		{
			for (auto &r : key[digits[index] - '0'])
			{
				solution.push_back(r);
				dfs(digits, index+1, solution);
				solution.pop_back();
			}
		}
	}
	vector<string> res;
	string key[10] = {"", 
		"", "abc", "def", 
		"ghi", "jkl", "mno",
		"pqrs", "tuv", "wxyz"};
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39272421

2014/09/14

posted in OJ题解

LeetCode: Maximum Subarray

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/maximum-subarray/

分析

一开始想用穷举法找出所有的子序列，并求出最大的和，然后结果是超时了。
后来发现这道题是一道很巧妙的DP题，

首先我们先来求另一个问题， “数组A[]中包含最后一个元素的最大连续子序列的和为多少？”

包含最后一个元素的最大连续子序列的和有两种情况：

最后一个元素和前面的元素构成一个子序列

或者最后一个元素自成一个子序列。

递归的求包含最后一个元素的最大连续子序列就是 f(n) = max(f(n-1), A[n]);

以此类推，每个元素为结尾的最大连续子序列的和就求出来了，

在2中，其中的最大值便是整个数列的最大连续子序列的和。

把上面递归用改写为递归的形式，就是最终结果了。

代码

class Solution
{
public:
	int maxSubArray(int A[], int n)
	{
		int sum[n], res;

		sum[0] = A[0];
		res = sum[0];
		for (int i = 1; i < n; i++)
		{
			sum[i] = max(A[i], sum[i-1] + A[i]);
			res = max(res, sum[i]);
		}

		return res;
	}
};

参考

http://blog.csdn.net/v_july_v/article/details/6444021

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39271637

2014/09/10

posted in OJ题解

LeetCode: Regular Expression Mathing

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/regular-expression-matching/

分析

普通字符和'.'的匹配很好解决，直接匹配即可，关键是'*'如何进行匹配
一开始我的想法是， ‘*’尽可能“贪婪”的匹配多个字符，直到不再匹配为止。然后在 s = "aaa", p = "a*a" 这个测试用例上跪了。。。
这说明'*'并不是尽可能多的进行匹配，而是匹配一定数量的字符。那么这个“一定数量”到底应该如何确定呢？

可以这样确定，每匹配一个字符，就跳过'*'继续匹配下面的，成功了就返回true, 如果失败了就返回'*'处再多匹配一个字符，再跳过'*'匹配后面的……以此类推。显然这的返回现场就是通过递归算法的DFS来实现了。

代码

class Solution
{
public:
	bool isMatch(const char *s, const char *p)
	{
		//递归基
		if (*p == '\0')
			return (*s == '\0');

		//如果下一个字符不是'*'
		if (*(p+1) != '*')
			return (*s != '\0') && (*s == *p || *p == '.') && isMatch(s+1, p+1);

		//如果下一个字符是'*'
		if (isMatch(s, p+2))
			return true;
		while ((*s != '\0') && (*s == *p || *p == '.')) 
		{
			s++;
			if (isMatch(s, p+2))
				return true;
		}
		return false;
	}
};

参考

http://leetcode.com/2011/09/regular-expression-matching.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39185791

2014/09/09

posted in OJ题解

LeetCode: Reverse Integer

题目
分析
代码

题目

https://oj.leetcode.com/problems/reverse-integer/

分析

循环求解即可。

代码

class Solution
{
public:
	int reverse(int x)
	{
		bool minus = false;
		int res = 0;

		if (x < 0)
		{
			x = -x;
			minus = true;
		}
		while (x != 0)
		{
			int t;
			t = x % 10;
			x = x / 10;
			res = res * 10 + t;
		}
		if (minus)
			res = -res;

		return res;
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39157653

2014/09/09

posted in OJ题解

LeetCode: Median of Two Sorted Arrays

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

分析

如果这道题的时间复杂度要求是O(m+n)的话，就很简单了，直接merge之后找出中位数即可。

如果时间复杂度要求为O(log(m+n))的话，可以把这道题转化为求第k小的问题。

如果(m+n)是奇数的话，中位数就是第（m+n）/2+1小；如果(m+n)是偶数，中位数就是第(m+n)/2小和第(m+n)/2+1小的平均数。
然后问题是如何求解第k小的数？

假设有两个数组：

A[0], A[1], ......A[m-1]

B[0], B[1], ......B[n-1]

两数组合并后为

C[0], C[1], ...... C[m+n-1]

不妨假设m和n都大于k/2, 比较A[k/2-1]和B[k/2-1]，

如果A[k/2-1] < B[k/2-1]，那么A[k/2-1]及其左侧的元素一定小于合并后的第k小的那个数（即C[k-1]）

为什么？

可以通过反证来证明，

假设A[k/2-1]等于合并后第k小元素 (即C[k-1]),

那么实际最多有多少个元素比A[k/2-1]小呢？ A[0], A[1]......A[k/2-2]以及B[0], B[1].......B[k/2-2]，共k-2个元素。也就是说A[k/2-1]最好情况下是第k-1小元素(即C[k-2])

这与假设矛盾，因此假设不成立

因此可以说， A[k/2-1]及其左侧元素一定小于合并后的第k小那个数，这样就可以排除掉这一范围的数，从而缩小了问题规模。

再来考虑递归基

当A为空或者B为空时，返回B[k-1]或A[k-1]

当k == 1时，返回A[0]和B[0]中较小的那个数

当A[k/2-1] == B[k/2-1]时，返回A[k/2-1]

否则的话，就递归缩小问题规模。

代码

class Solution
{
public:
	double findMedianSortedArrays(int A[], int m, int B[], int n)
	{
		if ((m + n) & 0x01)
			return findKth(A, m, B, n, (m + n) / 2 + 1);
		else
			return (findKth(A, m, B, n, (m + n) / 2) 
					+ findKth(A, m, B, n, (m + n) / 2 + 1)) / 2;
	}

	double findKth(int A[], int m, int B[], int n, int k)
	{
		if (m > n)
			return findKth(B, n, A, m, k);
		else if (m == 0)
			return B[k-1];
		else if (k == 1)
			return min(A[0], B[0]);
		else
		{
			int ALeftCount = min(k / 2, m);
			int BLeftCount = k - ALeftCount;

			if (A[ALeftCount-1] == B[BLeftCount-1])
				return A[ALeftCount-1];
			else if (A[ALeftCount-1] < B[BLeftCount-1])
				return findKth(A+ALeftCount, m-ALeftCount, 
						B, n, k-ALeftCount);
			else//A[ALeftCount-1] > B[BLeftCount-1]]
				return findKth(A, m, 
						B+BLeftCount, n-BLeftCount, k-BLeftCount);
		}
	}
};

参考

http://blog.csdn.net/yutianzuijin/article/details/11499917

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39156991

2014/09/09

posted in OJ题解

『转』LeetCode题目难度频率分布

20130909144941265


1	Two Sum	2	5	array	sort
				set	Two Pointers
2	Add Two Numbers	3	4	linked list	Two Pointers
					Math
3	Longest Substring Without Repeating Characters	3	2	string	Two Pointers
				hashtable
4	Median of Two Sorted Arrays	5	3	array	Binary Search
5	Longest Palindromic Substring	4	2	string
6	ZigZag Conversion	3	1	string
7	Reverse Integer	2	3		Math
8	String to Integer (atoi)	2	5	string	Math
9	Palindrome Number	2	2		Math
10	Regular Expression Matching	5	3	string	Recursion
					DP
11	Container With Most Water	3	2	array	Two Pointers
12	Integer to Roman	3	4		Math
13	Roman to Integer	2	4		Math
14	Longest Common Prefix	2	1	string
15	3Sum	3	5	array	Two Pointers
16	3Sum Closest	3	1	array	Two Pointers
17	Letter Combinations of a Phone Number	3	3	string	DFS
18	4Sum	3	2	array
19	Remove Nth Node From End of List	2	3	linked list	Two Pointers
20	Valid Parentheses	2	5	string	Stack
21	Merge Two Sorted Lists	2	5	linked list	sort
					Two Pointers
					merge
22	Generate Parentheses	3	4	string	DFS
23	Merge k Sorted Lists	3	4	linked list	sort
				heap	Two Pointers
					merge
24	Swap Nodes in Pairs	2	4	linked list
25	Reverse Nodes in k-Group	4	2	linked list	Recursion
					Two Pointers
26	Remove Duplicates from Sorted Array	1	3	array	Two Pointers
27	Remove Element	1	4	array	Two Pointers
28	Implement strStr()	4	5	string	Two Pointers
					KMP
					rolling hash
29	Divide Two Integers	4	3		Binary Search
					Math
30	Substring with Concatenation of All Words	3	1	string	Two Pointers
31	Next Permutation	5	2	array	permutation
32	Longest Valid Parentheses	4	1	string	DP
33	Search in Rotated Sorted Array	4	3	array	Binary Search
34	Search for a Range	4	3	array	Binary Search
35	Search Insert Position	2	2	array
36	Valid Sudoku	2	2	array
37	Sudoku Solver	4	2	array	DFS
38	Count and Say	2	2	string	Two Pointers
39	Combination Sum	3	3	array	combination
40	Combination Sum II	4	2	array	combination
41	First Missing Positive	5	2	array	sort
42	Trapping Rain Water	4	2	array	Two Pointers
					Stack
43	Multiply Strings	4	3	string	Two Pointers
					Math
44	Wildcard Matching	5	3	string	Recursion
					DP
					greedy
45	Jump Game II	4	2	array
46	Permutations	3	4	array	permutation
47	Permutations II	4	2	array	permutation
48	Rotate Image	4	2	array
49	Anagrams	3	4	string
				hashtable
50	Pow(x, n)	3	5		Binary Search
					Math
51	N-Queens	4	3	array	DFS
52	N-Queens II	4	3	array	DFS
53	Maximum Subarray	3	3	array	DP
54	Spiral Matrix	4	2	array
55	Jump Game	3	2	array
56	Merge Intervals	4	5	array	sort
				linked list	merge
				red-black tree
57	Insert Interval	4	5	array	sort
				linked list	merge
				red-black tree
58	Length of Last Word	1	1	string
59	Spiral Matrix II	3	2	array
60	Permutation Sequence	5	1		permutation
					Math
61	Rotate List	3	2	linked list	Two Pointers
62	Unique Paths	2	3	array	DP
63	Unique Paths II	3	3	array	DP
64	Minimum Path Sum	3	3	array	DP
65	Valid Number	2	5	string	Math
66	Plus One	1	2	array	Math
67	Add Binary	2	4	string	Two Pointers
					Math
68	Text Justification	4	2	string
69	Sqrt(x)	4	4		Binary Search
70	Climbing Stairs	2	5		DP
71	Simplify Path	3	1	string	Stack
72	Edit Distance	4	3	string	DP
73	Set Matrix Zeroes	3	5	array
74	Search a 2D Matrix	3	3	array	Binary Search
75	Sort Colors	4	2	array	sort
					Two Pointers
76	Minimum Window Substring	4	2	string	Two Pointers
77	Combinations	3	4		combination
78	Subsets	3	4	array	Recursion
					combination
79	Word Search	3	4	array	DFS
80	Remove Duplicates from Sorted Array II	2	2	array	Two Pointers
81	Search in Rotated Sorted Array II	5	3	array	Binary Search
82	Remove Duplicates from Sorted List II	3	3	linked list	Recursion
					Two Pointers
83	Remove Duplicates from Sorted List	1	3	linked list
84	Largest Rectangle in Histogram	5	2	array	Stack
85	Maximal Rectangle	5	1	array	DP
					Stack
86	Partition List	3	3	linked list	Two Pointers
87	Scramble String	5	2	string	Recursion
					DP
88	Merge Sorted Array	2	5	array	Two Pointers
					merge
89	Gray Code	4	2		combination
90	Subsets II	4	2	array	Recursion
					combination
91	Decode Ways	3	4	string	Recursion
					DP
92	Reverse Linked List II	3	2	linked list	Two Pointers
93	Restore IP Addresses	3	3	string	DFS
94	Binary Tree Inorder Traversal	4	3	tree	Recursion
				hashtable	morris
					Stack
95	Unique Binary Search Trees II	4	1	tree	DP
					DFS
96	Unique Binary Search Trees	3	1	tree	DP
97	Interleaving String	5	2	string	Recursion
					DP
98	Validate Binary Search Tree	3	5	tree	DFS
99	Recover Binary Search Tree	4	2	tree	DFS
100	Same Tree	1	1	tree	DFS
101	Symmetric Tree	1	2	tree	DFS
102	Binary Tree Level Order Traversal	3	4	tree	BFS
103	Binary Tree Zigzag Level Order Traversal	4	3	queue	BFS
				tree	Stack
104	Maximum Depth of Binary Tree	1	1	tree	DFS
105	Construct Binary Tree from Preorder and Inorder Tr	3	3	array	DFS
				tree
106	Construct Binary Tree from Inorder and Postorder T	3	3	array	DFS
				tree
107	Binary Tree Level Order Traversal II	3	1	tree	BFS
108	Convert Sorted Array to Binary Search Tree	2	3	tree	DFS
109	Convert Sorted List to Binary Search Tree	4	3	linked list	Recursion
					Two Pointers
110	Balanced Binary Tree	1	2	tree	DFS
111	Minimum Depth of Binary Tree	1	1	tree	DFS
112	Path Sum	1	3	tree	DFS
113	Path Sum II	2	2	tree	DFS
114	Flatten Binary Tree to Linked List	3	3	tree	Recursion
					Stack
115	Distinct Subsequences	4	2	string	DP
116	Populating Next Right Pointers in Each Node	3	3	tree	DFS
117	Populating Next Right Pointers in Each Node II	4	2	tree	DFS
118	Pascal's Triangle	2	1	array
119	Pascal's Triangle II	2	1	array
120	Triangle	3	1	array	DP
121	Best Time to Buy and Sell Stock	2	1	array	DP
122	Best Time to Buy and Sell Stock II	3	1	array	greedy
123	Best Time to Buy and Sell Stock III	4	1	array	DP
124	Binary Tree Maximum Path Sum	4	2	tree	DFS
125	Valid Palindrome	2	5	string	Two Pointers
126	Word Ladder II	1	1
127	Word Ladder	3	5	graph	BFS
					shortest path
128	Longest Consecutive Sequence	4	3	array
129	Sum Root to Leaf Numbers	2	4	tree	DFS
130	Surrounded Regions	4	3	array	BFS
					DFS
131	Palindrome Partitioning	3	4	string	DFS
132	Palindrome Partitioning II	4	3	string	DP

转自：

http://blog.csdn.net/yutianzuijin/article/details/11477603

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39155255