Posted on | In

为什么不推荐递归

递归的调试难度奇高，就决定了实际项目中很少用递归。

而且递归确实运行效率低，因为函数一层一层调用存在调用栈，

在切换到更深层的函数时要产生断点，为了保证回来时继续运行，

必须保存现在所处函数的各种状态，回来时恢复状态，这样一层层下去性能损失就不断增加。

大量开辟在栈区的内存 ，直到每一层的递归结束或整个递归结束才释放 且这个内存空间可能呈几何级数增加， 空间效率不佳， 有可能会栈溢出

而要知道什么是尾递归， 首先得指到什么是尾调用

. . .

Posted on | In

只谈一下单链表, 链表实在是太重要, 是前面两篇说算法博客的基础, 了解了其应用和衍生, 再去了解其本身就有动力了

存储结构

1
2
3
4
5
typedef struct Node
{
	DataType data;
	struct Node *next;
}Node, *Node_Ptr;
  • 链表中第一个结点的存储位置叫做头指针
  • 头指针和头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。链表中可以没有头结点，但不能没有头指针。
  • 如果链表有头结点，那么头指针就是指向头结点数据域的指针。
  • 单链表也可以没有头结点

头结点的优点:

  • 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
  • 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。

有头结点和无头结点的建立链表方法头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Link {
    int  elem;
    struct Link *next;
}link;
//无头结点链表的头插法实现函数
link * creatLink(int * arc, int length) {
    int i;
    //最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 H
    link * H =(link*)malloc(sizeof(link));
    H->elem = arc[0];
    H->next = NULL;
    //如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前
    for (i = 1; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //插入元素时，首先将插入位置后的链表链接到新结点上
        a->next = H;
        //然后再链接头指针 H
        H = a;
    }
    return H;
}
//有头结点链表的头插法实现函数
link * HcreatLink(int * arc, int length) {
    int i;
    //创建头结点 H，其链表的头指针也是 H
    link * H = (link*)malloc(sizeof(link));
    H->elem = 0;
    H->next = NULL;
    //采用头插法创建链表
    for (i = 0; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //首先将插入位置之后的链表链接到新结点 a 上
        a->next = H->next;
        //将新结点 a 插入到头结点之后的位置
        H->next = a;
    }
    return H;
}
//链表的输出函数
void display(link *p) {
    while (p) {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
int main() {
    int a[3] = { 1,2,3 };
    //采用头插法创建无头结点链表
    link * H = creatLink(a, 3);
    display(H);
    //采用头插法创建有头结点链表
    link * head = HcreatLink(a, 3);
    display(head);
    //使用完毕后，释放即可
    free(H);
    free(head);
    return 0;
}

运行结果：

1
2
3 2 1
0 3 2 1

提示：没有 0 的为无头结点的头插法输出结果，有 0 的为有头结点的头插法的输出结果

. . .

Posted on | In

前言

使用SVN在管理代码的时候免不了进行代码的合并和还原，特别是当前版本的修改发现有重大问题的时候，还原是避免不了的，那么究竟应该怎样操作呢？

内容

使用SVN查看文件或目录的日志的时候，右键单击日志记录会弹出下面这个界面，今天我们来着重了解一下被红圈标记的三个选项——“Update item to this version”，“Revert to this version”，“Revert changes from this version”，这三个选项对于刚接触SVN的人确实不太好区分，一开始我也搞不懂，直到亲自试验一下才搞清楚这三个选项的用法。

在讲解这三个选项的作用之前，我们还是先来假定一个使用情景，假设我们的项目文件一共有8个版本，它版本号分别是1，2，3，4，5，6，7，8。

Update item to this version

这个选项的作用是将文件版本更新到对应所选的版本（当然内容也修改到了相应的版本）。如果我们是在版本4这里点击“Update item to this version”，表示5~8版本所作的修改全部作废，这个文件的历史回退到了版本4那个时代，但是需要注意的是，此时文件的版本是4，并不是最新的。我们知道SVN工具中如果文件不是最新版本就无法上传，所以说这个功能只是用来暂时还原一下版本，来查询某个问题的，不能将还原后的文件上传。这个特别是当你服务器启动不了了, 把版本退回一个可以启动版本的情况

Revert to this version

这个选项的作用是将文件的内容更新到对应的版本，版本号没有发生变化。如果我们是在版本4这里点击“Revert to this version”，表示5~8版本所作的修改全部被还原，此时svn里会有5-8被还原的文件改动可以提交, 此时文件和版本4的文件一模一样，但需要注意的是这项操作相当于我们把版本4这个文件拷贝了一份赋值给了当前目录下的文件，此时的文件版本还是8，并且是可以提交的，提交以后文件的版本变成了9，增加了一个新的版本，虽然这个版本和版本4的内容是一样的。

Revert changes from this version

这个选项的作用是将对应版本的修改还原，文件的版本号不发生变化，相当于在当前本版本上剔除某些版本所作的改变。如果我们是在版本4这里点击“Revert changes from this version”，表示版本4所作的修改被抹杀了，只剩下除版本4以外的7个修改了，但是此时文件是可以上传的，并且会生成新的版本9，只是版本9只包括除版本4以外的7次修改。这个选项是可以选择多个版本的，如果我们选择4,5,6,7这四个版本点击“Revert changes from this revision”，那么这几次修改都会被抹杀。如果我们选择5,6,7,8这四个版本点击“Revert changes from this revision”，表示取消这几个版本的修改，实际上和在版本4这里点击“Revert to this version”的作用是一样的。

Posted on | In

考察cpp的静态绑定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18


struct MMPA{
	int value() const { return this->v_; }
	int tvalue() const { return 1; }
public:
	int v_;
};

int main(int argc, char* argv[]){
	{
		const MMPA* p = nullptr;
// 		std::cout << p->v_ << std::endl;
		std::cout << p->tvalue() << std::endl;
		std::cout << p->value() << std::endl;
		getchar(); return 0;
	}
}

会打印什么?

答案以及分析

答案: 打印1之后崩溃

真正的原因是：

因为对于非虚成员函数，Ｃ++这门语言是静态绑定的。这也是Ｃ++语言和其它语言Java, Python的一个显著区别。以此下面的语句为例：somenull->foo();这语句的意图是：调用对象somenull的foo成员函数。如果这句话在Java或Python等动态绑定的语言之中，编译器生成的代码大概是：找到somenull的foo成员函数，调用它。

（注意，这里的找到是程序运行的时候才找的，这也是所谓动态绑定的含义：运行时才绑定这个函数名与其对应的实际代码。有些地方也称这种机制为迟绑定，晚绑定。）但是对于C++。为了保证程序的运行时效率，Ｃ++的设计者认为凡是编译时能确定的事情，就不要拖到运行时再查找了。

所以C++的编译器看到这句话会这么干：

  1. 查找somenull的类型，发现它有一个非虚的成员函数叫foo。（编译器干的）
  2. 找到了，在这里生成一个函数调用，直接调B::foo(somenull)。

所以到了运行时，由于foo()函数里面并没有任何需要解引用somenull指针的代码，所以真实情况下也不会引发segment fault。这里对成员函数的解析，和查找其对应的代码的工作都是在编译阶段完成而非运行时完成的，这就是所谓的静态绑定，也叫早绑定。正确理解C++的静态绑定可以理解一些特殊情况下C++的行为。

求最大公约数

求 a 和 b 的最大公约数
辗转相除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int measure(int a, int b)
{
	int product = a * b;
	if (a == 0 || b == 0)
	{
		return -1;
	}
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}
	while (int mod = a % b)
	{
		a = b;
		b = mod;
	}
	//return b; // 最大公约数
	return product / b; // 记住这个公式： a*b=最小公倍数*最大公约数
}

棋盘/格子问题

在如下7*5的棋盘中，请计算从A移动到B一共有多少走法？要求每次只能向上或向右移动一格，并且不能经过P。(答案为492)

给定一个M*N的格子或棋盘，从左下角走到右上角的走法总数（每次只能向右或向上移动一个方格边长的距离）

运用动态规划来解答 :
我们可以把棋盘的左下角看做二维坐标的原点(0,0)，把棋盘的右上角看做二维坐标(M,N)(坐标系的单位长度为小方格的变长)
用f(i,j)表示移动到坐标f(i,j)的走法总数，其中0=<i,j<=n，设f(m,n)代表从坐标（0,0）到坐标（m,n）的移动方法，则
f(m,n)=f(m-1,n)+f(m,n-1).
于是状态f(i,j)的状态转移方程为： 

f(i,j)=f(i-1,j)+f(i,j-1)   if i,j>0
f(i,j)=f(i,j-1)            if i=0
f(i,j)=f(i-1,j)            if j=0

初始情况就为：f(0,0)=0, f(0,1)=1, f(1,0)=1，这个问题可以在时间O(n^2)，空间O(n^2)内求解，非递归解.

所以答案为 492 = 

1
SumWaysOfMoveOnChessBoard(7, 5) - SumWaysOfMoveOnChessBoard(3, 3) * SumWaysOfMoveOnChessBoard(7 - 3, 5 - 3)

递归解

1
2
3
4
5
6
7
8
int SumWaysOfMoveOnChessBoard_Recursion(int m, int n) 
{
    if (m == 0 && n == 0)
        return 0;
    if (m==0 || n==0)
        return 1;
    return SumWaysOfMoveOnChessBoard_Recursion(m, n - 1) + SumWaysOfMoveOnChessBoard_Recursion(m - 1, n);
}

非递归解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int SumWaysOfMoveOnChessBoard_NonRecursion_RawArray(int m, int n)
{
	if (m == 0 || n == 0)
		return 1;
	if (m == 0 && n == 0)
		return 0;

	int xSize = m + 1;
	int ySize = n + 1;

	int** arr = new int*[xSize];
	for (int i = 0; i < xSize; ++i)
		arr[i] = new int[ySize];

	arr[0][0] = 0;
	for (int i = 0; i < xSize; ++i) arr[i][0] = 1;
	for (int i = 0; i < ySize; ++i) arr[0][i] = 1;
	for (int i = 1; i < xSize; ++i)
		for (int j = 1; j < ySize; ++j)
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1];

	for (int i = 0; i < xSize; ++i)
		delete[] arr[i];
	delete[] arr;

	return arr[m][n];
}

int SumWaysOfMoveOnChessBoard_NonRecursion_STL(int m, int n)
{
	if (m == 0 && n == 0)
		return 0;

	int xSize = m + 1;
	int ySize = n + 1;

	std::vector< vector<int> > ChessBoardArray(xSize, vector<int>(ySize));;
	ChessBoardArray[0][0] = 0;
	for (int i = 0; i < xSize; ++i) ChessBoardArray[i][0] = 1;
	for (int j = 0; j < ySize; ++j) ChessBoardArray[0][j] = 1;
	for (int i = 1; i < xSize; ++i)
		for (int j = 1; j < ySize; ++j)
			ChessBoardArray[i][j] = ChessBoardArray[i][j - 1] + ChessBoardArray[i - 1][j];

	return ChessBoardArray[m][n];
}

大数加法/乘法

大数加法思路 :
模拟小学列竖式

        9  8
+       2  1
-------------
    (1)(1)(9)

大数乘法思路 :

模拟乘法累加 - 改进
简单来说，方法二就是先不算任何的进位，也就是说，将每一位相乘，相加的结果保存到同一个位置，到最后才计算进位。

例如：计算98×21,步骤如下

        9  8
×       2  1
-------------
       (9)(8)   <---- 第1趟: 98×1的每一位结果 
   (18)(16)     <---- 第2趟: 98×2的每一位结果 
-------------
   (18)(25)(8)  <---- 这里就是相对位的和，还没有累加进位

这里唯一要注意的便是进位问题，我们可以先不考虑进位，当所有位对应相加，产生结果之后，再考虑。
从右向左依次累加，如果该位的数字大于10，那么我们用取余运算，在该位上只保留取余后的个位数，而将十位数进位（通过模运算得到）累加到高位便可，循环直到累加完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
void BigIntAddition(char* bigIntA, char* bigIntB)
{
	if (!bigIntA || !bigIntB)
		return;

	size_t strlenA = strlen(bigIntA);
	size_t strlenB = strlen(bigIntB);
	size_t biggerStrlen = strlenA > strlenB ? strlenA : strlenB;

	int* reversedA = new int[biggerStrlen];
	int* reversedB = new int[biggerStrlen];
	// 先将例子中的 1234 和 98765 逆序存储, 不够的补零, 方便计算
	for (size_t i = 0; i < biggerStrlen; ++i)
	{
		//cout << int(strlenA - 1 - i) << endl;
		reversedA[i] = (int(strlenA - 1 - i) >= 0) ? (bigIntA[strlenA - 1 - i] - '0') : 0;
		reversedB[i] = (int(strlenB - 1 - i) >= 0) ? (bigIntB[strlenB - 1 - i] - '0') : 0;
	}

	for (size_t i = 0; i < biggerStrlen; ++i)
		cout << reversedA[i];
	cout << endl; // --> 43210

	for (size_t i = 0; i < biggerStrlen; ++i)
		cout << reversedB[i];
	cout << endl; // --> 98765

	int* bigIntSum = new int[biggerStrlen + 1];
	int x = 0; // 进位
						 // 模拟小学的列竖式加法, 满10进1
	for (size_t i = 0; i < biggerStrlen; ++i)
	{
		bigIntSum[i] = reversedA[i] + reversedB[i] + x;
		x = bigIntSum[i] / 10;
		bigIntSum[i] %= 10;
	}
	size_t printLen = biggerStrlen;
	// 查看最后一个进位是否 > 0, 大于零则最高位为1
	if (x > 0)
	{
		bigIntSum[biggerStrlen] = x;
		printLen = biggerStrlen + 1;
	}
	for (size_t i = 0; i < printLen; ++i)
		cout << bigIntSum[printLen - 1 - i]; // --> 58023
	cout << endl;

	delete[] bigIntSum;
}

void BigIntMultiplication(char* bigIntA, char* bigIntB)
{
	if (!bigIntA || !bigIntB)
		return;

	int strlenA = static_cast<int>(strlen(bigIntA));
	int strlenB = static_cast<int>(strlen(bigIntB));
	cout << strlenA << ", " << strlenB << endl;
	int biggerStrlen = strlenA > strlenB ? strlenA : strlenB;

	int* reversedA = new int[biggerStrlen];
	int* reversedB = new int[biggerStrlen];
	// 先将例子中的 1234 和 98765 逆序存储, 不够的补零, 方便计算
	for (int i = 0; i < biggerStrlen; ++i)
	{
		reversedA[i] = (int(strlenA - 1 - i) >= 0) ? (bigIntA[strlenA - 1 - i] - '0') : 0;
		reversedB[i] = (int(strlenB - 1 - i) >= 0) ? (bigIntB[strlenB - 1 - i] - '0') : 0;
	}

	for (int i = 0; i < biggerStrlen; ++i)
		cout << reversedA[i];
	cout << endl; // --> 43210

	for (int i = 0; i < biggerStrlen; ++i)
		cout << reversedB[i];
	cout << endl; // --> 98765

	// 分配一个空间，用来存储运算的结果，num1长的数 * num2长的数，
	// 结果不会超过num1+num2长
	int* bigIntProduct = new int[strlenA + strlenB];
	// 比如防止下面执行 bigIntSum[i + j] += reversedA[i] * reversedB[j]; 这句的时候
	// i+j = 0 时 出错, 因为 bigIntSum[0] 为一个未初始化的值
	for (int i = 0; i < strlenA + strlenB; ++i)
		bigIntProduct[i] = 0;
	int carry = 0; // 进位

	// 先不考虑进位问题，根据竖式的乘法运算，
	// num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上
	for (int i = 0; i < strlenA; ++i)
		for (int j = 0; j < strlenB; ++j)
			bigIntProduct[i + j] += reversedA[i] * reversedB[j];

	for (int i = 0; i < strlenA + strlenB; ++i)
		cout << bigIntProduct[i] << ", "; // --> 3659707060341650
	cout << endl;

	//单独处理进位
	for (int i = 0; i < strlenA + strlenB - 1; ++i)
	{
		bigIntProduct[i] += carry;
		carry = bigIntProduct[i] / 10;
		bigIntProduct[i] %= 10;
	}

	for (int i = 0; i < strlenA + strlenB; ++i)
		cout << bigIntProduct[i] << ", "; // --> 626770070
	cout << endl;

	int printLen = strlenA + strlenB - 1;
	// 查看最后一个进位是否 > 0, 大于零则最高位为1
	if (carry > 0)
	{
		bigIntProduct[strlenA + strlenB - 1] = carry;
		printLen = strlenA + strlenB;
	}
	for (int i = 0; i < printLen; ++i)
		cout << bigIntProduct[printLen - 1 - i]; // --> 70077626
	cout << endl;
	delete[] bigIntProduct;
}

int main()
{
	char *bigIntA = "1234";
	char *bigIntB = "56789";
	BigIntAddition(bigIntA, bigIntB);
	BigIntMultiplication(bigIntA, bigIntB);
	return 0;
}

最长公共子串

问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。

比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。

算法思路：

1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。

针对于上面的两个字符串我们可以得到的二维矩阵如下：

从上图可以看到，str和str2共有5个公共子串，但最长的公共子串长度为5。

为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，
即某个二维矩阵元素的值由 item[i][j]=1 演变为 item[i][j]=1 +item[i-1][j-1] ，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：

故状态转移方程

X[i] == Y[j]，dp[i][j] = dp[i-1][j-1] + 1
X[i] != Y[j]，dp[i][j] = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int LongestCommonSubstring(char* strA, char* strB)
{
	if (!strA || !strB)
		return -1;

	int maxLen = 0;

	int strlenA = static_cast<int>(strlen(strA));
	int strlenB = static_cast<int>(strlen(strB));

	int biggerStrlen = strlenA > strlenB ? (strlenA + 1) : (strlenB + 1);
	char * lcs = new char[biggerStrlen];
	int lcsMaxIndex = 0;

	int** temp = new int*[strlenA];
	for (int i = 0; i < strlenA; ++i)
		temp[i] = new int[strlenB];

	for (int i = 0; i < strlenA; ++i)
	{
		for (int j = 0; j < strlenB; ++j)
		{
			if (strA[i] == strB[j])
			{
				if (i > 0 && j > 0)
					temp[i][j] = temp[i - 1][j - 1] + 1;
				else
					temp[i][j] = 1;
			}
			else
			{
				temp[i][j] = 0;
			}
			if (temp[i][j] > maxLen)
			{
				maxLen = temp[i][j];
				lcsMaxIndex = i;
			}
		}
	}

	for (int i = 0;i < maxLen; ++i)
		*(lcs + maxLen - i - 1) = strA[lcsMaxIndex--];
	*(lcs+maxLen) = '\0';
	cout << lcs << endl;

	for (int i = 0; i < strlenA; ++i)
		delete[] temp[i];
	delete[] temp;

	delete[] lcs;

	return maxLen;
}

int main()
{
	cout << "maxLen = " <<
		LongestCommonSubstring("wwwadfabcdeasdf", "wwweoruqpeorqabcdezcvnz") << endl;
	return 0;
}

Posted on | In

队列和双端队列的比较

队列(queue)是一种是相对于栈的一种数据结构，它是先进先出(First In First Out)。
它只可以在尾部添加元素。

双端队列(deque double ended queue（双端队列）)是一种相对于队列的一种数据结构。它可以在尾部和头部插入、移除和获取。

三者成员函数的比较

通过他们各自的成员函数我们能一目了然的看出区别

栈的成员函数

  • stack<Type> s : 定义一个stack的变量
  • s.push(x) : 入栈，如例
  • s.pop() : 出栈，如例 . 注意，出栈操作只是删除栈顶元素，并不返回该元素。
  • s.top() : 访问栈顶，如例
  • s.empty() : 判断栈空，如例，当栈空时，返回true。
  • s.size() : 访问栈中的元素个数，如例

队列的成员函数

  • queue<Type> M : 定义一个queue的变量
  • M.empty() : 查看是否为空范例 是的话返回1，不是返回0;
  • M.push() : 从已有元素后面增加元素
  • M.size() : 输出现有元素的个数
  • M.front() : 显示第一个元素
  • M.back() : 显示最后一个元素
  • M.pop() : 清除第一个元素

双端队列的成员函数

  • deque<Type> c : 定义一个deque的变量
  • c.pop_back() : 删除最后一个数据。
  • c.pop_front() : 删除头部数据。
  • c.push_back(elem) : 在尾部加入一个数据。
  • c.push_front(elem) : 在头部插入一个数据。
  • c.clear() : 移除容器中所有数据。
  • c.front() : 传回地一个数据。
  • c.back() : 传回最后一个数据，不检查这个数据是否存在。
  • c.size() : 返回容器中实际数据的个数。
  • c.empty() : 判断容器是否为空。