18.深度优先遍历
深度优先搜索算法是一种用于遍历或搜索树或图的算法
建立一颗搜索树，沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
子集和问题
子集和问题的一个实例为<S,c>。其中S={x1,x2,…,xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中所有元素的和为c。
全排列问题
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。
N皇后问题
##N皇后（状态压缩）
这里我所习惯的二进制还是右边是第0位开始，这样正好与实际情况相反，所以都要反着来。
逐行放置皇后,首先排除每行有多个皇后互相排斥的情况
用二进制表示状态.1表示该点不能放(与其他位置的皇后排斥或初始状态就不能放).0表示该点可以放皇后
用sta[]来存储初始状态,将’.’位 置为1
dfs保存四个参数:当前行的状态,从左上到右下对角线的状态,从右上到左下对角线的状态,当前为第几行
获取当前哪一位可以放置皇后:将四者取并集(即将四者进行或运算).得到的状态中为0的就可以放置皇后.
为了快速得到可以放置皇后的位置,对上一步得到的状态进行取反.转换成快速得到1的位置.
用树状数组中的lowbit()就可以得到从右向左的第一个1
将状态中的1减掉,继续找下一个1
更新”将是下一行的状态”,由于对角线是斜着影响的,所以左上到右下对角线的状态需要右移一位,右上到左下对角线的状态需要左移一位.
知道当前行的状态全为1时,即每一行都有一个皇后时,ans++;
数独
首先需要从当前能填合法数字最小的位置开始填数字
排除等效冗余:任意一个状态下,我们只需要找一个位置填数即可,而不是找所有的位置和可填的数字.
位运算:很明显这里面check判定很多,我们必须优化这个check,所以我们可以对于,每一行,每一列,每一个九宫格,都利用一个九位二进制数保存,当前还有哪些数字可以填写.
lowbit:我们这道题目当前得需要用lowbit运算取出当前可以能填的数字.
微信打赏