pdu’s gists

pdu / leetcode_minimum_path_sum.cpp

Created February 16, 2013 11:28

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. http://leetcode.com/onlinejudge#question_64

	#define MAXN 1000
	#define MAX_INT 0x7fffffff
	int ans[MAXN][MAXN];

	class Solution {
	public:
	int minPathSum(vector<vector<int> > &grid) {
	int n = grid.size();
	int m = grid[0].size();
	for (int i = 0; i < n; ++i)

pdu / leetcode_unique_paths.cpp

Created February 16, 2013 11:54

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Above is a 3 x 7 grid. How many poss…

	#define MAXN 100
	int ans[MAXN][MAXN];

	class Solution {
	public:
	int uniquePaths(int m, int n) {
	for (int i = 1; i <= m; ++i)
	for (int j = 1; j <= n; ++j) {
	if (i == 1 && j == 1)
	ans[i][j] = 1;

pdu / leetcode_unique_paths_2.cpp

Created February 16, 2013 12:00

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths i…

	#define MAXN 100
	int ans[MAXN][MAXN];

	class Solution {
	public:
	int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
	int n = obstacleGrid.size();
	int m = obstacleGrid[0].size();
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j) {

pdu / leetcode_rotate_list.cpp

Created February 16, 2013 12:29

Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. http://leetcode.com/onlinejudge#question_61

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

pdu / leetcode_permutation_sequence.cpp

Created February 16, 2013 12:36

The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive. http://leetcode.com/onlinejudge#question_60

	#define MAXN 10
	int num[MAXN];

	class Solution {
	public:
	string getPermutation(int n, int k) {
	for (int i = 0; i < n; ++i)
	num[i] = i + 1;
	while (--k)
	next_permutation(num, num + n);

pdu / leetcode_spirial_matrix_2.cpp

Created February 17, 2013 11:20

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] http://leetcode.com/onlinejudge#question_59

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

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

	class Solution {
	public:
	vector<vector<int> > generateMatrix(int n) {
	vector<vector<int> > ans;

pdu / leetcode_length_of_last_word.cpp

Created February 17, 2013 11:23

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only. For example, Given s = "Hello World", return 5. http://leetcode.com/onlinejudge#que…

	class Solution {
	public:
	int lengthOfLastWord(const char *s) {
	int ans = 0;
	int cnt = 0;
	for (int i = 0; s[i] != 0; ++i) {
	if (s[i] == ' ')
	cnt = 0;
	else {
	cnt++;

pdu / leetcode_insert_interval.cpp

Created February 17, 2013 11:44

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9…

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/

pdu / leetcode_merge_intervals.cpp

Created February 17, 2013 11:57

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. http://leetcode.com/onlinejudge#question_56

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/

pdu / leetcode_jump_game.cpp

Created February 17, 2013 12:06

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. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. http://leetcode.com/onlinejudge#questio…

	class Solution {
	public:
	bool canJump(int A[], int n) {
	int dis = 0;
	for (int i = 0; i < n; ++i) {
	if (i <= dis)
	dis = max(dis, i + A[i]);
	else
	break;
	if (dis >= n - 1)

Peng Du pdu