¶ 华为od机试题目

华为机试open in new window

牛客网约定：

输入： readline

输出： print， console.log

¶ 错题标记

87，40， 59，

76，85

¶ 简单题

¶ HJ11 数字反转

let reserveNumToString = (num) => {
    return num.toString().split('').reverse().join('')
}
let input = readline(); // 获取输入
print(reserveNumToString(input)) // 输出

复制成功

1
2
3
4
5
6

¶ HJ12 字符串反转

let reverseStr = (str) => {
    return str.split('').reverse().join('')
}
let string = readline()
print(reverseStr(string))
复制成功

1
2
3
4
5

¶ HJ54 表达式求积

console.log(eval(readline()))
复制成功

¶ *HJ75 公共子串计算

API：

动态规划 dp[i] & max

let short = readline()
let long = readline()
if(short.length > long.length) {
    let temp = short
    short = long
    long = temp
}

// let dp = new Array(short.length).fill(0)
let dp = []
let max = 0
for(let i=0; i < short.length; i++) {
    for(let j=0; j <= i; j++) {
        let str = short.slice(j, i+1)
        if(long.indexOf(str) > -1) {
            dp[i] = Math.max(str.length, dp[i] || 0)
            max = Math.max(max, dp[i] || 0)	
        }
    }
}
print(max)

复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

¶ HJ76 尼科彻斯定理

let isNico = (num) => {
    let total =  Math.pow(num,3)
    let arr = []
    let firstIndex =  Math.pow(num,2) - (num -1)
    let lastIndex =  Math.pow(num,2) + (num -1)
    for(let i=firstIndex; i <= lastIndex; i+=2) {
        arr.push(`${i}`)
    }
//     while(num--) {
//         arr.push(`${firstIndex}`)
//         firstIndex += 2
//     }
    return arr.join('+')
}

let number = readline()
print(isNico(number))
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

¶ *HJ85 最长回文子串

dp max
String.slice(i, 可溢出)

const judge = (str) => {
    return str === str.split('').reverse().join('')
}
const dp = []
let max = 0

const getSubstrLength = (str) => {
    for(let i=0; i < str.length; i++) {
        for(let j=i+1; j <= str.length; j++) {
            let tempStr = str.slice(i,j)
            if(judge(tempStr)) {
                dp[i] = Math.max(tempStr.length, dp[i]||0)
                max = Math.max(max, dp[i]||0)
            }
        }
    }
}

getSubstrLength(readline())
console.log(max)
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

¶ HJ86 求最大连续bit数

let input = readline()

let getNumTimes = (number) => {
    let arr = parseInt(number).toString(2).split('0')	
    let result = 0
    for(let i=0; i < arr.length; i++) {
        if(arr[i].length > result) {
            result = arr[i].length
        }
    }
    return result
}
console.log(getNumTimes(input))
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13

¶ *HJ87 密码强度等级

diu 这么长

直接抄题解

function getScore(str) {
    const length = str.length;
    const map = {
        len: length,
        upperCaseLetters: 0,
        lowerCaseLetters: 0,
        symbols: 0,
        numbers: 0,
    };
    let score = 0;

    for (let i = 0; i < length; i++) {
        const code = str[i].charCodeAt(0);
        if (code >= 48 && code <= 57) {
            map.numbers++;
        } else if (code >= 65 && code <= 90) {
            map.upperCaseLetters++;
        } else if (code >= 97 && code <= 122) {
            map.lowerCaseLetters++;
        } else {
            map.symbols++;
        }
    }
    //   长度
    if (map.len >= 8) {
        score += 25;
    } else if (map.len >= 5 && map.len <= 7) {
        score += 10;
    } else {
        score += 5;
    }
    // 数字
    if (map.numbers === 1) {
        score += 10;
    } else if (map.numbers > 1) {
        score += 20;
    }
    // 字母
    if (map.upperCaseLetters > 0 && map.lowerCaseLetters > 0) {
        score += 20;
    } else if (map.upperCaseLetters > 0 || map.lowerCaseLetters > 0) {
        score += 10;
    }
    //   符号
    if (map.symbols === 1) {
        score += 10;
    } else if (map.symbols > 1) {
        score += 25;
    }

    //   奖励
    if (map.numbers > 0) {
        if (
            map.upperCaseLetters > 0 &&
            map.lowerCaseLetters > 0 &&
            map.symbols > 0 &&
            map.numbers > 0
        ) {
            score += 5;
        } else if (
            (map.upperCaseLetters > 0 || map.lowerCaseLetters > 0) &&
            map.symbols > 0 &&
            map.numbers > 0
        ) {
            score += 3;
        } else if (map.upperCaseLetters > 0 || map.lowerCaseLetters > 0) {
            score += 2;
        }
    }
    if (score >= 90) {
        return "VERY_SECURE";
    } else if (score >= 80) {
        return "SECURE";
    } else if (score >= 70) {
        return "VERY_STRONG";
    } else if (score >= 60) {
        return "STRONG";
    } else if (score >= 50) {
        return "AVERAGE";
    } else if (score >= 25) {
        return "WEAK";
    } else {
        return "VERY_WEAK";
    }

}

复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

¶ HJ100 等差数列

an = a1 + (n-1)d

while(line = readline()) {
    const num = parseInt(line);
    let total = 0;
    for (let i = 2; i <= 2 + 3*(num-1); i = i+3) {
        total += i;
    }
    print(total);
}
复制成功

1
2
3
4
5
6
7
8

¶ HJ106 字符逆序

let line = readline()
let result = line.split('').reverse().join('')
print(result)
复制成功

1
2
3

¶ 中等题

¶ HJ5 进制转换

parseInt(data, radix)

const hexTodec = (hex) => parseInt(hex,16)
let result = hexTodec(readline())
print(result)
复制成功

1
2
3

¶ HJ10 字符个数统计

let line = readline()
let result = new Set(line.split('')).size
print(result)
复制成功

1
2
3

¶ HJ14 字符串排序

let input = parseInt(readline())
function sortWordList(num) {
    const wordList = []
    while(num--) {
        wordList.push(readline())
    }
    wordList.sort((a,b) => a > b ? 1:-1).forEach(item => {console.log(item)})
}
sortWordList(input)
复制成功

1
2
3
4
5
6
7
8
9

¶ HJ40 统计字符

function countChar(str) {
    const arr = str.split('')
    let map = {
        letters: 0,
        space: 0,
        numbers: 0,
        symbols:0
    }
    for(let item of arr){
        let code = item.charCodeAt()
        if(code >=65 && code <=90 || code >=97 && code <=122) {
            map.letters++
        }
        else if(code >=48 && code <=57 ) {
            map.numbers++
        }
        else if(code === 32) {
            map.space++
        }else {
            map.symbols++
        }
    }
    print(map.letters)
    print(map.space)
    print(map.numbers)
    print(map.symbols)
}
countChar(readline())
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

¶ HJ46 截取字符串

function mySlice(str, end) {
    return str.slice(0, end)
}
const result = mySlice(readline(), readline())
print(result)
复制成功

1
2
3
4
5

¶ HJ58 输入n个整数，输出其中最小的k个

注意输入。第一行输入n和k，相当于输入有空格的字符串啦

let [n, k] = readline().split(' ')
let multies = readline()
const getSortedArr = (str) => {
    const arr = str.trim().split(' ')
    return arr.sort((a, b) => a - b)
}
let result = getSortedArr(multies).slice(0, k).join(' ')
print(result)


//
let [n, k] = readline().split(' ')
let secArr = readline().split(' ')
secArr = secArr.sort((a, b) => a - b).slice(0, k)
print(secArr.join(' '))

复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

¶ HJ59 找出字符串中第一个只出现一次的字符

用正则，let reg = new RegExp(${str[i]}, 'g')
string.match(reg).length === 1
- image-20220402131933853

function getOnceFirstChar(str) {
  let res = -1
  for(let i=0; i < str.length; i++){
    let reg = new RegExp(`${str[i]}`,'g')
    if(str.match(reg).length == 1){
      res = str[i]
      break
    }
  }
    return res
}
let result = getOnceFirstChar(readline())
print(result)
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13

¶ HJ60 查找组成一个偶数最接近的两个素数

检验是否是素数, 也是差不多遍历一半
1. 题解是这样的： i < Math.ceil(n / ``2``)
按偶数的大小遍历一半就可以了

function isPrime(num) {
    const temp = Math.floor(Math.sqrt(num))
    //为什么是2
    for(let i=2; i <= temp; i++) {
        if(num % i === 0) {
            return false
        } 
    }
    return true
}
function getPrimesFromEven(num) {
    let result = []
    for(let i=2; i <= Math.floor(num / 2); i++) {
        if(isPrime(i) && isPrime(num-i)) {
            result = [i, num-i]
        }
    }
    print(result[0])
    print(result[1])
}
getPrimesFromEven(readline())
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

¶ HJ81 字符串字符匹配

const short = readline()
const long = readline()
function cook(short='', long) {
    let arr = short.split('')
    return arr.every(item => long.includes(item))
    //both okay
    //return short.split('').every(char => long.indexOf(char) !== -1)
}
let result = cook(short, long)
print(result)
复制成功

1
2
3
4
5
6
7
8
9
10

¶ HJ96 表示数字

正则

string.replace(regExp, function)

function padStar(str) {
    return str.replace(/[0-9]+/g, val => `*${val}*`)
}
print(padStar(readline()))
复制成功

1
2
3
4

¶ leetcode

¶ 剑指 Offer 62. 圆圈中最后剩下的数字open in new window

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function(n, m) {
    // 迭代 f(n) = [f(n-1) + m] % n
    // i <= n 的解释：两个人就要通过迭代来找,需要参与循环
    let now = 0
    for(let i=2; i <= n; i++) {
        now = (now + m ) % i
    }
    return now
};
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14

¶ 【滑动窗口】剑指 Offer 57 - II. 和为s的连续正数序列open in new window

¶ 滑动窗口框架

let left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14

套入即可
这里的题意隐藏条件没有给定具体的数组num 我们可以通过下标关联[1,2,3,4,5,6,7....]

/**
 * @param {number} target
 * @return {number[][]}
 */
// 没有参照物数组 但是可以根据下标
// 滑动窗口（双指针）
var findContinuousSequence = function(target) {
    let l=1
    let r=2
    let sum = 3
    let res=[]
    // 滑动窗口框架
    while(l<r){
        if(sum===target){
            let ans =[]
            for(let k=l;k<=r;k++){
                ans[k-l]=k
            }
            res.push(ans)
            // 等于的情况 我们可以继续窗口往右搜索 同时缩小左边的
             sum=sum-l
             l++
        } else if(sum>target){
            // 大于的条件 缩小窗口 sum已经加过了
            sum=sum-l
            l++
        } else {
            // 小于的情况 滑动窗口继续扩大
            r++
            sum=sum+r
        }
    }
    return res
};
//[题解链接](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/song-gei-qian-duan-tong-xue-tong-su-yi-d-u7z9/)
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

¶ 【滑动窗口】3 无重复字符的最长子串

¶ 题解

var lengthOfLongestSubstring = function(s) {
    // 哈希集合，记录每个字符是否出现过
    const occ = new Set();
    const n = s.length;
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    let rk = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i != 0) {
            // 左指针向右移动一格，移除一个字符
            occ.delete(s.charAt(i - 1));
        }
        while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
            // 不断地移动右指针
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};

复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

¶ 复杂度分析

时间复杂度：O(N)O(N)，其中 NN 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

¶ 14. 最长公共前缀open in new window

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length === 1) return strs[0]
    let ans = strs[0]
    for(let i=1; i < strs.length; i++) {
        let j=0
        for(; j < ans.length; j++) {
            if(ans[j] !== strs[i][j]) {
                break
            }
        }
        ans = ans.slice(0, j)
    }
    return ans
};
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

¶ 151. 颠倒字符串中的单词open in new window

双指针
array.reverse

//待定
复制成功

https://leetcode-cn.com/problems/reverse-words-in-a-string/solution/151-fan-zhuan-zi-fu-chuan-li-de-dan-ci-j-zle0/

¶ 434. 字符串中的单词数open in new window

/**
 * @param {string} s
 * @return {number}
 */
var countSegments = function(s) {
    // return s.split(' ').filter(c => c).length
    let segmentCount = 0
    for(let i=0; i < s.length; i++) {
        if((i === 0 || s[i-1] === ' ') && s[i]!== ' ' ) {
            segmentCount++
        }
    }
    return segmentCount
};
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14

¶ 581. 最短无序连续子数组open in new window

解题思路这道题最难的地方在于，读懂题目！！！“如果对这个子数组进行升序排序，那么整个数组都会变为升序排序”，理解了这句话就很简单了。

数组复制一份，从小到大排序，用两个指针分别从左右开始移动，如果原数组中的元素和排序后一致，就可以继续移动，否则退出。最后判断一下两个指针的位置就可以了。

original: [2,6,4,8,10,9,15] sorted : [2,4,6,8,9,10,15] i ->
<- j 代码

/**

 * @param {number[]} nums
 * @return {number}
   */
var findUnsortedSubarray = function(nums) {
    const copied = nums.slice(0).sort((a, b) => a - b)
    let i = 0
    let j = nums.length - 1
    while (copied[i] === nums[i] && i < nums.length) {
        i++
    }
    while (copied[j] === nums[j] && j >= 0) {
        j--
    }
    if (i >= j) {
        return 0
    }
    return j - i + 1
};

复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

¶ *[gcd]1071. 字符串的最大公因子open in new window

https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/1071-zi-fu-chuan-de-zui-da-gong-yin-zi-by-wonderfu/

看到标题里面有最大公因子这个词，于是先默写一下 gcd 算法

const gcd = (a, b) => (0 === b ? a : gcd(b, a % b))

总有一种好像顺手就能用上的感觉呢。

其实看起来两个字符串之间能有这种神奇的关系是挺不容易的，我们希望能够找到一个简单的办法识别是否有解。

如果它们有公因子 abc，那么 str1 就是 mm 个 abc 的重复，str2 是 nn 个 abc 的重复，连起来就是 m+nm+n 个 abc，好像 m+nm+n 个 abc 跟 n+mn+m 个 abc 是一样的。

所以如果 str1 + str2 === str2 + str1 就意味着有解。

我们也很容易想到 str1 + str2 !== str2 + str1 也是无解的充要条件。

当确定有解的情况下，最优解是长度为 gcd(str1.length, str2.length) 的字符串。

这个理论最优长度是不是每次都能达到呢？是的。

因为如果能循环以它的约数为长度的字符串，自然也能够循环以它为长度的字符串，所以这个理论长度就是我们要找的最优解。

把刚刚写的那些拼起来就是解法了。

var gcdOfStrings = function(str1, str2) {
  if (str1 + str2 !== str2 + str1) return ''
  const gcd = (a, b) => (0 === b ? a : gcd(b, a % b))
  return str1.substring(0, gcd(str1.length, str2.length))
};
复制成功

1
2
3
4
5

¶ 1111. 有效括号的嵌套深度open in new window

// 不知道干嘛的，先照抄吧
let mid=max>>1;
return arr.map(item=>item>mid?1:0);
复制成功

1
2
3

¶ 题解

先计算seq每个位置i对应的深度arr[i] 在arr中最大深度max 取深度的一半mid，若某个点arr[i]>mid,那么将其分配给B，否则分配给A 例如：最大深度为4，无论如何取值max(deepth(A),deepth(B))都不可能比2小了，那么将所有深度大于2的都分配给B，深度小于2的都分配给A，那么此时的max(deepth(A),deepth(B))最小并为：2

var maxDepthAfterSplit = function(seq) {
    let deep=0;
    let arr=new Array(seq.length);
    let max=0;
    for(let i=0;i<seq.length;i++){
        if(seq[i]==="("){
            deep++;
        }
        arr[i]=deep;
        max=Math.max(max,deep)
        if(seq[i]===")"){
            deep--;
        }
    }
    let mid=max>>1;
    return arr.map(item=>item>mid?1:0);
};
//链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solution/javascript-by-wanyan/
复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

¶ **【马戏团】JS 排序+二分查找

¶ 解题思路

也是通过排序+二分法获取最大子串长度解决的。

将height升序排列，如果遇到同值，将对应序列的weight进行降序排列使用二分法获取weight的最大子串的长度，就是最终结果(有关二分法获取最大子串长度可以参考第300题的题解)

¶ 代码

/**
 * @param {number[]} height
 * @param {number[]} weight
 * @return {number}
 */
var bestSeqAtIndex = function(height, weight) {
  const data = [];
  const dp = [];
  for(let i = 0;i < height.length;i++) {
    const item  = {
      height: height[i],
      weight: weight[i]
    };
    data.push(item);
  }
  data.sort(function(a, b) {
    if(a.height === b.height) {
      return b.weight - a.weight;
    }
    return a.height - b.height;
  });
  // 利用二分法获取weight的最长子串的值就是结果
  let res = 0;
  for(let index in data) {
    index = Number(index);
    let w = data[index].weight;
    let i = 0;
    let j = res;
    while(i < j) {
      const m = parseInt((i + j) / 2);
      if(dp[m] < w) {
        i = m + 1;
      } else {
        j = m;
      }
    }
    dp[i] = w;
    if(j === res) res++;
  }
  return res;
};

复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

晓露寝安浅云逍遥十漾轻拟

¶ # 华为od机试题目

¶ # 错题标记

¶ # 简单题

¶ # HJ11 数字反转

¶ # HJ12 字符串反转

¶ # HJ54 表达式求积

¶ # *HJ75 公共子串计算

¶ # HJ76 尼科彻斯定理

¶ # *HJ85 最长回文子串

¶ # HJ86 求最大连续bit数

¶ # *HJ87 密码强度等级

¶ # HJ100 等差数列

¶ # HJ106 字符逆序

¶ # 中等题

¶ # HJ5 进制转换

¶ # HJ10 字符个数统计

¶ # HJ14 字符串排序

¶ # HJ40 统计字符

¶ # HJ46 截取字符串

¶ # HJ58 输入n个整数，输出其中最小的k个

¶ # HJ59 找出字符串中第一个只出现一次的字符

¶ # HJ60 查找组成一个偶数最接近的两个素数

¶ # HJ81 字符串字符匹配

¶ # HJ96 表示数字

¶ # leetcode

¶ # 剑指 Offer 62. 圆圈中最后剩下的数字open in new window

¶ # 【滑动窗口】 剑指 Offer 57 - II. 和为s的连续正数序列open in new window

¶ # 滑动窗口框架

¶ # 【滑动窗口】3 无重复字符的最长子串

¶ # 题解

¶ # 复杂度分析

¶ # 14. 最长公共前缀open in new window

¶ # 151. 颠倒字符串中的单词open in new window

¶ # 434. 字符串中的单词数open in new window

¶ # 581. 最短无序连续子数组open in new window

¶ # *[gcd]1071. 字符串的最大公因子open in new window

¶ # 1111. 有效括号的嵌套深度open in new window

¶ # 题解

¶ # **【马戏团】JS 排序+二分查找

¶ # 解题思路

¶ # 代码

¶ 华为od机试题目

¶ 错题标记

¶ 简单题

¶ HJ11 数字反转

¶ HJ12 字符串反转

¶ HJ54 表达式求积

¶ *HJ75 公共子串计算

¶ HJ76 尼科彻斯定理

¶ *HJ85 最长回文子串

¶ HJ86 求最大连续bit数

¶ *HJ87 密码强度等级

¶ HJ100 等差数列

¶ HJ106 字符逆序

¶ 中等题

¶ HJ5 进制转换

¶ HJ10 字符个数统计

¶ HJ14 字符串排序

¶ HJ40 统计字符

¶ HJ46 截取字符串

¶ HJ58 输入n个整数，输出其中最小的k个

¶ HJ59 找出字符串中第一个只出现一次的字符

¶ HJ60 查找组成一个偶数最接近的两个素数

¶ HJ81 字符串字符匹配

¶ HJ96 表示数字

¶ leetcode

¶ 剑指 Offer 62. 圆圈中最后剩下的数字open in new window

¶ 【滑动窗口】剑指 Offer 57 - II. 和为s的连续正数序列open in new window

¶ 滑动窗口框架

¶ 【滑动窗口】3 无重复字符的最长子串

¶ 题解

¶ 复杂度分析

¶ 14. 最长公共前缀open in new window

¶ 151. 颠倒字符串中的单词open in new window

¶ 434. 字符串中的单词数open in new window

¶ 581. 最短无序连续子数组open in new window

¶ *[gcd]1071. 字符串的最大公因子open in new window

¶ 1111. 有效括号的嵌套深度open in new window

¶ 题解

¶ **【马戏团】JS 排序+二分查找

¶ 解题思路

¶ 代码