題目鏈接：https://leetcode-cn.com/problems/reordered-power-of-2/

---

題目

給定正整數 N ，我們按任何順序（包括原始順序）將數字重新排序，注意其前導數字不能為零。

如果我們可以通過上述方式得到 2 的冪，返回 true；否則，返回 false。

示例 1：
輸入：1
輸出：true

示例 2：
輸入：10
輸出：false

示例 3：
輸入：16
輸出：true

示例 4：
輸入：24
輸出：false

示例 5：
輸入：46
輸出：true

提示：
1 <= N <= 10^9

---

解法：數據量比較小，dfs回溯即可。

---

class Solution { private:bool res = false;int vis[10] = {0}; // 某個數所有數字的出現次數；不用bool的原因是，數字可以重復int len = 0; // 數字的位數unordered_map<int, int>um;public:bool reorderedPowerOf2(int n) {// 構建集合匹配for (int i = 1; i < (int)1e9+10; i *= 2) {um[i] = 1;}// 求這個數中所有數字的出現次數while(n) {vis[n%10]++;n /= 10;len++;}// 回溯dfs(0, 0);return res;}void dfs(int step, int cur) {if (step == len) {if (um[cur] == 1) { // 為1，證明是2的冪res = true;}}// 全量遍歷的狀態for (int i = 0; i < 10; i++) {if (vis[i] > 0) {vis[i]--;if (i != 0 || cur != 0) {dfs(step + 1, cur * 10 + i);}vis[i]++;}}} };

總結

以上是生活随笔為你收集整理的Leecode 869. 重新排序得到 2 的幂——Leecode每日一题系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。