catalogue
recursive thinking
Using recursive solution, first find a whole f(x), then find the relationship between f(x-1) and f(x) (key step), and finally find the exit x=n, f(x) can be obtained.
subject
twelve p.m.
Title Description
Everyone has played poker (A,2,3,...,T,J,Q,K). We use T to represent 10, and A goes to value 1, J takes value 11, Q takes value 12, and K takes value 13. Your task is to judge whether A given four cards can be calculated by addition, subtraction, multiplication and division, so that the final result is 24
If the four cards are A, 5, 8 and J, you can calculate 5+J + (A*8) = 24.
Answer requirements
Time limit: 5000ms, memory limit: 100MB
input
Enter four characters to represent a card (A,2,3,...,T,J,Q,K), separated by spaces. Input ends at the end of the file.
output
If 24 can be calculated, output 'Yes', otherwise output' No '.
Example 1
A 5 5 5
A A A A
sample output
Yes
No
Tip example 1
(5-1/5)*5=24
answer
let inputArray = [5, 5, 5, 1]
function twentyFour(arr, num) {
//Analysis step 3
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()
//Parsing step 2
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)
//Analysis step 4
if (twentyFour(inputArray, 24)
|| twentyFour(inputArray2, 24)
|| twentyFour(inputArray3, 24)
|| twentyFour(inputArray4, 24)) {
console.log('Yes')
} else {
console.log('No')
}analysis
Note where arrays are used. If different arrays are used, shallow copy is required, that is, arr=[...arr]
Core idea
Take all numbers as a whole, take out one number at a time and sort the remaining numbers.
step
1. According to the thought, first find out what f(x) means. Four cards are 1,5,5,5, so f(x) is expressed as f ([1,5,5]).
2. Find the connection between f(x) and f(x-1). Here, we take out a number from the array every time to operate with 24, so the operation of the remaining three numbers and the number taken out must be equal to the operation of 24 (f([1,5,5]) = 24 / 5|24 + 5|24-5|24 * 5). Note that the subtraction can be 5-24, so I will use the absolute value to judge later.
3. Find the exit. When the array of X in f(x) has only 1 bit, the absolute value of the remaining number must be equal to the value on the right. Here, we should pay attention to the accuracy of decimal operation, which will lead to inequality. Therefore, we use the absolute value of subtraction less than 0.000001 to judge equality.
4. Here, we should also pay attention to the similar situation of four cards A,B,C,D, (A-B/C)*D=24. We can only have 24 points by first calculating 24 and D. if we first calculate with any value in A, B and C, we will not get 24 points. Therefore, we adjust the order of each card, and each card must be at the beginning, that is, find the four times of or operation f ([A,...]) |f ([b,...]) |f ([C,...]) |f ([C,...]) |f( [D,...])
Full arrangement
Title Description
Given an integer n, the full permutation of 1-n is output.
Answer requirements
Event limit: 1000ms, memory limit: 100MB
input
Each test file has only one data. Enter an integer n (0 < n < = 8).
output
Output all permutations (numbers in each permutation are separated by spaces), and each permutation should output all permutations in dictionary order (that is, output 123 before output 132, not output 132 before output 123).
Sample
Input sample 1
3
Output sample 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
answer
let inputArray=[4]
const getStr = (arr) => {
const len = arr.length
//The third step in correspondence analysis
if (len === 1) {
return arr
}
const out = []
if (len > 1) {
//The second step in correspondence analysis
for (let i = 0; i < len; i++) {
const arrStr = getStr(arr.slice(0, i).concat(arr.slice(i + 1)))
//The third step in correspondence analysis
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) })
}
})analysis
Note where arrays are used. If different arrays are used, shallow copy is required, that is, arr=[...arr]
Core idea
Take out one number at a time and operate with 24 until the last number is left, which is the same as the calculation result.
step
1. According to the thought, first find out what f(x) represents. Take case 3 as an example. If f(x) represents f(3), it is obviously not related to sorting, so here f(x) is expressed as f([1,2,3])
2. Find the connection between f(x) and f(x-1), which is expressed here as taking out one number in f([1,2,3]) at a time and picking it up from scratch, that is, the sorting of 1 and f([2,3]) plus the sorting of 2 and f([1,3]), and the sorting of 3 and f([1,2]) (note that the important question is that the string connected by spaces is output. According to the last exit, an array is returned, and forEach is used to splice the string in our answer).
3. Find the exit. When the array of X in f(x) has only 1 bit, for example, f([2,3])=2 f([3]), it is obvious that f[3] does not sort, so return x directly. Note that x is an array, and then put 2, [3] into an array to form ['2,3 '] return (here corresponds to out in the answer).
Word maze
Title Description
Word Maze is a small online game. You need to find the food marked with letters, but you need to eat it in the order of the letters of the given word. Assuming the given word if, you must eat i before you can eat f. but now your task is not so simple. You are in a Maze maze Maze maze (n*m matrix) Among them, there are food marked with letters everywhere, but you can only eat food that can be connected to a given word W.
Pay attention to the case of English letters, and you can only walk up, down, left and right.
Answer requirements
Time limit: 1000ms, memory limit: 100MB
input
The first row of input contains two integers n and m (0 < m, m < 21), which respectively represent the matrix of N rows and m columns. The second row is the word W with a length of no more than 100. From the third row to n+2, it is a string with a length of M containing uppercase and lowercase English letters.
Output '' if the given word can be connected in the map, output 'YES', otherwise output' NO '. Note: each letter can only be used once.
Input sample 1
5 5
SOLO
CPUCY
EKLQH
CRSOL
EKLQO
PGRBC
Output sample 1
YES
answer
let inputArray = ['5 5', 'SOLO', 'CPUCY', 'EKLQH', 'CRSOL', 'EKLQO', 'PGRBC']
//Replace the value of arrow [row] [col] with a + sign to avoid going back next time
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)
//Parsing step 2
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')
}analysis
Note where arrays are used. If different arrays are used, shallow copy is required, that is, arr=[...arr]
Core idea
Each character is matched. After each character is matched, the character at this position is assigned to other characters that cannot be matched, such as' + ', and the matching continues recursively up, down, left and right until the word is matched or the matching cannot be completed up, down, left and right.
step
1. First find out what f(x) means according to the idea. Here, f(x) obviously represents the first character matched. Note that because the title requires that each character can only be matched once, we change the character into a '+' sign every time we match a character, so it will not be matched next time.
2. Find the connection between f(x) and f(x-1). f(x-1) means to match the character next time. The connection between the two f(x-1) takes 4 times, up, down, left and right. In the answer, use the for loop 4 times and take 4 steps.
3. Find the exit. If the first character of the next match is not equal, return false. If the word matches, return true.