pdu’s gists

pdu / leetcode_spiral_matrix.cpp

Created February 17, 2013 13:19

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. http://leetcode.com/onlinejudge#question_54

	#define INF 0x7fffffff

	int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

	bool inBound(int x, int y, int n, int m) {
	return x >= 0 && x < n && y >= 0 && y < m;
	}

	class Solution {
	public:

pdu / leetcode_maximum_subarray.cpp

Created February 17, 2013 13:24

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6. More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, whi…

	class Solution {
	public:
	int maxSubArray(int A[], int n) {
	if (n == 0)
	return 0;
	int ret = A[0];
	int sum = 0;
	for (int i = 0; i < n; ++i) {
	sum += A[i];
	ret = max(sum, ret);

pdu / leetcode_pow.cpp

Created February 17, 2013 13:31

Implement pow(x, n). http://leetcode.com/onlinejudge#question_50

	class Solution {
	public:
	double pow(double x, int n) {
	if (n == 0)
	return 1;
	else if (n == 1)
	return x;
	if (n < 0) {
	x = 1 / x;
	n = -n;

pdu / leetcode_anagrams.cpp

Created February 17, 2013 13:41

Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. http://leetcode.com/onlinejudge#question_49

	class Solution {
	public:
	vector<string> anagrams(vector<string> &strs) {
	vector<string> ans;
	map<string, int> M;
	for (int i = 0; i < strs.size(); ++i) {
	string tmp = strs[i];
	sort(tmp.begin(), tmp.end());
	try {
	M[tmp]++;

pdu / leetcode_rotate_image.cpp

Created February 17, 2013 15:22

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? http://leetcode.com/onlinejudge#question_48

	class Solution {
	public:
	void rotate(vector<vector<int> > &matrix) {
	int n = matrix.size();
	for (int leftx = 0; leftx < n / 2; leftx++) {
	int len = n - leftx * 2;
	int rightx = leftx + len - 1;
	for (int i = 0; i < len - 1; ++i) {
	int tmp = matrix[leftx][leftx + i];
	matrix[leftx][leftx + i] = matrix[rightx - i][leftx];

pdu / leetcode_permutations.cpp

Created February 17, 2013 15:30

Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. http://leetcode.com/onlinejudge#question_46

	class Solution {
	public:
	vector<vector<int> > permute(vector<int> &num) {
	vector< vector<int> > ans;
	ans.push_back(num);
	vector<int> id(num.size());
	for (int i = 0; i < id.size(); ++i)
	id[i] = i;
	while (next_permutation(id.begin(), id.end())) {
	vector<int> tmp;

pdu / leetcode_permutations_2.cpp

Created February 17, 2013 15:39

Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. http://leetcode.com/onlinejudge#question_47

	#include <tr1::unordered_map>

	class Solution {
	public:
	vector<vector<int> > permuteUnique(vector<int> &num) {
	int n = num.size();
	vector<vector<int> > ans;
	vector<int> id(n);
	for (int i = 0; i < n; ++i)
	id[i] = i;

pdu / leetcode_jump_game_2.cpp

Created February 17, 2013 15:52

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is…

	#include <queue>

	struct Node {
	int pos;
	int val;
	Node(int p, int v) {
	pos = p;
	val = v;
	}
	};

pdu / leetcode_wildcard_matching.cpp

Created February 18, 2013 14:30

Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). 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") â…

	#define MAXN 500
	int f[MAXN][MAXN];

	bool isMatch_(const char* s, const char* p, int n, int m) {
	if (n < 0 && m < 0)
	return true;
	else if (n >= 0 && m < 0)
	return false;
	else if (n < 0) {
	for (int i = 0; i <= m; ++i)

pdu / leetcode_multiply_strings.cpp

Created February 18, 2013 15:13

Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. http://leetcode.com/onlinejudge#question_43

	#define MAXN 10000
	int f[MAXN];

	class Solution {
	public:
	string multiply(string num1, string num2) {
	int n = num1.length();
	int m = num2.length();
	memset(f, 0, sizeof(f));
	for (int i = m - 1; i >= 0; --i) {

Peng Du pdu