LeetCode 1017. 负二进制转换

1017. 负二进制转换

【进制转换】和2进制相比的话，偶数位是完全相同的，但是奇数位是由当前位和当前位 + 1 一起组成的。所以当遇到奇数位的时候该位为1，同时需要加上该位的值，然后继续向前转成 -2 进制。

class Solution {public String baseNeg2(int n) {// 1 -2 4 -8 16// 0  1if (n == 0) return "0";StringBuilder sb = new StringBuilder();int i = 0;while (n != 0) {if (n % 2 == 1) {if (i % 2 == 0) sb.append("1");else {sb.append("1");n += 1;}} else sb.append("0");n /= 2;i++;}sb.reverse();return sb.toString();}
}

【背包问题】也可以当成背包问题来看，因为有负的，所以一开始把负的都加入到n中，也就是才开始把负的都加入背包，然后从大到小枚举物品(1 >> i)，如果当前 n >= 这个值，那么根据 i 的奇偶性选择是加入背包还是拿出背包。

class Solution {public String baseNeg2(int n) {// 1 -2 4 -8 16// 0  1if (n == 0) return "0";int sum = n;for (int i = 1; i <= 30; i += 2) sum += 1 << i;// System.out.println(sum);StringBuilder sb = new StringBuilder();for (int i = 30; i >= 0; i--) {if (sum >= (1 << i)) {if (i % 2 == 1) sb.append("0");else sb.append("1");sum -= 1 << i;} else {if (i % 2 == 1) sb.append("1");else sb.append("0");}}boolean st = false;StringBuilder ans = new StringBuilder();for (int i = 0; i <= 30; i++) {if (sb.charAt(i) == '1') {st = true;}if (st) ans.append(sb.charAt(i));}return ans.toString();}
}