回溯算法 问题
类型
题目链接
子集、组合
子集、子集 II、组合、组合总和、组合总和 II
全排列
全排列、全排列 II、字符串的全排列、字母大小写全排列
搜索
解数独、单词搜索、N皇后、分割回文串、二进制手表
参考力扣解法C++ java
解题思路 ①递归树
总结：可以发现“排列”类型问题和“子集、组合”问题不同在于：“排列”问题使用used数组来标识选择列表，而“子集、组合”问题则使用start参数
1、不用中间变量,用两种方法交换A和B的值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 void swap (int a, int b) int temp = a; a = b; b = temp; } void swap (int a, int b) a = a + b; b = a - b; a = a - b; } void swap (int a, int b) a = a ^ b; b = a ^ b; a = a ^ b; }
2、求最大公约数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int maxCommonDivisor(int a , int b ) { int max = 0 ; for (int i = 1 ; i <=b; i++) { if (a % i == 0 && b % i == 0 ) { max = i; } } return max; } int maxCommonDivisor(int a , int b ) { int r; while (a % b > 0 ) { r = a % b; a = b; b = r; } return b; }
3、模拟栈操作
栈是一种数据结构，特点：先进后出 -
练习：使用全局变量模拟栈的操作
#include <stdio.h>
//保护全局变量：在全局变量前加static后，这个全局变量就只能在本文件中使用
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 void push (int x assert(!full()); data[count++] = x; } int pop () assert(!empty()); return data[--count]; } int top () assert(!empty()); return data[count-1 ]; } bool full () if (count >= 1024 ) { return 1 ; } return 0 ; } bool empty () if (count <= 0 ) { return 1 ; } return 0 ; } int main () for (int i = 1 ; i <= 10 ; i++) { push(i); } while (!empty()){ printf("%d " , top()); pop(); } printf("\n" ); return 0 ; }
4、排序算法 选择排序、冒泡排序、插入排序三种排序算法可以总结为如下：
1.选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。
2.冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。
3.插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。
4.1、选择排序
【选择排序】：最值出现在起始端
第1趟：在n个数中找到最小(大)数与第一个数交换位置
第2趟：在剩下n-1个数中找到最小(大)数与第二个数交换位置
重复这样的操作…依次与第三个、第四个…数交换位置
第n-1趟，最终可实现数据的升序（降序）排列。
1 2 3 4 5 6 7 8 9 10 11 void selectSort(int *arr, int length ) { for (int i = 0 ; i < length - 1 ; i++) { for (int j = i + 1 ; j < length ; j++) { if (arr[i] > arr[j]) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } }
4.2、冒泡排序
【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾
第1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n个元素位置
第2趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n-1个元素位置
…… ……
第n-1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第2个元素位置
1 2 3 4 5 6 7 8 9 10 11 void bublleSort(int *arr, int length ) { for (int i = 0 ; i < length - 1 ; i++) { for (int j = 0 ; j < length - i - 1 ; j++) { if (arr[j] > arr[j+1 ]) { int temp = arr[j]; arr[j] = arr[j+1 ]; arr[j+1 ] = temp; } } } }
#### 5、折半查找（二分查找） 折半查找：优化查找时间（不用遍历全部数据）
1> 数组必须是有序的
2> 必须已知min和max（知道范围）
3> 动态计算mid的值，取出mid对应的值进行比较
4> 如果mid对应的值大于要查找的值，那么max要变小为mid-1
5> 如果mid对应的值小于要查找的值，那么min要变大为mid+1
// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int findKey(int *arr, int length , int key) { int min = 0 , max = length - 1 , mid ; while (min <= max ) { mid = (min + max ) / 2 ; if (key > arr[mid ]) { min = mid + 1 ; } else if (key < arr[mid ]) { max = mid - 1 ; } else { return mid ; } } return -1 ; }
6、集合结构 线性结构 树形结构 图形结构
1.1、集合结构 说白了就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 这个很简单
1.2、线性结构 说白了就是一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可以是值的 相当于一条线被分成了好几段的样子 （发挥你的想象力）。 线性结构是一对一的关系
1.3、树形结构 说白了 做开发的肯定或多或少的知道xml 解析 树形结构跟他非常类似。也可以想象成一个金字塔。树形结构是一对多的关系
1.4、图形结构 这个就比较复杂了。他呢 无穷。无边 无向（没有方向）图形机构 你可以理解为多对多 类似于我们人的交集关系
7、数据结构的存储 数据结构的存储一般常用的有两种 顺序存储结构 和 链式存储结构
发挥想象力啊。 举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 举例说明啊。 栈。做开发的都熟悉。栈是先进后出 ，后进先出的形式 对不对 ？！他的你可以这样理解
hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储 再比如 队列 ，队列是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的
再次发挥想象力 这个稍微复杂一点 这个图片我一直弄好 ，回头找美工问问，再贴上 例如 还是一个数组
1-2-3-4-5-6-7-8-9-10 链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1（地址） 1后面跟着的这个地址指向的是2，2后面的地址指向的是3，3后面的地址指向是谁你应该清楚了吧。他执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储的时候就是完全随机的。明白了？！
8、单向链表\双向链表\循环链表 还是举例子。理解最重要。不要去死记硬背 哪些什么。定义啊。逻辑啊。理解才是最重要滴
A->B->C->D->E->F->G->H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉着跑
数组和链表区别：
循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。发挥想象力 A->B->C->D->E->F->G->H->A. 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论知识。
9、二叉树／平衡二叉树
树形结构下,两个节点以内 都称之为二叉树 不存在大于2 的节点 分为左子树 右子树 有顺序 不能颠倒 ，懵逼了吧，你肯定会想这是什么玩意，什么左子树右子树 ，都什么跟什么鬼？ 现在我以普通话再讲一遍，你把二叉树看成一个人 ，人的头呢就是树的根 ，左子树就是左手，右子树就是右手，左右手可以都没有（残疾嘛，声明一下，绝非歧视残疾朋友，勿怪，勿怪就是举个例子，i am very sorry） , 左右手呢可以有一个，就是不能颠倒。这样讲应该明白了吧
二叉树有五种表现形式
1.空的树（没有节点）可以理解为什么都没 像空气一样
二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到
