1.单词接龙
题目：
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
思路：首先，我们需要一个辅助函数去比较两个单词的不同字符的数量。。、然后，从起始单词开始，我们依次取找下一个和它相差一个字符的单词，直到找到目标单词
/*** @param {string} beginWord* @param {string} endWord* @param {string[]} wordList* @return {number}*/
var ladderLength = function(beginWord, endWord, wordList) {if (!wordList.includes(endWord)) return 0;if (beginWord.length < 2) return 2;const wordSet = new Set(wordList);const findDis = (s1, s2) => {let count = 0;for (let i = 0, l = s1.length; i < l; i++) {if (s1[i] !== s2[i]) count++;}return count;};let stack = [[beginWord, 1]];while (stack.length) {let [word, transNumber] = stack.pop();if (word === endWord) return transNumber;for (let str of wordSet) {if (findDis(word, str) === 1) {stack.unshift([str, transNumber + 1]);wordSet.delete(str);}}}return 0;
};
2.求根到叶子节点数字之和
题目：
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
思路：遍历，遍历节点的时候记录之前的父节点的值即可，遇到叶子节点就累加
/*** Definition for a binary tree node.* function TreeNode(val) {* this.val = val;* this.left = this.right = null;* }*/
/*** @param {TreeNode} root* @return {number}*/
var sumNumbers = function(root) {if (!root) return 0;const stack = [{node: root,val: "",},];let res = 0;while (stack.length) {const item = stack.shift();const v = item.val + item.node.val;if (!item.node.left && !item.node.right) {res+= +v;continue;}if (item.node.left) {stack.push({node: item.node.left,val: v,});}if (item.node.right) {stack.push({node: item.node.right,val: v,});}}return res;
};
3.被围绕的区域
题目：
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
思路：标记法。从四个边缘开始找，遇到字母O就深度遍历，并把遇到的O标记。然后遍历矩阵，遇到标记的O就还原，没标记的O就变为X
/*** @param {character[][]} board* @return {void} Do not return anything, modify board in-place instead.*/
var solve = function(board) {const m = board.length;if (m == 0) return; // [] 情况的特判const n = board[0].length;const dfs = (i, j) => {if (i < 0 || i == m || j < 0 || j == n) return; // 越界了if (board[i][j] == 'O') { // 遇到O，染为NO board[i][j] = 'NO'; dfs(i + 1, j); // 对四个方向的邻居进行dfsdfs(i - 1, j);dfs(i, j + 1);dfs(i, j - 1);}};for (let i = 0; i < m; i++) {if (board[i][0] == 'O') dfs(i, 0); // 从最外层的O，开始DFSif (board[i][n-1] == 'O') dfs(i, n-1); // 从最外层的O，开始DFS}
for (let j = 1; j < n - 1; j++) {if (board[0][j] == 'O') dfs(0, j); // 从最外层的O，开始DFSif (board[m-1][j] == 'O') dfs(m-1, j); // 从最外层的O，开始DFS}for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (board[i][j] === 'NO') board[i][j] = 'O'; // 恢复为Oelse if (board[i][j] === 'O') board[i][j] = 'X'; // O变为X}}};
4.分割回文串
题目：
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
/*** @param {string} s* @return {string[][]}*/
var partition = function(s) {let res = [];if (s.length === 0) {return res;}findPalidrome(0, s, res, []);return res;
};function findPalidrome(start, s, res, curArr) {if (start === s.length) {res.push(curArr);return;}for (let i = start; i < s.length; i++) {let subStr = s.slice(start, i + 1);if (subStr && isPal(subStr)) {findPalidrome(i + 1, s, res, [...curArr, subStr]);}}
}function isPal(str) {let len = Math.floor(str.length / 2);if (len === 0) {return true;}let add = str.length % 2 === 0 ? 0 : 1;let subStr = str.slice(0, len);for (let i = 0; i < len; i++) {if (subStr[len - i - 1] !== str[len + add + i]) {return false;}}return true;
}
5.克隆图
题目：
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
思路：从第一个节点开始遍历，然后用map记录每一个新节点，遇到需要这些节点的地方直接返回引用，用set记录遍历过的节点，防止死循环
/*** // Definition for a Node.* function Node(val, neighbors) {* this.val = val === undefined ? 0 : val;* this.neighbors = neighbors === undefined ? [] : neighbors;* };*//*** @param {Node} node* @return {Node}*/
var cloneGraph = function(node) {if(!node)return nodeconst map = new Map();const set = new Set();const stack = [node];let head;while (stack.length) {const item = stack.pop();if (set.has(item.val)) continue;const newItem = findChild(item, set, map);head = head || newItem;newItem.neighbors = newItem.neighbors.map((child) => {return findChild(child, set, map);});set.add(newItem.val)stack.push(...newItem.neighbors);}function findChild(child, set, map) {if (map.has(child.val)) return map.get(child.val);const node = new Node(child.val, child.neighbors);map.set(child.val, node);return node;}return head;
};