力扣刷题篇之数与位1

系列文章目录

---

目录

系列文章目录

前言

一、进制转换

 

总结

---

前言

本系列是个人力扣刷题汇总，本文是数与位。刷题顺序按照[力扣刷题攻略] Re：从零开始的力扣刷题生活 - 力扣（LeetCode）

---

一、进制转换

67. 二进制求和 - 力扣（LeetCode）

主要思路是从二进制串的最低位（右边）开始，逐位相加，使用 carry 变量来处理进位。在遍历的过程中，分别处理相等和不相等的情况，并更新结果数组。最后，检查最高位是否有进位，若有，则在结果数组的最前面加上进位。最终返回相加的结果。

注意，在Java中，如果你创建一个字符串数组但还没有为元素分配具体的值，那么数组的元素将被初始化为 null。

class Solution {
    public static String addBinary(String a, String b) {
        // 保持a的长度大于等于b的长度，方便处理
        if (a.length() < b.length()) {
            return addBinary(b, a);
        }
        
        // 创建一个字符数组来保存相加的结果，长度为a.length() + 1
        char[] sum = new char[a.length() + 1];
        int indexA = a.length() - 1, diffLen = a.length() - b.length();
        char carry = '0';  // 进位初始为0
        
        // 从右往左遍历a的每一位
        while (indexA > -1) {
            // 获取b的相应位，如果b的长度小于a，超出部分视为0
            char bitB = indexA - diffLen > -1 ? b.charAt(indexA - diffLen) : '0';
            
            // 判断当前位与进位的情况，更新相应位置的值和进位
            if (a.charAt(indexA) == bitB) {
                sum[indexA-- + 1] = carry;
                carry = bitB;
            } else {
                sum[indexA-- + 1] = carry == '0' ? '1' : '0';
            }
        }
        
        // 处理最高位的进位
        sum[0] = carry;
        
        // 返回相加的结果，去掉可能多余的前导零
        return carry == '1' ? new String(sum, 0, a.length() + 1) : new String(sum, 1, a.length());
    }
}

 504. 七进制数 - 力扣（LeetCode）

把十进制变成七进制：

这个我想得太繁琐了 

class Solution {
    public String convertToBase7(int num) {
        // 如果数字的绝对值小于7，直接返回数字的字符串表示
        if (Math.abs(num) < 7) {
            return Integer.toString(num);
        }
 
        // 判断数字的正负性
        boolean isPos = true;
        if (num < 0) {
            isPos = false;
        }
        num = Math.abs(num);
 
        // 计算数字的位数
        int temp = num;
        int count = 0;
        while (temp / 7 > 0) {
            count++;
            temp /= 7;
        }
 
        // 创建数组来存储7进制的每一位数字
        int[] res = new int[count + 1];
        for (int i = count; i >= 0; i--) {
            // 计算并存储当前位的数字
            res[count - i] = num / (int) Math.pow(7, i);
            num = num - (num / (int) Math.pow(7, i)) * (int) Math.pow(7, i);
        }
 
        // 使用StringBuilder拼接数组中的数字
        StringBuilder result = new StringBuilder();
        for (int digit : res) {
            result.append(digit);
        }
 
        // 返回结果，如果原始数字为负数，则加上负号
        return isPos ? result.toString() : "-" + result.toString();
    }
}

不如，取余的，不断更新num，然后翻转

class Solution {
    public String convertToBase7(int num) {
        if(num == 0) return "0";
        boolean isN = num < 0;
        if(isN) {
            num = -num;
        }
        StringBuilder sb = new StringBuilder();
        while(num > 0) {
            sb.append(num % 7);
            num /= 7;
        }
        if(isN) {
            sb.append("-");
        }
        return sb.reverse().toString();
    }
}

  

当然，也可以，抽象的哈哈哈哈（一个简单题越搞越多）

Java内置的 Integer.toString(int i, int radix) 方法，它可以将整数 i 转换为指定基数（radix）的字符串表示。在这里，基数是7，所以它直接实现了将整数转换为7进制字符串的功能。这是一种更简洁的实现方式，避免了手动计算每一位数字和使用循环的繁琐过程。

class Solution {
    public String convertToBase7(int num) {
        return Integer.toString(num, 7);
    }
}

405. 数字转换为十六进制数 - 力扣（LeetCode）

经过上一题启示，先用秀的方法

Java 内置的 Integer.toHexString(int num) 方法，该方法用于将整数转换为十六进制字符串。

class Solution {
    public String toHex(int num) {
        return Integer.toHexString(num);
    }
}

 

 

 使用了位运算和循环，从高位到低位依次取出每个四位二进制数的值，然后将其转换为对应的十六进制字符。最终，将这些字符拼接起来形成最终的十六进制字符串。

这个位运算很有意思：

class Solution {
    public String toHex(int num) {
        // 如果 num 为 0，直接返回 "0"
        if (num == 0) {
            return "0";
        }
 
        // 用于拼接十六进制字符串的 StringBuffer
        StringBuffer sb = new StringBuffer();
 
        // 从高位到低位遍历每个四位二进制数
        for (int i = 7; i >= 0; i--) {
            // 取出当前四位二进制数的值
            int val = (num >> (4 * i)) & 0xf;
 
            // 如果 StringBuffer 非空或者当前值大于 0，则将当前值添加到 StringBuffer 中
            if (sb.length() > 0 || val > 0) {
                // 将数字转换为十六进制字符
                char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
                sb.append(digit);
            }
        }
 
        // 返回最终的十六进制字符串
        return sb.toString();
    }
}

妙：先将 temp 不断右移，直到变为 0，这样可以得到与 num 二进制表示相同位数的全1的数。然后通过异或操作，将 num 的每一位取反，得到最终的补数。

class Solution {
    public int findComplement(int num) {
        // 将 temp 初始化为 num，c 初始化为 0
        int temp = num, c = 0;
 
        // 循环右移 temp，直到 temp 变为 0
        while (temp > 0) {
            temp >>= 1;  // 右移一位
            c = (c << 1) + 1;  // 将 c 左移一位，并将最低位设置为 1
        }
 
        // 返回 num 与 c 的异或结果，即 num 的补数
        return num ^ c;
    }
}

通过迭代找到 num 的最高位的位置，然后构造一个掩码 mask，用于取反高位以下的所有位。最后，通过异或操作得到 num 的补数。这种方法避免了使用循环右移的方式，采用了更直接的方法。

其实这两种方法都是找异或的掩码，方法也差不多。

class Solution {
    public int findComplement(int num) {
        // 初始化 highbit 为 0
        int highbit = 0;
 
        // 遍历 1 到 30，找到 num 的最高位的位置
        for (int i = 1; i <= 30; ++i) {
            if (num >= 1 << i) {
                highbit = i;
            } else {
                break;
            }            
        }
 
        // 构造一个掩码 mask，用于取反高位以下的所有位
        int mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
 
        // 返回 num 与 mask 的异或结果，即 num 的补数
        return num ^ mask;
    }
}

 66. 加一 - 力扣（LeetCode）

 要处理一个特别的情况，全是九的时候，这里处理得很妙。

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
			if (digits[i] != 9) {
                digits[i]++;
				return digits;
			} 
			digits[i] = 0;
		}
        //跳出for循环，说明数字全部是9
		int[] temp = new int[digits.length + 1];
		temp[0] = 1;
		return temp;
    }
}

 开摆的节奏哈哈哈

class Solution {
    public int largestPalindrome(int n) {
        switch (n) {
            case 1: return 9;
            case 2: return 987;
            case 3: return 123;
            case 4: return 597;
            case 5: return 677;
            case 6: return 1218;
            case 7: return 877;
            default: return 475;
        }
    }
}

枚举回文数的左半部分，然后构造右半部分，查找是否存在两个 n 位数的乘积，得到最大回文数。该方法在处理较小的 n 时效率较高，但可能对于较大的 n 不够高效。

class Solution {
    public int largestPalindrome(int n) {
        // 对于 n = 1，最大回文数为 9
        if (n == 1) {
            return 9;
        }
        
        // 计算 n 位数的上限值
        int upper = (int) Math.pow(10, n) - 1;
        int ans = 0;
 
        // 枚举回文数的左半部分
        for (int left = upper; ans == 0; --left) {
            long p = left;
 
            // 翻转左半部分到其自身末尾，构造回文数 p
            for (int x = left; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
 
            // 枚举右半部分，查找是否存在两个 n 位数的乘积
            for (long x = upper; x * x >= p; --x) {
                if (p % x == 0) { // x 是 p 的因子
                    ans = (int) (p % 1337);
                    break;
                }
            }
        }
        return ans;
    }
}

564. 寻找最近的回文数 - 力扣（LeetCode）

class Solution {
    public String nearestPalindromic(String n) {
        
        Long input = Long.parseLong(n);
        int order = (int)Math.pow(10, n.length()/2);
        Long noChange = mirror(input);
        Long larger = mirror((input/order)*order + order + 1);
        Long smaller = mirror((input/order)*order - 1);
        
        if(noChange > input){
            larger = noChange < larger ? noChange : larger;
        }
        else if(noChange < input){
            smaller = noChange > smaller ? noChange : smaller;
        }
            
        return (input - smaller) <= (larger - input) ? String.valueOf(smaller) : String.valueOf(larger);
    }
 
    Long mirror(Long ans) {
        
        char[] arr = String.valueOf(ans).toCharArray();
        int i = 0;
        int j = arr.length-1;
        while(i < j){
            arr[j--] = arr[i++];
        }
        
        return Long.parseLong(String.valueOf(arr));
    }
}

class Solution {
    public int reverse(int x) {
        // int len=0,y=0,result=0,sub=1;
        // if(x<0) sub=-1;
        // x=Math.abs(x);
        // while(x>0){
        //     y=x%10;
        //     x=x/10;
        //     if(x>0){
        //         result=10*(y+result);
        //     }else{
        //         result=result+y;
        //     } 
        // }
        // //return sub*result>2^(31)-1 || sub*result<-2^(31) ? 0 : sub*result;
        // return sub * result > Math.pow(2, 31) - 1 || sub * result < -Math.pow(2, 31) ? 0 : sub * result;
 
        // long n = 0;
        // while(x != 0) {
        //     n = n*10 + x%10;
        //     x = x/10;
        // }
        // return (int)n==n? (int)n:0;
 
        int result = 0;
        while (x != 0) {
            //每次取末尾数字
            int temp = x % 10;
            //判断是否 大于 最大32位整数
           /* if (result > 214748364 || (result == 214748364 && temp > 7)) {
                return 0;
            }
            //判断是否 小于 最小32位整数
            if (result < -214748364 || (result == -214748364 && temp < -8)) {
                return 0;
            }*/
       /*     因为x本身会被int限制，
            当x为正数并且位数和Integer.MAX_VALUE的位数相等时首位最大只能为2，
            所以逆转后不会出现res = Integer.MAX_VALUE / 10 && tmp > 2的情况，
            自然也不需要判断res==214748364 && tmp>7了，反之负数情况也一样*/
            if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 10)  {
                return 0;
            }
            result = result * 10 + temp;
            x /= 10;
 
        }
        return result;
    }
}

---

总结

今天把数与位的第一个部分，进制转换做完了，感觉大部分都是简单题，仔细想想也能自己敲出来，需要注意的是一些回文数和进制的处理需要牢记。多敲！