2014/11/07

posted in OJ题解

LeetCode: Edit Distance

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/edit-distance/

分析

一开始没有思路，看了一些大神的解法以后才明白如何用动态规划的思路来解决这道题。

数据结构

创建一个二维数组res[][]，其中res[i][j]用来代表word1[0 : i-1]和word2[0 : j-1]的EditDistance。

递归关系

考虑word1[i] == word2[j]的情况，直接匹配即可，res[i][j] = res[i-1][j-1];

考虑word1[i] == word2[j]的情况，这种情况下分为以下多种情况来处理，然后取其中的最小值即可

A. 用replace来处理，res[i][j] = res[i-1][j-1] + 1。这个应该很好理解，比如"abc1"和"abc2"两个字符串，res["abc1"]["abc2"] = res["abc"]["abc"] + 1。

B. 用insert来处理，res[i][j] = res[i][j-1] + 1; 举个例子，还是"abc1"和"abc2"两个字符串，res["abc1"]["abc2"] = res["abc1"]["abc"] + 1;

C. 用delete来处理，res[i][j] = res[i-1][j] + 1; 举个例子，还是"abc1"和"abc2"两个字符串，res["abc1"]["abc2"] = res["abc"]["abc2"] + 1;

数据结构的初始化

因为在递归关系中用到了res[i-1][j-1]，所以数据结构中的数据必然要先初始化才行，

res[i][0] = i; 代表 ""和"abc2"的EditDistance为4

res[0][i] = i; 代表 "abc1"和""的EditDistance为4

其他

在2. 递归关系中，还少考虑了一种情况，只不过为了理解起见一开始没有说，

当res[i] == res[j]时， res[i][j] 有时不能直接等于res[i-1][j-1]，因为有可能用insert/delete处理的EditDistance比直接匹配的EditDistance更小，

所以res[i][j] = min(直接匹配，insert处理， delete处理)，即 res[i][j] = min(res[i-1][j-1], res[i-1][j] + 1, res[i][j-1] + 1);

代码

class Solution
{
public:
	int minDistance(string word1, string word2)
	{
		int m = word1.size();
		int n = word2.size();
		vector<vector<int>> res(m + 1, vector<int>(n + 1));

		for (int i = 0; i <= m; i++)
			res[i][0] = i;
		for (int i = 0; i <= n; i++)
			res[0][i] = i;

		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
			{
				res[i][j] = min(res[i-1][j] + 1, res[i][j-1] + 1);
				if (word1[i-1] == word2[j-1])
					res[i][j] = min(res[i][j], res[i-1][j-1]);
				else
					res[i][j] = min(res[i-1][j-1] + 1, res[i][j]);
		}

		return res[m][n];
	}
};

参考

http://yucoding.blogspot.com/2013/09/leetcode-question-29-edit-distance.html

http://fisherlei.blogspot.com/2012/12/leetcode-edit-distance.html

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

2014/11/06

posted in OJ题解

LeetCode: Minimum Path Sum

题目
分析
代码

题目

https://oj.leetcode.com/problems/minimum-path-sum/

分析

动态规划题，

某一点的MinimumPathSum = min(左侧点的MinimumPathSum, 上侧点的MinimumPathSum) + 该点的数值

不过第一行和第一列的MinimumPathSum有些特殊，需要单独处理一下。

代码

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

		//First row and first col 's Minimum Path Sum
		for (int i = 1; i < m; i++)
			res[i][0] += res[i-1][0];
		for (int i = 1; i < n; i++)
			res[0][i] += res[0][i-1];

		//Other points's Minimum Path Sum
		for (int i = 1; i < m; i++)
			for (int j = 1; j < n; j++)
				res[i][j] += min(res[i-1][j], res[i][j-1]);

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

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

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/11/01

posted in C/C++

关于C++构造析构顺序的总结

起因
代码
输出
分析
结论

起因

之前对C++基类派生类构造函数和析构函数的调用顺序存在疑惑，因此写了个小程序验证一下。

代码

#include <iostream>
using namespace std;

class Base
{
public:
	Base()
	{
		cout << "Base::Base()" << endl;
	}

	~Base()				//case3
//	virtual ~Base()		//case4
	{
		cout << "Base::~Base()" << endl;
	}
};

class Derived : public Base
{
public:
	Derived()
	{
		cout << "Derived::Derived()" << endl;
	}
	~Derived()
	{
		cout << "Derived::~Derived()" << endl;
	}
};

int main()
{
	cout << "------case1: Base Object------------------------------" << endl;
	Base *p = new Base();
	delete p;

	cout << "\n\n";
	cout << "------case2: Derived Object---------------------------" << endl;
	Derived *p3 = new Derived();
	delete p3;

	cout << "\n\n";
	cout << "------case3/case4: Base pointer to Derived Object-----" << endl;
	cout << "------(not virtual function/virtual function)---------" << endl;
	Base *p2 = new Derived();
	delete p2;

	return 0;
}

输出

------case1: Base Object------------------------------
Base::Base()
Base::~Base()


------case2: Derived Object---------------------------
Base::Base()
Derived::Derived()
Derived::~Derived()
Base::~Base()


------case3: Base pointer to Derived Object-----
------(not virtual function)---------
Base::Base()
Derived::Derived()
Base::~Base()


------case4: Base pointer to Derived Object-----
------(virtual function)---------
Base::Base()
Derived::Derived()
Derived::~Derived()
Base::~Base()

分析

由case1可知，
基类对象在创建的时候会自动调用构造函数；
销毁时会自动调用析构函数。
由case2可知，
普通派生类对象在创建时会先自动调用基类构造函数，然后调用自身构造函数；
销毁时会先自动调用自身的析构函数，然后调用基类的析构函数。
由case3/case4可知，
基类指针指向的派生类对象在创建时先自动调用基类构造函数，然后调用自身构造函数；
销毁时先判断，
如果析构函数不是虚函数，则当做基类对象析构————自动调用基类析构函数，
如果析构函数是虚函数，则当做派生类对象————先自动调用派生类析构函数，然后调用基类构造函数。

结论

综上，派生类对象构造析构的过程是这样的：

创建对象时，调用的构造函数只跟创建的对象类型有关，
判断对象类型，
  如果是基类对象，自动调用自身构造函数
  如果是派生类对象，先自动调用基类构造函数，然后调用自身构造函数。

销毁对象时，调用的析构函数跟析构函数是否是虚函数、指向它的指针类型和析构的对象类型有关
判断构造函数是否是为虚函数
  如果构造函数不是虚函数，按照指针类型（静态类型）析构
      如果指针类型是基类类型
      如果指针类型是派生类类型
  如果构造函数是虚函数，按照对象类型（动态类型）析构
      如果析构对象是基类类型
      如果析构对象是派生类类型

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