2024.4.28力扣每日一题——负二进制转换

本文主要是介绍2024.4.28力扣每日一题——负二进制转换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源

力扣每日一题；题序：1017

我的题解

方法一 进制转换

对于以-2为基数的系统，可以这样理解：在-2进制中，每一位的权重是-2的幂。这与传统的二进制表示法不同，后者每一位的权重是2的幂。
要将一个正整数转换为以-2为基数的表示法，可以遵循以下步骤：

• 初始化：创建一个空的字符串或列表来存储-2进制表示的每一位。
• 迭代计算：从最高位开始，不断地将整数除以-2，记录每次操作的余数。
• 反转结果：由于是从最高位开始计算的，最终得到的序列需要反转，以得到正常的-2进制表示。
• 处理负数：由于除以负数时，除数和被除数的符号会相互影响，需要在每次除法后根据结果调整符号。

时间复杂度：O(${\log }_{-2}n$)
空间复杂度：O(1)

public String baseNeg2(int n) {if (n == 0) {return "0";}StringBuilder negativeBinary = new StringBuilder();while (n != 0) {int remainder = n % -2;n = n / -2;// 如果余数是负数，转换为正数if (remainder < 0) {remainder += 2;n += 1;}negativeBinary.append(remainder);}return negativeBinary.reverse().toString();
}

方法二 模拟进位

官方题解
比较复杂，没怎么看懂，各位看官请移步官方题解。

时间复杂度：O©。C=32
空间复杂度：O©

public String baseNeg2(int n) {if (n == 0) {return "0";}int[] bits = new int[32];for (int i = 0; i < 32 && n != 0; i++) {if ((n & 1) != 0) {bits[i]++;if ((i & 1) != 0) {bits[i + 1]++;}}n >>= 1;}int carry = 0;for (int i = 0; i < 32; i++) {int val = carry + bits[i];bits[i] = val & 1;carry = (val - bits[i]) / (-2);}int pos = 31;StringBuilder res = new StringBuilder();while (pos >= 0 && bits[pos] == 0) {pos--;}while (pos >= 0) {res.append(bits[pos]);pos--;}return res.toString();
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

这篇关于2024.4.28力扣每日一题——负二进制转换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---