【 数据结构 & 算法 】—— 回溯、递归、分治（更新中）
2020-10-27 本文已影响0人
Du1in9
< 思维导图 >
预备知识：递归 ，回溯（★）
- Recursive function.cpp
#include <stdio.h>
void compute_sum_3(int i, int &sum){
sum += i; // sum = 3 + 3
}
void compute_sum_2(int i, int &sum){
sum += i; // sum = 1 + 2
compute_sum_3(i + 1, sum);
}
void compute_sum_1(int i, int &sum){
sum += i; // sum = 0 + 1
compute_sum_2(i + 1, sum);
}
int main(){
int sum = 0;
compute_sum_1(1, sum);
printf("sum = 0 + 1 + 2 + 3 = %d", sum);
return 0;
}
- Recursive function 2.cpp
#include <stdio.h>
void compute_sum(int i, int &sum){
if (i > 3){
return;
}
sum += i;
compute_sum(i + 1, sum);
}
int main(){
int sum = 0;
compute_sum(1, sum);
printf("sum = 0 + 1 + 2 + 3 = %d", sum);
return 0;
}
- Recursive function 3.cpp
#include <stdio.h>
#include <vector>
// 链表数据结构
struct ListNode {
int val;
ListNode *next;
ListNode (int x): val(x), next(NULL) { }
};
// 递归将 head 指针的节点数据域 val 存到 vec
void add_to_vector (ListNode *head, std::vector<int> &vec) {
// 若 head 为空，结束递归
if (!head) {
return;
}
vec.push_back (head->val);
add_to_vector (head->next, vec);
}
int main() {
ListNode a(1), b(2), c(3), d(4), e(5);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
std::vector<int> vec;
add_to_vector (&a, vec);
for (int i = 0; i < vec.size(); i++) {
printf("[%d] ", vec[i]);
}
return 0;
}
vector 是向量类型，可以容纳许多类型的数据，也被称为容器
vector 可以理解为动态数组，是封装好了的类
vector 进行操作前应添加头文件 #include <vector>
- Circulation function.cpp
#include <stdio.h>
#include <vector>
int main() {
std::vector<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
// 生成子集的数组
std::vector<int> item;
// 最终结果的数组
std::vector< std::vector<int> > result;
// i=0 时，item = [1]
// i=1 时，item = [1,2]
// i=2 时，item = [1,2,3]
for (int i = 0; i < nums.size(); i++) {
item.push_back(nums[i]);
result.push_back(item);
}
// result = [[1], [1,2], [1,2,3]]
for (int i = 0; i < result.size(); i++) {
for (int j = 0; j < result[i].size(); j++) {
printf("[%d] ",result[i][j]);
}
printf("\n");
}
return 0;
}
预备知识：位运算（★）
- Bit operation function.cpp
一、求子集（ 回溯 ，位运算 ）（★★）
① 回溯法
- LeetCode 78.Subsets.cpp
#include <stdio.h>
#include <vector>
class Solution{
private:
void generate(int i, std::vector<int> &nums,
std::vector<int> &item,
std::vector<std::vector<int> > &result){
// 递归结束条件
if(i >= nums.size()){
return;
}
item.push_back(nums[i]);
// 将当前子集 push 入 result
result.push_back(item);
// 第一次调用递归
generate(i+1, nums, item, result);
item.pop_back();
// 第二次调用递归
generate(i+1, nums, item, result);
}
public:
std::vector<std::vector<int> > subsets(std::vector<int> &nums){
// 存储最终结果的 result
std::vector<std::vector<int> > result;
// 回溯时，产生各个子集的数组 item
std::vector<int> item;
// 将空子集 push 入 result
result.push_back(item);
// 计算各个子集
generate(0, nums, item, result);
return result;
}
};
int main() {
std::vector<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4);
nums.push_back(5);
nums.push_back(6);
Solution solve;
std::vector<std::vector<int> > result = solve.subsets(nums);
for (int i = 0; i < result.size(); i++) {
printf("[ ");
for (int j = 0; j < result[i].size(); j++) {
printf("%d ", result[i][j]);
}
printf("]\n");
}
return 0;
}
