牛客上的化为机试题目

挑选了一些我认为比较有难度或者延伸知识比较多的题目做题解。

HJ6 质数因子

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）
数据范围: 1<=n<=2x10^9+14
输入描述：
输入一个整数
输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。

相关信息

质数： 只能被自己和1整除的数。
因子： 乘法的一部分叫做因子。
题目的意思约等于： 给定一个整数x，有不定多个质数能整除x，在数学上叫做分解质因式。
切入点： 任何一个数，只要大于2，就一定会被1，2，3，5，7自身等其其中之一或多个整除。 以180来说，从path=2开始，被2整除，说明2是它的质因数，得到90，也能被2整除，得到45，能被3整除，得到15 能被3整除，得到5，只能被自身整除，最后num等于1，完全整除，如果不等，则说明它本身就是一个质数。

有主要代码如下

const multiples = (num:number):string => {
  let path = 2; //质数从2以上开始计算
  let res = "" //结果集
  while (path <= num && path*path <= num){
      if (num % path === 0){
          res+= ` ${path}`
          num /= path
          path = 2
      }else {
          path++
      }
  }
  if (num !== 1){
      res+= ` ${num}`
  }
  return res
}

HJ14 字符串排序

描述：给定 n 个字符串，请对 n 个字符串按照字典序排列。

JavaScript中的字典排序

java等高级语言一般需要手动实现字典排序，但是JavaScript不一样，js默认使用的排序方式为字典排序。 比如一个序列[1,2,5,10],使用arrayObj.sort得到的结果为[1,10,2,5]。js一般需要手动实现精确的排序。

const arr = readLine
arr.forEach(item=>{
        console.log(item)
    })

HJ15 求int型正整数在内存中存储时1的个数

输入一个 int 型的正整数，计算出该 int 型数据在内存中存储时 1 的个数。
数据范围：保证在 32 位整型数字范围内
输入描述：
输入一个整数（int类型）
输出描述：
这个数转换成2进制后，输出1的个数

js中进制转换的方法

一般都使用parseInt(num,进制)转换为十进制，使用toString(进制)转换为指定进制

const num:string = "输入一个数值型的数字"
const arr = parseInt(num).toString(2).split("")
let count = 0
arr.forEach(item=>{
    if (item === "1") count++
})
console.log(count)

HJ28 素数伴侣

题目太长，请前往查看 这是一个二分图求最大匹配数的问题，使用匈牙利算法解答 以下是代码块：

//HJ28
const prime = (num:any): boolean => {
    debugger
    if (num < 2) {
        return false;
    }
    for (let i = 2; i < num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
const even  = (num:number|any):boolean => {
    return num%2 === 0
}

let N = 0 //左侧数组长度
let M = 0 //右侧数组长度
let k = 0 //记录输入字符串长度，同时用于判断是否第一次输入
let odds:number[] = [] //奇数串
let evens:number[] = [] //偶数串
let eToO:any = [] //记录当前偶数匹配的奇数定位
let oddStatus:any = [] //记录当前奇数是否被访问过
let mapPrime:any = [] // 左侧和右侧的公共边（两数相加能为素数）
rl.on("line",(line:string) => {
    if (k === 0) k = Number(line)
    else {
        let temp = line.split(" ").map(Number)
        for (let number of temp) {
            if (even(number)){
                evens.push(number)
            }else {
                odds.push(number)
            }
        }
        N = evens.length
        M = odds.length
        eToO = new Array(M).fill(-1) //初始化长度为奇数（右侧）长度的数组，匹配位置不能大于0
        mapPrime = new Array(N).fill(undefined).map(()=>{
            return  new Array(M).fill(false)
        }) //初始化公共边数量为0
        // 初始化map,eToO,oddStatus
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (prime(evens[i]+odds[j])){
                    mapPrime[i][j] = true
                }
            }
        }
        let res = 0
        for (let i = 0; i < N; i++) { //开始遍历偶数列表
            oddStatus = new Array(M).fill(false) //初始化访问状态为false 全未访问
            if (HJ28(i)){
                res++
            }
        }
        console.log(res)
        rl.close()
    }
})



//HJ28
const HJ28 = (i:number):boolean => {
    for (let j = 0; j < M; j++) {
        if (mapPrime[i][j] && !oddStatus[j]){ //当前访问的奇数和偶数能组成素数并且当前的奇数没有被访问过
            oddStatus[j] = true //j位置的素数已经访问过了
            if (eToO[j] === -1 || HJ28(eToO[j])){ //当前奇数还没有被匹配过或者当前奇数的原配能够找到另一个
                eToO[j] = i
                return true
            }
        }
    }
    return  false
}

匈牙利算法在我的另一篇文章有学习过程:匈牙利算法