2023-04-06 LeetCode：负二进制转换

1017. 负二进制转换

问题描述

给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。

示例

输入：n = 2
输出："110"
解释：(-2)² + (-2)¹ = 2

输入：n = 3
输出："111"
解释：(-2)² + (-2)¹ + (-2)¹ = 3

输入：n = 4
输出："100"
解释：(-2)² = 4

解题思路

1. 先按照“十进制转二进制”对整数n进行处理；
2. 将“二进制”数转为“负二进制”数：
   在“负二进制”数中，偶数位上的数为正数，可以正常处理；
   奇数位上的数位为负数，2ⁱ=(−2) ⁱ⁺¹+(−2)ⁱ

代码示例（JAVA）

class Solution {
    public String baseNeg2(int n) {
        if (n == 0) {
            return "0";
        }
        // 二进制转换
        List<Integer> list = new ArrayList<>();
        int temp = n;
        while (temp != 0) {
            int remainder = temp % 2;
            temp = temp / 2;
            list.add(remainder);
        }

        for (int i = 0; i < list.size(); i++) {
            Integer item = list.get(i);
            // 偶数位
            if (i % 2 == 0) {
                // 发生进位
                if (item == 2) {
                    if (i == list.size() - 1) {
                        list.add(0);
                    }
                    list.set(i, 0);
                    list.set(i + 1, list.get(i + 1) + 1);
                }
            } else {
                // 奇数位
                if (i == list.size() - 1) {
                    list.add(0);
                }
                list.set(i + 1, list.get(i + 1) + item / 2 + item % 2);
                list.set(i, item % 2);
            }
        }

        StringBuilder str = new StringBuilder();
        for (int i = list.size() - 1; i >= 0; i--) {
            int item = list.get(i);
            if (item == 0 && str.length() == 0) {
                continue;
            }
            str.append(item);
        }

        return str.toString();
    }
}