什么？卡诺图都来了吗!?(･_･;?
来提每日一题
2024-06-28 00:23:19
近期找工作现状 笔记灵感 数码大玩家 每日一题 LeetCode 转码 北美求职 互联网大厂 程序员
关注我，每天59秒拿下每日一题
国区每日一题今日思路：
排序题，按要求我们对每一行进行排序，然后按列选取每一列的最大值即可。这里因为数据的值不超过1000，可以使用桶排序来将排序优化到线性。
国际站每日一题今日思路：
这道题使用hash表来对数据频率进行统计，找出只出现一次的数字即可；但是如果只使用常数空间如何求解？这里我们需要借助卡诺图，因为数字出现频率为0，1，2，3，需要借助两个bit位来存储。我们记AB为数字出现频率(二进制表示)，C为数据输入，即触发电平，我们不难画出如图3的卡诺图，换成状态转移方程为，每当输入一个num，我们根据它的频率，从0变化到1，2，然后从2变化到0，若没有输入，其状态保持不变，图中的XX表示任意值，即我们可以不用考虑这种状态。
那么我们根据卡诺图不难写出转移方程A = (~A)BC+A(~B)(~C), B = (~A)(~B)C + (~A)B(~C) = (~A)(B^C)。然后最终只有一个数的频率为01，那么这个数就是计算结束后的B。因为在卡诺图中我们令C为触发，即每次出现C为1，不出现C为0。所以最后这个01中的1就是我们要求的C。初始状态所有数频率为0，即AB=00。注意上述状态转移方程不是加法和乘法，是逻辑加法(或)，逻辑乘法(与)。
看到这里点个赞吧[喝奶茶R]
0
阅读：0
