华为OD机试真题 新系统【双系统资源类型调配】

双系统资源类型调配(C/C++/Py/Java/Js/Go)题解

华为OD机试新系统真题 华为OD上机考试新系统真题 6月10号 200分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

给定两个仅由小写字母组成的字符串 resA 和 resB。你可以执行恰好一次操作：选择下标 i 和 j，交换 resA[i] 与 resB[j]。问是否存在一种交换，使交换后两个字符串中不同字符的数量相等。 如果存在该交换，则返回交换后resA和resB中不同字符的数量；如果有多种交换方式则采用让两个字符串中不同的字符的数量最少的方式。 如果不存在任何交换方式则返回

−

1

– 1

−1。 提示:

• $1<=resA.length,resB.length<=10^5$
• $resA$

样例1

输入

ac
b

输出

-1

说明 交换任何一组下标都会导致第一个字符串中有

2

2

2 个不同的字符，而在第二个字符串中只有

1

1

1个不同字符。故无法完成返回

−

1

– 1

−1。

样例2

输入

abcc
aab

输出

2

说明 交换第一个字符串的下标

1

1

1 和第二个字符串的下标

0

0

0。之后得到 word1 = “aacc” 和 word2 = “abb”，各有

2

2

2 个不同字符。

样例3

输入

abcde
fghij

输出

5

说明 无论交换哪一组下标，两个字符串中都会有

5

5

5个不同字符。

题解

思路：逻辑分析

C++

#include<bits/stdc++.h>
#include <vector>
using namespace std;

int dispatch(string &A, string& B) {
// 每种字符的数量
vector<int> cntA(26, 0);
vector<int> cntB(26,0);
for (auto c : A) {
cntA[c – 'a']++;
}
for (auto c : B) {
cntB[c – 'a']++;
}
// 不同字符种类
int diffCountA , diffCountB;
diffCountA = diffCountB = 0;

for (int i = 0; i < 26; i++) {
if (cntA[i] > 0){
diffCountA++;
}
if (cntB[i] > 0) {
diffCountB++;
}
}

int ans = INT_MAX;
// 枚举A交换的字符
for (int x = 0; x < 26; x++) {
if (cntA[x] == 0) {
continue;
}
// 枚举B交换的字符
for (int y = 0; y < 26; y++) {
if (cntB[y] == 0) {
continue;
}
int newDA = diffCountA;
int newDB = diffCountB;
// 相同字符交换不影响数量
if (x != y) {
// x在A中数量变为0，种类-1
if (cntA[x] == 1) {
newDA—;
}
// y在A中数量由0->1,导致种类+1
if (cntA[y] == 0) {
newDA++;
}
// 类推
if (cntB[x] == 0) {
newDB++;
}
if (cntB[y] == 1) {
newDB—;
}
}
if (newDA == newDB) {
ans = min(ans, newDA);
}
}
}
return ans == INT_MAX ? –1 : ans;

}

int main() {
string A,B;
getline(cin, A);
getline(cin, B);
cout << dispatch(A, B);
return 0;
}

JAVA

import java.io.*;

public class Main {

static int dispatch(String A, String B) {
// 每种字符的数量
int[] cntA = new int[26];
int[] cntB = new int[26];

for (char c : A.toCharArray()) {
cntA[c – 'a']++;
}

for (char c : B.toCharArray()) {
cntB[c – 'a']++;
}

// 不同字符种类
int diffCountA = 0, diffCountB = 0;

for (int i = 0; i < 26; i++) {
if (cntA[i] > 0) {
diffCountA++;
}
if (cntB[i] > 0) {
diffCountB++;
}
}

int ans = Integer.MAX_VALUE;

// 枚举A交换的字符
for (int x = 0; x < 26; x++) {
if (cntA[x] == 0) {
continue;
}

// 枚举B交换的字符
for (int y = 0; y < 26; y++) {
if (cntB[y] == 0) {
continue;
}

int newDA = diffCountA;
int newDB = diffCountB;

// 相同字符交换不影响数量
if (x != y) {
// x在A中数量变为0，种类-1
if (cntA[x] == 1) {
newDA—;
}

// y在A中数量由0->1,导致种类+1
if (cntA[y] == 0) {
newDA++;
}

// 类推
if (cntB[x] == 0) {
newDB++;
}

if (cntB[y] == 1) {
newDB—;
}
}

if (newDA == newDB) {
ans = Math.min(ans, newDA);
}
}
}

return ans == Integer.MAX_VALUE ? –1 : ans;
}

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String A = br.readLine();
String B = br.readLine();

System.out.println(dispatch(A, B));
}
}

Python

def dispatch(A, B):
# 每种字符的数量
cntA = [0] * 26
cntB = [0] * 26

for c in A:
cntA[ord(c) – ord('a')] += 1

for c in B:
cntB[ord(c) – ord('a')] += 1

# 不同字符种类
diffCountA = 0
diffCountB = 0

for i in range(26):
if cntA[i] > 0:
diffCountA += 1

if cntB[i] > 0:
diffCountB += 1

ans = float('inf')

# 枚举A交换的字符
for x in range(26):
if cntA[x] == 0:
continue

# 枚举B交换的字符
for y in range(26):
if cntB[y] == 0:
continue

newDA = diffCountA
newDB = diffCountB

# 相同字符交换不影响数量
if x != y:
# x在A中数量变为0，种类-1
if cntA[x] == 1:
newDA -= 1

# y在A中数量由0->1,导致种类+1
if cntA[y] == 0:
newDA += 1

# 类推
if cntB[x] == 0:
newDB += 1

if cntB[y] == 1:
newDB -= 1

if newDA == newDB:
ans = min(ans, newDA)

return –1 if ans == float('inf') else ans

A = input().strip()
B = input().strip()

print(dispatch(A, B))

JavaScript

const readline = require('readline');

function dispatch(A, B) {
// 每种字符的数量
const cntA = new Array(26).fill(0);
const cntB = new Array(26).fill(0);

for (const c of A) {
cntA[c.charCodeAt(0) – 97]++;
}

for (const c of B) {
cntB[c.charCodeAt(0) – 97]++;
}

// 不同字符种类
let diffCountA = 0;
let diffCountB = 0;

for (let i = 0; i < 26; i++) {
if (cntA[i] > 0) {
diffCountA++;
}

if (cntB[i] > 0) {
diffCountB++;
}
}

let ans = Number.MAX_SAFE_INTEGER;

// 枚举A交换的字符
for (let x = 0; x < 26; x++) {
if (cntA[x] === 0) {
continue;
}

// 枚举B交换的字符
for (let y = 0; y < 26; y++) {
if (cntB[y] === 0) {
continue;
}

let newDA = diffCountA;
let newDB = diffCountB;

// 相同字符交换不影响数量
if (x !== y) {
// x在A中数量变为0，种类-1
if (cntA[x] === 1) {
newDA—;
}

// y在A中数量由0->1,导致种类+1
if (cntA[y] === 0) {
newDA++;
}

// 类推
if (cntB[x] === 0) {
newDB++;
}

if (cntB[y] === 1) {
newDB—;
}
}

if (newDA === newDB) {
ans = Math.min(ans, newDA);
}
}
}

return ans === Number.MAX_SAFE_INTEGER ? –1 : ans;
}

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

const lines = [];

rl.on('line', line => {
lines.push(line.trim());
});

rl.on('close', () => {
const A = lines[0];
const B = lines[1];

console.log(dispatch(A, B));
});

Go

package main

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

func dispatch(A string, B string) int {
// 每种字符的数量
cntA := make([]int, 26)
cntB := make([]int, 26)

for _, c := range A {
cntA[c–'a']++
}

for _, c := range B {
cntB[c–'a']++
}

// 不同字符种类
diffCountA := 0
diffCountB := 0

for i := 0; i < 26; i++ {
if cntA[i] > 0 {
diffCountA++
}

if cntB[i] > 0 {
diffCountB++
}
}

ans := int(^uint(0) >> 1)

// 枚举A交换的字符
for x := 0; x < 26; x++ {
if cntA[x] == 0 {
continue
}

// 枚举B交换的字符
for y := 0; y < 26; y++ {
if cntB[y] == 0 {
continue
}

newDA := diffCountA
newDB := diffCountB

// 相同字符交换不影响数量
if x != y {
// x在A中数量变为0，种类-1
if cntA[x] == 1 {
newDA—
}

// y在A中数量由0->1,导致种类+1
if cntA[y] == 0 {
newDA++
}

// 类推
if cntB[x] == 0 {
newDB++
}

if cntB[y] == 1 {
newDB—
}
}

if newDA == newDB {
if newDA < ans {
ans = newDA
}
}
}
}

if ans == int(^uint(0)>>1) {
return –1
}

return ans
}

func main() {
in := bufio.NewReader(os.Stdin)

var A, B string
fmt.Fscanln(in, &A)
fmt.Fscanln(in, &B)

fmt.Println(dispatch(A, B))
}

C语言

#include <stdio.h>
#include <string.h>
#include <limits.h>

int dispatch(char *A, char *B) {
// 每种字符的数量
int cntA[26] = {0};
int cntB[26] = {0};

for (int i = 0; A[i]; i++) {
cntA[A[i] – 'a']++;
}

for (int i = 0; B[i]; i++) {
cntB[B[i] – 'a']++;
}

// 不同字符种类
int diffCountA = 0;
int diffCountB = 0;

for (int i = 0; i < 26; i++) {
if (cntA[i] > 0) {
diffCountA++;
}

if (cntB[i] > 0) {
diffCountB++;
}
}

int ans = INT_MAX;

// 枚举A交换的字符
for (int x = 0; x < 26; x++) {
if (cntA[x] == 0) {
continue;
}

// 枚举B交换的字符
for (int y = 0; y < 26; y++) {
if (cntB[y] == 0) {
continue;
}

int newDA = diffCountA;
int newDB = diffCountB;

// 相同字符交换不影响数量
if (x != y) {
// x在A中数量变为0，种类-1
if (cntA[x] == 1) {
newDA—;
}

// y在A中数量由0->1,导致种类+1
if (cntA[y] == 0) {
newDA++;
}

// 类推
if (cntB[x] == 0) {
newDB++;
}

if (cntB[y] == 1) {
newDB—;
}
}

if (newDA == newDB) {
if (newDA < ans) {
ans = newDA;
}
}
}
}

return ans == INT_MAX ? –1 : ans;
}

int main() {
char A[100005];
char B[100005];

fgets(A, sizeof(A), stdin);
fgets(B, sizeof(B), stdin);

A[strcspn(A, "\\n")] = '\\0';
B[strcspn(B, "\\n")] = '\\0';

printf("%d\\n", dispatch(A, B));

return 0;
}