[leetcode] 1073. Adding Two Negabinary Numbers

[leetcode] 1073. Adding Two Negabinary Numbers

Description

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array, format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]Output: [1,0,0,0,0]Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Example 2:

Input: arr1 = [0], arr2 = [0]Output: [0]

Example 3:

Input: arr1 = [0], arr2 = [1]Output: [1]

Constraints:

1 <= arr1.length, arr2.length <= 1000arr1[i] and arr2[i] are 0 or 1arr1 and arr2 have no leading zeros

分析

题目的意思是：给定两个-2进制的数，求其和。这道题我参考了一下别人的思路，首先算一下进位怎么参与运算： sum=arr1[i]+arr2[i] 我们会得到如下的规律

sum = 0 -> carry = 0, result = 0sum = 1 -> carry = 0, result = 1sum = 2 -> carry = -1, result = 0sum = 3 -> carry = -1, result = 1sum = -1 -> carry = 1, result = 1

如果知道了这个，剩下的就是把两数一反转，然后相应位的数求和，进行进位就行了。最后可能会碰见高位为0的情况，比如0001000，我们需要删除前面的0，就行了。

代码

class Solution: def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]: m=len(arr1) n=len(arr2) arr1.reverse() arr2.reverse() carry=0 k=max(m,n) res=[] for i in range(k): if(i1): carry=-1 elif(t<0): carry=1 else: carry=0 t=carry while(t!=0): res.append(abs(t)%2) if(t>1): t=-1 elif(t<0): t=1 else: t=0 while(len(res)>1 and res[-1]==0): res.pop(-1) res.reverse() return res

参考文献

​​1073. Adding Two Negabinary Numbers​​​​进制-Adding Two Negabinary Numbers​​​​LeetCode 1073. Adding Two Negabinary Numbers​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。