Leetcode单数II运算符解决方案说明 [英] Leetcode Single Number II Operator Solution Explanation

问题描述

问题是""给出了一个非空的整数数组，每个元素出现三次，除了一次，它恰好出现一次.找到一个.'我想出了一个简单的解决方案，但在网上找到了这个解决方案，感到很困惑.有人可以解释一下这些代码，也许可以解释一下这些运算符的用途，以及在提出编码问题的解决方案时应何时使用它们.

class Solution:
def singleNumber(self, nums: List[int]) -> int:
    seen_once = seen_twice = 0
    for num in nums:
        seen_once = ~seen_twice & (seen_once ^ num)
        seen_twice = ~seen_once & (seen_twice ^ num)
    return seen_once

解决方案

Hung Thai 的评论之一中提到了这种方法的粗略想法，但我想进一步阐述./p>

变量seen_once和seen_twice用于存储遍历数组时出现的元素的值.如果元素出现一次，则其值存储在seen_once中；如果元素出现两次，则其值存储在seen_twice变量中.如果它出现3次，它将不会存储在任何变量中，因为如果我们多次将整数传递给该函数，则(seen_once, seen_twice)将具有以下值状态:(0,0) -> (n,0) -> (0,n) -> (0,0) -> ....因此，任何整数都将处理到第三个整数时间会将变量重置到其初始状态，即(0,0).因此，遍历整个数组后在seen_once元素中获得的值将是我们的答案.

让我们看一个数组:{2, 2, 2, 3}

seen_once = 00, seen_twice == 00

当我们在第一个元素(即2)处时，其二进制表示形式为10.

现在为seen_once will be (~00)&(00^10) = 10 which is 2的值. 还有seen_twice will be (~10)&(10^10) = 00的值.

因此，seen_once存储2，因为它到目前为止只发生过一次，并且seen_twice为0.

当我们进一步遍历时，我们再次得到2，所以seen_twice will become 2的值到现在为止已经出现过两次，而seen_once will become 0的值.

然后我们第三次获得 2 .现在，两个变量的值都将变为0.

最后，我们得到 3 ，它只出现一次，因此将被存储在seen_once中.

循环结束后，我们得到的答案为seen_once = 3.

The question is 'Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.' I came up with a simple solution but found this solution online and was confused. Can someone explain this code and probably can explain whats the use of these operators and when should we use them while coming up with a solution of a coding problem.

class Solution:
def singleNumber(self, nums: List[int]) -> int:
    seen_once = seen_twice = 0
    for num in nums:
        seen_once = ~seen_twice & (seen_once ^ num)
        seen_twice = ~seen_once & (seen_twice ^ num)
    return seen_once

解决方案

A rough idea of the approach is mentioned in one of the comments by Hung Thai but I would like to elaborate it further.

Variables seen_once and seen_twice are being used to store the value of elements that are being occurred as we traverse through the array. If the element occurs once then it's value is stored in seen_once, if it occurs twice then it is stored in seen_twice variable. If it occurs three times it won't be stored in any of the variables because if we pass an integer several times to the function, (seen_once, seen_twice) will have the following states of value: (0,0) -> (n,0) -> (0,n) -> (0,0) -> .... Thus, any integer processed to the third time will reset the variables to its initial state, which is (0,0). So, the value that we get in the seen_once element after traversing through the whole array will be our answer.

Let's take an array: {2, 2, 2, 3}

seen_once = 00, seen_twice == 00

When we are at first element i.e. 2 its binary representation will be 10.

Now the value of seen_once will be (~00)&(00^10) = 10 which is 2. And the value of seen_twice will be (~10)&(10^10) = 00.

So, seen_once stores 2 because it has occurred only once till now and seen_twice is 0.

As we traverse further, we again get 2, so the value of seen_twice will become 2 as it has occurred twice till now and value of seen_once will become 0.

Then we get 2 for the third time. Now the values of both variables will become 0.

And at last, we get 3, which has occurred only once so it will be stored in seen_once.

After the loop ends, we get our answer as seen_once = 3.

这篇关于Leetcode单数II运算符解决方案说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！