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

2014/10/26

posted in Linux相关

配置GDB支持STL调试

环境
步骤
使用效果
参考

原生GDB不能支持STL调试，要进行STL调试必须进行一些配置才行，但网上的一些配置说明已经过时了，因此重新总结一下。

环境

Ubuntu 14.04 32位

GDB 7.7

步骤

Check-out最新的调试工具到本地一个文件夹下，比如 ~/yourname/gdb_printers

svn co svn://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/python
将下列内容添加到 ~/.gdbinit 文件夹中，其中的路径名改成上一步Check-out的工具对应的路径名

python
import sys
sys.path.insert(0, '/home/yourname/gdb_printers/python')
sys.path.append("/home/yourname/gdb_printers/python/libstdcxx/v6")
from libstdcxx.v6.printers import register_libstdcxx_printers
end

使用效果

如果代码是这样的：

vector a = {2, 3, 6, 7};

调试效果是这样的：

(gdb) p a
$1 = std::vector of length 4, capacity 4 = {2, 3, 6, 7}

参考

http://sourceware.org/gdb/wiki/STLSupport

http://stackoverflow.com/questions/26205564/gdb-pretty-printing-importerror-no-module-named-printers

http://blog.csdn.net/fdl19881/article/details/8710636

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

2014/10/26

posted in OJ题解

LeetCode: Search for a Range

题目
分析
代码

题目

https://oj.leetcode.com/problems/search-for-a-range/

分析

时间复杂度O(log n)，多半便是二分查找的题目。

题目要求找出一个范围，无非就是找到一个起始点和一个终止点，通过两次二分查找找到起始点和终止点即可。

起始点的特点是，等于target，而且它左侧没有target了或者它是数组第一个数。

终止点的特点是，等于target，而且它右侧没有target了或者它是数组最后一个数。

P.S. 标准二分查找代码可以查看这里。

代码

class Solution
{
public:
	vector<int> searchRange(int A[], int n, int target)
	{
		vector<int> res;
		int l, r, m;

		l = 0;
		r = n - 1;
		while (l <= r)
		{
			m = (l + r) >> 1;
			if ((A[m]==target) && (m==0 || A[m-1]!=target))
			{
				res.push_back(m);
				break;
			}
			else if (A[m] > target || A[m-1] == target)
				r = m - 1;
			else
				l = m + 1;
		}
		if (res.size() == 0)
		{
			res.push_back(-1);
			res.push_back(-1);
			return res;
		}

		l = 0;
		r = n - 1;
		while (l <= r)
		{
			m = (l + r) >> 1;
			if ((A[m]==target) && (m==n-1 || A[m+1]!=target))
			{
				res.push_back(m);
				break;
			}
			else if (A[m] < target || A[m+1] == target)
				l = m + 1;
			else 
				r = m - 1;
		}
		return res;
	}
};

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

2014/10/26

posted in 数据结构与算法

标准二分查找代码

代码
参考

二分查找算法在各种场合下经常会用到，在此总结一下它的标准代码。

代码

int binary_search(int array[], int n, int value)
{
	int left = 0;
	int right = n - 1;

	while (left <= right)
	{
		int mid = (left + right) >> 1;

		if (array[mid] < value)
			left = mid + 1;
		else if (array[mid] > value)
			right = mid + 1;
		else
			return mid;
	}

	return -1;
}