[数据结构与算法] 学习记录合辑 (01) 数组和字符串

• 该合辑为笔者自b站自学的“C++数据结构与算法”课程学习记录，旨在将重要的学习要点、思考内容与部分代码进行记录，以便后续自行翻看，亦可给其他读者带来一些参考
• 内容基于笔者自身的理解或感悟，可能存在不妥当或是错误之处
• 系统环境：Win10，Visual Studio 2019

算法复杂性从时间和空间两个维度进行评估 ，其中，时间复杂度评估算法执行所需要耗费的时间，比较好理解。空间复杂度评估执行该算法需要占用多少内存空间，如果同样能胜任要求，则两者均越小越好

利用大O符号表示法来进行描述

分为几种常见的阶次，常量、线性、平方、对数、线性对数等

不同阶次算法对比 - 引自看动画轻松理解时间复杂度（一）_吴师兄学算法

最好时间复杂度/最坏时间复杂度

一些算法会有一定的随机性，运气好的时候一下就算出来，比如在一大串数据中找到“X”，查找的时候首位就恰巧是“X”，则时间复杂度为O（1），当然相应的也会有最坏情况，例如一些排序算法在处理特定排列的数据时会耗费比平时更多的时间等等

平均时间复杂度

正因如上有最好及最坏情况，则产生一种按照出现概率进行加权平均的平均时间复杂度，可以较为客观的将算法的时间复杂度进行描述

算法所占用内存空间的描述，分为固定和可变两部分，固定部分包含代码本身及其定义的变量等，在代码编制完成后基本确定，还有可变部分，为代码运行时所产生的动态分配的空间，以及递归栈所需的空间等，其为算法衍生出的空间，会随数据的变化而产生变化

在现实中，时间复杂度与空间复杂度往往会产生对峙关系，即想要好的时间复杂度可能就意味着空间复杂度要相应的付出，反之亦然，因此，对于一个项目，基于各个因素考量与优化时间与空间复杂度是一门很深的学问

简单的Brute-Force暴力算法及Rabin-Karp算法等，可以实现对字符串进行匹配

通过 if(!*str) 来判断字符串是否为空

Stack & Heap，Stack的先进后出，以及Heap需要程序员自行进行管理（delete），防止内存泄漏

HashTable（几乎是最重要的数据结构），碰到unique或统计一个元素集中元素出现的次数等问题时，想想能不能用HashTabl

给定一字符串，要求将字符串中的空格替换为“%20”并输出

class Solution2 {
public:
	string replaceSpace(string s) {
		int count = 0, len = s.size();
		// 统计空格数量
		// 此处用到了C++11语法，利用char c来遍历字符串s
		for (char c : s) {
			if (c == ' ') count++;
		}
		// 修改 s 长度
		s.resize(len + 2 * count);
		// 倒序遍历修改
		for (int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
			if (s[i] != ' ')
				s[j] = s[i];
			else {
				s[j - 2] = '%';
				s[j - 1] = '2';
				s[j] = '0';
				j -= 2;
			}
		}
		return s;
	}
};

代码参考LeetCode用户：力扣

for (char c : s) 为C++11中的语法，可以非常方便的遍历字符串，除此之外，还可以类似的使用double number[5] = {0.12, 9.12, 3.12, 4.64, 9.99}; for(double x : number)等，特别的，还可利用for(char &c : s)直接修改字符串

for (int i = len - 1, j = s.size() - 1; i < j; i--, j--) 判断中，当 i