算法题--华为od机试考试（组成最大数、第k个排列、最小传输时延）

目录

组成最大数

题目描述

输入描述

输出描述

示例1

输入

输出

示例2

输入

输出

解析

答案

第k个排列

题目描述

输入描述

输出描述

示例1

输入

输出

示例2

输入

输出

解析

答案 

最小传输时延

题目描述

输入描述

输出描述

示例1

输入

输出

解析

答案

---

组成最大数

考察排序

题目描述

小组中每位都有一张卡片，卡片上是6位内的正整数，将卡片连起来回以组成多种数字。

输入描述

","号分割的多个正整数字符串，不需要考虑非数字异常情况，小组最多25个人。

输出描述

最大的数字字符串

示例1

输入

22,221

输出

22221

示例2

输入

22,221,35,351,356

输出

3563535122221

解析

通过逗号分割成若干个数组，高位数字越大的应该越放前面。需要考虑不同个数的数字该如何排序，例如456,43632，这种比较前三位即可出结果456排前面。

例子改为456和456457时应该谁排前面？这里可以通过循环小的位数补齐判断，456456和456457可以得出456457排前面。所以我们可以将所有的位数不够6位的循环补齐6位后再直接排序。

答案

function getMaxNumber(str) {let numArr = str.split(',')numArr = numArr.map(v => ({value: v,sortValue: v.repeat(6).slice(0, 6)}))numArr.sort((a, b) => b.sortValue - a.sortValue)return numArr.map(v => v.value).join('')
}
console.log(getMaxNumber('22,221,35,351,356'))

第k个排列

考察分解问题，排列

题目描述

给定参数n，从1到n会有n个整数：1,2,3,...,n，这n个数字共有n！种排列。按大小顺序升序列出所有排列情况，并一一标记，

当n=3时，所有排列如下：

'123'

'132'

'213'

'231'

'312'

'321'

给定n和k，返回第k个排列

输入描述

输入两行，第一行为n，第二行为k，给定n的范围是[1,9]，给定k的范围是[1,n!]。

输出描述

输出排在第k位置的数字。

示例1

输入

3

3

输出

213

示例2

输入

4

7

输出

2134

解析

分解问题，每次取出第一位数。最后组成结果，例如示例2，所有的排列有1***，2***，3***，4***。以1开头的一共有3！=6个数，即排1~6的都是1***的。

故直接除以6即可得到在哪个区间，余数是剩余几位数的位置。同理依次往下取下一位即可。

答案 

function getPermutation(str) {let arr = str.split('\n')if (arr[0] === '1') {return 1}let num = Number(arr[0])// 剩余数let numArr = new Array(num).fill(0).map((v, i) => i + 1)let index = Number(arr[1])let res = ''while (index) {let tmp = Math.ceil(index / factorial(num - 1)) - 1// 每次取出第一位数res += numArr[tmp]numArr.splice(tmp, 1)// 剩余数的第k个位置index = index % factorial(num - 1)num--}return res + numArr[0]
}
function factorial(n) {if (n === 1) {return 1}return n * factorial(n - 1)
}console.log(getPermutation(`3
3`))
console.log(getPermutation(`4
7`))

最小传输时延

考察深度遍历，递归，hash

题目描述

某通信网络中有N个网络节点，用1到N进行标识。网络通过一个有向无环图表示，其中图的边的值表示节点之间的消息传递时延。现给定相连节点之间

的时延列表times[i]={u,v,w},其中u表示源节点，v表示目的节点，w表示u和v之间的消息传递时延。请计算给定源节点到目的节点的最小传输时延，如果目的

节点不可达，返回-1。注：1.N的取值范围为[1,100];2.时延列表times的长度不超过6000，且1<=u,v<=N,0<=w<=100;

输入描述

输入的第一行为两个正整数，分别表示网络结点的个数N，以及时延列表的长度M，用空格分隔；接下来的M行为两个节点间的

时延列表[u v w];输入的最后一行为两个正整数u和v，分别表示源结点和目的结点；

输出描述

输出一个整数，表示源结点到目的结点的最小时延。

示例1

输入

3 3

1 2 11

2 3 13

1 3 50

1 3

输出

24

解析

1.将能否到达目标节点用key-value的形式表示。通过访问对象的key是否存在判断是否能到达目标节点，其中key为起点-终点，value为时延值。

2.使用深度遍历（递归）来查找是否能到达终点。

我们用f(start,end)表示start到end的最小时延，首先需要找到f(start,end)和下一次的关系。等于start能到的所有节点出发的值中最小的一个加第一次时延的最小值。

即f(start,end)=min(f(start1,end)+start-start1,f(start2,end)+start-start2,f(start3,end)+start-start3....)，这里start1，start2，start3，为start能到的节点。

start-start1，表示start到start1节点的时延。

3.找终点。

    1.走过的节点不能再走避免循环（通过set记录走过的节点）。

    2.当前时延超过之前记录的最小时延时不需要继续往下了。

    3.当start的可达节点中有end时不需要往下继续找了。

答案

function getMinTimeDelay(str) {let paramArr = str.split('\n')let [start, end] = paramArr.pop().split(' ')let hash = {}let nodeHash = {}paramArr.forEach(v => {let tmp = v.split(' ')hash[`${tmp[0]}-${tmp[1]}`] = Number(tmp[2])if (!nodeHash[tmp[0]]) {nodeHash[tmp[0]] = {next: [tmp[1]]}} else {nodeHash[tmp[0]].next.push(tmp[1])}})let res = 0let set = new Set(start)let min = findMin(start, end, res, set, nodeHash, hash)if (min) {return min}return -1
}
function findMin(start, end, res, set, nodeHash, hash, min = Infinity) {let next = nodeHash[start].next// 大于已有结果的时延，不再往下继续寻找if (res >= min) {return}let len = next.length// 深度遍历，查找每一条路径的时延for (let i = 0; i < len; i++) {let tmp = next[i]// 找到了终点if (tmp === end) {if (min > res + hash[start + '-' + end]) {min = res + hash[start + '-' + end]}continue}// 下一个结点不能为走过的节点if (!set.has(tmp)) {// 记录走过的节点set.add(tmp)let result = findMin(tmp, end, res + hash[start + '-' + tmp], set, nodeHash, hash, min)if (result < min) {min = result}// 下一次循环前还原走过的节点set.delete(tmp)}}if (min !== Infinity) {return min}return
}
console.log(getMinTimeDelay(`3 3
1 2 11
2 3 13
1 3 50
1 3`))