1073.负二进制数相加.md

1073.负二进制数相加

/*
 * @lc app=leetcode.cn id=1073 lang=typescript
 *
 * [1073] 负二进制数相加
 */

// @lc code=start
function addNegabinary(arr1: number[], arr2: number[]): number[] {}
// @lc code=end

解法 1: 模拟

function addNegabinary(arr1: number[], arr2: number[]): number[] {
  const n = arr1.length,
    m = arr2.length
  if (n > m) return addNegabinary(arr2, arr1)
  arr1.reverse()
  arr2.reverse()
  const res: number[] = new Array(m).fill(0)
  for (let i = 0; i < m; i++) {
    let type = 0
    if (arr1[i] && arr2[i]) {
      type = 1
    } else if (arr1[i] || arr2[i]) {
      if (res[i]) {
        type = 1
        res[i] = 0
      } else {
        res[i] = 1
      }
    }
    if (type === 1) {
      if (arr1[i + 1]) {
        arr1[i + 1] = 0
      } else if (arr2[i + 1]) {
        arr2[i + 1] = 0
      } else if (res[i + 1]) {
        res[i + 1] = 0
      } else {
        res[i + 1] = 1
        res[i + 2] = 1
      }
    }
  }

  while (res.length > 1 && !res[res.length - 1]) res.pop()
  res.reverse()
  for (let i = 0; i < res.length; i++) {
    if (res[i] === undefined) res[i] = 0
  }
  return res
}

Case

test.each([
  { input: { arr1: [1, 1, 1, 1, 1], arr2: [1, 0, 1] }, output: [1, 0, 0, 0, 0] },
  { input: { arr1: [0], arr2: [0] }, output: [0] },
  { input: { arr1: [0], arr2: [1] }, output: [1] },
])('input: arr1 = $input.arr1, arr2 = $input.arr2', ({ input: { arr1, arr2 }, output }) => {
  expect(addNegabinary(arr1, arr2)).toEqual(output)
})