17网站一起做网店东莞,租房网站的财务分析表怎么做,wordpress 图片边框,如何学网络推广文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出说明 示例二输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
某生产门电路的厂商发现某一批次的或门电路不稳定#xff0c;具体现象为计… 文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出说明 示例二输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
某生产门电路的厂商发现某一批次的或门电路不稳定具体现象为计算两个二进制数的或操作时第一个二进制数中某两个比特位会出现交换交换的比特位置是随机的但只交换这两个位其他位不变。
很明显这个交换可能会影响最终的或结果也可能不会有影响。
为了评估影响和定位出错的根因工程师需要研究在各种交换的可能下最终的或结果发生改变的情况有多少种。
输入描述
第一行有一个正整数 N其中 1 ≤ N ≤ 1000000。
第二行有一个长为 N 的二进制数表示与电路的第一个输入数即会发生比特交换的输入数。
第三行有一个长为 N 的二进制数表示与电路的第二个输入数。注意第二个输入数不会发生比特交换。
输出描述
输出只有一个整数表示会影响或结果的交换方案个数。
示例一
输入
3
010
110输出
1说明
原本 010 和 110 的或结果是 110但第一个输入数可能会发生如下三种交换
交换第 1 个比特和第 2 个比特第一个输入数变为 100计算结果为 110计算结果不变交换第 1 个比特和第 3 个比特第一个输入数变为 010计算结果为 110计算结果不变交换第 2 个比特和第 3 个比特第一个输入数变为 001计算结果为 111计算结果改变
故只有一种交换会改变计算结果。
示例二
输入
6
011011
110110输出
4说明
原本 011011 和 110110 的或结果是 111111但第一个输入数发生如下比特交换会影响最终计算结果
交换第 1 个比特和第 3 个比特第一个输入数变为 110011计算结果变为 110111交换第 1 个比特和第 6 个比特第一个输入数变为 111010计算结果变为 111110交换第 3 个比特和第 4 个比特第一个输入数变为 010111计算结果变为 110111交换第 4 个比特和第 6 个比特第一个输入数变为 011110计算结果变为 111110
其他的交换都不会影响计算结果故输出 4。
解题思路
第一个二进制数我们记为num1第二个二进制数我们记为num2或运算的结果记为num_or。对num1所选取的两个位置记为i和j。
如果num1[i]和num1[j]交换之后或运算的结果和之前的不一致说明交换的两个位置必定满足以下条件
num1[i] ! num1[j]即交换的两个数必须是一个0一个1不能均为0或者均为1。因为如果num1[i] num1[j]说明交换前后的num1是一致的与num2进行位运算得到的结果的num_or自然也是一致的。num2[i]和num2[j]不能均为1即num2的对应位置至少有存在1个0。因为如果存在num2[i] num2[j] 1那么无论num1[i]和num1[j]是什么内容或运算的结果一定存在num_or[i] num_or[j] 1不会因为num1[i]和num1[j]的交换而改变。
简单来说
num1的两个位置必须是一个0和一个1。num2的两个位置必须至少有一个0。
因此如果num_or在交换前后出现改变那么只可能是以下三种情况。
num1的情况num2的情况num_or交换前num_or交换后num1[i] 1num1[j] 0num2[i] 0num2[j] 0num1[i] 1num1[j] 0num1[i] 0num1[j] 1num1[i] 1num1[j] 0num2[i] 1num2[j] 0num1[i] 1num1[j] 0num1[i] 1num1[j] 1num1[i] 1num1[j] 0num2[i] 0num2[j] 1num1[i] 1num1[j] 1num1[i] 0num1[j] 1
由于i和j两者的地位是等价的因此我们只需要求出以下四种情况下的索引i的个数
num1[i] 1num2[i] 1的i的个数记为cnt11。num1[i] 0num2[i] 0的i的个数记为cnt00。num1[i] 1num2[i] 0的i的个数记为cnt10。num1[i] 0num2[i] 1的i的个数记为cnt01。
上述表格中的三种情况的个数根据乘法原理分别对应
cnt10 * cnt00cnt11 * cnt00cnt10 * cnt01
再将上述三者的结果相加即为答案。
代码
Python
# 题目2023B-出错的或电路
# 分值200
# 作者闭着眼睛学数理化
# 算法数学/乘法原理
# 代码看不懂的地方请直接在群上提问n int(input())
num1 input()
num2 input()# 初始化四个变量分别统计四种情况
cnt11, cnt00, cnt10, cnt01 0, 0, 0, 0
for i in range(n):# 分别根据num1[i]和num2[i]的情况# 统计对应变量的个数if num1[i] 1 and num2[i] 1:cnt11 1elif num1[i] 0 and num2[i] 0:cnt00 1elif num1[i] 1 and num2[i] 0:cnt10 1elif num1[i] 0 and num2[i] 1:cnt01 1# 根据乘法原理进行计算
ans cnt10 * cnt00 cnt11 * cnt00 cnt10 * cnt01
print(ans)Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();String num1 scanner.next();String num2 scanner.next();int cnt11 0, cnt00 0, cnt10 0, cnt01 0;for (int i 0; i n; i) {if (num1.charAt(i) 1 num2.charAt(i) 1) {cnt11;} else if (num1.charAt(i) 0 num2.charAt(i) 0) {cnt00;} else if (num1.charAt(i) 1 num2.charAt(i) 0) {cnt10;} else if (num1.charAt(i) 0 num2.charAt(i) 1) {cnt01;}}int ans cnt10 * cnt00 cnt11 * cnt00 cnt10 * cnt01;System.out.println(ans);}
}C
#include iostream
using namespace std;int main() {int n;cin n;string num1, num2;cin num1 num2;int cnt11 0, cnt00 0, cnt10 0, cnt01 0;for (int i 0; i n; i) {if (num1[i] 1 num2[i] 1) {cnt11;} else if (num1[i] 0 num2[i] 0) {cnt00;} else if (num1[i] 1 num2[i] 0) {cnt10;} else if (num1[i] 0 num2[i] 1) {cnt01;}}int ans cnt10 * cnt00 cnt11 * cnt00 cnt10 * cnt01;cout ans endl;return 0;
}时空复杂度
时间复杂度O(N)。一次遍历求出四个变量的情况。
空间复杂度O(1)。仅需若干常数变量 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
