负二进制数相加【LC1073】
给出基数为 -2 的两个数
arr1和arr2，返回两数相加的结果。数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。
例如，
arr = [1,1,0,1]表示数字(-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字arr也同样不含前导零：即arr == [0]或arr[0] == 1。返回相同表示形式的
arr1和arr2相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
“出狱”啦
- 思路
class Solution { public int[] addNegabinary(int[] arr1, int[] arr2) { // 负二进制数的性质 // 1 + 1 进位 -1 // 0 - 1 进位 1，当前位置1 List<Integer> res = new ArrayList<>(); int n = arr1.length, m = arr2.length; int i = n - 1, j = m - 1; int cnt = 0; while (i >= 0 || j >= 0 || cnt != 0){ int num1 = i >= 0 ? arr1[i] : 0; int num2 = j >= 0 ? arr2[j] : 0; int x = num1 + num2 + cnt; cnt = 0; if (x >= 2){ x -= 2; cnt -= 1; }else if (x == -1){ x = 1; cnt += 1; } res.add(x); i--; j--; } // 去除前导0 while (res.size() > 1 && res.get(res.size() - 1) == 0){ res.remove(res.size() - 1); } // 反转 Collections.reverse(res); return res.stream().mapToInt(x -> x).toArray(); } }
