LeeCode 1611 DFS

题意

传送门 LeeCode 1611. 使整数变为 0 的最少操作次数

题解

先考虑基本变换，定义 $F(i)$ 为使 $0$ 变为 $2^i$ 或使 $2^i$ 变为 $0$ 的操作次数，那么需要 $F(i-1)$ 次操作使将 $0$ 变为 $2^{i-1}$，将 $i$ 位异或 $1$ 后，在通过 $F(i-1)$ 次操作使 $2^{i-1}$ 变为 $0$。则有 $$\{\begin{array}{l}F(i)=2F(i-1)+1\\ F(0)=1\end{array}$$ 求解得到 $F(i)=2^{i+1}-1$。

目标是将高位的 $1$ 翻转，参照基本变换，定义 $f(n)$ 为使 $n$ 变为 $0$ 的操作次数，定义 $g(n,p)$ 为使 $n$ 变为 $p$ 位为 $1$ 其余位为 $0$，即 $1000\dots$ 形式的操作次数。对于 $f(n)$，首先需要将低位转换为 $1000\dots$ 的形式，翻转高位，再将低位转换为 $0$；对于 $g(n,p)$，若 $p$ 位为 $1$ 那么需要将低位转换为 $0$，否则将低位转换为 $1000\dots$ 翻转高位，再将低位转换为 $0$。

class Solution { public: int f(int n) { if (!n) { return 0; } int p; for (int i = 30; i >= 0; i--) { if ((n >> i) & 1) { p = i; break; } } return (1 << p) + g(n ^ (1 << p), p - 1); } int g(int n, int p) { if (p == -1) { return 0; } if ((n >> p) & 1) { return f(n ^ (1 << p)); } return (1 << p) + g(n, p - 1); } int minimumOneBitOperations(int n) { return f(n); } };