华为OD机试真题新系统【数组按二进制比特排序】-171主机测评

数组按二进制比特排序(C/C++/Py/Java/Js/Go)题解

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

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

题目内容

给定两个

int

$in t$ 数组，数据数组（一维）和操作数组（二维）：

数据数组：存放待操作的整数；
操作数组：每个元素为包含两个

操作流程

对数据数组排序：按整数二进制表示中

依次对操作数组中的每个元素执行以下操作：

读取两个下标，取当前数据数组中对应位置的元素，计算它们的二进制按位或，将结果追加到数据数组末尾，并删除原来的两个元素（元素下标允许相同，此时仅删除一个元素）。

对更新后的数据数组按步骤

输出最终排序后的数据数组。

注意

数据数组的长度范围为 $[-2^{31},2^{31}-1] [−231,231−1]。$
操作数组的长度范围为
即使操作数组为空，最后输出的数据数组也需要按照描述的排序方式输出有序数据数组。

样例1

输入

3,2,1
0,1

输出

3,3

说明排序后内容为

[

]

[1,2,3]

$[1, 2, 3]$ ，对

$1$ 和

$2$ 进行或操作得到

$3$ ，删除并插入重新排序后得到

[

]

[3,3]

$[3, 3]$ 。

样例2

输入

1024,512,256,128,64,32,16,8,4,2,1,0,-1
0,1 0,1 0,1 1,2

输出

16,128,256,512,1024,3,12,96,-1

说明排序后内容为

[

128

256

512

1024

−

]

[0,1,2,4,8,16,32,64,128,256,512,1024,-1]

$[0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, - 1]$ ，经过第一次操作结果为

[

128

256

512

1024

−

]

[0,1,2,4,8,16,32,64,128,256,512,1024,-1]

$[0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, - 1]$ ，第二次操作结果为

[

128

256

512

1024

−

]

[4,8,16,32,64,128,256,512,1024,3,1024,-1]

$[4, 8, 16, 32, 64, 128, 256, 512, 1024, 3, 1024, - 1]$ ，第三次操作结果为

[

128

256

512

1024

−

]

[16,32,64,128,256,512,1024,3,12,-1]

$[16, 32, 64, 128, 256, 512, 1024, 3, 12, - 1]$ ，最后一次操作结果为

[

128

256

512

1024

−

]

[16,128,256,512,1024,3,12,96,-1]

$[16, 128, 256, 512, 1024, 3, 12, 96, - 1]$ 。

样例3

输入

2147483647,-2147483648,-1,0
1,2 2,2

输出

0,-1,-1

说明原始数组按照二进制表示为

[

01111111111111111111111111111111

10000000000000000000000000000000

11111111111111111111111111111111

00000000000000000000000000000000

]

[01111111111111111111111111111111,10000000000000000000000000000000,11111111111111111111111111111111,00000000000000000000000000000000]

$[01111111111111111111111111111111, 10000000000000000000000000000000, 11111111111111111111111111111111, 00000000000000000000000000000000]$ ，按照

$1$ 的数量进行排序后数组顺序为：

[

−

2147483648

2147483647

−

]

[0,-2147483648,2147483647,-1]

$[0, - 2147483648, 2147483647, - 1]$ 。接下来对

index

$in d e x$ 为

$1$ 和

$2$ 的元素即

−

2147483648

-2147483648

$- 2147483648$ 、

2147483647

$2147483647$ 进行或操作获得结果

−

-1

$- 1$ ，将

[

−

2147483648

2147483647

]

[-2147483648,2147483647]

$[- 2147483648, 2147483647]$ 从数组中删除并插入

−

-1

$- 1$ 后得到

[

−

]

[0,-1,-1]

$[0, - 1, - 1]$ 。最后对

index

$in d e x$ 为

$2$ 的元素自身进行或操作不会改变数据。最终返回

[

−

]

[0,-1,-1]

$[0, - 1, - 1]$ 。

题解

思路：自定义排序

首先将输入数组按照题目要求进行二进制1的个数升序排序，1的个数相同的情况按照值升序

遍历操作，每次取出对应两个下标index1,index2

获取对应a = data[index1], b = data[index2]

然后执行或操作mergeValae = a | b

考虑移除数组对应元素

index1 == index2只需要移除一个元素，移除元素位于index1位置

indedx != index2需要移除两个元素，根据数组特性，需要先移除下标大的位置。

将mergeValue插入数组尾部，并重新进行排序。

C++

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

// 通用切割函数函数将字符串str根据delimiter进行切割
vector<string> split(const string& str, const string& delimiter) {
vector<string> result;
size_t start = 0;
size_t end = str.find(delimiter);
while (end != string::npos) {
result.push_back(str.substr(start, end – start));
start = end + delimiter.length();
end = str.find(delimiter, start);
}
// 添加最后一个部分
result.push_back(str.substr(start));
return result;
}

// 求指定数二进制1的数量
int countBitOne(int x) {
int cnt = __builtin_popcount((unsigned int)x);
return cnt;
}

// 将数组按照二进制个数排序
vector<int> sortArrByBitOne(vector<int>& a) {
sort(a.begin(), a.end(),[&](int a, int b) {
int aOne = countBitOne(a);
int bOne = countBitOne(b);
if (aOne == bOne) {
return a < b;
}
return aOne < bOne;
});
return a;
}

vector<int> sortArrByBit(vector<int>& data, vector<vector<int>> ops) {
vector<int> data_back = data;
data_back = sortArrByBitOne(data_back);

for (auto& op : ops) {
int index1 = op[0], index2 = op[1];
int x = data_back[index1];
int y = data_back[index2];
int mergeValue = x | y;
// 移除对应元素
// 只需要移除一个
if (index1 == index2) {
data_back.erase(data_back.begin() + index1);
// 移除两个需要先移除后面位置的
} else {
if (index1 > index2) {
swap(index1, index2);
}
data_back.erase(data_back.begin() + index2);
data_back.erase(data_back.begin() + index1);
}
data_back.push_back(mergeValue);
data_back = sortArrByBitOne(data_back);
}
return data_back;
}

int main() {
string input1,input2;
getline(cin ,input1);
getline(cin ,input2);
vector<int> data;
if (!input1.empty()) {
vector<string> tmp = split(input1, ",");
for (auto& s : tmp) {
data.push_back(stoi(s));
}
}

vector<vector<int>> ops;
if (!input2.empty()) {
vector<string> tmp = split(input2, " ");
for (auto& s : tmp) {
vector<string> index = split(s, ",");
ops.push_back({stoi(index[0]), stoi(index[1])});
}
}

vector<int> ans = sortArrByBit(data, ops);
for (int i = 0; i < ans.size(); i++) {
if (i > 0) {
cout << ",";
}
cout << ans[i];
}
return 0;
}

JAVA

import java.util.*;

public class Main {

// 求指定数二进制1的数量
public static int countBitOne(int x) {
return Integer.bitCount(x);
}

// 将数组按照二进制个数排序
public static List<Integer> sortArrByBitOne(List<Integer> a) {
a.sort((x, y) -> {
int aOne = countBitOne(x);
int bOne = countBitOne(y);

if (aOne == bOne) {
return Integer.compare(x, y);
}
return Integer.compare(aOne, bOne);
});
return a;
}

public static List<Integer> sortArrByBit(List<Integer> data, List<int[]> ops) {
List<Integer> dataBack = new ArrayList<>(data);
sortArrByBitOne(dataBack);

for (int[] op : ops) {
int index1 = op[0];
int index2 = op[1];

int x = dataBack.get(index1);
int y = dataBack.get(index2);

int mergeValue = x | y;

// 移除对应元素
// 只需要移除一个
if (index1 == index2) {
dataBack.remove(index1);
} else {
// 移除两个需要先移除后面位置的
if (index1 > index2) {
int tmp = index1;
index1 = index2;
index2 = tmp;
}

dataBack.remove(index2);
dataBack.remove(index1);
}

dataBack.add(mergeValue);
sortArrByBitOne(dataBack);
}

return dataBack;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

String input1 = sc.hasNextLine() ? sc.nextLine() : "";
String input2 = sc.hasNextLine() ? sc.nextLine() : "";

List<Integer> data = new ArrayList<>();

if (!input1.isEmpty()) {
String[] tmp = input1.split(",");
for (String s : tmp) {
data.add(Integer.parseInt(s));
}
}

List<int[]> ops = new ArrayList<>();

if (!input2.isEmpty()) {
String[] tmp = input2.split(" ");
for (String s : tmp) {
String[] index = s.split(",");
ops.add(new int[]{
Integer.parseInt(index[0]),
Integer.parseInt(index[1])
});
}
}

List<Integer> ans = sortArrByBit(data, ops);

for (int i = 0; i < ans.size(); i++) {
if (i > 0) {
System.out.print(",");
}
System.out.print(ans.get(i));
}
}
}

Python

# 求指定数二进制1的数量
def count_bit_one(x):
return bin(x & 0xffffffff).count('1')

# 将数组按照二进制个数排序
def sort_arr_by_bit_one(arr):
arr.sort(key=lambda x: (count_bit_one(x), x))
return arr

def sort_arr_by_bit(data, ops):
data_back = data[:]
sort_arr_by_bit_one(data_back)

for op in ops:
index1, index2 = op

x = data_back[index1]
y = data_back[index2]

merge_value = x | y

# 移除对应元素
# 只需要移除一个
if index1 == index2:
data_back.pop(index1)
else:
# 移除两个需要先移除后面位置的
if index1 > index2:
index1, index2 = index2, index1

data_back.pop(index2)
data_back.pop(index1)

data_back.append(merge_value)
sort_arr_by_bit_one(data_back)

return data_back

input1 = input().strip()
input2 = input().strip()

data = []
if input1:
data = list(map(int, input1.split(",")))

ops = []
if input2:
for s in input2.split():
idx = list(map(int, s.split(",")))
ops.append(idx)

ans = sort_arr_by_bit(data, ops)

print(",".join(map(str, ans)))

JavaScript

const readline = require('readline');

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

const input = [];

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

rl.on('close', () => {
const input1 = input[0] || "";
const input2 = input[1] || "";

let data = [];

if (input1.length > 0) {
data = input1.split(',').map(Number);
}

const ops = [];

if (input2.length > 0) {
for (const s of input2.split(' ')) {
const index = s.split(',').map(Number);
ops.push(index);
}
}

const ans = sortArrByBit(data, ops);

console.log(ans.join(','));
});

// 求指定数二进制1的数量
function countBitOne(x) {
let cnt = 0;
let u = x >>> 0;

while (u) {
u &= (u – 1);
cnt++;
}

return cnt;
}

// 将数组按照二进制个数排序
function sortArrByBitOne(arr) {
arr.sort((a, b) => {
const aOne = countBitOne(a);
const bOne = countBitOne(b);

if (aOne === bOne) {
return a – b;
}

return aOne – bOne;
});

return arr;
}

function sortArrByBit(data, ops) {
let dataBack = […data];

sortArrByBitOne(dataBack);

for (const op of ops) {
let [index1, index2] = op;

const x = dataBack[index1];
const y = dataBack[index2];

const mergeValue = x | y;

// 移除对应元素
// 只需要移除一个
if (index1 === index2) {
dataBack.splice(index1, 1);
} else {
// 移除两个需要先移除后面位置的
if (index1 > index2) {
[index1, index2] = [index2, index1];
}

dataBack.splice(index2, 1);
dataBack.splice(index1, 1);
}

dataBack.push(mergeValue);

sortArrByBitOne(dataBack);
}

return dataBack;
}

Go

package main

import (
"bufio"
"fmt"
"math/bits"
"os"
"sort"
"strconv"
"strings"
)

// 求指定数二进制1的数量
func countBitOne(x int) int {
return bits.OnesCount32(uint32(x))
}

// 将数组按照二进制个数排序
func sortArrByBitOne(a []int) []int {
sort.Slice(a, func(i, j int) bool {
aOne := countBitOne(a[i])
bOne := countBitOne(a[j])

if aOne == bOne {
return a[i] < a[j]
}
return aOne < bOne
})
return a
}

func sortArrByBit(data []int, ops [][]int) []int {
dataBack := append([]int{}, data…)
dataBack = sortArrByBitOne(dataBack)

for _, op := range ops {
index1 := op[0]
index2 := op[1]

x := dataBack[index1]
y := dataBack[index2]

mergeValue := x | y

// 移除对应元素
// 只需要移除一个
if index1 == index2 {
dataBack = append(dataBack[:index1], dataBack[index1+1:]…)
} else {
// 移除两个需要先移除后面位置的
if index1 > index2 {
index1, index2 = index2, index1
}

dataBack = append(dataBack[:index2], dataBack[index2+1:]…)
dataBack = append(dataBack[:index1], dataBack[index1+1:]…)
}

dataBack = append(dataBack, mergeValue)
dataBack = sortArrByBitOne(dataBack)
}

return dataBack
}

func main() {
scanner := bufio.NewScanner(os.Stdin)

input1 := ""
input2 := ""

if scanner.Scan() {
input1 = scanner.Text()
}
if scanner.Scan() {
input2 = scanner.Text()
}

var data []int

if input1 != "" {
tmp := strings.Split(input1, ",")
for _, s := range tmp {
v, _ := strconv.Atoi(s)
data = append(data, v)
}
}

var ops [][]int

if input2 != "" {
tmp := strings.Split(input2, " ")

for _, s := range tmp {
index := strings.Split(s, ",")
a, _ := strconv.Atoi(index[0])
b, _ := strconv.Atoi(index[1])

ops = append(ops, []int{a, b})
}
}

ans := sortArrByBit(data, ops)

for i, v := range ans {
if i > 0 {
fmt.Print(",")
}
fmt.Print(v)
}
}

C语言

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

#define MAXN 1005

// 求指定数二进制1的数量
int countBitOne(int x) {
unsigned int u = (unsigned int)x;
int cnt = 0;

while (u) {
u &= (u – 1);
cnt++;
}

return cnt;
}

int cmp(const void *a, const void *b) {
int x = *(int *)a;
int y = *(int *)b;

int xOne = countBitOne(x);
int yOne = countBitOne(y);

if (xOne == yOne) {
if (x < y) return –1;
if (x > y) return 1;
return 0;
}
return xOne – yOne;
}

// 将数组按照二进制个数排序
void sortArrByBitOne(int arr[], int size) {
qsort(arr, size, sizeof(int), cmp);
}

int* sortArrByBit(int data[], int dataSize,
int ops[][2], int opsSize,
int *returnSize) {

int *dataBack = (int *)malloc(sizeof(int) * MAXN);

for (int i = 0; i < dataSize; i++) {
dataBack[i] = data[i];
}

int curSize = dataSize;

sortArrByBitOne(dataBack, curSize);

for (int k = 0; k < opsSize; k++) {
int index1 = ops[k][0];
int index2 = ops[k][1];

int x = dataBack[index1];
int y = dataBack[index2];

int mergeValue = x | y;

// 移除对应元素
// 只需要移除一个
if (index1 == index2) {
for (int i = index1; i < curSize – 1; i++) {
dataBack[i] = dataBack[i + 1];
}
curSize—;
} else {
// 移除两个需要先移除后面位置的
if (index1 > index2) {
int tmp = index1;
index1 = index2;
index2 = tmp;
}

for (int i = index2; i < curSize – 1; i++) {
dataBack[i] = dataBack[i + 1];
}
curSize—;

for (int i = index1; i < curSize – 1; i++) {
dataBack[i] = dataBack[i + 1];
}
curSize—;
}

dataBack[curSize++] = mergeValue;

sortArrByBitOne(dataBack, curSize);
}

*returnSize = curSize;
return dataBack;
}

int main() {
char input1[10000000];
char input2[10000000];

fgets(input1, sizeof(input1), stdin);
fgets(input2, sizeof(input2), stdin);

input1[strcspn(input1, "\\n")] = 0;
input2[strcspn(input2, "\\n")] = 0;

int data[MAXN];
int dataSize = 0;

if (strlen(input1) > 0) {
char *token = strtok(input1, ",");

while (token) {
data[dataSize++] = atoi(token);
token = strtok(NULL, ",");
}
}

int ops[MAXN][2];
int opsSize = 0;

if (strlen(input2) > 0) {
char *token = strtok(input2, " ");

while (token) {
sscanf(token, "%d,%d", &ops[opsSize][0], &ops[opsSize][1]);
opsSize++;
token = strtok(NULL, " ");
}
}

int returnSize;
int *ans = sortArrByBit(data, dataSize, ops, opsSize, &returnSize);

for (int i = 0; i < returnSize; i++) {
if (i > 0) {
printf(",");
}
printf("%d", ans[i]);
}

free(ans);

return 0;
}

华为OD机试真题新系统【数组按二进制比特排序】

数组按二进制比特排序(C/C++/Py/Java/Js/Go)题解

题目内容

操作流程

注意

样例1

样例2

样例3

题解

C++

JAVA

Python

JavaScript

Go

C语言

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

数组按二进制比特排序(C/C++/Py/Java/Js/Go)题解

题目内容

操作流程

注意

样例1

样例2

样例3

题解

C++

JAVA

Python

JavaScript

Go

C语言

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发