可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

相关推荐阅读

题目练习网址：【位运算】双机位A-出错的或电路

题目描述与示例

题目描述

某生产门电路的厂商发现某一批次的或门电路不稳定，具体现象为计算两个二进制数的或操作时，第一个二进制数中某两个比特位会出现交换，交换的比特位置是随机的，但只交换这两个位，其他位不变。

很明显，这个交换可能会影响最终的或结果，也可能不会有影响。

为了评估影响和定位出错的根因，工程师需要研究在各种交换的可能下，最终的或结果发生改变的情况有多少种。

输入描述

第一行有一个正整数 N；其中 1 ≤ N ≤ 1000000。

第二行有一个长为 N 的二进制数，表示与电路的第一个输入数，即会发生比特交换的输入数。

第三行有一个长为 N 的二进制数，表示与电路的第二个输入数。注意第二个输入数不会发生比特交换。

输出描述

输出只有一个整数，表示会影响或结果的交换方案个数。

示例一

输入

3
010
110

输出

1

说明

原本 010 和 110 的或结果是 110，但第一个输入数可能会发生如下三种交换：

  1. 交换第 1 个比特和第 2 个比特，第一个输入数变为 100，计算结果为 110，计算结果不变
  2. 交换第 1 个比特和第 3 个比特，第一个输入数变为 010，计算结果为 110，计算结果不变
  3. 交换第 2 个比特和第 3 个比特，第一个输入数变为 001，计算结果为 111，计算结果改变

故只有一种交换会改变计算结果。

示例二

输入

6
011011
110110

输出

4

说明

原本 011011 和 110110 的或结果是 111111，但第一个输入数发生如下比特交换会影响最终计算结果：

  1. 交换第 1 个比特和第 3 个比特，第一个输入数变为 110011，计算结果变为 110111
  2. 交换第 1 个比特和第 6 个比特，第一个输入数变为 111010，计算结果变为 111110
  3. 交换第 3 个比特和第 4 个比特，第一个输入数变为 010111，计算结果变为 110111
  4. 交换第 4 个比特和第 6 个比特，第一个输入数变为 011110，计算结果变为 111110

其他的交换都不会影响计算结果，故输出 4。

解题思路

第一个二进制数我们记为num1，第二个二进制数我们记为num2，或运算的结果记为num_or。对num1所选取的两个位置记为i和j。

如果num1[i]和num1[j]交换之后或运算的结果和之前的不一致，说明交换的两个位置必定满足以下条件：

  1. num1[i] != num1[j]，即交换的两个数必须是一个0一个1，不能均为0或者均为1。因为如果num1[i] == num1[j]，说明交换前后的num1是一致的，与num2进行位运算得到的结果的num_or自然也是一致的。
  2. 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]的交换而改变。

简单来说：

  1. num1的两个位置必须是一个0和一个1。
  2. num2的两个位置必须至少有一个0。

因此，如果num_or在交换前后出现改变，那么只可能是以下三种情况。

num1的情况 num2的情况 num_or交换前 num_or交换后
num1[i] = 1``num1[j] = 0 num2[i] = 0``num2[j] = 0 num1[i] = 1``num1[j] = 0 num1[i] = 0``num1[j] = 1
num1[i] = 1``num1[j] = 0 num2[i] = 1``num2[j] = 0 num1[i] = 1``num1[j] = 0 num1[i] = 1``num1[j] = 1
num1[i] = 1``num1[j] = 0 num2[i] = 0``num2[j] = 1 num1[i] = 1``num1[j] = 1 num1[i] = 0``num1[j] = 1

由于i和j两者的地位是等价的，因此我们只需要求出以下四种情况下的索引i的个数

  1. num1[i] == 1，num2[i] == 1的i的个数，记为cnt11。
  2. num1[i] == 0，num2[i] == 0的i的个数，记为cnt00。
  3. num1[i] == 1，num2[i] == 0的i的个数，记为cnt10。
  4. num1[i] == 0，num2[i] == 1的i的个数，记为cnt01。

上述表格中的三种情况的个数，根据乘法原理，分别对应

  • cnt10 * cnt00
  • cnt11 * cnt00
  • cnt10 * cnt01

再将上述三者的结果相加，即为答案。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2023B/双机位A-出错的或电路
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：数学/乘法原理/位运算
# 代码看不懂的地方，请直接在群上提问


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 += 1
    elif num1[i] == "0" and num2[i] == "0":
        cnt00 += 1
    elif num1[i] == "1" and num2[i] == "0":
        cnt10 += 1
    elif 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;
}

C

#include <stdio.h>

int main() {
    int n;
    // 读取输入的长度 n
    scanf("%d", &n);

    char num1[100005], num2[100005];
    // 读取两个二进制字符串
    scanf("%s", num1);
    scanf("%s", 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;

    // 输出结果
    printf("%d\n", ans);

    return 0;
}

Node JavaScript

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];
rl.on('line', line => {
  input.push(line.trim());
});

rl.on('close', () => {
  // 读取输入
  const n = parseInt(input[0]);
  const num1 = input[1];
  const num2 = input[2];

  // 初始化四类统计变量
  let cnt11 = 0, cnt00 = 0, cnt10 = 0, cnt01 = 0;

  // 遍历字符串，统计对应位的组合情况
  for (let i = 0; i < n; i++) {
    const a = num1[i];
    const b = num2[i];
    if (a === '1' && b === '1') {
      cnt11++;
    } else if (a === '0' && b === '0') {
      cnt00++;
    } else if (a === '1' && b === '0') {
      cnt10++;
    } else if (a === '0' && b === '1') {
      cnt01++;
    }
  }

  // 根据题意公式计算结果
  const ans = cnt10 * cnt00 + cnt11 * cnt00 + cnt10 * cnt01;

  // 输出结果
  console.log(ans);
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
)

func main() {
        var n int
        reader := bufio.NewReader(os.Stdin)

        // 读取输入
        fmt.Fscan(reader, &n)
        var num1, num2 string
        fmt.Fscan(reader, &num1)
        fmt.Fscan(reader, &num2)

        // 初始化计数变量
        cnt11, cnt00, cnt10, cnt01 := 0, 0, 0, 0

        // 遍历统计每位组合
        for i := 0; i < n; i++ {
                a := num1[i]
                b := num2[i]
                if a == '1' && b == '1' {
                        cnt11++
                } else if a == '0' && b == '0' {
                        cnt00++
                } else if a == '1' && b == '0' {
                        cnt10++
                } else if a == '0' && b == '1' {
                        cnt01++
                }
        }

        // 根据题意公式计算
        ans := cnt10*cnt00 + cnt11*cnt00 + cnt10*cnt01

        // 输出结果
        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(N)。一次遍历求出四个变量的情况。

空间复杂度：O(1)。仅需若干常数变量

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

  • 课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1441或了解更多

# python # 算法 # java
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

【AI】-7 从知识库到 AI Agent -进阶

avatar AI Agent技术社区

AI Agent 面试题 353：A2A协议的服务发现和注册机制详解

A2A 协议 是 AI Agent 技术体系中的重要组成部分。简单来说，它涉及到 Agent 如何在 工具使用与函数调用 层面实现智能化的行为和决策。在实际应用中，A2A 协议 的核心目标是让 Agent 能够更加高效、准确地完成特定任务。这需要我们深入理解其底层原理和实现机制。从学术角度来看，A2A 协议 的研究可以追溯到人工智能的早期阶段。早在 1950 年代，Alan Turing 就提出了

avatar AI Agent技术社区
cover

英伟达AI刷爆ARC-AGI-3！AVO Harness架构让Agent从30%飙升到100%

avatar AI Agent技术社区