發表於   |   分類於

前面

关于算法这一块，怎么说呢，目前为止我还是比较盲目的在OJ上面A水题，但即便如此AC率也很低——这到底还是不行的，不过终究是给自己探了个底子——在仅有基础概念的RAW状态下能走多远。

就目前来看，很多时候问题出在自己见得少，给不出思路。对于抽象思维要求不高的题目，知道怎么去做之后多数情况还下是能够拿到TLE（并非纯暴搜导致）或者AC的——当然TLE也不是算过，终究还是代码技巧不足；而对于需要有较高抽象能力的题目，或是比较Tricky的题目，则力有不逮——一个是因为见得少而不知道怎么下手，再就是抽象思维能力不过关。

因此，就算法这块，现在开始进行专项练习吧。咱对自己的要求不高，也不指望能有ACM的程度，但至少买的那三本书：《算法竞赛入门经典》、《算法竞赛入门经典训练指南》以及《挑战程序设计竞赛》不能白瞎了。

由于不知道自己对《刷油漆》那道题的题解理解正确与否，文中对那道题目的讲解我是没有信心的，虽然最终代码是AC了……还是要多做多体会。

正文

今次就看三个问题吧，从老生常谈的背包问题开始，到树形DP的简单介绍。

这里先推荐知乎上面关于DP的回答看一看，两个高票答案已经将DP的核心问题讲得很明白了：就是“如何定义状态”以“如何控制状态的转移”——状态转移方程集中体现此两者，至于如何求解（递推或者是记忆化搜索）都只是求解方程的手段而已。

在谨记上面的条款之后，下面开始看3个题目，以协助理解。

0-1背包问题

From：HiHoCoder，HiHo一下第6周。

老题，网上有很多讲解的，包括状态方程怎么来的一应俱全，这里不去赘述，直接给AC的代码：

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
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> vi;

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

int main(int argc, char** argv)
{
	int N = 0, M = 0;
	cin >> N >> M;

	if (N <= 0 || M <= 0) { cout << 0 << endl; return 0; }

	vector<vi> dp(N + 1, vi(M + 1, 0));
	vi need(N + 1, 0);
	vi value(N + 1, 0);

	for (int i = 1; i <= N; ++i)
	{
		cin >> need[i] >> value[i];
	}

	int result = INT_MIN;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
		{
			if (j < need[i])
			{
				dp[i][j] = dp[i - 1][j];
			}
			else
			{
				int a = dp[i - 1][j];
				int b = dp[i - 1][j - need[i]] + value[i];
				dp[i][j] = (a>b) ? a : b;
			}
			if (dp[i][j] > result)
			{
				result = dp[i][j];
			}
		}
	}
	cout << result << endl;
	return 0;
}

需要注意一下：关于剩余空间M的For循环是从1开始加一递增的；而在采用记忆化搜索的递归解法中，剩余空间M并非是逐1递减的。这里需要逐步领会如何将尾递归转换为迭代的形式（PS：并非是指用显示Stack来辅助的方法）。

完全背包问题

From： HiHoCoder，HiHo一下第7周。

题解HiHo上面已经有了，这里不赘述。下面的AC代码中并没有进行第二步的优化阶段：

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int VALUE[501];
int NEED[501];
int N, W;

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

int main(int argc, char** argv)
{
	cin >> N >> W;

	for (int i = 0; i < N; ++i)
	{
		cin >> NEED[i + 1] >> VALUE[i + 1];
	}

	int** DP = (int**)new int*[N + 1];
	for (int m = 0; m <= N; ++m)
	{
		DP[m] = new int[W + 1];
		for (int n = 0; n <= W; ++n)
		{
			DP[m][n] = 0;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= W; j++)
		{
			int K = j / NEED[i];
			for (int k = 0; k <= K; k++)
			{
				int r = DP[i - 1][j - k*NEED[i]] + k * VALUE[i];
				if (DP[i][j] < r) DP[i][j] = r;
			}
		}
	}

	cout << DP[N][W];

	return 0;
}

刷油漆（树形DP）

From：HiHoCoder，HiHo一下第12周

虽然HiHo有给出题解，但是还是这里还是先借用《训练指南》P70的例题30的讲解开始吧——至少，对于我这种比较笨的人，HiHo的那个题解后半部分一开始是看不太懂的。

当然例题30并非是《刷油漆》原题，但也是树形DP的应用。

下面是整理的引用，需要注意的是后面两句：

无向无环图，或者称为森林，有多棵树组成，动态规划是解决树上的优化问题的常用工具。

为了能够使用动态规划，这要求：森林中的每个节点都互不相干，以便可以单独优化。

我们只考虑一棵树的情况：首先对这棵树进行DFS，将无根树转化为有根树，然后试着设置，并计算它的状态。

我们来看看单独的一棵树的情况，状态的定义HiHo题解中已经说明了，这里主要说明状态转移是如何发生的，也就是HiHo题解后半部分究竟是怎么回事。

先看给出的由case构造出来的树：

case

就从以节点4为根的子树开始吧。

显然我们要在这棵子树中选择三个节点，而如果想要对这棵子树进行评估，那么很显然，节点4也必须被选择（于是我们的DFS也就进行了2层了）。

剩下的两个节点只有从节点4的子树中选取了。

类比背包问题，这就相当于背包只剩下两个空间，而每个节点占用一个空间，选取的物品价值就相当于节点的最大估值，但这个值是存在于DP数组中的，并非是给定的值。

那么，对于节点4的每一个子树，都有可能分配0~2个空间。

这里应当注意：由于采用了DFS，我们已经把节点4的所有子树对应的状态都计算好了，因此，可以认为我们是在背包空间为2的情况下选取下面几个值来达到要求的最大值：

1
2
3
DP[8][0], DP[8][1], DP[8][2]
DP[6][0], DP[6][1], DP[6][2]
DP[7][0], DP[7][1], DP[7][2]

类比完全背包问题：完全背包问题要求对于每种物品选取K个，来得到最大值。这里可以认为是：对于子节点8，选取0~2个；对于子节点6，选取0~2个；对于子节点7，选取0~2个。

这里需要注意的是，上面关于如何选择的情况均是在自顶向下的情况下说明的——而实际代码中，采用的是自底向上的填充方式。

在完全背包中，状态转移方程以及对应代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DP[i][j] = max{ DP[i][j], DP[i-1][ j-k*w[i] ] + k*v[i] | k = [0...j/w[i]] }

for (int i = 1; i <= N; ++i )
{
  for (int j = 1; j <= M; ++j)
  {
    int K = j/w[i];
    for (int k = 0; k <= K; ++k)
    {
      int r = DP[i-1][j-k*w[i]]+k*v[i];
      if (r > DP[i][j]) DP[i][j] = r;
    }
  }
}

那么，类比可以写出对于单个节点的DP值计算式：

1
DP[i][j] = max{ DP[i][j], DP[i][j-k] + DP[l][k] | l = [i的子节点] }

举个栗子：

1
2
3
4
5
6
7
8
DP[4][3] = DP[4][2] + DP[6][1]
         = max{
                  (DP[4][1] + DP[8][1]),
                  “DP[4][1] + DP[6][1],”
                  (DP[4][1] + DP[7][1])
              } + DP[6][1]  

// 显然max{...}中的DP[6][1]是不应该重复计算的

注意，完全背包的填充方式是在已经有的结果上再装上k个第i种物品（也就是剩余的空间还足够在第i中物品上做出多个选择）；而在当前问题中我们则是在选择了当前子树中的k个节点之后，根节点上还可以再选择多少个其他子树中的节点。

那么尝试写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
DFS(int i, int M)
{
  //vis[ci] = true;
  for (each child ci of node i)
  {
      // 不对已经计算过的节点重复计算。
      if (vis[ci]) continue;
      // 先DFS计算子树
      DFS(ci,M-1);
      // 然后根据子树，计算当前节点
      for ( m = [M ... 2]) // 对于 “剩余空间” m
      {
        for ( k = [1 ... m] ) // 接下来要取 k 个节点
        {
          int r = DP[i][m-k] + DP[ci][k];
          if (r > DP[i][m]) DP[i][m] = r;
        }
      }
  }
}

注意到M的值是从大到小计算的，这一点可以从前面列举的那个小例子中看出来：M值大的DP值是依赖于M值小的DP值的。而M的值最小只到2，原因在于，对于M=0时肯定为0，M=1时，就是节点本身。

下面是我的AC代码：

另：如果在HiHo一下的比赛排名中查找AC代码的话，会发现有关于edge、vis数组这样的东西，这是因为那些代码是基于无向图的，需要使用vis数组来标记节点以防止出现环的问题。大部分ACM相关的博客上也是此类型的代码，此类代码更具普适性。

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
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int N, M;
int V[101];
int vis[101];

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

vector<int> Tree[101];

int DP[101][101];

void solve(int n, int m)
{
	vector<int>& children = Tree[n];
	for (auto ci = 0; ci < children.size(); ++ci)
	{
		solve(children[ci], m - 1);

		for (int j = m; j >= 2; --j)
		{
			for (int k = 1; k < j; ++k)
			{
				int r = DP[n][j - k] + DP[children[ci]][k];
				if (r > DP[n][j]) DP[n][j] = r;
			}
		}
	}
}

int main(int argc, char** argv)
{
	// 注意下面的不要删除，重定向io流
	// std::ifstream in("in.txt");
	// std::streambuf* cinbuf = std::cin.rdbuf(); //save old buf
	// std::cin.rdbuf(in.rdbuf()); //redirect std::cin to in.txt!

	//
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) cin >> V[i];
	int a, b;
	for (int i = 1; i < N; ++i)
	{
		cin >> a >> b;
		Tree[a].push_back(b);
	}
	for (int i = 1; i <= N; ++i)
	{
		DP[i][1] = V[i];
	}

	solve(1, M);

	cout << DP[1][M] << endl;

	return 0;
}

發表於   |   分類於

优化延迟

From：[Offer收割]编程练习赛1

描述
小Ho编写了一个处理数据包的程序。程序的输入是一个包含N个数据包的序列。每个数据包根据其重要程度不同，具有不同的”延迟惩罚值”。序列中的第i个数据包的”延迟惩罚值”是Pi。如果N个数据包按照的顺序被处理，那么总延迟惩罚

SP=1*Pi1+2*Pi2+3*Pi3+…+N*PiN（其中i1, i2, … iN是1, 2, 3, … N的一个排列)。

小Ho的程序会依次处理每一个数据包，这时N个数据包的总延迟惩罚值SP为

1 * P1+2 * P2+3 * P3+…+i * Pi+…+N * PN。

小Hi希望可以降低总延迟惩罚值。他的做法是在小Ho的程序中增加一个大小为K的缓冲区。N个数据包在被处理前会依次进入缓冲区。当缓冲区满的时候会将当前缓冲区内”延迟惩罚值”最大的数据包移出缓冲区并进行处理。直到没有新的数据包进入缓冲区时，缓冲区内剩余的数据包会按照”延迟惩罚值”从大到小的顺序被依次移出并进行处理。

例如，当数据包的”延迟惩罚值”依次是<5，3，1，2，4>，缓冲区大小K=2时，数据包被处理的顺序是：<5，3，2，4，1>。这时SP=1 * 5+2 * 3+3 * 2+4 * 4+5 * 1=38。

现在给定输入的数据包序列，以及一个总延迟惩罚阈值Q。小Hi想知道如果要SP<=Q，缓冲区的大小最小是多少？

输入

1
2
Line 1: N Q
Line 2: P1 P2 ... PN

对于50%的数据： 1 <= N <= 1000

对于100%的数据： 1 <= N <= 100000, 0 <= Pi <= 1000, 1 <= Q <= 1013

输出
输出最小的正整数K值能满足SP<=Q。如果没有符合条件的K，输出-1。

样例输入

1
2
5 38
5 3 1 2 4

样例输出

1
2

优先队列的问题。

然而只用优先队列是会超时的，应该使用二分查找——原因在于：对于缓冲区的大小K，随着K值的增大，延迟惩罚是个非递增序列（只可能不变或者下降，而不会递增）。

想到了优先队列但是没有想到二分……

AC代码：

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
#include <queue>
#include <iostream>
using namespace std;

#define LL long long
priority_queue<int> q;
LL Q,N,SP,K;
LL nums[1000001];


LL cal(int m)
{
	LL result = 0;
	LL j = 0;
	for (LL i = 0; i < N; ++i)
	{
		q.push(nums[i]);
		if (q.size() == m)
		{
			++j;
			result += j * q.top();
			q.pop();
		}
	}
	while (q.size())
	{
		++j;
		result += j * q.top();
		q.pop();
	}
	return result;
}


void bin(LL s, LL e)
{
	while (s <= e)
	{
		LL mid = (s + e) / 2;
		SP = cal(mid);
		if (SP > Q)
		{
			s = mid + 1;
		}
		else
		{
			if (mid < K)
			{
				K = mid;
			}
			e = mid - 1;
		}
	}
}

int main()
{
	cin >> N >> Q;

	for (int i = 0; i < N; ++i)
	{
	    cin >> nums[i];
	}

	K = N + 1;
	bin(1,N);
	if (K <= N)
	{
	    cout << K << endl;
	}
	else
	{
	    cout << "-1" << endl;
	}

	return 0;
}

發表於   |   分類於

HiHoCoder: 九宫

From：[Offer收割]编程练习赛1

描述
小Hi最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

九宫

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小Hi准备将一个三阶幻方（不一定是上图中的那个）中的一些数组抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一组解。

而你呢，也被小Hi交付了同样的任务，但是不同的是，你需要写一个程序~

输入
输入仅包含单组测试数据。

每组测试数据为一个3*3的矩阵，其中为0的部分表示被小Hi抹去的部分。

对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。

输出
如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。

样例输入

1
2
3
0 7 2
0 5 0
0 3 0

样例输出

1
2
3
6 7 2
1 5 9
8 3 4

使用回溯法进行求解。

还是做题少了，不够敏锐。知道用回溯的话写代码还好，一旦想偏就怎么也拉不回来了……

AC代码：

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;

int Nine[9];
int a, b, c;
int* addr = Nine;
int nums = 0;
int o2nine[10] = { 0,1,2,3,4,5,6,7,8,9 };

int present[9];

#define index(r,c) ((r) * (3)+(c))

bool check()
{
	int r = 0;
	r = Nine[index(0, 0)] + Nine[index(0, 1)] + Nine[index(0, 2)];
	if (r > 15) return false; r = 0;

	r = Nine[index(1, 0)] + Nine[index(1, 1)] + Nine[index(1, 2)];
	if (r > 15) return false; r = 0;

	r = Nine[index(2, 0)] + Nine[index(2, 1)] + Nine[index(2, 2)];
	if (r > 15) return false; r = 0;

	r = Nine[index(0, 0)] + Nine[index(1, 0)] + Nine[index(2, 0)];
	if (r > 15) return false; r = 0;

	r = Nine[index(0, 1)] + Nine[index(1, 1)] + Nine[index(2, 1)];
	if (r > 15) return false; r = 0;

	r = Nine[index(0, 2)] + Nine[index(1, 2)] + Nine[index(2, 2)];
	if (r > 15) return false; r = 0;

	r = Nine[index(0, 0)] + Nine[index(1, 1)] + Nine[index(2, 2)];
	if (r > 15) return false; r = 0;

	r = Nine[index(0, 2)] + Nine[index(1, 1)] + Nine[index(2, 0)];
	if (r > 15) return false;

	return true;
}

void cal(int x)
{
	bool allZero = true;

	for (int i = 1; i < 10; ++i)
	{
		if (o2nine[i] != 0)
		{
			allZero = false;
		}
	}

	if (allZero)
	{
		++nums;
		for (int i = 0; i < 9; ++i)
		{
			present[i] = Nine[i];
		}
		return;
	}

	if (Nine[x] == 0)
	{
		for (int i = 1; i < 10; ++i)
		{
			if (o2nine[i] != 0)
			{
				Nine[x] = i;
				o2nine[i] = 0;
				if (check())
				{
					cal(x+1);
				}
				Nine[x] = 0;
				o2nine[i] = i;
			}
		}
	}
	else
	{
		cal(x+1);
	}
}

int main(int argc, char** argv)
{

	for (int i = 0; i < 3; ++i)
	{
		cin >> a >> b >> c;
		addr[0] = a;
		addr[1] = b;
		addr[2] = c;
		addr += 3;
		o2nine[a] = 0;
		o2nine[b] = 0;
		o2nine[c] = 0;
	}
	Nine[index(1, 1)] = 5;
	o2nine[5] = 0;
	cal(0);
	if (nums == 1)
	{
		for (int i = 0; i < 3; ++i)
		{
			for (int j = 0; j < 3; ++j)
			{
				cout << present[index(i, j)] << " ";
			}
			cout << endl;
		}
	}
	else
	{
		cout << "Too Many" << endl;
	}

	return 0;
}

發表於   |   分類於

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

只需要控制好状态就行了。

AC代码：

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
class Solution {
public:

    struct Runner
    {
        int leftBorder;
        int rightBorder;
        int topBorder;
        int downBorder;
        int dir;
        int counter;
        int x;
        int y;
        Runner(int n)
        {
            leftBorder = 0;
            rightBorder = n;
            topBorder = 0;
            downBorder = n;
            dir = 1;
            counter = 0;
            x = 0;
            y = 0;
        }
    };

    void goRight(vector<vector<int>>& m, int n, Runner& r)
    {
        if (r.x < r.rightBorder)
        {
            ++r.counter;
            m[r.y][r.x] = r.counter;
            ++r.x;
        }
        else
        {
            r.dir = 2;
            ++r.topBorder;
            ++r.y;
            --r.x;
        }
    }

    void goLeft(vector<vector<int>>& m, int n, Runner& r)
    {
        if (r.x >= r.leftBorder)
        {
            ++r.counter;
            m[r.y][r.x] = r.counter;
            --r.x;
        }
        else
        {
            r.dir = 3;
            --r.downBorder;
            --r.y;
            ++r.x;
        }
    }

    void goDown(vector<vector<int>>& m, int n, Runner& r)
    {
        if (r.y < r.downBorder)
        {
            ++r.counter;
            m[r.y][r.x] = r.counter;
            ++r.y;
        }
        else
        {
            r.dir = 0;
            --r.rightBorder;
            --r.x;
            --r.y;
        }
    }

    void goUp(vector<vector<int>>& m, int n, Runner& r)
    {
        if (r.y >= r.topBorder)
        {
            ++r.counter;
            m[r.y][r.x] = r.counter;
            --r.y;
        }
        else
        {
            r.dir = 1;
            ++r.leftBorder;
            ++r.x;
            ++r.y;
        }
    }

    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n,vector<int>(n,0));
        int num = n * n;
        Runner r(n);
        while(r.counter < num)
        {
            if (r.dir == 0)
            {
                goLeft(result,n,r);
            }
            else if (r.dir == 1)
            {
                goRight(result,n,r);
            }
            else if (r.dir == 2)
            {
                goDown(result,n,r);
            }
            else
            {
                goUp(result,n,r);
            }
        }
        return result;
    }
};

發表於   |   分類於

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1
2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

依赖关系判定，实际上就是一个拓扑结构，层序遍历可解。BFS每下降一层，其对应后续节点的入度减一，入度为0的节点入队列，如果最后所有节点的入度都为0，则返回true，否则返回false。

AC的C++代码：

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
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> graphic(numCourses,vector<int>(0));
        vector<int> indegrees(numCourses,0);
        queue<int> q;

        for(auto it = prerequisites.begin(); it != prerequisites.end(); ++it)
        {
            int succ = it->first;
            int pre = it->second;
            indegrees[succ]++;
            graphic[pre].push_back(succ);
        }

        for (int i = 0 ; i < indegrees.size(); ++i)
        {
            if (indegrees[i] == 0)
            {
                q.push(i);
            }
        }

        while(q.size())
        {
            int n = q.front();
            q.pop();// 注意这里与C版本的顺序不一致。
            vector<int>& v = graphic[n];
            for (int i = 0; i < v.size(); ++i)
            {
                --indegrees[v[i]];
                if (indegrees[v[i]] == 0)
                {
                    q.push(v[i]);
                }
            }
        }

        for (int i = 0 ; i < indegrees.size(); ++i)
        {
            if (indegrees[i] != 0)
            {
                return false;
            }
        }

        return true;
    }
};

超过规定内存空间的C代码：

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

bool canFinish(int numCourses, int** prerequisites, int prerequisitesRowSize, int prerequisitesColSize) {
    int* indegrees = (int*)malloc(numCourses*sizeof(int));
    int** graphic = (int**)malloc(sizeof(int*) * numCourses);
    int * queue = (int*)malloc(numCourses*sizeof(int));
    int begin = 0;
    int end = 0;
    for (int i = 0 ; i < numCourses; ++i)
    {
        indegrees[i] = 0;
    }

    for (int i = 0 ; i < numCourses; ++i)
    {
        graphic[i] = (int*)malloc(sizeof(int*) * numCourses);
        for (int j = 0 ; j < numCourses; ++j)
        {
            graphic[i][j] = -1;
        }
    }

    for (int i = 0 ;i < prerequisitesRowSize; ++i)
    {
        int* row = prerequisites[i];
        int succ = row[0];
        int pre = row[1];
        indegrees[succ]++;//后续课程入度加一
        graphic[pre][succ] = 1;//设置前导课程的后续边
    }
    //找出所有入度为0的点作为起始节点
    for(int i = 0; i < numCourses; ++i)
    {
        if (indegrees[i] == 0)
        {
            queue[end++] = i;
        }
    }
    // BFS
    while(begin != end)
    {
        int n = queue[begin];
        //查找所有n的后继节点，每处理一次，后续节点入度减一，如果后续节点入度为0，那么就加入队列
        for (int i = 0 ; i < numCourses; ++i)
        {
            if (graphic[n][i] == 1)
            {
                --indegrees[i];
                if (indegrees[i] == 0)
                {
                    queue[end++] = i;
                }
            }
        }
        ++begin;
    }

    //如果最后还有入度不为0的节点，返回false
    for (int i = 0 ; i < numCourses; ++i)
    {
        if (indegrees[i] != 0)
        {
            return false;
        }
    }
    return true;
}

發表於   |   分類於

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
2
3
4
5
   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

1
["1->2->5", "1->3"]

DFS。

AC代码：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	vector<int> sk;
	vector<string> result;
	string str;
	void solve(TreeNode* root)
	{
		if (root)
		{
			sk.push_back(root->val);
			solve(root->left);
			solve(root->right);

			if (root->left == NULL && root->right == NULL)
			{
				str.clear();
				for (int i = 0; i < sk.size(); ++i)
				{
					string number = to_string(sk[i]);
					str += number;
					if (i < sk.size() - 1)
					{
						str += "->";
					}
				}
				result.push_back(str);
			}

			sk.pop_back();
		}
	}

	vector<string> binaryTreePaths(TreeNode* root) {
		if (root)
		{
			solve(root);
		}
		return result;
	}
};

發表於   |   分類於

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

N-QueensII

N皇后问题，回溯可解。

AC代码：

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
int getState(int n, int* board, int r, int c)
{
	return board[r * n + c];
}

void setState(int n, int* board, int r, int c, int state)
{
	board[r * n + c] = state;
}

void printBoard(int* board, int n)
{
	printf("***************\n\n");
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			printf("%d ", getState(n, board, i, j));
		}
		printf("\n");
	}
}

bool palced(int n, int* board, int r, int c)
{
	for (int i = 0; i < n; ++i)
	{
		if (getState(n, board, r, i))
			return false;
	}
	for (int i = 0; i < n; ++i)
	{
		if (getState(n, board, i, c))
			return false;
	}
	int ir = r + 1;
	int ic = c + 1;
	// 斜线为0
	while (ir < n && ic < n)
	{
		if (getState(n, board, ir, ic))
			return false;
		++ir;
		++ic;
	}
	ir = r - 1;
	ic = c - 1;
	while (ir >= 0 && ic >= 0)
	{
		if (getState(n, board, ir, ic))
			return false;
		--ir;
		--ic;
	}
	ir = r - 1;
	ic = c + 1;
	while (ir >= 0 && ic < n)
	{
		if (getState(n, board, ir, ic))
			return false;
		--ir;
		++ic;
	}
	ir = r + 1;
	ic = c - 1;
	while (ir < n && ic >= 0)
	{
		if (getState(n, board, ir, ic))
			return false;
		++ir;
		--ic;
	}
}

void queens(int n, int* board, int* nums, int r, int c)
{
	if ((r >= 0 && r < n) && ((c >= 0 && c < n)))
	{
		if (r == n - 1)
		{
			for (int i = 0; i < n; ++i)
			{
				if (palced(n, board, r, i))
				{
					//setState(n, board, r, i, 1);
					++(* nums);
					//printBoard(board, n); //可以打印棋盘
					//setState(n, board, r, i, 0);
				}
			}
		}
		else
		{
			for (int i = 0; i < n; ++i)
			{
				if (palced(n,board,r,i))
				{
					setState(n, board, r, i, 1);//放置一个皇后
					queens(n, board, nums, r + 1, 0);//对剩下的棋盘进行摆放
					setState(n, board, r, i, 0);//恢复棋盘
				}
			}
		}
	}
}

int totalNQueens(int n) {
    if (n ==0)
    {
        return 1;
    }
    int* board = (int*)malloc(sizeof(int) * n * n);
    for (int i = 0; i < n*n; ++i)
    {
        board[i] = 0;
    }
    int result = 0;

    queens(n, board, &result, 0, 0);

    return result;
}

發表於   |   分類於

Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

1
2
3
4
5
6
7
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

Example 1:
“9,3,4,#,#,1,#,#,2,#,6,#,#”
Return true

Example 2:
“1,#”
Return false

Example 3:
“9,#,#,1”
Return false

解法是利用栈，逐个消去节点的子树：

1
2
3
4
5
6
7
8
9
10
"9,3,4,#,#,1,#,#,2,#,6,#,#"

9    3    4    #     #        9    3    #
true true true false false -> true true false

9    3    #     1    #     #        9    3    #     #        9    #     
true true false true false false -> true true false false -> true false

9    #     2    #     6    #     #        9    #     2    #     #        9    #     #        #
true false true false true false false -> true false true false false -> true false false -> false

AC代码，使用了vector作为栈：

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
class Solution {
public:
    bool isValidSerialization(string preorder) {
        string s;
        vector<bool> sk;
        if (preorder[0] == '#' && preorder.length() == 1)
        {
            return true;
        }
        if(preorder.length() < 3 || preorder[0] == '#')
        {
            return false;
        }
        preorder.push_back(',');
        for (int i = 0 ; i < preorder.length(); ++i)
        {
            if (preorder[i] == ',')
            {
                if (s.length() && s[0] != '#')
                {
                    sk.push_back(true);
                }
                s.clear();
                if (sk.size() > 2)
                {
                    size_t preLen = 0;
                    while(preLen != sk.size() && sk.size() >= 2)
                    {
                        preLen = sk.size();
                        if (sk[sk.size()-1] == false && sk[sk.size()-2] == false)
                        {
                            sk.pop_back();
                            if (sk.size() == 0)
                            {
                                return false;
                            }
                            sk.pop_back();
                            if (sk.size() == 0)
                            {
                                return false;
                            }
                            sk.pop_back();
                            sk.push_back(false);
                            if (sk[0] == false && i < preorder.length() - 1)
                            {
                                return false;
                            }
                        }
                    }
                }
            }
            else if (preorder[i] == '#')
            {
                sk.push_back(false);
            }
            else
            {
                s.push_back(preorder[i]);
            }
        }
        if (sk.size() == 1)
        {
            return true;
        }
        return false;
    }
};

發表於   |   分類於

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree.

There is no restriction on how your serialization/deserialization algorithm should work.

You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

1
2
3
4
5
  1
 / \
2   3
   / \
  4   5

as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ serializes a binary tree.

You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

这个题目的设置条件……我个人认为对C++不是很友好就是了，最后用C解决了，用了一个小小的协议，并使用节点的地址作为唯一标识符来使用。

就我个人对网络那点贫瘠的理解来讲，序列化与反序列化其实就是一个“协议”的问题：根据某个协议将数据编码成一个流发出去，然后再根据协议解析接收到的数据流，完成数据的创建。

在碰到这个题目的之前恰好做了HiHoCoder一个类似的题目，就是还原二叉树的，题目在这里。

两题的思路是一样的：从前序遍历和中序遍历还原整个二叉树。当然本题还可以通过层序来恢复就是了。

然而问题出在：HiHo的用例中，所有的二叉树结点的标识都是唯一的，而LeetCode则不唯一，因此在查找中序序列中的节点的过程是很需注意的。

放上AC代码：

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
130
131
132
133
134
135
typedef struct TreeNode TreeNode;

typedef struct Protocol
{
	TreeNode* addr;
	int val;
}Protocol;

typedef struct DynArray
{
    int size;
    int cap;
    Protocol* array;
}DynArray;

void array_init(DynArray* a)
{
    a->size = 0;
    a->cap = 0;
    a->array = NULL;
}

void array_insert(DynArray* a, Protocol* p)
{
    if (a->array == NULL)
    {
        a->cap = 1;
        a->array = (Protocol*)malloc(sizeof(Protocol));
    }
    else
    {
        if (a->cap == a->size)
        {
            a->cap *= 2;
            Protocol* narray = (Protocol*)malloc(a->cap*sizeof(Protocol));
            for (int i = 0; i < a->size; ++i)
            {
                narray[i].addr = a->array[i].addr;
                narray[i].val = a->array[i].val;
            }
            free(a->array);
            a->array = narray;
        }
    }
    a->array[a->size].addr = p->addr;
    a->array[a->size].val = p->val;
    a->size++;
}

void preOrder(TreeNode* root, DynArray* a)
{
    if (root)
    {
        Protocol p;
        p.addr = root;
        p.val = root->val;
        array_insert(a,&p);

        preOrder(root->left,a);
        preOrder(root->right,a);
    }
}

void inOrder(TreeNode* root, DynArray* a)
{
    if (root)
    {
        inOrder(root->left,a);

        Protocol p;
        p.addr = root;
        p.val = root->val;
        array_insert(a,&p);

        inOrder(root->right,a);
    }
}

int findInOrder(TreeNode* addr, Protocol* address, int len)
{
    for(int i = 0 ; i < len; ++i)
    {
        if (address[i].addr == addr)
        {
            return i;
        }
    }
    return 0;
}

TreeNode* reBuild(Protocol* pre, Protocol* in, int* index, int begin, int end, int len)
{
    if (begin < end)
    {
        * index +=1;
        TreeNode* r = (TreeNode*)malloc(sizeof(TreeNode));
        r->val = pre[* index].val;
        r->left = NULL;
        r->right = NULL;
        int pos = findInOrder(pre[* index].addr,in,len);
        r->left = reBuild(pre,in,index,begin,pos-1,len);
        r->right = reBuild(pre,in,index,pos+1,end,len);
        return r;
    }
    else if (begin == end)
    {
        * index += 1;
        TreeNode* r = (TreeNode*)malloc(sizeof(TreeNode));
        r->left = NULL;
        r->right = NULL;
        r->val = pre[* index].val;
        return r;
    }
    else
    {
        return NULL;
    }
}

char* serialize(struct TreeNode* root) {
    DynArray* result = (DynArray*)malloc(sizeof(DynArray));
    array_init(result);
    preOrder(root,result);
    inOrder(root,result);
    return (char*)result;
}

struct TreeNode* deserialize(char* data) {
    DynArray* darray = (DynArray*)(data);
    int len = darray->size / 2;
    Protocol* pre = darray->array;
    Protocol* in = darray->array + len;
    int index = -1;
    return reBuild(pre,in,&index,0,len-1,len);
}

再放上HiHo那个题目的AC代码：

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
#include <iostream>
#include <string>
using namespace std;

string preOrder;
string inOrder;
string postOrder;

struct BTNode
{
	BTNode* left;
	BTNode* right;
	char data;
	BTNode()
	{
		left = NULL;
		right = NULL;
	}
};

int findRootInMidSeq(char c)
{
	int pos = 0;
	while (true)
	{
		if (inOrder[pos] == c)
		{
			return pos;
		}
		++pos;
	}
	return pos;
}

BTNode* buildTree(int start, int end, int& root)
{
	if (start > end)
	{
		return NULL;
	}
	root += 1;
	if (start == end)
	{
		BTNode* r = new BTNode;
		r->data = preOrder[root];
		return r;
	}
	BTNode* r = new BTNode;
	r->data = preOrder[root];
	int pos = findRootInMidSeq(preOrder[root]);
	r->left = buildTree(start, pos - 1, root );
	r->right = buildTree(pos + 1, end, root );
	return r;
}

void post(BTNode* root)
{
	if (root)
	{
		post(root->left);
		post(root->right);
		postOrder.push_back(root->data);
	}
}

int main(int argc, char** argv)
{
	cin >> preOrder;
	cin >> inOrder;
	int index = -1;
	BTNode* root = buildTree(0, inOrder.length() - 1, index);
	post(root);
	cout << postOrder << endl;
	return 0;
}

以及，类似，然而却RE了的LeetCode代码，其中的findRootIninOrder()函数是不能用在这里的：

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

class Codec {
public:
	// 序列化为串
	void preOrder(TreeNode* root, string& btree)
	{
		if (root)
		{
			btree.push_back((char)(root->val));
			preOrder(root->left, btree);
			preOrder(root->right, btree);
		}
	}

	void inOrder(TreeNode* root, string& btree)
	{
		if (root)
		{
			inOrder(root->left, btree);
			btree.push_back((char)(root->val));
			inOrder(root->right, btree);
		}
	}

	// 反序列化，实际上就是从前序遍历和后序遍历的结果上把二叉树还原出来
	// 这是一个分治法的应用。

	int findRootIninOrder(char c, string& midStr)
	{
		for (int i = 0; i < midStr.length(); ++i)
		{
			if (midStr[i] == c)
			{
				return i;
			}
		}
	}

	TreeNode* rebuild(int begin, int end, int& index, string& midStr, string& preStr)
	{
		TreeNode* root = NULL;

		if (begin < end)
		{
			++index;
			root = new TreeNode((int)(preStr[index]));
			int pos = findRootIninOrder(preStr[index], midStr);
			root->left = rebuild(begin, pos - 1, index, midStr, preStr);
			root->right = rebuild(pos + 1, end, index, midStr, preStr);

		}
		else if (begin == end)
		{
			++index;
			root = new TreeNode((int)(preStr[index]));
		}
		else
		{
			return NULL;
		}
		return root;
	}


	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		string btree;
		preOrder(root, btree);
		inOrder(root, btree);
		return btree;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		string preStr;
		string midStr;
		int btreeSize = data.length() / 2;
		preStr = data.substr(0, btreeSize);
		midStr = data.substr(btreeSize, btreeSize);
		if (preStr.length() == 0)
		{
			return NULL;
		}
		int index = -1;
		return rebuild(0, btreeSize - 1, index, midStr, preStr);
	}
};

發表於   |   分類於

给自己提个醒

除了通过刷题来认识自己的不足之外之外，这里再给自己打一针，放上自己自不量力的失败作，提醒自己还差得很远。

尝试写的一个编辑器

editor

单从图片上来看马马虎虎，实际上也就图片上那么点东西而已，“装饰”面板就是个空的……

而且从图中可以看到刷子做的效果不好，不同地皮的接缝处没处理。

那个模型读过《3D游戏编程大师技巧》的兄台应该知道，就是个MD2的帧动画，况且这里也没做帧插值。

至于地表刷子的算法，就是网上流传的“WarIII地形拼接算法”，比如这篇博文。这个算法是基于2D时代的地形拼接算法的，很巧妙的一个算法，但过程不难理解。

这里每一个刷子对应了一个它自己的纹理坐标，规定好层序，然后开始刷——这带来的后果是刷高层的地标没有问题，但是想刷回低层的地表就会出现前面说的那个接缝问题。

这个东西写了一段时间，然后还想加UI，考虑到想要加装饰，然后就需要一个粒子系统……总之是想到什么加什么，然后……然后就挂了。

这个破玩意儿就放这儿吧，各种意义上都给自己个提醒。