算法解题经验

解题套路：

回溯算法：

image-20240720152129405

1，核心条件

image-20240717154006594 image-20240717154023009

几个常规函数的使用

string常用

  1. 1），isalpha（），判断给定内容是不是字母，头文件 cctype.h
  2. 2），tolower()，将给定的char字母转化为小写，头文件 cctype.h
  3. 3），transform(），对给定范围内的所有内容进行一次给定操作并将结果输出到第三个参数指定的容器中，
  4. ​ 有四个参数，1,2是范围的开头和结尾，3是要输出地方，4是指定操作
  5. substr：字符串截取，接受两个参数，起始位置和长度，长度从其实位置开始算起，由string变量本身调用
  6. 判断是不是数字：isdigit（），头文件：#include，在vs的环境中，可以被默认使用，另在 文心一言 的解释中，该方法同样存在于cctype.h的头文件中
  7. stoll ，头文件 string，将string转换为int

数字常用

1，std::accumulate()，头文件：累加求和，同样，std：：reduce是在C++17后新加入的累计求和方法

以下代码示例就是来求vector范围内的和，

1
int s = reduce(possible.begin(), possible.end(), 0) * 2 - n;

  1. 输入迭代器（first, last）：

    • first：指向要访问的序列（如容器）的第一个元素的迭代器。
    • last：指向要访问的序列的“超过最后一个元素”的位置的迭代器（即序列末尾的下一个位置）。

    这两个迭代器定义了要操作的元素范围。

  2. 初始值（init）：

    • 这是累积操作的初始值。在每次迭代中，这个值都会与序列中的元素进行某种操作（通常是加法，但也可以是其他可重载的操作）。

  3. 二元操作（可选，默认为std::plus<>）：

    • 这是一个二元函数对象（或者是一个可以隐式转换为函数对象的类型），它接受两个参数（通常是当前累积值和序列中的下一个元素），并返回它们的某种组合（通常是它们的和，但也可以是其他任何可定义的操作结果）。
    • 如果不提供此参数，则默认使用std::plus<>，即执行加法操作。

  4. 执行策略（可选，默认为std::execution::sequenced_policy）：

    • 这是一个执行策略，它定义了算法的执行方式。C++17引入了三种执行策略：std::execution::sequenced_policy（顺序执行）、std::execution::parallel_policy（并行执行）和std::execution::parallel_unsequenced_policy（并行且向量化执行，如果可能）。
    • 执行策略允许算法以不同的方式执行，以利用现代多核处理器的并行计算能力。但是，请注意，并行算法的正确使用需要额外的注意，以确保算法的正确性和效率。

numeric头文件

C++的<numeric>头文件中包含了一系列用于操作数值序列（或可通过修改参数类型适用于非数值序列）的函数。这些函数提供了基础的数值算法，便于对如vector<>、list<>等容器进行数值计算。以下是<numeric>头文件中常用的函数及其简要说明：

  1. std::accumulate
    • 功能：计算给定范围内元素的累积值。可以通过修改操作符来计算累乘积、累减、累除或其他自定义累计结果。
    • 模板参数：InputIterator（输入迭代器类型），T（初始值类型），BinaryOperation（可选，二元操作类型）。
    • 示例用法：计算一个vector<int>中所有元素的和。
  2. std::adjacent_difference
    • 功能：计算给定范围内相邻元素之间的差值（或自定义操作的结果），并将结果写入到输出序列中。
    • 模板参数：InputIterator（输入迭代器类型），OutputIterator（输出迭代器类型），BinaryOperation（可选，二元操作类型）。
    • 示例用法：计算一个整数数组中相邻元素之间的差值。
  3. std::inner_product
    • 功能：计算两个序列对应元素的内积，即对应元素相乘后的和（或自定义操作的结果）。
    • 模板参数：InputIterator1、InputIterator2（两个输入迭代器类型），T（初始值类型），BinaryOperation1、BinaryOperation2（可选，两个二元操作类型）。
    • 示例用法：计算两个vector<int>对应元素相乘后的和。
  4. std::partial_sum
    • 功能：计算给定范围内元素的部分和（或自定义操作的结果），并将结果写入到输出序列中。
    • 模板参数：InputIterator（输入迭代器类型），OutputIterator（输出迭代器类型），BinaryOperation（可选，二元操作类型）。
    • 示例用法：计算一个整数数组中每个位置之前所有元素的和。
  5. std::iota
    • 功能：生成一个范围内的连续整数序列，并将它们赋值给输出序列中的元素。
    • 模板参数：OutputIterator（输出迭代器类型），T（整数类型）。
    • 示例用法：初始化一个vector<int>，使其包含从0开始的连续整数。
  6. C++17新增函数
    • **std::gcd**：计算两个整数的最大公约数。
    • **std::lcm**：计算两个整数的最小公倍数。
    • **std::midpoint**：计算两个数值的中点，避免溢出

algorithm：

next_permutation：获取给定区间内容的下一个排列范方式，直到遍历完成所有的排列组合后false，对string也同样适用

1
next_permutation(from.begin(), from.end())

手撕全排序算法，想起见test工程下的BackTracking专栏

lower_bound()
//给定两个参数，a和b，a是容器，元素已经排好序，b是目标，作用是在a中找到第一个大于等于b的元素的位置并返回迭代器

upper_bound（）：给定的参数是和lower_bound一样的，不同的是，该函数在a中找到第一个大于b的

算法套路：

创建一个长度26的int类型的数组，保存是对应的ASCII编码，在使用前需要将字母类型- ‘a’，来获取ASCII码

image-20240713165422734

具体手撕可见

4，std::ranges::sort()：C++20后新加入的排序，对于原有的sort排序，二者都可以对嵌套数组进行排序操作，对比元素是每个数组的0号索引位置

image-20240718105454408

典型题目：

leetcode 3 无重复字符的最长子串

image-20240714182233599 image-20240714182315119 
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
int lengthOfLongestSubstring(string s) {
 
		int size = s.size();
		if (size == 0) return 0;
		if (size == 1) return 1;
		std::unordered_map<int, int> m; //key是位置上的值，value是index
		int res = 0;
		int flag = 0;
		int resFalg = 0;
 
		for (size_t i = 0; i < size; i++)
		{
			int tempStr = s[i];
			if (m.find(tempStr) != m.end())
			{
				resFalg = resFalg > flag ? resFalg : flag;
				flag = 1;
				int value = i - m[tempStr];//与题目进行适配
				res = res > value ? res : value;
				//更新这个值的位置
				m[tempStr] = i;
			}
			else
			{
				m[tempStr] = i;
				++flag;
			}
		}
 
		resFalg = resFalg < flag ? flag : resFalg;
		res = res >= resFalg ? res : resFalg;
		return res;
	}

以上演示的是错误示范，在使用flag标记中，考虑到了在返回结果的时候没有找到重复元素，但是没有考虑到查找起始点位，也就是俗称的滑动窗口，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lengthOfLongestSubstring(std::string s) {  
      int size = s.size();  
      if (size == 0) return 0;  
      if (size == 1) return 1;  

      std::unordered_map<char, int> m; // key是字符，value是字符最后出现的位置  
      int maxLength = 0;  
      int start = 0; // 最长子串的起始位置  

      for (size_t i = 0; i < size; i++) {  
          if (m.find(s[i]) != m.end() && m[s[i]] >= start) {  
              // 如果当前字符在之前的子串中出现过，并且位置在当前子串范围内  
              // 更新起始位置为当前字符上一次出现位置的下一个位置  
              start = m[s[i]] + 1;  
          }  
          // 更新当前字符的最后出现位置  
          m[s[i]] = i;  
          // 更新最长子串的长度  
          maxLength = std::max(maxLength, i - start + 1);  
      }  

      return maxLength;  
  }

2，二维数组寻找各行各列最高值

1
2
3
4
5
6
7
// 找出每行和每列的最大值  
	for (int i = 0; i < size; ++i) {
		for (int j = 0; j < size; ++j) {
			rowMax[i] = std::max(rowMax[i], grid[i][j]);
			colMax[j] = std::max(colMax[j], grid[i][j]);
		}
	}

回溯：

1，求子集和分割的解法很像：

分割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
          if (index == n)
{
	res.emplace_back(path);
	return;
}
for (int i = index; i < n; ++i)
{
	if (isPalindrome(s, index, i))
	{
		path.emplace_back(s.substr(index, i - index + 1));
		dfs(i + 1);
		path.pop_back();
	}
}

子集：

1
2
3
4
5
6
7
         res.emplace_back(path);
for (int i = index; i < n; i++)
{
	path.emplace_back(nums[i]);
	dfs(i + 1);
	path.pop_back();
}

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
vector<vector<string>> BackTracking::solveNQueens(int n)
{
	vector<vector<string>> ans;
	vector<int> col(n), on_path(n), diag1(n * 2 - 1), diag2(n * 2 - 1);
	function<void(int)> dfs = [&](int r) {
		if (r == n) {
			vector<string> board(n);
			for (int i = 0; i < n; i++) {
				board[i] = string(col[i], '.') + 'Q' + string(n - 1 - col[i], '.');
			}
			ans.emplace_back(board);
			return;
		}
		for (int c = 0; c < n; c++) {
			int rc = r - c + n - 1;
			if (!on_path[c] && !diag1[r + c] && !diag2[rc]) {
				col[r] = c;
				on_path[c] = diag1[r + c] = diag2[rc] = true;
				dfs(r + 1);
				on_path[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
			}
		}
		};
	dfs(0);
	return ans;

}

n皇后操作其实并不难，只是后来加进去的的皇后棋都会被之前加入的棋子约束，一开始很容易想到在保存使用数组按照点的形式保存下来，但是这之后每次筛查点的时候都需要遍历之前保存的棋子，时间复杂度很高，以上代码给出一种新的方式。

动态规划：

image-20240724152332341

动态规划背包问题常见变形

image-20240724153617434

完全背包优化到最后的结果：

image-20240724185655022

如上图所示：基本处理逻辑仍然是遵循不选和选这一基本操作，只是在memo的上对不需要的数据进行了覆盖处理，

对0索引位置上的数据初始化一个0是为了让当前硬币x就可以组成目前需要的值

VS快捷操作经验：

ctrl + K + O：在头文件和cpp中快速切换

xml注释换行： 将要新一行的内容包裹起来

STL容器

特性

1.对于vector，一开始就规定大小然后使用索引访问要比push_back（）快上很多

常规操作：

1，back()：返回容器中最后一个元素，

2，优先级队列：

以下内容是在优先级队列中使用自定义变量并设置自定义比较标准的示例

1
2
3
4
auto myCompare = [](ListNode* node1, ListNode* node2) {
	return node1->value < node2->value;
	};
std::priority_queue<ListNode*,std::vector<ListNode*>,decltype(myCompare)> heapSortO(myCompare);

以下是优先级队列使用lamba表达式快速构建自定义比较类型的例子，注意，使用greater（greater自带的比较器）是小根堆，即 return i>j；i在参数中是前者

1
priority_queue < pair<int, int>, vector<pair<int, int>>, decltype([](pair<int, int> i, pair<int, int> j) {return i.first > j.first; }) > pq;

用法示例

清空内存

1，在STL中某些容器不提供清空操作的前提下，快速清空指定内存，例如清空栈

1
std::stack<int>().swap(sta); //清空栈

具体的底层内存操作过程如下：

  1. 创建了一个空的临时std::stack<int>对象。
  2. 这个临时对象与sta进行了swap操作，导致sta的内容被清空，而临时对象现在包含了sta原来的内容。
  3. 临时对象在表达式结束时被销毁。销毁过程中，如果临时对象内部有动态分配的内存（例如，std::deque可能会为其元素分配堆内存），则这些内存会被回收（通过调用析构函数和可能的内存释放操作）。但是，请注意，这里的“回收”并不意味着内存被立即返回给操作系统；它可能只是被标记为可重用，以便后续的堆分配可以重用这些内存块。

删除内容：

image-20240720172221617

image-20240720172907972

通过以上内容可以知道：容器在保存node指针的时候类似于在函数传递过程中的形参，构造了一个新的指针并拷贝了原始指针，

因为node的数据是保存在堆上的，所以现在相当于在栈和堆上同时拥有一份指向保存在堆上的node地址的指针，对node值的修改可以做到同步，删除原始指针或者map的都不会对最终的结果产生影响。

所以建议在创建node的时候还是new一个，因为容器最终是要释放掉的

2，特殊操作

==判断内容相等

image-20240716154802788

image-20240716155146719

不熟悉但是重要的特性：

lamba表达式：

auto :自动变量标签

reverse定义变量名

&，=：在中括号内使用这两个参数，编辑器自动捕获需要的内容，捕获的方式分别是引用捕获和值捕获

值捕获：在lamba表达式被创建的时候就完成值的复制，之后对值的修改无影响

引用捕获：顾名思义，和方法的引用传递差不多，但是主要注意调用的时候捕获的值的存在与否之类的问题

1
2
3
4
5
6
7
8
9
10
11
12
    void rotate(vector<int>& nums, int k) {
        auto reverse = [&](int i, int j) {
            while (i < j) {
                swap(nums[i++], nums[j--]);
            }
        };
    int n = nums.size();
    k %= n; // 轮转 k 次等于轮转 k%n 次
    reverse(0, n - 1);
    reverse(0, k - 1);
    reverse(k, n - 1);
}

image-20240718114132322

自我调用的两种形式：

1
2
3
4
5
6
7
8
auto dfs = [&](auto&& dfs, int i) -> void {
	ans.emplace_back(path);
	for (int j = i; j < n; ++j) { // 枚举选择的数字
		path.push_back(nums[j]);
		dfs(dfs, j + 1);
		path.pop_back(); // 恢复现场
	}
	};
1
2
3
4
5
6
7
8
9
10
function<void(int)> dfs = [&](int index)
	{
		res.emplace_back(path);
		for (int i = index; i < n; i++)
		{
			path.emplace_back(nums[i]);
			dfs(i+1);
			path.pop_back();
		}
	};

lamba在使用auto这种不完成的类型进行自我调用的时候需要使用第一种形式，第二种就是完整的调用流程，头文件