在刚开始学习代码时,我们通常会创建一个数组或者map来标记一些我们已经选择过的值或者对象。但是在面对一些路径问题,组合问题,且处理的对象数量较少时,数组不仅不方便且要
在刚开始学习代码时,我们通常会创建一个数组或者map来标记一些我们已经选择过的值或者对象。但是在面对一些路径问题,组合问题,且处理的对象数量较少时,数组不仅不方便且要浪费一定内存。
状态压缩面对以上问题,我们可以利用一个二进制数state来代表所走的路径或者组合方案,每一位数就代表着一个元素。
例如:有A B C D E5个元素 我们用 5位的二进制数来代表 这5个元素 ① 当A被选取时 二进制数状态:00001
② 当A,B同时被选取时 二进制数状态:00011
于是我们可以推导出以下式子
/**查看元素k是否被选取**/int n = (state>>k)n == 1; //已被选取n == 0; //未被选取/**查看元素k选择前的状态**/state = state^(1< 于是我们便可以借助状态压缩来处理一些路径问题以及组合问题 526.优美的排列847.访问所有节点的最短路径