CHAPTER 2

Section 2.1

Graph Theory

The Castle

N皇后

问题描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

DFS

Wormholes

问题描述

Farmer John’s hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 <= N <= 12, N even) to materialize on his farm, each located at a distinct point on the 2D map of his farm (the x,y coordinates are both integers).

According to his calculations, Farmer John knows that his wormholes will form N/2 connected pairs. For example, if wormholes A and B are connected as a pair, then any object entering wormhole A will exit wormhole B moving in the same direction, and any object entering wormhole B will similarly exit from wormhole A moving in the same direction. This can have rather unpleasant consequences.

For example, suppose there are two paired wormholes A at (1,1) and B at (3,1), and that Bessie the cow starts from position (2,1) moving in the +x direction. Bessie will enter wormhole B [at (3,1)], exit from A [at (1,1)], then enter B again, and so on, getting trapped in an infinite cycle!

   | . . . .
   | A > B .      Bessie will travel to B then
   + . . . .      A then across to B again

Farmer John knows the exact location of each wormhole on his farm. He knows that Bessie the cow always walks in the +x direction, although he does not remember where Bessie is currently located.

Please help Farmer John count the number of distinct pairings of the wormholes such that Bessie could possibly get trapped in an infinite cycle if she starts from an unlucky position. FJ doesn’t know which wormhole pairs with any other wormhole, so \fBfind all the possibilities (i.e., all the different ways that N wormholes could be paired such that Bessie can, in some way, get in a cycle\fP). Note that a loop with a smaller number of wormholes might contribute a number of different sets of pairings to the total count as those wormholes that are not in the loop are paired in many different ways.

Milking Cows

问题描述

Milking Cows

Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).

Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):

• The longest time interval at least one cow was milked.
• The longest time interval (after milking starts) during which no cows were being milked.

农民挤奶牛,每个农民有各自的挤奶时间段
求至少有一名农民在挤奶的最长连续时间段
求没有一个农民在挤奶的最长时间间隔

Broken Necklace

问题描述

Broken Necklace

暴力法

思路分析

遍历一遍，记录下上一个颜色的数量信息
再处理环的特殊情况

矩形面积

问题描述

我们给出了一个（轴对齐的）矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标，（x2，y2）是该矩形右上角的坐标。

找出平面中所有矩形叠加覆盖后的总面积。 由于答案可能太大，请返回它对 10 ^ 9 + 7 取模的结果。

示例 1：
输入：[[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出：6
示例 2：
输入：[[0,0,1000000000,1000000000]]
输出：49
解释：答案是 10^18 对 (10^9 + 7) 取模的结果， 即 (10^9)^2 → (-7)^2 = 49 。

提示：

• 1 <= rectangles.length <= 200
• rectanges[i].length = 4
• 0 <= rectangles[i][j] <= 10^9
• 矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。

空间压缩

cmake

跨平台的安装（编译）工具
CMake是一个跨平台的安装（编译）工具，可以用简单的语句来描述所有平台的安装(编译过程)。他能够输出各种各样的makefile或者project文件，能测试编译器所支持的C++特性,类似UNIX下的automake。只是 CMake 的组态档取名为 CMakeLists.txt。Cmake 并不直接建构出最终的软件，而是产生标准的建构档（如 Unix 的 Makefile 或 Windows Visual C++ 的 projects/workspaces），然后再依一般的建构方式使用。这使得熟悉某个集成开发环境（IDE）的开发者可以用标准的方式建构他的软件，这种可以使用各平台的原生建构系统的能力是 CMake 和 SCons 等其他类似系统的区别之处。

单项目构建

基础

1
2
3
4
5
6
7
8
9
10
11
12
13
14

cmake_minimum_required(VERSION 3.3.0)

# specify the C++ standard
set(CMAKE_CXX_STANDARD 11)

project(TESTCMAKE VERSION 1.12.7)
set(TESTCMAKE_SOVERSION ${TESTCMAKE_VERSION})

INCLUDE_DIRECTORIES(${PROJECT_SOURCE_DIR}/include)	   
INCLUDE_DIRECTORIES(${PROJECT_SOURCE_DIR}/include2)

FILE(GLOB testgroup "./testgroup/src\/*.cpp" "./testgroup/include\/*.h")
source_group(testgroup FILES ${testgroup})
add_executable(TESTCMAKE src/TESTCMAKE.cpp include/TESTCMAKE.h ${testgroup})

模快组织

文件目录结构

头文件和源文件分离

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

动态规划

思路分析

代码实现

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

十进制错位相乘

思路分析

代码实现

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

class Solution {
public:
	string multiply(string num1, string num2) {
		if (num1.length() < num2.length()) {
			swap(num1,num2);
		}
		//if (num2 == "0") {
		//	return 0;
		//}
		int i, j;
		string strvalue = "";
		vector<string> v(10);
		v[0] = "";
		strvalue = num2;
		reverse(strvalue.begin(), strvalue.end());
		v[1] = strvalue;
		int forward = 0;
		int value = 0;

		for (i = 2; i < 10; i++) {
			forward = 0;
			strvalue = "";
			for (j = num2.length() - 1; j >= 0; j--) {
				value = (i * (num2[j] - '0') + forward);
				forward = value / 10;
				strvalue.insert(strvalue.begin(),value%10+'0');
			}
			if (forward != 0) { strvalue.insert(strvalue.begin(), forward + '0'); }
			reverse(strvalue.begin(),strvalue.end());
			v[i] = strvalue;
		}
		reverse(num1.begin(), num1.end());
		string ans(num1.length() + num2.length(),'0');
		for (i = 0; i < num1.length(); i++) {
			strvalue = v[num1[i] - '0'];
			forward = 0;
			for (j = 0; j < strvalue.length(); j++) {
				value = (ans[i + j] - '0' + strvalue[j] - '0') + forward;
				forward = value / 10;
				ans[i + j] = value % 10 + '0';
			}
			if (forward != 0) {
				ans[i + j] = forward + '0';
			}
		}
		while (ans.length() > 1 && ans[ans.length() - 1] == '0') {
			ans.erase(ans.begin() + ans.length() - 1);
		}
		reverse(ans.begin(),ans.end());

		return ans;
	}
};

BM算法

1.The bad character rule

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void badCharHeuristic( string str, int size,  
                        int badchar[NO_OF_CHARS])  
{  
    int i;  

    // Initialize all occurrences as -1  
    for (i = 0; i < NO_OF_CHARS; i++)  
        badchar[i] = -1;  

    // Fill the actual value of last occurrence  
    // of a character  
    for (i = 0; i < size; i++)  
        badchar[(int) str[i]] = i;  
}

2.The good suffix rule

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

// preprocessing for strong good suffix rule
void preprocess_strong_suffix(int *shift, int *bpos,
                                char *pat, int m)
{
    // m is the length of pattern  
    int i=m, j=m+1;
    bpos[i]=j;

    while(i>0)
    {
        /*if character at position i-1 is not equivalent to
          character at j-1, then continue searching to right
          of the pattern for border */
        while(j<=m && pat[i-1] != pat[j-1])
        {
            /* the character preceding the occurrence of t in  
               pattern P is different than the mismatching character in P,  
               we stop skipping the occurrences and shift the pattern
               from i to j */
            if (shift[j]==0)
                shift[j] = j-i;

            //Update the position of next border  
            j = bpos[j];
        }
        /* p[i-1] matched with p[j-1], border is found.
           store the  beginning position of border */
        i--;j--;
        bpos[i] = j;  
    }
}

//Preprocessing for case 2
void preprocess_case2(int *shift, int *bpos,
                      char *pat, int m)
{
    int i, j;
    j = bpos[0];
    for(i=0; i<=m; i++)
    {
        /* set the border position of the first character of the pattern
           to all indices in array shift having shift[i] = 0 */
        if(shift[i]==0)
            shift[i] = j;

        /* suffix becomes shorter than bpos[0], use the position of  
           next widest border as value of j */
        if (i==j)
            j = bpos[j];
    }
}