目录
围棋的气
考察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。
答案
function getWeiQiAir(str) {
let [black, white] = str.split('\n')
black = black.split(' ').map(Number)
white = white.split(' ').map(Number)
// value: 0 ,1,2表示空、黑、白,white和black属性用于表示是否已经计算过黑白棋的气。
// 注意生成的二维数组不能直接用fill填{ value: 0, white: true, black: true }。这样会导致引用一致，改一个value，所有的value都会变。
let qipan = new Array(19).fill(0).map(v => new Array(19).fill(0).map(v => ({ value: 0, white: true, black: true })))
// 棋盘上下对应的棋
let lenB = black.length
for (let i = 0; i < lenB; i = i + 2) {
qipan[black[i]][black[i + 1]].value = 1
}
let lenW = white.length
for (let i = 0; i < lenW; i = i + 2) {
qipan[white[i]][white[i + 1]].value = 2
}
let sum = 0
// 计算黑棋的气
for (let i = 0; i < lenB; i = i + 2) {
let x = black[i]
let y = black[i + 1]
// 第一个条件判断某一个方向是否为空，第二个条件判断是否被当前颜色计算过
// 注意如果棋下在边界需要考虑数组越界问题。这里使用?.访问，当属性不存在时会返回undefined
if (qipan?.[x - 1]?.[y]?.value == 0 && qipan[x - 1][y].black) {
qipan[x - 1][y].black = false
sum++
}
if (qipan[x]?.[y - 1]?.value == 0 && qipan[x][y - 1].black) {
qipan[x][y - 1].black = false
sum++
}
if (qipan?.[x + 1]?.[y]?.value == 0 && qipan[x + 1][y].black) {
qipan[x + 1][y].black = false
sum++
}
if (qipan[x]?.[y + 1]?.value == 0 && qipan[x][y + 1].black) {
qipan[x][y + 1].black = false
sum++
}
}
// 计算白棋的气
for (let i = 0; i < lenW; i = i + 2) {
let x = white[i]
let y = white[i + 1]
if (qipan?.[x - 1]?.[y]?.value == 0 && qipan[x - 1][y].white) {
qipan[x - 1][y].white = false
sum++
}
if (qipan[x]?.[y - 1]?.value == 0 && qipan[x][y - 1].white) {
qipan[x][y - 1].white = false
sum++
}
if (qipan?.[x + 1]?.[y]?.value == 0 && qipan[x + 1][y].white) {
qipan[x + 1][y].white = false
sum++
}
if (qipan[x]?.[y + 1]?.value == 0 && qipan[x][y + 1].white) {
qipan[x][y + 1].white = false
sum++
}
}
return sum
}
console.log(getWeiQiAir(`0 5 8 9 9 10
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时结束循环。
答案
// 方法一
function continusInteger(n) {
let res = [`${n}=${n}`]
for (let i = 2; i < Math.floor(n / 2); i++) {
// new Array(i).fill(0).reduce((t,v,i)=>t+i)表示1+2+...+i-1
let tmp = n - new Array(i).fill(0).reduce((t, v, i) => t + i)
let start = tmp / i
// 找到最小的数start，拼接连续自然数加入结果数组中
if (Number.isInteger(start)) {
let str = `${n}=${start}`
for (j = 1; j < i; j++) {
str = str + `+${start + j}`
}
res.push(str)
}
}
return `${res.join('\n')}\nResult:${res.length}`
}
// 方法二
function continusInteger(n) {
if (n < 3) {
return `${n}=${n}\nRestult:1`
}
let res = [`${n}=${n}`]
let i = 1, j = 2
sum = i + j
while (i < n / 2 || j < n / 2) {
if (sum < n) {
j++
sum = sum + j
} else if (sum > n) {
sum = sum - i
i++
} else {
// 找到目标值记录
let str = `${n}=${i}`
for (let x = i + 1; x <= j; x++) {
str = str + `+${x}`
}
res.push(str)
j++
sum = sum + j
}
}
return `${res.join('\n')}\nResult:${res.length}`
}
console.log(continusInteger(9))
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。
function getMinPath(str) {
let arr = str.split('\n')
let len = Number(arr.shift())
let start = {}, end = {}
// 用二维数组表示图中的每个点
arr = arr.map((v, i) => v.split(' ').map((v, j) => {
v = Number(v)
// 记录起点和终点的位置
if (v === -3) {
start.x = i
start.y = j
}
if (v === -2) {
end.x = i
end.y = j
}
return { v, can: true }
}))
let res = bfs(start, end, 0, 0, len, arr)
if (res) {
return res[1]
}
return -1
}
function bfs(start, end, step, candi, len, arr, min = Infinity, max = 0) {
if (Math.abs(start.x - end.x) + Math.abs(start.y - end.y) === 1) {
return [step, candi]
}
if (step >= min) {
return
}
if (start.x + 1 < len) {
if (arr[start.x + 1][start.y].v >= 0 && arr[start.x + 1][start.y].can) {
start.x++
step++
candi += arr[start.x][start.y].v
arr[start.x][start.y].can = false
let r = bfs(start, end, step, candi, len, arr, min, max)
if (r) {
if (r[0] < min) {
// 当前解的步数小于已有的成功步数，
min = r[0]
max = r[1]
} else if (r[0] === min && r[1] > max) {
// 当前解的步数等于已有的成功步数，糖果数大于已有成功步数的糖果数
判断当前解的
max = r[1]
}
}
//还原
start.x--
step--
candi -= arr[start.x][start.y].v
arr[start.x][start.y].can = true
}
}
if (start.x - 1 >= 0) {
if (arr[start.x - 1][start.y].v >= 0 && arr[start.x - 1][start.y].can) {
start.x--
step++
candi += arr[start.x][start.y].v
arr[start.x][start.y].can = false
let l = bfs(start, end, step, candi, len, arr, min, max)
if (l) {
if (l[0] < min) {
min = l[0]
max = l[1]
} else if (l[0] === min && l[1] > max) {
max = l[1]
}
}
//还原
start.x++
step--
candi -= arr[start.x][start.y].v
arr[start.x][start.y].can = true
}
}
if (start.y + 1 < len) {
if (arr[start.x][start.y + 1].v >= 0 && arr[start.x][start.y + 1].can) {
start.y++
step++
candi += arr[start.x][start.y].v
arr[start.x][start.y].can = false
let t = bfs(start, end, step, candi, len, arr, min, max)
if (t) {
if (t[0] < min) {
min = t[0]
max = t[1]
} else if (t[0] === min && t[1] > max) {
max = t[1]
}
}
//还原
start.y--
step--
candi -= arr[start.x][start.y].v
arr[start.x][start.y].can = true
}
}
if (start.y - 1 >= 0) {
if (arr[start.x][start.y - 1].v >= 0 && arr[start.x][start.y - 1].can) {
start.y--
step++
candi += arr[start.x][start.y].v
arr[start.x][start.y].can = false
let b = bfs(start, end, step, candi, len, arr, min, max)
if (b) {
if (b[0] < min) {
min = b[0]
max = b[1]
} else if (b[0] === min && b[1] > max) {
max = b[1]
}
}
//还原
start.y++
step--
candi -= arr[start.x][start.y].v
arr[start.x][start.y].can = true
}
}
if (min !== Infinity) {
return [min, max]
}
}
console.log(getMinPath(`4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3`))
console.log(getMinPath(`4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3`))
