leetcode 困难题 1611. 使整数变为 0 的最少操作次数

Problem: 1611. 使整数变为 0 的最少操作次数通过深度优先搜索函数dfs产出的ret数组可以观察ret数组可以发现要去掉最左侧的1需要pow(2, len -i)次操作而且从左到右不同索引的1索引从1开始奇数累加偶数相减得到最终的答案深度优先搜索超时了的Codeclass Solution { public: string s; int len, mimi INT_MAX; unordered_mapint, int mem; vectorstring tmp, ret; int dfs(int h, int num, bool op1, bool op2) { if(h mimi) return INT_MAX/10; if(num 0) { mimi min(mimi, h); return 0; } if(mem.count(num) ! 0) return mem[num]; int r 0, ans1 INT_MAX, ans2 INT_MAX, mi INT_MAX; while(r len (num(1r))0) r; char ch, ch2; if(!op1) { if(r len || op2) { bitset32 st(num); tmp.push_back(st.to_string()); ans1 dfs(h 1, num ^ (1(r 1)), true, false); tmp.pop_back(); } } if(!op2) { bitset32 st(num); tmp.push_back(st.to_string()); ans2 dfs(h 1, num ^ 1, false, true); tmp.pop_back(); } mi min({ans1, ans2}) 1; mem[num] mi; return mi; } int minimumOneBitOperations(int n) { if(n0) return 0; if(n1) return 1; bitset32 nn(n); s nn.to_string(); int l 0; while(l32 s[l]0) l; s s.substr(l); len (int)s.size(); int count 0, sum 0, tp; for(int i 0; i len; i) { if(s[i]1) { count; tp pow(2, len - i) - 1; if((count1)1) sum tp; else sum - tp; } } // int answer dfs(0, n, false, false); return sum; } };