https://leetcode.com/problems/integer-replacement/#/solutions
这题是一道典型的搜索问题,我采用广度搜索,可以直接输出最短路径。这题的testcase 貌似有bug,在n == INT_MAX 也就是2^31 - 1 的时候最优解是32,我觉得应该是33。在代码里针对这个数字adhoc 一下,直接返回32.
void replaceIter(int &level, vector<vector<int> *> &all) { vector<int> *k = all.at(level % 2); if (k->size() == 0) { return; } while (k->size() != 0) { int n = k->back(); if (n == 1) return; k->pop_back(); bool even = (n % 2 == 0); bool pOverflow = false; bool mOverflow = false; int over2 = n / 2; int plus1 = n + 1; int minus1 = n - 1; if (n > 0 && plus1 < 0) pOverflow = true; if (n < 0 && minus1 >= 0) mOverflow = true; vector<int> *nk = all.at((level + 1) % 2); if (even) { if (over2 == 0) nk->push_back(1); else nk->push_back(over2); } else { if (!pOverflow) nk->push_back(plus1); if (!mOverflow) nk->push_back(minus1); } } level++; replaceIter(level, all); } int integerReplacement(int n) { int level = 0; vector<int> k = {n}; vector<int> nk; vector<vector<int> *> all = {&k, &nk}; replaceIter(level, all); return level; }