数与位(一)
大家好！我是小笙！字符串(三)系列落下帷幕，开始新的征程数与位!大家一起加油呀!!
数与位(一)系列题型如下
数与位系列一
数与位（231,504,263,461,172）
231. 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。
如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：
输入：n = 3
输出：false
示例 4：
输入：n = 4
输出：true
示例 5：
输入：n = 5
输出：false
提示：
-231 <= n <= 231 - 1
方法一 简单解法（MyCode）
2 的幂有一个特点就是一直整除2得到的最后的结果一定是1
所以解法很简单如下
class Solution {
public boolean isPowerOfTwo(int n) {
while(n%2 == 0 && n != 0) n = n/2;
return n == 1;
}
}
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.5 MB, 在所有 Java 提交中击败了34.87%的用户
方法二位运算 (Other’s04Code)
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
504. 七进制数
给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。
示例 1:
输入: num = 100 输出: “202” whisum
示例 2:
输入: num = -7 输出: “-10”
提示：
-107 <= num <= 107
方法一 栈（MyCode）
解题思路:
我觉得对于转换几进制，最后还需要进行倒序
所以我采用了栈的方式出栈入栈进行倒序输出
class Solution {
public String convertToBase7(int num) {
String sum = "";
int count = 0; // 记录入栈数，方便倒数输出
Stack<String> s1 = new Stack<String>();
if(num >= 0){
while(num/7!=0){
s1.push(String.valueOf(num%7));
num = num/7;
count++;
}
s1.push(String.valueOf(num%7));
count++;
}else{
num = -num;
while(num/7!=0){
s1.push(String.valueOf(num%7));
num = num/7;
count++;
}
s1.push(String.valueOf(num%7));
s1.push("-");
count += 2;
}
for(int i=count-1;i>=0;i--){
sum += s1.pop();
}
return sum;
}
}
方法二 递归形式（Other’sCode）
int转String有三种方式
(1)num + “”
(2)String.valueOf(num)
(3)Integer.toString(num)
class Solution {
public String convertToBase7(int num) {
if (num < 0) return "-" + convertToBase7(-1 * num); // 实现正负的检测
if (num < 7) return Integer.toString(num); // 转换成字符串
return convertToBase7(num / 7) + Integer.toString(num % 7); // 实现倒序关键，秒！
}
}
方法三 迭代形式（Other’sCode）
(char)(num % 7 + ‘0’) 的含义(num%7)字符
num % 7 + ‘0’ 将num%7变成字符串
class Solution {
public String convertToBase7(int num) {
if (num == 0) return "0";
boolean sign = (num >= 0); // 判断正负
StringBuilder ans = new StringBuilder(); // 定义可变长度的字符串
num = Math.abs(num); // 取绝对值
while (num != 0) {
ans.append((char)(num % 7 + '0'));
num /= 7;
}
if (!sign) ans.append('-');
return ans.reverse().toString(); // 函数反转
}
}
263. 丑数
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 6
输出：true
解释：6 = 2 × 3
示例 2：
输入：n = 8
输出：true
解释：8 = 2 × 2 × 2
示例 3：
输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
示例 4：
输入：n = 1
输出：true
解释：1 通常被视为丑数。
提示：
-231 <= n <= 231 - 1
方法一：暴力解法(MyCode)
代码很简单就是判断是否能被2，3，5整除
class Solution {
public boolean isUgly(int n) {
if(n == 0) return false;
while(n != 1){
if(n%2 == 0){
n = n/2;
}else if(n%3 == 0){
n = n/3;
}else if(n%5 == 0){
n = n/5;
}else{
return false;
}
}
return true;
}
}
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.1 MB, 在所有 Java 提交中击败了95.67%的用户
方法二：数学(Other’sCode)
class Solution {
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
int[] factors = {2, 3, 5};
for (int factor : factors) { // 精妙之处!
while (n % factor == 0) {
n /= factor;
}
}
return n == 1;
}
}
461. 汉明距离
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
示例 2：
输入：x = 3, y = 1
输出：1
提示：
0 <= x, y <= 231 - 1
方法一: 比较（MyCode）
我看到这道题的想法就是首先要获得二进制的字符串，才可以进行比较
所以我写了一个方法 public String CountOne(int num){}
但是转换出来的二进制长度不一定相同
我们分成两段比较
1.就是取最短的二进制字符串的长度作为比较长度
2.然后再把长度长的字符串超出部分和1进行比较
class Solution {
public int hammingDistance(int x, int y) {
String m = CountOne(x),n = CountOne(y);
int count = 0;
if(m.length()>n.length()){
for(int i = 0;i<n.length();i++){
if(m.charAt(i) != n.charAt(i)){
count++;
}
}
for(int j=n.length();j<m.length();j++){
if(m.charAt(j) == '1'){
count++;
}
}
}else{
for(int i = 0;i<m.length();i++){
if(m.charAt(i) != n.charAt(i)){
count++;
}
}
for(int j=m.length();j<n.length();j++){
if(n.charAt(j) == '1'){
count++;
}
}
}
return count;
}
public String CountOne(int num){ // 将数字转换成二进制字符串返回 这里的二进制都是倒序的
String sum = "";
while(num/2>0){
sum += String.valueOf(num%2);
num = num/2;
}
sum += String.valueOf(num%2);
return sum;
}
}
方法二：内置位计数功能（Other’sCode）
大多数编程语言都内置了计算二进制表达中 11 的数量的函数。在工程中，我们应该直接使用内置函数。
class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
方法三：移位实现位计数（Other’sCode）
// ^ 如果相对应位值相同，则结果为0，否则为1
// ＆ 如果相对应位都是1，则结果为1，否则为0
// >> 按位右移运算符。左操作数按位右移右操作数指定的位数
class Solution {
public int hammingDistance(int x, int y) {
int s = x ^ y, ret = 0;
while (s != 0) {
ret += s & 1;
s >>= 1;
}
return ret;
}
}
172. 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
示例 1：
输入：n = 3 输出：0 解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5 输出：1 解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0 输出：0
提示：
0 <= n <= 104
方法一:寻找5（Other’s Code）
这道题更考验问题本质，太难想到解法了！
核心思路就是寻找5的因子个数（因为5和一个偶数相乘等于0，偶数数量远远大于5，所以5的个数就是0的个数）
5 15 1个5
10 25 1个5
15 35 1个5
…
25 55 2个5
30 56 1个5
…
125 55*5 3个5
…
5 10 15 20 算第一层
25 30 35 … 120 算第二层
125 130 135 … 555*5-5 算第三层
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while (n > 0) { // 决定层数 每加一层5的个数再加1
count += n / 5; // 决定每层有几个5
n = n / 5;
}
return count;
}
}