华为OD机试新系统真题 - 部门内部最大层级

部门内部最大层级(Py/Java/C/C++/Js/Go)题解

华为OD机试新系统真题 华为OD上机考试新系统真题 5月31号 100分题型

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

题目内容

企业的组织架构以树形结构表示，每个节点包含：

• $left$
• $right$

为了优化管理结构，实现扁平化管理，需要计算企业的最大管理层级深度。 请计算企业的部门层级的最大深度。 注意

样例1

输入

1,#,2,#,3,#,4,#,5

输出

5

说明

1
\\
2
\\
3
\\
4
\\
5

样例2

输入

1,2,3,4,5,6,7,8,9

输出

4

说明

1
/ \\
2 3
/ \\ / \\
4 5 6 7
/ \\
8 9

样例3

输入

1,2,#

输出

2

说明

1
/
2

题解

思路：BFS

c++

#include<iostream>
#include<vector>
#include<string>
#include <utility>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<queue>
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;
}

int getMaxDepth(vector<string>& node) {

if (node.empty() || node[0] == "#") {
return 0;
}
int n = node.size();
// 使用队列进行bfs
queue<pair<string,int>> q;
int res = 1;
int index = 0;
q.push({node[index], 1});
index++;

while (!q.empty() && index < n) {
pair<string,int> cur = q.front();
int depth = cur.second;
q.pop();

string left = "#";
string right = "#";
// 左节点
if (index < n) {
left = node[index];
index++;
}
// 右节点
if (index < n) {
right = node[index];
index++;
}
// 放入队列，并记录最大深度
if (left != "#") {
q.push({left, depth + 1});
res = max(res, depth + 1);
}
// 放入队列，并记录最大深度
if (right != "#") {
q.push({right, depth + 1});
res = max(res, depth + 1);
}
}
return res;
}

int main() {
string input;
getline(cin, input);

vector<string> node ;
if (!input.empty()) {
node = split(input, ",");
}
cout << getMaxDepth(node);
return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {

static int getMaxDepth(List<String> node) {

if (node.isEmpty() || node.get(0).equals("#")) {
return 0;
}

int n = node.size();

// 使用队列进行bfs
Queue<Pair> q = new LinkedList<>();

int res = 1;
int index = 0;

q.offer(new Pair(node.get(index), 1));
index++;

while (!q.isEmpty() && index < n) {
Pair cur = q.poll();

int depth = cur.depth;

String left = "#";
String right = "#";

// 左节点
if (index < n) {
left = node.get(index++);
}

// 右节点
if (index < n) {
right = node.get(index++);
}

// 放入队列，并记录最大深度
if (!left.equals("#")) {
q.offer(new Pair(left, depth + 1));
res = Math.max(res, depth + 1);
}

// 放入队列，并记录最大深度
if (!right.equals("#")) {
q.offer(new Pair(right, depth + 1));
res = Math.max(res, depth + 1);
}
}

return res;
}

static class Pair {
String val;
int depth;

Pair(String val, int depth) {
this.val = val;
this.depth = depth;
}
}

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

String input = br.readLine();

List<String> node = new ArrayList<>();

if (input != null && !input.isEmpty()) {
node = Arrays.asList(input.split(","));
}

System.out.print(getMaxDepth(node));
}
}

Python

from collections import deque

def get_max_depth(node):

if not node or node[0] == "#":
return 0

n = len(node)

# 使用队列进行bfs
q = deque()

res = 1
index = 0

q.append((node[index], 1))
index += 1

while q and index < n:
cur, depth = q.popleft()

left = "#"
right = "#"

# 左节点
if index < n:
left = node[index]
index += 1

# 右节点
if index < n:
right = node[index]
index += 1

# 放入队列，并记录最大深度
if left != "#":
q.append((left, depth + 1))
res = max(res, depth + 1)

# 放入队列，并记录最大深度
if right != "#":
q.append((right, depth + 1))
res = max(res, depth + 1)

return res

input_str = input().strip()

node = []

if input_str:
node = input_str.split(",")

print(get_max_depth(node), end="")

JavaScript

const readline = require("readline");

function getMaxDepth(node) {

if (node.length === 0 || node[0] === "#") {
return 0;
}

const n = node.length;

// 使用队列进行bfs
const q = [];

let res = 1;
let index = 0;

q.push([node[index], 1]);
index++;

while (q.length > 0 && index < n) {
const [cur, depth] = q.shift();

let left = "#";
let right = "#";

// 左节点
if (index < n) {
left = node[index++];
}

// 右节点
if (index < n) {
right = node[index++];
}

// 放入队列，并记录最大深度
if (left !== "#") {
q.push([left, depth + 1]);
res = Math.max(res, depth + 1);
}

// 放入队列，并记录最大深度
if (right !== "#") {
q.push([right, depth + 1]);
res = Math.max(res, depth + 1);
}
}

return res;
}

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

const lines = [];

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

rl.on("close", () => {

const input = lines[0] || "";

let node = [];

if (input.length > 0) {
node = input.split(",");
}

process.stdout.write(String(getMaxDepth(node)));
});

Go

package main

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

type Pair struct {
val string
depth int
}

func getMaxDepth(node []string) int {

if len(node) == 0 || node[0] == "#" {
return 0
}

n := len(node)

// 使用队列进行bfs
q := []Pair{}

res := 1
index := 0

q = append(q, Pair{node[index], 1})
index++

for len(q) > 0 && index < n {

cur := q[0]
q = q[1:]

depth := cur.depth

left := "#"
right := "#"

// 左节点
if index < n {
left = node[index]
index++
}

// 右节点
if index < n {
right = node[index]
index++
}

// 放入队列，并记录最大深度
if left != "#" {
q = append(q, Pair{left, depth + 1})
if depth+1 > res {
res = depth + 1
}
}

// 放入队列，并记录最大深度
if right != "#" {
q = append(q, Pair{right, depth + 1})
if depth+1 > res {
res = depth + 1
}
}
}

return res
}

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

input, _ := reader.ReadString('\\n')
input = strings.TrimSpace(input)

var node []string

if input != "" {
node = strings.Split(input, ",")
}

fmt.Print(getMaxDepth(node))
}

C语言

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

typedef struct {
char value[105];
int depth;
} Pair;

int getMaxDepth(char node[][105], int nodeSize) {

if (nodeSize == 0 || strcmp(node[0], "#") == 0) {
return 0;
}

// 使用队列进行bfs
Pair queue[100005];

int front = 0;
int rear = 0;

int res = 1;
int index = 0;

strcpy(queue[rear].value, node[index]);
queue[rear].depth = 1;
rear++;
index++;

while (front < rear && index < nodeSize) {

Pair cur = queue[front++];

int depth = cur.depth;

char left[105] = "#";
char right[105] = "#";

// 左节点
if (index < nodeSize) {
strcpy(left, node[index++]);
}

// 右节点
if (index < nodeSize) {
strcpy(right, node[index++]);
}

// 放入队列，并记录最大深度
if (strcmp(left, "#") != 0) {
strcpy(queue[rear].value, left);
queue[rear].depth = depth + 1;
rear++;
if (depth + 1 > res) {
res = depth + 1;
}
}

// 放入队列，并记录最大深度
if (strcmp(right, "#") != 0) {
strcpy(queue[rear].value, right);
queue[rear].depth = depth + 1;
rear++;

if (depth + 1 > res) {
res = depth + 1;
}
}
}

return res;
}

int main() {

char input[100005];

fgets(input, sizeof(input), stdin);

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

char node[100005][105];
int nodeSize = 0;

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

while (token != NULL) {
strcpy(node[nodeSize++], token);
token = strtok(NULL, ",");
}
}

printf("%d", getMaxDepth(node, nodeSize));

return 0;
}