目录

递归思想

题目

24点

题目描述

解答要求

答案

解析

核心思想

步骤

全排列

题目描述

解答要求

答案

解析

核心思想

步骤

单词迷宫

题目描述

解答要求

答案

解析

核心思想

步骤

递归思想

使用递归解法首先找到一个整体f(x),然后找到f(x-1)和f(x)的联系（关键步骤），最后找到出口x=n时，能求出f(x)。

题目

24点

题目描述

大家都玩过扑克牌（A,2,3,...,T,J,Q,K），我们使用T来表示10，且A去值1，J取值11，Q取值12，K取值13，你的任务是判断给定四张牌，能否通过加减乘除四种运算，使得最后的结果是24.

若四张牌为A、5、8、J，则可以这么计算5+J+（A*8）=24。

解答要求

时间限制：5000ms，内存限制：100MB

输入

输入四个字符表示张牌（A,2,3,...,T,J,Q,K），用空格隔开。输入到文件末尾结束。

输出

若能计算出24，输出‘Yes’，否则输出‘No’。

样例1

A 5 5 5

A A A A

输出样例

Yes

No

提示样例1

（5-1/5）*5=24

答案

let inputArray = [5, 5, 5, 1]
function twentyFour(arr, num) {
    //解析第三步
    if (arr.length == 1) {
        if (Math.abs(Math.abs(arr[0]) - Math.abs(num)) <= 0.00001) {
            return true
        } else {
            return false
        }
    } else {
        let x = arr.pop()
        //解析第二步
        return twentyFour([...arr], num / x)
            || twentyFour([...arr], num - x)
            || twentyFour([...arr], num * x)
            || twentyFour([...arr], num + x)
    }
}
let hash = {
    A: 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, T: 10, 'J': 11, 'Q': 12, 'K': 13
}
function changeOrder(arr) {
    arr = [...arr]
    arr.unshift(arr.pop())
    return arr
}
let inputArray2 = changeOrder(inputArray)
let inputArray3 = changeOrder(inputArray2)
let inputArray4 = changeOrder(inputArray3)
//解析第四步
if (twentyFour(inputArray, 24)
    || twentyFour(inputArray2, 24)
    || twentyFour(inputArray3, 24)
    || twentyFour(inputArray4, 24)) {
    console.log('Yes')
} else {
    console.log('No')
}

解析

注意用到数组的地方，如果是不同的数组要浅拷贝即arr=[...arr]

核心思想

把所有数看成一个整体，每次拿出一个数和剩下的数进行排序。

步骤

1.根据思想首先化整找到f(x)表示什么，4张牌1,5,5,5，故f(x)表示为f([1,5,5,5])。

2.找到f(x)和f(x-1)的联系，这里我们每次从数组中拿出一个数与24进行运算，则要求剩余的3个数进行的运算和拿出的数与24进行的运算相等（f([1,5,5]）=24/5||24+5||24-5||24*5）,这里注意减法可能是5-24，所以我后面统一用绝对值进行判断。

3.找出口，当f(x)中，x的数组只有1位时，那么剩下的这个数的绝对值就要和右侧的值相等，这里要注意小数运算的精度问题会导致无法相等，所以我们用相减的绝对值小于0.000001判断相等。

4.这里我们还要注意一点，4张牌A,B,C,D，(A-B/C)*D=24的类似情形，我们只有先将24和D运算了才能有24点，如果先和A，B，C中的任意值运算都不会得到24点。所以我们将每个牌的顺序调一遍，每张牌都要在开头一次，即求4次的或运算f（[A,...]）||f（[B,...]）||f（[C,...]）||f（[D,...]）

全排列

题目描述

给定一个整数n，输出1-n的全排列。

解答要求

事件限制：1000ms，内存限制：100MB

输入

每个测试文件只有一个数据，输入一个整数n（0<n<=8）。

输出

输出全排列（每个排列中的数字用空格隔开），且每组排列注意按字典序输出所有排列（即要先输出123才能输出132，而不能先输出132在输出123）。

样例

输入样例1

3

输出样例1

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

答案

let inputArray=[4]
const getStr = (arr) => {
    const len = arr.length
    //对应解析中的第三步
    if (len === 1) {
        return arr
    }
    const out = []
    if (len > 1) {
        //对应解析中的第二步
        for (let i = 0; i < len; i++) {
            const arrStr = getStr(arr.slice(0, i).concat(arr.slice(i + 1)))
            //对应解析中的第三步
            arrStr.forEach((val) => {
                out.push(arr[i] + ' ' + val)
            })
        }
    }
    return out
}
inputArray.forEach((val) => {
    if (val) {
        const arr = getStr(new Array(Number(val)).fill(0).map((val, index) => String(index + 1)))
        arr.forEach((val) => { console.log(val) })
    }
})

解析

注意用到数组的地方，如果是不同的数组要浅拷贝即arr=[...arr]

核心思想

每次拿出一个数与24运算直到剩下最后一个数时与计算结果相同。

步骤

1.根据思想首先化整找到f(x)表示什么，用案例3为例子，f(x)表示f(3)的话，显然和排序关联不上，故这里f(x)表示成f([1,2,3])

2.找到f(x)和f(x-1)的联系，这里表示为f([1,2,3])中每次拿出一个数，从头拿起，即1和f([2,3])的排序加上2和f([1,3])的排序，3和f([1,2])的排序（注意题目重要求是空格连接的字符串输出，根据最后出口返回的是一个数组，我们答案中使用forEach去拼接字符串）。

3.找出口，当f(x)中，x的数组只有1位时，例如f([2,3])=2 f([3])，此时显然是f[3]没有排序可言的，所以直接返回x，注意x为数组，然后把2，[3]放进一个数组中组成['2 3']返回（这里对应的是答案中的out）。

单词迷宫

题目描述

Word Maze是一个网络小游戏，你需要找到以字母标注的食物，但要求以给定单词字母的顺序吃掉。假设给定单词if，你必须先吃掉i然后才能吃掉f。但现在你的任务可没有这么简单，你现在处于一个迷宫Maze（n*m的矩阵）当中，里面到处都是以字母标注的食物，但你只能吃掉能连成给定单词W的食物。

注意区分英文字母大小写，并且你只能上下左右行走。

解答要求

时间限制：1000ms，内存限制：100MB

输入

输入第一行包含两个整数n、m（0<m,m<21）分别表示n行m列的矩阵，第二行是长度不超过100的单词W，从第三行到第n+2行是值包含大小写英文字母的长度为m的字符串。

输出‘’如果能在地图中连成给定的单词，则输出‘YES’，否则输出‘NO’。注意：每个字母只能用一次。

输入样例1 

5 5

SOLO

CPUCY

EKLQH

CRSOL

EKLQO

PGRBC

输出样例1

YES

答案

let inputArray = ['5 5', 'SOLO', 'CPUCY', 'EKLQH', 'CRSOL', 'EKLQO', 'PGRBC']
//将arr[row][col]的值替换成+号，避免下一次往回走
function replace(arr, row, col) {
    return arr[row].substr(0, col) + '+' + arr[row].substr(col + 1)
}
function adjacent(row, col, arr, x) {
    arr = [...arr]
    if (arr[row][col] == word[x] && x == word.length - 1) {
        return true
    } else if (arr[row][col] == word[x]) {
        arr[row] = replace(arr, row, col)
        //解析第二步
        for (let i = 0; i < 4; i++) {
            newRow = row + go[i][0]
            newCol = col + go[i][1]
            if (newRow >= n
                || newRow < 0
                || newCol >= m
                || newCol < 0) {
                continue
            }
            if (adjacent(newRow, newCol, arr, x + 1)) {
                return true
            }
        }
    } else {
        return false
    }
}
let go = [[0, 1], [1, 0], [-1, 0], [0, -1]]
let word = inputArray[1]
let n = inputArray[0].split(' ')[0]
let m = inputArray[0].split(' ')[1]
inputArray.shift()
inputArray.shift()
let find = false
for (let i = 0; i < n; i++) {
    if (find == true) {
        break
    }
    for (let j = i; j < m; j++) {
        if (adjacent(i, j, inputArray, 0)) {
            find = true
            break
        }
    }
}
if (find) {
    console.log("YES")
} else {
    console.log('NO')
}

解析

注意用到数组的地方，如果是不同的数组要浅拷贝即arr=[...arr]

核心思想

对每一个字符都进行匹配，每匹配到一个后将该位置的字符赋值为其它不可能匹配到的字符如‘+’，递归上下左右继续匹配，直到单词匹配完或上下左右都无法匹配到结束。

步骤

1.根据思想首先找到f(x)表示什么，这里f(x)明显表示匹配到的第一个字符。这里注意因为题目要求每个字符只能匹配一次，所以我们每次匹配到了一个字符，就把该字符变为‘+’号，这样下次就不可能在匹配到了。

2.找到f(x)和f(x-1)的联系，f(x-1)表示下一次匹配到字符，2个之间的联系四f（x-1）要走4次，上下左右，答案中用了for循环4次，走了4步。

3.找出口，如果下一次匹配的字符第一个不相等则返回false，如果单词匹配完了则返回true。