当前位置：首页 > news >正文

leetCode 137. 只出现一次的数字 II（拓展篇） + 模5加法器 + 真值表（数字电路）

news 2025/7/27 16:51:54

leetCode 137. 只出现一次的数字 II 题解可看我的往期文章

leetCode 137. 只出现一次的数字 II + 位运算 + 模3加法器 + 真值表（数字电路） + 有限状态机-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134138112?spm=1001.2014.3001.5501【拓展思考】如果改成除了一个数字出现一次，其余数字均出现 5 次呢？

(一)「同时计算」

$a=ab'c'x'+a'bcx$

$b=a'bc'x'+a'bcx'+a'b'cx+a'bc'x$

$c=a'b'cx'+a'bcx'+a'b'c'x+a'bc'x$

化简 b 和 c：

$b=a'bc'x'+a'bcx'+a'b'cx+a'bc'x$

$=a'bx'(c'+c)+a'x(b'c+bc')$

$=a'bx'(c'+c)+a'x(b\bigoplus c)$

$=a'bx'+a'x(b\bigoplus c)$

$=a'(bx'+x(b\bigoplus c))$

$c=a'b'cx'+a'bcx'+a'b'c'x+a'bc'x$

$=a'b'cx'+a'b'c'x+a'bcx'+a'bc'x$

$=a'b'(cx'+c'x)+a'b(cx'+c'x)$

$=a'b'(c\bigoplus x)+a'b(c \bigoplus x)$

$=a'(b'+b)(c\bigoplus x)$

$=a'(c\bigoplus x)$

#include <iostream>
#include <vector>
using namespace std;int singleNumber(vector<int> nums) {int i, a, b, c, tmpa, tmpb, tmpc;a = 0;b = 0;c = 0;for (const int& x : nums) {// 第一种tmpa = a;tmpb = b;tmpc = c;a = a & ~tmpb & ~tmpc & ~x | ~a & tmpb & tmpc & x;b = ~tmpa & b & (~tmpc | tmpc) | ~tmpa & x & (b ^ tmpc);c = ~tmpa & (c ^ x);}return c;
}int main() {vector<int> nums{3,3,3,3,3,2,2,2,2,2,6,6,6,6,6,4,4,4,10,4,4 };cout<<"打印结果:"<<singleNumber(nums) << endl;return 0;
}

(二)「分别计算」

发现上面化简c后，式子很简洁：

$c=a'(c\bigoplus x)$

$b=a'bc'x'+a'bcx'+a'b'c'x+a'bcx$

$=a'bc'x'+a'b'c'x+a'bcx'+a'bcx$

$=a'c'(bx'+b'x)+a'bc(x'+x)$

$=a'c'(b\bigoplus x)+a'bc$

$a=ab'c'x'+a'b'c'x$

$=b'c'(ax'+a'x)$

$=b'c'(a\bigoplus x)$

#include <iostream>
#include <vector>
using namespace std;int singleNumber(vector<int> nums) {int i, a, b, c, tmpa, tmpb, tmpc;a = 0;b = 0;c = 0;for (const int& x : nums) {// 第二种c = ~a & (c ^ x);b = ~a & ~c & (b ^ x) | ~a & b & c;a = ~b & ~c & (a ^ x);}return c;
}int main() {vector<int> nums{3,3,3,3,3,2,2,2,2,2,6,6,6,6,6,4,4,4,10,4,4 };cout<<"打印结果:"<<singleNumber(nums) << endl;return 0;
}