算法题--华为od机试测验（围棋的气、用一连天然数之和来表达整数、亲子游戏 ...

目次
围棋的气
题目描述
输入描述
示例1
输入
输出
剖析
答案
用一连天然数之和来表达整数
题目描述
输入描述
输出描述
示例1
输入
输出
说明
示例2
输入
输出
剖析
答案
亲子游戏
题目描述
输入描述
输出描述
示例1
输入
输出
说明
示例2
输入
输出
说明
备注
剖析

---

围棋的气

观察hash、理解、二维数组
题目描述

围棋棋盘由纵横各19条线垂直相交构成，棋盘上一共19x19=361个交点，对弈双方一方执白棋，一方执黑棋，落子时只能将棋子置于交点上。
“气”是围棋中很重要的一个概念，某个棋子有几口气，是指其上下左右方向四个相邻的交织点中，有几个交织点没有棋子，由此可知：
1、在棋盘的边沿上的棋子最多有3口气（黑1），在棋盘角点的棋子最多有2口气（黑2），别的情况最多有4口气（白1）
2、全部同色棋子的气之和叫作该色棋子的气，必要注意的是，同色棋子重合的气点，对于该颜色棋子来说，只能盘算一次气，比如下图中，黑棋一共4口气，而不是5口气，因为黑1和黑2中心红色三角标出的气是两个黑棋共有的，对于黑棋整体来说只能算一个气。
3、本题目只盘算气，对于眼也按气盘算，假如您不清楚“眼”的概念，可忽略，按照前面描述的规则盘算即可。
现在，请根据输入的黑棋和白棋的坐标位置，盘算黑棋和白起一共各有多少气？
输入描述

输入包括两行数据，如：
0 5 8 9 9 10
5 0 9 9 9 8
1、每行数据以空格分隔，数据个数是2的整数倍，每两个数是一组，代表棋子在棋盘上的坐标；
2、坐标的原点在棋盘左上角点，第一个值是行号，范围从0到18；第二个值是列号，范围从0到18。
示例1

输入

0 5 8 9 9 10
5 0 9 9 9 8
输出

15
剖析

起首天生一个19*19的二维数组，这里注意new Array后用fill填值天生会导致对象的引用一致题目，必要用map解决。
这里必要设计棋盘每个点的对象，这里用value表示下得棋的颜色， 0 ,1,2表示空、黑、白，white和black属性用于表示是否已经盘算过黑白棋的气。
然后只用通过for循环盘算每个方向上的假如value为0且，当前盘算的属性的值对应为true即可+1。这里注意假如棋下在边界必要思量数组越界题目。
这里使用?.访问，当属性不存在时会返回undefined。
答案

1. function getWeiQiAir(str) {
2.     let [black, white] = str.split('\n')
3.     black = black.split(' ').map(Number)
4.     white = white.split(' ').map(Number)
5.     // value: 0 ,1,2表示空、黑、白,white和black属性用于表示是否已经计算过黑白棋的气。
6.     // 注意生成的二维数组不能直接用fill填{ value: 0, white: true, black: true }。这样会导致引用一致，改一个value，所有的value都会变。
7.     let qipan = new Array(19).fill(0).map(v => new Array(19).fill(0).map(v => ({ value: 0, white: true, black: true })))
8.     // 棋盘上下对应的棋
9.     let lenB = black.length
10.     for (let i = 0; i < lenB; i = i + 2) {
11.         qipan[black[i]][black[i + 1]].value = 1
12.     }
13.     let lenW = white.length
14.     for (let i = 0; i < lenW; i = i + 2) {
15.         qipan[white[i]][white[i + 1]].value = 2
16.     }
17.     let sum = 0
18.     // 计算黑棋的气
19.     for (let i = 0; i < lenB; i = i + 2) {
20.         let x = black[i]
21.         let y = black[i + 1]
22.         // 第一个条件判断某一个方向是否为空，第二个条件判断是否被当前颜色计算过
23.         // 注意如果棋下在边界需要考虑数组越界问题。这里使用?.访问，当属性不存在时会返回undefined
24.         if (qipan?.[x - 1]?.[y]?.value == 0 && qipan[x - 1][y].black) {
25.             qipan[x - 1][y].black = false
26.             sum++
27.         }
28.         if (qipan[x]?.[y - 1]?.value == 0 && qipan[x][y - 1].black) {
29.             qipan[x][y - 1].black = false
30.             sum++
31.         }
32.         if (qipan?.[x + 1]?.[y]?.value == 0 && qipan[x + 1][y].black) {
33.             qipan[x + 1][y].black = false
34.             sum++
35.         }
36.         if (qipan[x]?.[y + 1]?.value == 0 && qipan[x][y + 1].black) {
37.             qipan[x][y + 1].black = false
38.             sum++
39.         }
40.     }
41.     // 计算白棋的气
42.     for (let i = 0; i < lenW; i = i + 2) {
43.         let x = white[i]
44.         let y = white[i + 1]
45.         if (qipan?.[x - 1]?.[y]?.value == 0 && qipan[x - 1][y].white) {
46.             qipan[x - 1][y].white = false
47.             sum++
48.         }
49.         if (qipan[x]?.[y - 1]?.value == 0 && qipan[x][y - 1].white) {
50.             qipan[x][y - 1].white = false
51.             sum++
52.         }
53.         if (qipan?.[x + 1]?.[y]?.value == 0 && qipan[x + 1][y].white) {
54.             qipan[x + 1][y].white = false
55.             sum++
56.         }
57.         if (qipan[x]?.[y + 1]?.value == 0 && qipan[x][y + 1].white) {
58.             qipan[x][y + 1].white = false
59.             sum++
60.         }
61.     }
62.     return sum
63. }
64. console.log(getWeiQiAir(`0 5 8 9 9 10
65. 5 0 9 9 9 8`))

复制代码

用一连天然数之和来表达整数

观察数学，双指针
题目描述

一个整数可以由一连的天然数之和来表示。
给定一个整数，盘算该整数有几种一连天然数之和的表达式，且打印出每种表达式
输入描述

一个目标整数T (1 <=T<= 1000)
输出描述

该整数的全部表达式和表达式的个数。假如有多种表达式，输出要求为：
天然数个数最少的表达式优先输出
每个表达式中按天然数递增的次序输出，具体的格式参见样例。
在每个测试数据结束时，输出一行”Result:X”，其中X是最终的表达式个数。
示例1

输入

9
输出

9=9
9=4+5
9=2+3+4
Result:3
说明

整数9有三种表达方法
示例2

输入

10
输出

10=10
10=1+2+3+4
Result:2
剖析

方法一：通过遍历加盘算，假设有i个数合为目标数n，其中最小的数为m，即m，m+1,m+2,...,m+i-1的和为n，即i*m+1+2+...+i-1=n。故n减去1加到i-1的和
必要被m整除即可。
方法二：类似于双指针，用i和j指向头和尾(i<j)，i不停加到j假如大于即是目标值时（即是的时候还必要记录效果），i加一，假如小于目标值时j+1，
当i和j都大于目标值除以2时结束循环。
答案

1. // 方法一
2. function continusInteger(n) {
3.     let res = [`${n}=${n}`]
4.     for (let i = 2; i < Math.floor(n / 2); i++) {
5.         // new Array(i).fill(0).reduce((t,v,i)=>t+i)表示1+2+...+i-1
6.         let tmp = n - new Array(i).fill(0).reduce((t, v, i) => t + i)
7.         let start = tmp / i
8.         // 找到最小的数start，拼接连续自然数加入结果数组中
9.         if (Number.isInteger(start)) {
10.             let str = `${n}=${start}`
11.             for (j = 1; j < i; j++) {
12.                 str = str + `+${start + j}`
13.             }
14.             res.push(str)
15.         }
16.     }
17.     return `${res.join('\n')}\nResult:${res.length}`
18. }
19. // 方法二
20. function continusInteger(n) {
21.     if (n < 3) {
22.         return `${n}=${n}\nRestult:1`
23.     }
24.     let res = [`${n}=${n}`]
25.     let i = 1, j = 2
26.     sum = i + j
27.     while (i < n / 2 || j < n / 2) {
28.         if (sum < n) {
29.             j++
30.             sum = sum + j
31.         } else if (sum > n) {
32.             sum = sum - i
33.             i++
34.         } else {
35.             // 找到目标值记录
36.             let str = `${n}=${i}`
37.             for (let x = i + 1; x <= j; x++) {
38.                 str = str + `+${x}`
39.             }
40.             res.push(str)
41.             j++
42.             sum = sum + j
43.         }
44.     }
45.     return `${res.join('\n')}\nResult:${res.length}`
46. }
47. console.log(continusInteger(9))
48. console.log(continusInteger(10))

复制代码

亲子游戏

观察深度遍历、递归
题目描述

宝宝和妈妈到场亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有差别的糖果数量，部分格子有障碍物。
游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的全部糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
叨教妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先思量最短时间到达的情况下尽大概多拿糖果）。
输入描述

第一行输入为N，N标识二维矩阵的大小
之后N行，每行有N个值，表格矩阵每个位置的值
其中：
-3：妈妈
-2：宝宝
-1：障碍
=0：糖果数(0表示没有糖果，但是可以走)
输出描述

输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格
示例1

输入输出示例仅供调试，后台判题数据一样平常不包罗示例
输入

4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
输出

9
说明

此地图有两条最短路径可到宝宝位置，绿色线和黄色线都是最短路径6步，但是黄色拿到的糖果更多，9个
示例2

输入

4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3
输出

-1
说明

此地图妈妈无法到达宝宝位置
备注

地图最大5050
剖析

1.用二维数组表示图中每个点，每个点为一个对象v属性对应每个点的数值，can属性对应是否可以颠末。
2.用深度遍向来找出效果：
    1.起首f(start,end)表示从起点到终点获得的最短路劲已经最大糖果数。f(start,end)即是min(f(start-top,end),f(start-bottom,end),f(start-left,end),f(start-end,end))。其中start-top表示start位置向
上走一格后的位置。这里表示从4个方向走一格后到终点位置的值，取最短的一个路径,注意假如路径同样短的要取一个糖果多的，所以f(start,end)必要
返回2个效果一个为最短路径和最大的糖果数。
    2.找终点：
        1>当start和end对应的横、纵坐标之差的绝对值为1时，说明起点和终点相邻，即可以直接退出。
        2>当当前的步数已经大于即是已有乐成的步数时，可以直接退出。
        3>每次走过的位置，把can属性设置为false，防止走回头路，当4个方向都走不了时，直接退出。
        4>每次走完后必要还原之前的步数、糖果数、起点坐标以及数组中的是否已经颠末的属性can。

1. function getMinPath(str) {
2.     let arr = str.split('\n')
3.     let len = Number(arr.shift())
4.     let start = {}, end = {}
5.     // 用二维数组表示图中的每个点
6.     arr = arr.map((v, i) => v.split(' ').map((v, j) => {
7.         v = Number(v)
8.         // 记录起点和终点的位置
9.         if (v === -3) {
10.             start.x = i
11.             start.y = j
12.         }
13.         if (v === -2) {
14.             end.x = i
15.             end.y = j
16.         }
17.         return { v, can: true }
18.     }))
19.     let res = bfs(start, end, 0, 0, len, arr)
20.     if (res) {
21.         return res[1]
22.     }
23.     return -1
24. }
25. function bfs(start, end, step, candi, len, arr, min = Infinity, max = 0) {
26.     if (Math.abs(start.x - end.x) + Math.abs(start.y - end.y) === 1) {
27.         return [step, candi]
28.     }
29.     if (step >= min) {
30.         return
31.     }
32.     if (start.x + 1 < len) {
33.         if (arr[start.x + 1][start.y].v >= 0 && arr[start.x + 1][start.y].can) {
34.             start.x++
35.             step++
36.             candi += arr[start.x][start.y].v
37.             arr[start.x][start.y].can = false
38.             let r = bfs(start, end, step, candi, len, arr, min, max)
39.             if (r) {
40.                 if (r[0] < min) {
41.                     // 当前解的步数小于已有的成功步数，
42.                     min = r[0]
43.                     max = r[1]
44.                 } else if (r[0] === min && r[1] > max) {
45.                     // 当前解的步数等于已有的成功步数，糖果数大于已有成功步数的糖果数
46.                     判断当前解的
47.                     max = r[1]
48.                 }
49.             }
50.             //还原
51.             start.x--
52.             step--
53.             candi -= arr[start.x][start.y].v
54.             arr[start.x][start.y].can = true
55.         }
56.     }
57.     if (start.x - 1 >= 0) {
58.         if (arr[start.x - 1][start.y].v >= 0 && arr[start.x - 1][start.y].can) {
59.             start.x--
60.             step++
61.             candi += arr[start.x][start.y].v
62.             arr[start.x][start.y].can = false
63.             let l = bfs(start, end, step, candi, len, arr, min, max)
64.             if (l) {
65.                 if (l[0] < min) {
66.                     min = l[0]
67.                     max = l[1]
68.                 } else if (l[0] === min && l[1] > max) {
69.                     max = l[1]
70.                 }
71.             }
72.             //还原
73.             start.x++
74.             step--
75.             candi -= arr[start.x][start.y].v
76.             arr[start.x][start.y].can = true
77.         }
78.     }
79.     if (start.y + 1 < len) {
80.         if (arr[start.x][start.y + 1].v >= 0 && arr[start.x][start.y + 1].can) {
81.             start.y++
82.             step++
83.             candi += arr[start.x][start.y].v
84.             arr[start.x][start.y].can = false
85.             let t = bfs(start, end, step, candi, len, arr, min, max)
86.             if (t) {
87.                 if (t[0] < min) {
88.                     min = t[0]
89.                     max = t[1]
90.                 } else if (t[0] === min && t[1] > max) {
91.                     max = t[1]
92.                 }
93.             }
94.             //还原
95.             start.y--
96.             step--
97.             candi -= arr[start.x][start.y].v
98.             arr[start.x][start.y].can = true
99.         }
100.     }
101.     if (start.y - 1 >= 0) {
102.         if (arr[start.x][start.y - 1].v >= 0 && arr[start.x][start.y - 1].can) {
103.             start.y--
104.             step++
105.             candi += arr[start.x][start.y].v
106.             arr[start.x][start.y].can = false
107.             let b = bfs(start, end, step, candi, len, arr, min, max)
108.             if (b) {
109.                 if (b[0] < min) {
110.                     min = b[0]
111.                     max = b[1]
112.                 } else if (b[0] === min && b[1] > max) {
113.                     max = b[1]
114.                 }
115.             }
116.             //还原
117.             start.y++
118.             step--
119.             candi -= arr[start.x][start.y].v
120.             arr[start.x][start.y].can = true
121.         }
122.     }
123.     if (min !== Infinity) {
124.         return [min, max]
125.     }
126. }
127. console.log(getMinPath(`4
128. 3 2 1 -3
129. 1 -1 1 1
130. 1 1 -1 2
131. -2 1 2 3`))
132. console.log(getMinPath(`4
133. 3 2 1 -3
134. -1 -1 1 1
135. 1 1 -1 2
136. -2 1 -1 3`))

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。