2014/11/06

posted in OJ题解

LeetCode: Unique Paths II

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/unique-paths-ii/

分析

这道题是Unique Paths的变形，只是稍微复杂了一点。

在Unique Paths中， paths[i][j] = paths[i-1][j] + paths[i][j-1];

在Unique Paths II中，在这句之前要加一个判断语句来判断obstacleGrid[i][j]的值是否为1，如果是1则将paths[i][j]直接赋值为0

仅仅做完第一步还不行，原本第一行都为1，

现在如果第一行某个元素是obstacle，那么这一行该元素及其之后的元素路径数都为0，为什么呢？

因为要想如Unique Paths中所说路径长度达到最小，那么第一行obstacle之后的元素必然不能走。

第一列也是同样的道理。

代码

class Solution
{
public:
	int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
	{
		int m = obstacleGrid.size();
		int n = obstacleGrid[0].size();
		vector<vector<int>> paths(m, vector<int>(n, 1));

		int firstRowFirstObstacle = -1;
		int firstColFirstObstacle = -1;
		//get first obstacle position in first col and first row 
		for (int i = 0; i < m; i++)
			if (obstacleGrid[i][0] == 1)
			{
				firstColFirstObstacle = i;
				break;
			}
		for (int i = 0; i < n; i++)
			if (obstacleGrid[0][i] == 1)
			{
				firstRowFirstObstacle = i;
				break;
			}

		//assign 0 where firstObstacle and after that in first row and col
		if (firstColFirstObstacle != -1)
			for (int i = firstColFirstObstacle; i < m; i++)
				paths[i][0] = 0;
		if (firstRowFirstObstacle != -1)
			for (int i = firstRowFirstObstacle; i < n; i++)
				paths[0][i] = 0;

		//calculate paths
		for (int i = 1; i < m; i++)
		{
			for (int j = 1; j < n; j++)
			{
				if (obstacleGrid[i][j] == 1)
				{
					paths[i][j] = 0;
					continue;
				}
				paths[i][j] = paths[i-1][j] + paths[i][j-1];
			}
		}

		return paths[m-1][n-1];
	}
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40865761

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

2014/11/06

posted in OJ题解

LeetCode: Unique Paths

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/unique-paths/

分析

一开始没弄懂题意，存在一些问题：能不能走重复的路径？路径长度是否要求为最短的？

后来看了一些答案才明白，题目的隐含要求是，在走最短的路径的前提下，求不同路径数目。

这样一来题目就简单了，某一点的不同路径数 = 左侧点的不同路径数 + 上侧点的不同路径数

可以用递归来求解，但这样效率底下，需要动态规划的方法来解决。

代码

class Solution
{
public:
	int uniquePaths(int m, int n)
	{
		vector<vector<int>> paths(m, vector<int>(n, 1));

		for (int i = 1; i < m; i++)
			for (int j = 1; j < n; j++)
				paths[i][j] = paths[i-1][j] + paths[i][j-1];

		return paths[m-1][n-1];
	}
};

参考

http://blog.csdn.net/kenden23/article/details/17303497

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

2014/11/02

posted in OJ题解

LeetCode: N-Queens II

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/n-queens-ii/

分析

跟N-Queens这道题解法一样，略作修改即可。

代码

class Solution
{
public:
	int totalNQueens(int n)
	{
		vector<int> solution(n);
		helper(solution, 0, n);

		return res;
	}
	void helper(vector<int> &solution, int row, int n)
	{
		if (row == n)
			res++;
		else
		{
			for (int i = 0; i < n; i++)
			{
				if (isValid(solution, row, i))
				{
					solution[row] = i;
					helper(solution, row + 1, n);
				}
			}
		}
	}
	bool isValid(vector<int> &solution, int row, int col)
	{
		for (int i = 0; i < row; i ++)
			if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
				return false;
		return true;
	}
	
private:
	int res = 0;
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40686105

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

2014/11/02

posted in OJ题解

LeetCode: N-Queens

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/n-queens/

分析

这道题采用的是回溯法，跟DFS非常类似，只不过是在DFS的递归前加一个判断。
关于如何表示结果。

可以采用一个N*N二维数组来存放结果，但是我们可以采用更好的办法：经过观察我们可以发现，每一行必然有一个皇后，因此我们可以用一个一维数组来表示结果，solution[0]=3 代表第0行的皇后放在第三列， solution[1]=5 代表第1行的皇后放在第5列，……以此类推。

关于如何判断一种结果是否合法。

题目要求任意两个皇后不能在同一行、同一列或者用一斜线上，在2中我们已经提过了用一维数组solution[n]来表示结果，任两个皇后肯定不在同一行，判断第i行和第j行的皇后是否同一列可以用 solution[i] == solution[j]来判断；如何判断第i行皇后和第j行皇后是否在同一斜线上呢？可以用 abs(i-j) == abs(solution[i] - solution[j]) 来判断。

代码

class Solution
{
public:
	vector<vector<string>> solveNQueens(int n)
	{
		vector<int> solution(n);
		helper(solution, 0, n);

		return res;
	}

	void helper(vector<int>& solution, int row, int n)
	{
		if (row == n)
		{
			vector<string> solution_2d(n, string(n, '.'));
			for (int i = 0; i < n; i++)
				solution_2d[i][solution[i]] = 'Q';

			res.push_back(solution_2d);
		}
		else
		{
			for (int i = 0; i < n; i++)
			{
				if (isValid(solution, row, i))
				{
					solution[row] = i;
					helper(solution, row + 1, n);
				}
			}
		}
	}

	bool isValid(vector<int>& solution, int row, int col)
	{
		for (int i = 0; i < row; i++)
			if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
				return false;
		return true;
	}

private:
	vector<vector<string>> res;
};

参考

http://www.cnblogs.com/TenosDoIt/p/3801621.html

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

2014/10/30

posted in OJ题解

LeetCode: Multiply Strings

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/multiply-strings/

分析

大数乘法，不能直接相乘，因为会溢出。

首先两个乘数的各位之间两两相乘，得到多个同一列结果相加，

然后对结果进行进位。

如 25 × 25 = 625

2 5

× 2 5

————————————————————

10 25

4 10

————————————————————

4 20 25

————————————————————

6 2 5

代码

class Solution
{
public:
	string multiply(string num1, string num2)
	{
		vector<int> temp_res(num1.size() + num2.size(), 0);
		reverse(num1.begin(), num1.end());
		reverse(num2.begin(), num2.end());

		for (int i = 0; i < num1.size(); i++)
			for (int j = 0; j < num2.size(); j++)
				temp_res[i + j] += (num1[i]-'0') * (num2[j]-'0');

		int carry = 0;
		for (int i = 0; i < temp_res.size(); i++)
		{
			int temp = temp_res[i] + carry;
			temp_res[i] = temp % 10;
			carry = temp / 10;
		}

		for (int i = temp_res.size() - 1; i >= 0; i--)
		{
			if (temp_res[i] != 0)
				break;
			temp_res.pop_back();
		} 
		reverse(temp_res.begin(), temp_res.end());
		string res;
		for (int i = 0; i < temp_res.size(); i++)
			res += temp_res[i] + '0';

		return res.size() != 0 ? res : string("0");
	}
};

参考

http://www.cnblogs.com/TenosDoIt/p/3735309.html

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

2014/10/27

posted in OJ题解

LeetCode: Combination Sum II

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/combination-sum-ii/

分析

这道题是Combination Sum的变形，也是采用DFS的思路，但相比之下要注意两点：

因为不能重复，所以在进进行DFS递归时，要直接从当前位置的下一个位置开始进行“试探”。
若num中存在两个相同的元素，为了防止结果中重复出现，只有在第一个元素被选中的情况下，第二个元素才进行“试探”，否则不进行“试探”。

代码

class Solution
{
public:
	vector<vector<int>> combinationSum2(vector<int> &num, int target)
	{
		vector<int> solution;
		this->num = num;
		sort(this->num.begin(), this->num.end());

		DFS(solution, target, 0);

		return res;
	}

	void DFS(vector<int> &solution, int target, int start)
	{
		if (target == 0)
		{
			res.push_back(solution);
		}
		else
		{
			for (int i = start; i < num.size() && num[i] <= target; i++)
			{
				if (i > 0 && num[i] == num[i-1] && num[i-1] != solution.back())
					continue;
				solution.push_back(num[i]);
				DFS(solution, target - num[i], i + 1);
				solution.pop_back();
			}
		}
	}

private:
	vector<int> num;
	vector<vector<int>> res;
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40479161

http://www.cnblogs.com/remlostime/archive/2012/10/29/2745125.html

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

2014/10/26

posted in OJ题解

LeetCode: Combination Sum

题目
分析
代码

题目

https://oj.leetcode.com/problems/combination-sum/

分析

DFS，之前总结过很多道同类型的题。

代码

class Solution
{
public:
	vector<vector<int>> combinationSum(vector<int> &candidates, int target)
	{
		if (candidates.size() == 0)
			return res;
		this->candidates = candidates;
		sort(this->candidates.begin(), this->candidates.end());
		vector<int> solution;

		DFS(solution, 0, target);

		return res;
	}
	void DFS(vector<int> &solution, int start, int target)
	{
		if (target == 0)
			res.push_back(solution);
		else
		{
			for (int i = start; i < candidates.size() && candidates[i] <= target; i++)
			{
				solution.push_back(candidates[i]);
				DFS(solution, i, target-candidates[i]);
				solution.pop_back();
			}
		}
	}
private:
	vector<int> candidates;
	vector<vector<int>> res;
};

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