pdu’s gists

pdu / leetcode_flatten_binary_tree_to_linked_list.cpp

Created January 7, 2013 14:39

Given a binary tree, flatten it to a linked list in-place. http://leetcode.com/onlinejudge

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {

pdu / leetcode_generate_parentheses.cpp

Created January 9, 2013 15:28

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" http://leetcode.com/onlinejudge

	class Solution {
	public:
	void dfs(vector<string>& ret, char* buf, int n, int id, int cnt1, int cnt2) {
	if (id == 2 * n) {
	buf[id] = 0;
	ret.push_back(buf);
	return;
	}
	if (cnt1 < n) {
	buf[id] = '(';

pdu / leetcode_gray_code.cpp

Created January 9, 2013 15:43

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. http://leetcode.com/onlinejudge

	class Solution {
	public:
	vector<int> grayCode(int n) {
	vector<int> ret;
	if (n == 0) {
	ret.push_back(0);
	return ret;
	}
	else if (n == 1) {
	ret.push_back(0);

pdu / leetcode_strstr.cpp

Created January 10, 2013 15:14

Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack. http://leetcode.com/onlinejudge

	class Solution {
	public:
	char strStr(char haystack, char *needle) {
	if (haystack == NULL && needle == NULL)
	return haystack;
	char* ret;
	for (ret = haystack; *ret != NULL; ++ret) {
	int k;
	for (k = 0; needle[k] != NULL; ++k)
	if (ret[k] != needle[k])

pdu / leetcode_merge_sorted_array.cpp

Created January 15, 2013 15:02

Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. http://leetcode.com/onlinejudge#question_88

	class Solution {
	public:
	void merge(int A[], int m, int B[], int n) {
	int *C = new int[m];
	memcpy(C, A, m * sizeof(int));
	int i = 0, j = 0;
	int id = 0;
	while (i < m \|\| j < n) {
	if (i == m)
	A[id++] = B[j++];

pdu / leetcode_scramble_string.cpp

Created January 15, 2013 16:22

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. http://leetcode.com/onlinejudge#question_87

	#define MAXN 100

	int f[MAXN][MAXN][MAXN];

	class Solution {
	public:
	bool dp(int f[MAXN][MAXN][MAXN], const string& s1, const string& s2, int i, int j, int k) {
	if (f[i][j][k] != -1)
	return f[i][j][k] == 1;
	if (k == 1)

pdu / leetcode_partition_list.cpp

Created January 16, 2013 15:47

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. http://leetcode.com/onlinejudge#question_86

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

pdu / leetcode_maximal_rectangle.cpp

Created January 17, 2013 15:25

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. http://leetcode.com/onlinejudge#question_85

	class Solution {
	public:
	int maximalRectangle(vector<vector<char> > &matrix) {
	int n = matrix.size();
	if (0 == n)
	return 0;
	int m = matrix[0].size();
	if (0 == m)
	return 0;

pdu / leetcode_largest_rectangle_in_histogram.cpp

Created January 20, 2013 15:21

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit. For example, Given height = [2,1…

	#define MAXN 1000000

	int st[MAXN];
	int l[MAXN];
	int r[MAXN];

	class Solution {
	public:
	int largestRectangleArea(vector<int> &height) {
	int n = height.size();

pdu / leetcode_remove_duplicates_from_sorted_list_2.cpp

Created January 21, 2013 13:34

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3. http://leetcode.com/onlinejudge#question_82

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

Peng Du pdu