前言说明
算法学习，日常刷题记录。
题目连接
题目内容
给定正整数N，我们按任何顺序(包括原始顺序)将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到2的幂，返回true；否则，返回false。
示例1:
输入：1
输出：true
示例2:
输入：10
输出：false
示例3:
输入：16
输出：true
示例4:
输入：24
输出：false
示例5:
输入：46
输出：true
提示:
1 <= N <= 10^9
分析过程
这里介绍两种方法，方法1，直线思维分析，容易理解，但是运行超时，不建议使用；方法2，开辟新思路，运行高效，建议使用。
方法1
思路：先判断一次数字本身是否为2的幂，若是2的幂，直接返回true，结束程序；否则，通过不断对10取余和除以10获取到每个位的数字，保存到列表中，对列表的下标进行全排列，获得全排列结果列表，遍历全排列的结果列表，逐个判断是否是2的幂，若有一个是2的幂，那么返回true，结束程序，若没有一个是2的幂，那么最后返回false，结束程序。
第一步
先判断一次原来的数字是否是2的幂，直接使用n >= 1 && (n & (n - 1)) == 0来判断，若这个条件成立，那么数字是2的幂，直接返回true，结束程序，否则继续程序。
为什么n >= 1 && (n & (n - 1)) == 0能判断出数字是否是2的幂？
请参考之前的文章：LeetCode刷题-2的幂
打开文章后，找到"方法2"，里面有提到如何推导出使用n >= 1 && (n & (n - 1)) == 0来判断一个数字是否是2的幂。
第二步
定义列表list，保存数字每个位的数字，通过不断对10取余和除以10，把数字每个位的数字保存进列表list中。
第三步
对数字每个位的数字进行全排列，调用全排列函数获取到结果列表dataList。
第四步
进行全排列时，利用递归和回溯算法，想象成树，遍历列表list就是以哪个元素开头，用一个列表保存每次排列的结果，找到一次结果后删除最后元素进行回溯，逐步向上回溯。
注意：这里进行全排列时，是对列表list中各个元素的下标进行全排列，不是对列表list中各个元素进行全排列，而下标是不会重复的。
第五步
全排列结束后，遍历结果列表dataList，逐个判断是否存在2的幂，判断时，前导数字不能为零，把列表中各个位的数字不断乘以对应的10的幂，然后累加得到重新排序的数字，再通过前面的介绍方法判断数字是否为2的幂，使用n >= 1 && (n & (n - 1)) == 0来判断，如果有一个重新排序后的数字是2的幂，那么返回true，结束程序，否则返回false，结束程序。
解答代码
class Solution {
public boolean reorderedPowerOf2(int n) {
// 思路：先判断一次数字本身是否为2的幂，若是2的幂，直接返回true，结束程序；否则，通过不断对10取余和除以10获取到每个位的数字，保存到列表中，对列表的下标进行全排列，获得全排列结果列表，遍历全排列的结果列表，逐个判断是否是2的幂，若有一个是2的幂，那么返回true，结束程序，若没有一个是2的幂，那么最后返回false，结束程序
if (n >= 1 && (n & (n - 1)) == 0) {
// 先判断一次原来的数字是否是2的幂
return true;
}
// 定义列表，保存数字每个位的数字
List<Integer> list = new ArrayList<>();
// 不断对10取余，然后除以10，把数字每个位的数字保存进列表中
while (n > 0) {
list.add(n % 10);
n /= 10;
}
// 定义结果列表
List<List<Integer>> dataList = new ArrayList<>();
// 定义每种顺序的下标列表
List<Integer> indexList = new ArrayList<>();
// 对列表下标进行全排列，初始层数0
arrange(dataList, indexList, list, 0);
// 遍历结果列表，判断是否存在2的幂
for (List<Integer> data : dataList) {
// 前导数字不能为零
if (list.get(data.get(0)) != 0) {
// 定义列表中数字组成的数字
int num = 0;
// 定义位
int e = 1;
// 列表中各位的数字转为数字
for (int i = data.size() - 1; i >= 0; --i) {
num += list.get(data.get(i)) * e;
e *= 10;
}
// 判断是否是2的幂，若存在2的幂，返回true
if (num >= 1 && (num & (num - 1)) == 0) {
return true;
}
}
}
// 若遍历完结果列表也没有找到2的幂，那么返回false
return false;
}
// 全排列函数，递归，回溯算法
// 想象成树，遍历列表list就是以哪个元素开头，用一个列表保存每次排列的结果，找到一次结果后删除最后元素进行回溯，逐步向上回溯
private void arrange(List<List<Integer>> dataList, List<Integer> indexList, List<Integer> list, int n) {
if (n == list.size()) {
// 若层数达到了列表list的长度，结果列表添加元素，结束函数
dataList.add(new ArrayList<>(indexList));
return;
}
// 遍历数组nums
for (int i = 0; i < list.size(); ++i) {
if (indexList.contains(i)) {
// 重复元素不添加，直接跳过
continue;
}
// 每条结果列表添加元素，这里保存的是下标
indexList.add(i);
// 递归调用，n增加一层
arrange(dataList, indexList, list, n + 1);
// 每条结果列表去掉最后一个元素，进行回溯
indexList.remove(indexList.size() - 1);
}
}
}
提交结果
执行程序后，提示超出时间限制。
运行结果
方法2
因为方法1运行超时，所以想出方法2，方法2改变思路，不进行全排列，使用其他的思路。
思路：预处理+哈希集合，因为范围是1 <= N <= 10^9，这个范围内2的幂也没有多少个，可以先列举出来，记录每个2的幂中各种数字出现的次数，利用计数排序的思想记录次数，因为数字的范围是0-9，所以定义一个长度为10的字符数组，在数组对应的下标的元素里记录数字出现的次数，再把字符数组保存成字符串，把字符串放到哈希集合中，最后用同样的方法统计n中各种数字出现的次数，得到一个字符串，如果这个字符串在哈希集合中能找到，那么代表n中的数字可以通过重新排序得到2的幂，否则不能。
第一步
同样先判断一次原来的数字是否是2的幂，直接使用n >= 1 && (n & (n - 1)) == 0来判断，若这个条件成立，那么数字是2的幂，直接返回true，结束程序，否则继续程序。
请参考之前的文章：LeetCode刷题-2的幂
第二步
定义哈希集合countDigitSet，保存范围内所有2的幂中各种数字出现的次数，用字符串表示。
从1开始，每次乘以2，也就是位向左移动1位，然后统计这个数字中各位的各种数字出现的次数，把结果转成字符串，通过调用函数countDigit实现，保存字符串到哈希集合countDigitSet中。
第三步
函数countDigit的作用：输入一个数字，统计这个数字中各位的各种数字出现的次数，把结果转成字符串返回。
定义长度为10的字符数组result，因为数字的范围是0-9，利用计数排序的思想记录次数，在数组对应的下标的元素里记录数字出现的次数。
循环，数字n不断对10取余，不断除以10，逐个得到各个位上的数字。
每次循环时：
通过当前位的数字找到对应的下标，此下标的元素记录数字出现次数，每次加1，这样就能确定每个数字出现的次数。
除以10，直到缩小到0，结束循环。
结束循环后，字符数组result转为字符串，返回结果，结束函数countDigit。
第四步
同样统计n中各位的各种数字出现的次数，把结果转成字符串，若这个字符串在哈希集合中能找到，那么代表n中的数字可以通过重新排序得到2的幂，返回true；否则不能，返回false。
解答代码
class Solution {
public boolean reorderedPowerOf2(int n) {
// 思路：预处理+哈希表，此方法比较高效，因为范围是1 <= N <= 10^9，这个范围内2的幂也没有多少个，可以先列举出来，记录每个2的幂中各种数字出现的次数，利用计数排序的思想记录次数，因为数字的范围是0-9，所以定义一个长度为10的字符数组，在数组对应的下标的元素里记录数字出现的次数，再把字符数组保存成字符串，把字符串放到哈希表中，最后用同样的方法统计n中各种数字出现的次数，得到一个字符串，如果这个字符串在哈希表中能找到，那么代表n中的数字可以通过重新排序得到2的幂，否则不能
if (n >= 1 && (n & (n - 1)) == 0) {
// 先判断一次原来的数字是否是2的幂
return true;
}
// 定义哈希表，保存范围内所有2的幂中各种数字出现的次数，用字符串表示
Set<String> countDigitSet = new HashSet<>();
// 从1遍历到10^9，找出范围所有2的幂
for (int i = 1; i <= 1e9; i <<= 1) {
// 从1开始，每次乘以2，也就是位向左移动1位，然后统计这个数字中各位的各种数字出现的次数，把结果转成字符串，保存到哈希表中
countDigitSet.add(countDigit(i));
}
// 同样统计n中各位的各种数字出现的次数，把结果转成字符串，若这个字符串在哈希表中能找到，那么代表n中的数字可以通过重新排序得到2的幂，否则不能
return countDigitSet.contains(countDigit(n));
}
// 输入一个数字，统计这个数字中各位的各种数字出现的次数，把结果转成字符串返回
private String countDigit(int n) {
// 定义长度为10的字符数组，因为数字的范围是0-9，利用计数排序的思想记录次数，在数组对应的下标的元素里记录数字出现的次数
char[] result = new char[10];
// 循环，数字n不断对10取余，不断除以10，逐个得到各个位上的数字
while (n > 0) {
// 通过当前位的数字找到对应的下标，此下标的元素记录数字出现次数，每次加1
++result[n % 10];
// 除以10，直到缩小到0
n /= 10;
}
// 字符数组转为字符串
return new String(result);
}
}
提交结果
执行用时1ms，时间击败97.93%的用户，内存消耗35.7MB，空间击败24.48%的用户。
运行结果
原文链接
原文链接：重新排序得到2的幂
网友评论