2014/09/01

posted in Linux相关

Shell脚本： Windows下可用源码转换为 Linux下可用源码

简介
使用方式
代码
参考：

简介

Windows下编写的代码（如C\C++\Java等）放到Linux下不能直接编译，因为主要存在两个问题：

Windows和Linux的行尾符不同， Windows下行尾符是"\n\r"，而Linux的行尾符是"\n"
Windows下编码通常是GB2312, 而Linux中的编码通常是UTF-8。

所以编写了这个脚本文件用于将Windows下编写的源码转化为Linux下可用的源码，

该脚本文件可以将指定目录及其子目录下指定后缀名的源文件进行转换。

使用方式

sudo apt-get install dos2unix
bash trans.sh 指定文件夹 要转换文件的拓展名

例如，

将/home文件夹及其子文件下所有java源文件进行转换

bash trans.sh /home java

代码

#!/bin/bash
#Program:
#   convert the text written in windows to the text usable in linux.
#Author:
#   Chen Zhongzheng
#History:
#   2014年09月03日20:17:36  v1.0
#TODO:
#   add a parameter to specify the origin encoding, eg. gb2312\cp936\gbk...

function recursion()
{
	cd $1
	for i in $(ls)
	do
		if [ -d "$i" ]; then
			recursion ``i ``2
		elif [ "``{i##*.}" = "``{2}" ]; then
			iconv -f cp936 -t utf-8 $i > temp_111
			mv temp_111 $i
			dos2unix $i
		fi
	done
	cd ..
}

if [ ! $# -eq 2 ]; then
    echo "usage: bash convert.sh directory_name extension_name"
elif [ ! -d $1 ]; then
	echo "usage: bash convert.sh directory_name extension_name"
else
	recursion ``1 ``2
fi










#!/bin/bash
#Program:
#   convert the text written in windows to the text usable in linux.
#Author:
#   Chen Zhongzheng
#History:
#   2015年12月04日21:33:29  v1.1
#TODO:
#   add a parameter to specify the origin encoding, eg. gb2312\cp936\gbk...

function recursion()
{
  cd $1
  for i in $(ls)
  do
    if [ -d "$i" ]; then
      recursion ``i ``2
    elif [ "``{i##*.}" = "``{2}" ]; then
      enca -L zh_CN -x UTF-8 $i
      dos2unix $i
    fi
  done
  cd ..
}

if [ ! $# -eq 2 ]; then
  echo "usage: bash convert.sh directory_name extension_name"
elif [ ! -d $1 ]; then
  echo "usage:  bash convert.sh directory_name extension_name"
else
  recursion ``1 ``2
fi

参考：

http://www.wenzizone.cn/?p=313

http://bbs.chinaunix.net/thread-624345-1-1.html

http://blog.csdn.net/rainharder/article/details/6030255

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

2014/08/30

posted in OJ题解

Leetcode: Binary Tree Preorder Traversal

题目
分析
代码
- 递归版
- 迭代版
参考

题目

https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

分析

第一种方法采用递归版先序遍历。
第二种方法用循环和递归实现迭代版先序遍历。

代码

递归版

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		preorder(root);

		return res;
	}
	
	void preorder(TreeNode *root)
	{
		if (!root)
			return;
			
		res.push_back(root->val);
		preorderTraversal(root->left);
		preorderTraversal(root->right);
	}
private:
	vector<int> res;
};

迭代版

class Solution
{
public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		while (true)
		{
			preorder(root);
			if (stk.empty())
				break;
			root = stk.top();
			stk.pop();
		}
		return res;
	}
	void preorder(TreeNode *root)
	{
		while (root)
		{
			res.push_back(root->val);
			if (root->right)
				stk.push(root->right);
			root = root->left;
		}
	}

private:
	vector<int> res;
	stack<TreeNode *> stk;
};

参考

《数据结构》邓俊辉

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

2014/08/29

posted in OJ题解

Leetcode: Sum Root to Leaf Numbers

题目
分析
代码

题目

https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

分析

DFS

代码

class Solution
{
public:
	int sumNumbers(TreeNode *root)
	{
		int solution = 0;

		if (!root)
			return 0;
		dfs(root, solution);

		return sum;
	}

	void dfs(TreeNode *root, int solution)
	{
		if (!root->left && !root->right)
		{
			solution = solution * 10 + root->val;
			sum += solution;
		}
		else
		{
			solution = solution * 10 + root->val;
			if (root->left)
				dfs(root->left, solution);
			if (root->right)
				dfs(root->right, solution);
		}
	}

private:
	int sum = 0;
};

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

2014/08/29

posted in OJ题解

Leetcode: Binary Tree Level Order Traversal II

题目
分析
代码

题目

https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

分析

和Binary Tree Level Order Traversal一样，只不过在最后把结果反转一下就行了。

代码

class Solution
{
public:
	vector<vector<int>> levelOrderBottom(TreeNode *root)
	{
		queue<TreeNode*> nodeQue;
		queue<int> depQue;
		TreeNode *node;
		int dep;
		int depBefore;
		vector<vector<int>> res;
		vector<int> solution;

		if (!root)
			return res;

		nodeQue.push(root);
		depQue.push(1);
		depBefore = 1;
		while (!nodeQue.empty())
		{
			node = nodeQue.front();
			nodeQue.pop();
			dep = depQue.front();
			depQue.pop();

			if (dep == depBefore)
				solution.push_back(node->val);
			else
			{
				res.push_back(solution);
				depBefore = dep;
				solution.clear();
				solution.push_back(node->val);
			}

			if (node->left)
			{
				nodeQue.push(node->left);
				depQue.push(dep + 1);
			}
			if (node->right)
			{
				nodeQue.push(node->right);
				depQue.push(dep + 1);
			}
		}
		res.push_back(solution);
		reverse(res.begin(), res.end());
		
		return res;
	}
};

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

2014/08/29

posted in OJ题解

Leetcode: Binary Tree Level Order Traversal

题目
分析
代码：

题目

https://oj.leetcode.com/submissions/detail/10496925/

分析

树的层次遍历，唯一的难点在于如何判断两个结点是否在同一层上。

可以除了nodeQue之外，再增加一个depQue, 来记录每个结点的深度。

代码：

class Solution
{
public:
	vector<vector<int>> levelOrder(TreeNode *root)
	{
		queue<TreeNode*> nodeQue;
		queue<int> depQue;
		TreeNode *node;
		int dep;
		int depBefore;
		vector<vector<int>> res;
		vector<int> solution;

		if (!root)
			return res;

		nodeQue.push(root);
		depQue.push(1);
		depBefore = 1;
		while (!nodeQue.empty())
		{
			node = nodeQue.front();
			nodeQue.pop();
			dep = depQue.front();
			depQue.pop();

			if (dep == depBefore)
				solution.push_back(node->val);
			else
			{
				res.push_back(solution);
				depBefore = dep;
				solution.clear();
				solution.push_back(node->val);
			}

			if (node->left)
			{
				nodeQue.push(node->left);
				depQue.push(dep + 1);
			}
			if (node->right)
			{
				nodeQue.push(node->right);
				depQue.push(dep + 1);
			}
		}
		res.push_back(solution);
		return res;
	}
};

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

2014/08/28

posted in OJ题解

Leetcode: Decode Ways

题目
分析
代码
参考

题目

https://oj.leetcode.com/problems/decode-ways/

分析

和Leetcode: Climbing Stairs这道题类似，都是用类似斐波那契数列的算法解决问题。只不过在递归或者迭代时加一点条件判断。
运用动态规划思想，先想出递归的算法，然后再改变成迭代的方式提高算法效率。
递归的算法：

设前n个数的decode ways是f(n)，则

若最后俩数小于26，则

f(n) = f(n-1) + f(n-2);

否则

f(n) = f(n-1);

再改造成迭代的算法：

设前n个数的decode ways是s(n)，则

若最后俩数小于26，则

s(n) = s(n-1) + s(n-2);

否则

s(n) = s(n-1);

因为“0”是一个比较特殊的数字，所以针对一些测试用例，需要对算法进行一些改进。

这些改进如果没有测试用例，感觉很难就作出来。这大概也是测试工程师的作用吧。

代码

class Solution
{
public:
	int numDecodings(string s)
	{
		if (s.empty())
			return 0;
		if (s[0] == '0')
			return 0;
		if (s.size() == 1)
			return 1;

		int a, b, c;
		a = 1;
		b = 1; 
		for (int i = 1; i < s.size(); i++)
		{
			if (s[i] == '0' && s[i-1] == '0')
				return 0;
			if (s[i] == '0' && s[i-1] > '2')
				return 0;

			if (stoi(s.substr(i-1, 2)) > 26)
				c = b;
			else if (s[i] == '0')
				c = a;
			else if (s[i-1] == '0')
				c = b;
			else
				c = a + b;

			a = b;
			b = c;
		}

		return c;
	}
};

参考

http://blog.csdn.net/worldwindjp/article/details/19938131

http://fisherlei.blogspot.com/2013/01/leetcode-decode-ways-solution.html

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

2014/08/27

posted in OJ题解

Leetcode: Word Ladder

题目：
分析：
代码：
参考：

题目：

https://oj.leetcode.com/problems/word-ladder/

分析：

求最短路径，用BFS算法。 [3]
求各个单词之间的邻接关系，不能用邻接矩阵，否则会Time Limit Exceeded。 [2]

因为并非所有单词之间的邻接关系在求解过程中都需要，只需要求解用到的一些单词的邻居即可。要是求邻接矩阵的话，会花费大量时间。

一个单词访问过了之后，直接从dict中删除即可，从而避免重复加入队列，进而导致浪费时间。[1]
关于如何记录路径长，可以再创建一个depth队列，这样que队列push时， depth队列也同时的push一个对应的路径。[1]

代码：

class Solution
{
public:
	int ladderLength(string start, string end, unordered_set<string> &dict)
	{
		dict.insert(end);
		queue<string> que;
		queue<int> depth;
		que.push(start);
		depth.push(2);
		int len;

		while (!que.empty())
		{
			string ver = que.front();
			que.pop();
			len = depth.front();
			depth.pop();

			vector<string> res;
			adjacency(ver, dict, res);
			for (auto &r : res)
			{
				if (r == end)
					return len;
				else
				{
					dict.erase(r);
					que.push(r);
					depth.push(len+1);
				}
			}
		}

		return 0;
	};

	void adjacency(const string &ver, const unordered_set<string> &dict, vector<string> &res)
	{
		for (int i = 0; i < ver.size(); i++)
		{
			string temp = ver;
			for (int j = 'a'; j <= 'z'; j++)
			{
				temp[i] = j;
				if (temp != ver && dict.find(temp) != dict.end())
					res.push_back(temp);
			}
		}

		return;
	}
};

参考：

[1] http://blog.csdn.net/lanxu_yy/article/details/17588317

[2] http://blog.csdn.net/yutianzuijin/article/details/12887747

[3] 《数据结构(C++语言版)》（第三版）邓俊辉 p169

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