共计 11302 个字符，预计需要花费 29 分钟才能阅读完成。
???? 前言
大家好呀，我是毛小悠，能够叫我二毛，在家中排行老二，是一名前端开发工程师。
本系列文章旨在通过练习来进步 JavaScript 的能力，一起欢快的做题吧。????????????
以下每道题，二毛我都有尝试做一遍。倡议限时训练，比方限定为半小时，如果半小时内想不进去，能够联合文章开端的参考答案来思考。
能够在下方评论区留言或者加我的微信：code\_maomao。期待你的到来。
求关注求点赞 ????\~~~????????????
???? 题目 1：单词搜寻难题挑战
单词搜寻是经典的儿童拼图游戏，您须要在其中找到程度、垂直或对角线暗藏在随机字母网格中的单词列表。
单词“dog”，“cat”和“parrot”都暗藏在上面的单词搜寻拼图网格中。
A B C D E F G H
1 F H K E F F H D
2 F D O G I O P V
3 F J D K O I A Q
4 F J E I H Q R M
5 C W B X X N R I
6 A A E S F U O F
7 C U T H E S T U
8 F J J S N J I O参数：
零碎会为您提供单词列表：[‘DOG’，’CAT’，’PARROT’] 和代表方形字母网格的字符串：’FHKEFFHDFDOGIOPVFJDKOIAQFJEIHQRMUWTXXNRIAAESFUOFCUHHESTUFJJSNJIO’。
拼图字符串全副大写，并且不蕴含空格或网格题目（例如，在下面的可视示例中，列 A - H 和行 1 -8）。
单词只会在程度，垂直或对角线的左右方向上拼写。
假如网格拼图将始终是一个现实的正方形，最小尺寸为 4 ×4，最大尺寸为 26×26（A- Z 列）。
您的挑战：
您必须返回一个数组的子数组，该数组代表每个单词的每个字母的网格地位。行用数字示意。列用字母示意。
在下面的示例中，解决方案为：[[B2，C2，D2]，[A5，B6，C7，]，[G2，G3，G4，G5，G6，G7]]
如果在拼图中找不到单词，则其地位子数组应显示为 [‘ 找不到单词。’]。例如：
[[B2，C2，D2]，[‘ 找不到单词。]，[G2，G3，G4，G5，G6，G7]]]
您能够假如任何一个谜题中都不会暗藏反复的单词。
习题代码：
function wordSearch(words, puzzle) {// your code goes here.}答案
???? 题目 1 的答案
参考答案 1：
function wordSearch(words, puzzle) {var s=Math.sqrt(puzzle.length), m = puzzle.match(new RegExp(`.{${s}}`,'g'));
return words.map(w=>{for(let j=0; j<s; j++) for(let i=0; i<s; i++) {
var r=true, d=true, v=true;
if(i+w.length<=s) {for(let k=0; k<w.length; k++) if(m[j][i+k]!==w[k]) r=false;
if(r) return [...Array(w.length)].map((_,k)=>[i+k,j]);
}
if(j+w.length<=s) {for(let k=0; k<w.length; k++) if(m[j+k][i]!==w[k]) d=false;
if(d) return [...Array(w.length)].map((_,k)=>[i,j+k]);
}
if(i+w.length<=s&&j+w.length<=s) {for(let k=0; k<w.length; k++) if(m[j+k][i+k]!==w[k]) v=false;
if(v) return [...Array(w.length)].map((_,k)=>[i+k,j+k]);
}
}
return -1;
}).map(r=>r===-1?['Word not found.']:r.map(([i,j])=>'ABCDEFGHIJKLMNOPQRSTUVWXYZ'[i]+(j+1)));
}参考答案 2：
function buildGrid(puzzle, sideSize) {const regex = new RegExp(`[A-Z]{${sideSize}}`, 'g');
return puzzle.match(regex);
}
function buildCoords(sideSize) {
const alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
const letters = [...alpha.slice(0, sideSize)];
let coords = [];
for (let num = 1; num <= sideSize; num++) {let row = letters.map(letter => letter + String(num));
coords.push(row);
}
return coords;
}
function getCols(grid) {return [...grid[0]].map((_, colIdx) => {return grid.map(row => row[colIdx])
.join('');
});
}
function getDiagonals(rows) {rows = rows.map(row => [...row]);
const sideSize = rows.length;
let shiftFromLast = true;
let rowCounts = [];
for (let count = 1; count < sideSize; count++) {rowCounts.push(count);
}
for (let count = sideSize; count >= 1; count--) {rowCounts.push(count);
}
const diagonals = rowCounts.map(rowCount => {let targetRows = shiftFromLast ? rows.slice(-rowCount) : rows.slice(0, rowCount);
if (rowCount === sideSize) shiftFromLast = false;
let diagonal = targetRows.map(row => row.shift());//.join('');
return diagonal;
});
return diagonals;
}
function getGridDiagonals(grid) {let rows = grid.map(rowStr => [...rowStr]);
return getDiagonals(rows);
}
function getCoordDiagonals(gridCoords) {return getDiagonals(gridCoords);
}
function searchRows(grid, gridCoords, word) {const targetRow = grid.findIndex(row => row.includes(word));
if (targetRow !== -1) {let wordStart = grid[targetRow].search(word);
let wordStop = wordStart + word.length;
return gridCoords[targetRow].slice(wordStart, wordStop);
} else {return null;}
}
function searchCols(grid, gridCoords, word) {const gridCols = getCols(grid);
const coordCols = [...grid[0]].map((_, colIdx) => {return gridCoords.map(row => row[colIdx]);
});
const targetCol = gridCols.findIndex(col => col.includes(word));
if (targetCol !== -1) {let wordStart = gridCols[targetCol].search(word);
let wordStop = wordStart + word.length;
return coordCols[targetCol].slice(wordStart, wordStop);
} else {return null;}
}
function searchDiagonals(grid, gridCoords, word) {const gridDiagonals = getGridDiagonals(grid);
const coordDiagonals = getCoordDiagonals(gridCoords);
const targetDiagonal = gridDiagonals.map(diagonal => diagonal.join(''))
.findIndex(diagonal => diagonal.includes(word));
if (targetDiagonal !== -1) {let wordStart = gridDiagonals[targetDiagonal].join('').search(word);
let wordStop = wordStart + word.length;
return coordDiagonals[targetDiagonal].slice(wordStart, wordStop);
} else {return null;}
}
function wordSearch(words, puzzle) {const sideSize = Math.sqrt(puzzle.length);
const grid = buildGrid(puzzle, sideSize);
const gridCoords = buildCoords(sideSize);
const letterCoords = words.map (word => {if (searchRows(grid, gridCoords, word) !== null) {return searchRows(grid, gridCoords, word);
} else if (searchCols(grid, gridCoords, word) !== null) {return searchCols(grid, gridCoords, word);
} else if (searchDiagonals(grid, gridCoords, word) !== null) {return searchDiagonals(grid, gridCoords, word);
} else {return ['Word not found.'];
}
});
return letterCoords;
}参考答案 3：
// Approach:
//
// Create a tree of all potential paths for a given word and pick first path
// that has all letters traveling in same direction.
// Paths can go east ("across"), south ("down") or southeast ("diagonal").
// First level of tree is the first letter of the word, anywhere in the puzzle.
// Continue building tree from there, one letter of the word at a time.
// Main Program
function wordSearch(words, puzzle) {const grid = new Grid(puzzle);
grid.init();
return words.map((word) => {return grid.search(word);
});
}
// Classes and helper functions
class Node {constructor(letter, x, y, parent, direction) {
this.letter = letter;
this.x = x;
this.y = y;
this.parent = parent;
this.direction = direction;
}
}
class Grid {constructor(puzzle) {this.size = Math.sqrt(puzzle.length);
this.puzzle = puzzle;
this.grid = [];
this.showPuzzle();}
init() {
const size = this.size;
for (let i = 0; i < size; i++) {this.grid.push(this.puzzle.substring(i * size, i * size + size));
}
}
showPuzzle() {
let topLabel = '';
for (let i = 0; i < this.size; i++) {topLabel += String.fromCharCode(65 + i);
}
console.log(' ', topLabel);
for (let i = 0; i < this.size; i++) {
let rowLabel = '';
if (i+1 < 10) {rowLabel = ` ${i+1}`;
} else {rowLabel = `${i+1}`;
}
console.log(rowLabel, this.puzzle.substring(i * this.size, i * this.size + this.size));
}
console.log();}
search(word) {
// create a tree with root node that points to all first letters of the word
// search for 2nd letter to east, south and south-east
// continue until word is done
// follow the leaf note back to the root to find the path
console.log(`Searching for '${word}'...`);
const rootNode = new Node();
let leafNodesQueue = [];
// find all the first letters
const firstLetter = word[0];
for (let x = 0; x < this.size; x++) {for (let y = 0; y < this.size; y++) {if (this.grid[y][x] === firstLetter) {const node = new Node(firstLetter, x, y, root);
leafNodesQueue.push(node);
}
}
}
// loop from 2nd letter to end of the word
for (let i = 1; i < word.length; i++) {const newLeafs = [];
if (leafNodesQueue.length === 0) {
// short circuit, word not found
break;
}
// loop through all the leaf nodes
// discover if next letter is east, south or southeast
while (leafNodesQueue.length) {const leaf = leafNodesQueue.pop();
const {x, y} = leaf;
if (x < this.size - 1 && this.grid[y][x + 1] === word[i]) {const node = new Node(word[i], x + 1, y, leaf, 'east');
newLeafs.push(node);
}
if (y < this.size - 1 && this.grid[y + 1][x] === word[i]) {const node = new Node(word[i], x, y + 1, leaf, 'south');
newLeafs.push(node);
}
if (x < this.size - 1 && y < this.size - 1 && this.grid[y + 1][x + 1] === word[i]) {const node = new Node(word[i], x + 1, y + 1, leaf, 'southeast');
newLeafs.push(node);
}
} // end while
leafNodesQueue = newLeafs;
}
// ensure we only capture paths where letters are all going in one direction
const validResults = [];
while (leafNodesQueue.length) {let result = [];
const leaf = leafNodesQueue.pop();
findPath(leaf, result);
const officialDirection = result[0].direction;
let ok = true;
for (let i = result.length - 2; i > 0; i--) {if (result[i].direction !== officialDirection) {ok = false;}
}
if (ok) {validResults.push(result);
break; // only need one valid result
}
}
// if we have at least one solution, grab first one
if (validResults.length) {return validResults[0].reverse().map((node) => {return node.location;});
}
return ['Word not found.'];
}
}
function findPath(node, result) {if (node === undefined) {return;}
// only push on nodes that have letters (to skip adding root node)
if (node.letter) {result.push({ direction: node.direction, location: `${String.fromCharCode(65 + node.x)}${node.y+1}`, letter: node.letter });
}
return findPath(node.parent, result);
}参考答案 4：
function wordSearch(words, puzzle) {const position = []
const arr = puzzle.split('')
const gridLenght = Math.pow(arr.length, 0.5)
// create Grid.
const gridHoriz = arr.reduce(function(result, value, index, array) {if (index % gridLenght === 0)
result.push(array.slice(index, index + gridLenght));
return result;
}, []);
const gridVert = []
for(let i = 0; i< gridHoriz.length; i++) {const line = []
for(let j = 0; j < gridHoriz.length; j ++) {line.push(gridHoriz[j][i])
}
gridVert.push(line)
}
const diagonal = (array) => {
const gridLength = array.length
const rowLength = array[0].length
const maxLength = Math.max(rowLength, gridLength)
const gridDiag = []
for(let i = 0; i <= 2 * (maxLength - 1) ; ++i){let temp = []
for(let j = gridLength - 1; j >=0; --j) {const foo = i - (gridLength - j)
if(foo >= 0 && i - (gridLength - j) < rowLength) {temp.push(array[j][foo])
}
}
if(temp.length > 0) {gridDiag.push(temp.reverse())
}
}
return gridDiag
}
const gridDiagonal = diagonal(gridHoriz)
const addPosition = (grid, gridName) => {return grid.map((row, rowIndex) => {return row.map( (letter, letterIndex) => {const alphabet = (gridName === 'gridVert') ? String.fromCharCode(rowIndex+1 + 64) : String.fromCharCode(letterIndex+1 + 64)
const obj ={}
const position = (gridName === 'gridVert') ? `${alphabet}${letterIndex + 1}` : `${alphabet}${rowIndex + 1}`
obj[position] = letter
return obj
})
})
}
const gridHorizPosition = addPosition(gridHoriz, 'gridHoriz')
const gridVertPosition = addPosition(gridVert,'gridVert')
const gridDiagonalPosition = diagonal(gridHorizPosition)
const gridMaster = [gridDiagonal, gridVert, gridHoriz]
const gridMasterPosition = [gridDiagonalPosition, gridVertPosition, gridHorizPosition]
words.map((word, index) => {const temp = []
for(let i =0 ; i < gridMaster.length; i++){for(let j = 0; j < gridMaster[i].length; j++) {const string = gridMaster[i][j].join('')
if(string.includes(word)) {const wordStart = string.search(word)
const rowPosition = gridMaster[i].indexOf(gridMaster[i][j])
for(let f = 0 ; f < word.length; f++) {const coordinate = Object.keys(gridMasterPosition[i][rowPosition][wordStart + f])[0]
temp.push(coordinate)
}
}
}
}
(temp.length > 0) ? position.push(temp) : position.push(['Word not found.'])
})
return position
}参考答案 5：
function wordSearch(words, puzzle) {function horizontal(word) {for (let row = 0; row < side; row++) {const pos = puzzleH[row].indexOf(word)
if (pos !== -1) {const answer = []
const row2 = row + 1
for (let i = 0, len = word.length; i < len; i++) {answer.push(String.fromCharCode((pos + i) + A) + row2)
}
return answer
}
}
return []}
function vertical(word) {for (let col = 0; col < side; col++) {const pos = puzzleV[col].indexOf(word)
if (pos !== -1) {const answer = []
const col2 = String.fromCharCode(col + A)
for (let i = 0, len = word.length; i < len; i++) {answer.push(col2 + (pos + 1 + i))
}
return answer
}
}
return []}
function diagonal(word) {
const len = word.length
const max = side - len
let found = false
let foundRow = -1
let foundCol = -1
for (let col = 0; col <= max; col++) {
let s = "";
for (let col2 = col; col2 < side; col2++) {s += puzzleH[col2 - col][col2]
}
let pos = s.indexOf(word)
if (pos !== -1) {
found = true
foundRow = pos + 1
foundCol = col + pos
break
}
}
for (let row = 1; row <= max; row++) {
let s = "";
for (let row2 = row; row2 < side; row2++) {s += puzzleH[row2][row2 - row]
}
let pos = s.indexOf(word)
if (pos !== -1) {
found = true
foundRow = row + pos + 1
foundCol = pos
break
}
}
let answer = []
if (found) {for (let i = 0; i < len; i++) {answer.push(String.fromCharCode((foundCol + i) + A) + (foundRow + i))
}
}
return answer
}
const side = Math.sqrt(puzzle.length)
const puzzleArray =puzzle.split('')
const puzzleH =[...Array(side).keys()].map(row => {
const start = row * side;
return puzzleArray.slice(start, start + side).join('')
})
const puzzleV =[...Array(side).keys()].map(col => puzzleArray.filter((letter, i) => i % side === col).join(''))
const A = 'A'.charCodeAt(0)
// console.log(puzzleH)
// console.log(puzzleV)
const results = []
for (const word of words) {
let found = false
const hres = horizontal(word)
if (hres.length > 0) {
found = true
results.push(hres)
}
const vres = vertical(word)
if (vres.length > 0) {
found = true
results.push(vres)
}
const dres = diagonal(word)
if (dres.length > 0) {
found = true
results.push(dres)
}
if (!found) {results.push(['Word not found.'])
}
}
return results
}???? 后序
本系列会定期更新的，题目会由浅到深的逐步提高。
求关注求点赞 ????~~????????????
能够关注我的公众号： 前端毛小悠 。欢送浏览
正文完
发表至： javascript
2021-03-17
