目录
- 正则表达式匹配
- 二叉树和为某一值的路径(此题解法同样可以适用于求解二叉树的深度)
- 二叉树的深度
- 判断一棵二叉树是否为平衡二叉树
- 字符流中第一个不重复的字符
- 二叉树的下一个结点
- 对称的二叉树
- 按之字形顺序打印二叉树
- 矩阵中的路径
- 机器人的运动范围
- 链表中环的入口结点
- 二叉树的镜像
- 两个链表的第一个公共结点
- 二叉搜索树的后序遍历序列
- 链表中倒数第K个结点
- 反转链表
- 合并两个排序的链表
- 树的子结构
- 从上往下打印出二叉树
- 顺时针打印矩阵
- 连续子数组的最大和
- 复杂链表的复制
- 二叉搜索树与双向链表
- 和为S的连续正数序列
- 孩子们的游戏(圆圈中最后剩下的数)
- 整数中1出现的次数
- 丑数
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
思路-递归实现
每次分别在str和pattern中取一个字符进行匹配，如果匹配，则匹配下一个字符，否则返回false, 设置匹配递归函数 matchStr(str, pattern)。这里总共分两种情况:
一种是模式串的下一个字符是"*"
- 如果pattern当前字符能匹配目标串中的0个字符(.*这种情况)：
matchStr(str,pattern+2) - 如果pattern当前字符能匹配目标串中的1个字符(.*这种情况)：
matchStr(str+1,pattern+2) - 如果pattern当前字符能匹配目标串中的多个字符(.*这种情况)：
matchStr(str+1,pattern) - 如果pattern当前字符串与目标串(非.)当前字符串不匹配但是模式串下一个为"*"：
matchStr(str, pattern+2)
另一种情况是模式串的当前字符为".":
- "."可以匹配任意字符一次，因此有:
matchStr(str+1, pattern+1) - 另外"."可以与空字符串匹配，所以就算目标串遍历结束，只要模式串中字符只剩"."或者任意一个字符接"*"都是算匹配成功的
代码
// s, pattern都是字符串
function match(s, pattern)
{
if(s === null && pattern === null) return true;
if(s === null || pattern === null) return false;
return matchStr(s, 0, pattern, 0);
}
function matchStr(str, s, pattern, p) {
if(str.length <= s && pattern.length <= p) { // 匹配完了
return true;
}
if(str.length > s && pattern.length <= p) {
return false; // 模式串匹配完了，字符串还有，则匹配不成功
}
// 字符串结束，模式串没结束，可能匹配也可能不匹配，因为模式串的.可以匹配任意字符，包括空字符串；
if(p+1 < pattern.length && pattern[p+1] === "*") {// 当前模式串下一个字符是*时
// 分三种情况
if(s >= str.length) return matchStr(str, s, pattern, p+2);
// 当前字符串结束之后看看模式串之后的是不是能匹配空字符串
else {
// 模式串当前字符能匹配字符串的不止一个字符
if(pattern[p] === str[s] || pattern[p] === '.') { // 都是代表当前模式串和字符串的字符相等
return matchStr(str, s+1, pattern, p+2) // 匹配一个字符串字符
|| matchStr(str, s+1, pattern, p) // 匹配多个字符串字符
|| matchStr(str, s, pattern, p+2); // pattern[p]==="."时匹配空字符串的情况
}else {
return matchStr(str, s, pattern, p+2); // 模式串当前字符匹配字符串的0个字符时；
}
}
}
if(s >= str.length) return false; // 模式串下一个不是"*"，字符串
else {
if(pattern[p] === str[s] || pattern[p] === ".") {
return matchStr(str, s+1, pattern, p+1);
}
}
return false;
}
复制代码输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路-回溯
开辟两个数组，第一个数组为存放所有路径的，第二个数组为存放一次遍历到叶节点符合条件的路径，从根节点开始遍历左子树，再遍历右子树，若左右子树都存在，左右子树依次递归，并记录当前遍历的目标整数值减去当前节点值expectNumber，若expectNumber===0并且当前节点为叶节点，则保存该条路径；
expectNumber === 0 && root.left === null && root.right === null
代码
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function FindPath(root, expectNumber)
{
// write code here
// 深度搜索,由于是整数，可能为负值，因此只能暴力求解每条路径之和，存入结果数组
let result = [], res = [];
if(root === null) return result;
sumPath(root, expectNumber, res, result);
return result;
function sumPath(root, expectNumber, res, result) {
res.push(root.val);
expectNumber -= root.val;
if(expectNumber === 0 && root.left === null && root.right === null) {
// 和为目标整数并且当前节点为叶节点
result.push(res.concat()); // 此处为什么不直接push(res)而是push(res.concat())即
// res的一个副本，是因为res在后面会改变,如果直接push(res)由于引用传递，
// 内存地址不变，指向相同，到最后都会是空数组(res.pop());
}
if (root.left !== null) {
sumPath(root.left, expectNumber, res, result)
}
if (root.right !== null) {
sumPath(root.right, expectNumber, res, result)
}
res.pop();
}
}
复制代码输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路-递归&&非递归
- 递归思路
如果一棵树只有一个结点，它的深度为1，如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度+1.同样如果根节点只有右子树而没有左子树，那么树的深度应该是其右子树+1.如果既有左子树又有右子树，那概述的深度就是左、右子树的深度的较大值加1。利用这个思路，我们可以用递归来实现代码：
代码
function TreeDepth(root) {
if (root === null) return 0;
let treeDepthLeft = getTreeDepth(root.left);
let treeDepthRight = getTreeDepth(root.right);
return treeDepthLeft > treeDepthRight ? treeDepthLeft+1 : treeDepthRight+1;
}
复制代码- 非递归思路
按层遍历计算树的深度，维护一个队列queue和一个深度depth变量记录当前遍历的深度(层数)，每一层的节点入队，遍历完成后出队，depth++，同时下一层的节点入队，循环直到节点为叶节点
代码
function TreeDepth(pRoot) {
if(!pRoot) return 0;
let depth = 0, queue = [];
queue.push(pRoot);
while(queue.length !== 0) {
depth++;
for(let i = 0; i < queue.length; i++) {
let root = queue.pop();
root.left && queue.unshift(root.left);
root.right && queue.unshift(root.right);
}
}
return depth;
}
复制代码输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路-递归求证
- 暴力递归
从根节点开始，求左右子树的深度，其差是否小于等于1，如果是，以左右子树的节点为根节点递归判定是否满足左右子树深度之差小于等于1；如果其中任意一次递归不满足，则返回false;这样做时间复杂度比较高，每次遍历都要重新计算每个左右子树的深度，其中叶节点的深度计算次数最多；
代码
function IsBalanced_Solution_1(pRoot)
{
if (pRoot === null) return true;
if (Math.abs(getDepth(pRoot.left) - getDepth(pRoot.right)) <= 1) {
return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
}else {
return false;
}
}
function getDepth(root) {
if (root === null) return 0;
let leftDepth = getDepth(root.left);
let rightDepth = getDepth(root.right);
return leftDepth > rightDepth ? (leftDepth+1) : (rightDepth+1);
}
复制代码- 后序遍历返回每次子树深度的计算结果，无需重复计算
先遍历左子树，再遍历右子树，最后遍历根节点，也就是从叶节点开始计算，把每次计算的节点深度在递归函数中传递出来在下次的递归中使用，减少重复计算
代码
function IsBalanced_Solution_2(pRoot) {
let isBalanced = true;
return getDepth(pRoot) !== -1; // 如果返回的是-1，说明不是平衡二叉树；
}
function getDepth(root) {
if (root === null) return 0;
let leftDepth = getDepth(root.left);
if (leftDepth === -1) return -1; // 如果返回的深度为-1，说明不是平衡二叉树，无需递归计算深度之差了；
let rightDepth = getDepth(root.right);
if (rightDepth === -1) return -1; // 如果返回的深度为-1，说明不是平衡二叉树，无需递归计算深度之差了；
return Math.abs(leftDepth - rightDepth) > 1 ? -1 : Math.max(leftDepth, rightDepth) + 1; // 这里进行了剪枝，如果当前节点左右子树深度之差大于1，说明不是平衡二叉树，直接无需后续的计算了，直接返回-1；
}
复制代码请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述:如果当前字符流没有存在出现一次的字符，返回#字符。
思路-HashMap(java) | Map(javascript)
代码
- HashMap
import java.util.HashMap;
import java.util.ArrayList;
public class Solution {
HashMap<Character, Integer> map = new HashMap<>();
ArrayList<Character> list = new ArrayList<>();
//Insert one char from stringstream
public void Insert(char ch)
{
if (map.containsKey(ch)) {
map.put(ch, map.get(ch)+1);
}else {
map.put(ch, 1);
}
list.add(ch);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
char ch = '#';
for(int i = 0; i < list.size(); i++) {
if(map.get(list.get(i)) == 1) {
ch = list.get(i);
break;
}
}
return ch;
}
}
复制代码- Map
//Init module if you need
let map, temp;
function Init()
{
// write code here
map = new Map();
temp = [];
}
//Insert one char from stringstream
function Insert(ch)
{
// write code here
if(map.has(ch)) {
map.set(ch, map.get(ch)+1);
}else {
map.set(ch, 1);
}
temp.push(ch);
}
//return the first appearence once char in current stringstream
function FirstAppearingOnce()
{
// write code here
let ch = "#";
for(let i = 0, len = temp.length; i < len; i++) {
if (map.get(temp[i]) === 1) {
ch = temp[i];
break;
}
}
return ch;
}
复制代码给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路-分左右子树查找
- 若当前结点的右子树存在，则按中序遍历，其下一个结点是其右子树的中序遍历第一个结点，直接找右子节点的左叶节点；
- 若当前结点的右子树不存在，分两种情况：
当前结点的父节点的左子节点为自己，按中序遍历，下一个结点为当前结点的父节点；
当前结点的父节点的右子节点为自己，按中序遍历，下一个结点应该循环查找当前结点的父节点，直到父节点的父节点的左子结点为该父节点，该父节点的父节点即为下一个结点；
- 如下图有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G);
- 没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。
代码
/*function TreeLinkNode(x){
this.val = x;
this.left = null;
this.right = null;
this.next = null;
}*/
function GetNext(pNode)
{
// write code here
if (pNode === null) return null;
if (pNode.right !== null) {
pNode = pNode.right;
while(pNode.left !== null) {
pNode = pNode.left;
}
return pNode;
}
while (pNode.next !== null) {
if (pNode.next.left === pNode) return pNode.next;
pNode = pNode.next;
}
return null;
}
复制代码请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的
思路-递归
从根节点开始递归，左子树的左子节点和右子树的右子节点，左子树的右子节点和右子树的左子节点分别递归比较是否相等
代码
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function isSymmetrical(pRoot)
{
// write code here
if(pRoot === null) return true;
return isSame(pRoot.left, pRoot.right);
}
function isSame(root1, root2) {
if (root1 === null && root2 === null) return true;
if ((root1 === null && root2) || (root1 && root2 === null)) return false;
if (root1.val === root2.val) {
return isSameTree(root1.left, root2.right) && isSameTree(root1.right, root2.left);
}else {
return false
}
}
复制代码请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路-按层遍历二叉树
根据当前深度为偶数还是奇数决定是push还是unshift结点；
代码
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Print(pRoot)
{
// write code here
let queue = [], i = 0;
let result = [];
if (pRoot === null) return result;
queue.push(pRoot);
while(queue.length > 0) {
i++;
let res = queue.reduce((prev, cur) => {
i % 2 === 0 ? prev.push(cur.val) : prev.unshift(cur.val);
return prev;
}, []);
result.push(res);
for (let j = 0, len = queue.length; j < len; j++) {
let temp = queue.pop();
temp.left && queue.unshift(temp.left);
temp.right && queue.unshift(temp.right);
}
}
return result;
}
复制代码请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路-回溯法DFS
- 递归法实现深度搜索
这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置。
代码
function hasPath(matrix, rows, cols, path)
{
// write code here
// 典型的回溯法
if (matrix === null || rows <= 0 || cols <= 0 || path === null) return false;
if (path.length === 0) return true;
let visited = Array.from({length: matrix.length}, (item, index) => item = false)
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (helper(matrix, i, j, rows, cols, 0, visited, path)) {
return true;
}
}
}
return false;
}
function helper(matrix, row, col, rows, cols, k, visited, str) {
if (row >= rows || row < 0 || col < 0 || col >= cols || str[k] !== matrix[row*cols+col] || visited[row*cols+col]) {
return false;
}
if (k === str.length-1) {
return true;
}
visited[row*cols+col] = true;
if (helper(matrix, row+1, col, rows, cols, k+1, visited, str)
|| helper(matrix, row, col+1, rows, cols, k+1, visited, str)
|| helper(matrix, row-1, col, rows, cols, k+1, visited, str)
|| helper(matrix, row, col-1, rows, cols, k+1, visited, str)) { // 四个方向任意一条路径满足条件即代表符合路径要求
return true;
}
visited[row*cols+col] = false;
return false;
}
复制代码地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路-回溯法
思路跟上一题的矩阵路径类似，需要一个数组来记录该格点是否被访问过；递归方程为当前机器人所在位置能够到达的格子数加上上下左右运动能够到达的格子数；递归终止条件为机器人运动范围越界或者走到已经访问过的格子或者数位加起来大于K值的格子，终止递归返回计算后能够到达的格子数；
代码
function movingCount(threshold, rows, cols)
{
// write code here
if (rows <= 0 || cols <= 0 || threshold <= 0) return 0;
let visited = Array.from({length: rows*cols}, (item, index) => item = false); // 构造状态数组
return countMesh(threshold, rows, cols, 0, 0, visited);
}
function countMesh(k, rows, cols, row, col, visited) {
let count = 0;
if (canWorkInto(k, rows, cols, row, col, visited)) {
visited[row*cols+col] = true; // 将当前格子记为已访问
count = 1 + countMesh(k, rows, cols, row+1, col, visited) + countMesh(k, rows, cols, row, col+1, visited)
+ countMesh(k, rows, cols, row-1, col, visited) + countMesh(k, rows, cols, row, col-1, visited) // 四个方向递归计数
}
return count;
}
function canWorkInto(k, rows, cols, row, col, visited) {
if (row >= 0 && col >= 0 && row < rows && col < cols && sum(row, col) <= k && !visited[row*cols+col]) {
return true; // 这些条件代表机器人可以走到该格子
}else {
return false;
}
}
function sum(row, col) { // 数位相加之和函数
let rowArr = [], colArr = [];
while(Math.floor(row/10) > 0) {
rowArr.push(row%10);
row = Math.floor(row/10);
}
rowArr.push(row);
while(Math.floor(col/10) > 0) {
colArr.push(col%10);
col = Math.floor(col/10);
}
colArr.push(col);
return [...rowArr, ...colArr].reduce((prev, cur) => prev+cur, 0);
}
复制代码给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路
- 快慢指针法
如果单链表有环，按照判断是否有环的思路，当快指针和慢指针相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈。假设slow指针走了s步，则fast指针走了2*s步，设环长为r，则:
2\*s=s+n\*r; => s=n\*r;
设链表头到环入口距离为l，入口处距离相遇点距离为a，则：s=l+a+mr; => l=（n-m）r - a
可见，相遇后，如果在链表头和相遇点各设置一个指针，每次走一步，两指针必定相遇，且在相遇第一个点为环入口。
代码
function EntryNodeOfLoop(pHead) {
let slow = pHead, fast = pHead;
while(fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (fast === slow) { // 找到相遇点
break;
}
}
slow = pHead; // 让快慢指针速度一样，慢指针重新指向头指针，快指针在第一次相遇处，重新开始走，直到相遇即为入口结点；
while(slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
复制代码- 断链法
遍历链表，依次删除链表之间的链接，直到当前结点的下一个结点为null，此时该结点一定为入口结点，但是这种方法一定会破坏当前链表结构；
代码
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
// write code here
let prev = pHead;
let cur = pHead.next;
if (prev === null || cur === null) {
return null;
}
while(cur !== null) {
prev.next = null;
prev = cur;
cur = cur.next;
}
return prev;
}
复制代码操作给定的二叉树，将其变换为源二叉树的镜像。
思路-递归交换左右子树
代码
function Mirror(root) {
if (root === null) return null;
let temp = root.left;
root.left = Mirror(root.right);
root.right = Mirror(temp);
return root;
}
复制代码输入两个链表，找出它们的第一个公共结点。
思路
先分别找出两个链表的长度，分别设置两个指针，长链表的指针先走两个链表长度的差值，然后短链表的指针开始走，直到两个指针的下一个结点一致，那么该一致的结点为第一个公共结点；
代码
function FindFirstCommonNode(pHead1, pHead2)
{
let len1 = getLength(pHead1);
let len2 = getLength(pHead2);
let shortList, longList, k;
if (len1 >= len2) {
shortList = pHead2;
longList = pHead1;
k = len1 - len2;
}else {
shortList = pHead1;
longList = pHead2;
k = len2 - len1;
}
while(k >= 1 && longList !== null) {
longList = longList.next;
k--;
}
while (shortList !== null && longList !== null) {
if (shortList === longList) return shortList;
shortList = shortList.next;
longList = longList.next;
}
return null;
function getLength(head) {
let length = 0;
let temp = head;
while(temp !== null) {
length++;
temp = temp.next;
}
return length;
}
}
复制代码输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
假设该数组是二叉搜索树的后序遍历结果，那么数组最后一个项为根节点的值，比根结点小的为左子树，比根结点大的为右子树； 对于左子树和右子树而言，同样左子树最后一个结点为左子树的根结点，右子树的最后一个结点为右子树的根结点，递归执行分别对数组剩余项进行分为左右子树的结点，先对左子树进行遍历，然后对右子树进行遍历，如果出现右子树上的值小于根结点，则不是二叉搜索树的后序遍历结果(No)；如果遍历完则返回Yes;
代码
function VerifySquenceOfBST(sequence)
{
// write code here
// 先假设该数组是二叉搜索树的的后序遍历结果，这样最后一个数字为根节点，
// 比根节点小的为左子树，比根节点大的为右子树；再在左子树的最后一个节点确定为左子树的根节点；
// 右子树的最后一个节点为右子树的根节点
if(sequence === null || sequence.length === 0) {
return false;
}
return isBSTTree(sequence, 0, sequence.length-1);
}
function isBSTTree(arr, start, end) {
if(start >= end) {
return true;
}
let root = arr[end];
let i = start;
for(; i < end; i++) {
if(arr[i]>root) {
break;
}
}
let j = i;
for(; j < end; j++) {
if(arr[j] < root) {
return false;
}
}
return isBSTTree(arr, start, i-1) && isBSTTree(arr, i, end-1);
}
复制代码输入一个链表，输出该链表中倒数第k个结点。
思路-双指针
假设同时指向链表头部的双指针，第一个指针先走k-1步，然后两个指针同时开始从各自位置开始走，直到第一个指针走到末尾，那么第二个指针的位置即为链表的倒数第K个结点
代码
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k)
{
if (head === null || k <= 0) return null;
let p1 = head, p2 = head;
while(k-1 > 0) {
if ( p1.next !== null) {
p1 = p1.next;
k--;
}else {
return null;
}
}
while(p1.next !== null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
复制代码输入一个链表，反转链表后，输出新链表的表头。
思路
设置两个指针，一个指向头部p1，一个指向头部下一个指针p2;
p1.next = p2.next; p2.next = head; head = p2; p2 = p1.next;
代码
function ReverseList(pHead)
{
if (pHead === null || pHead.next === null) return pHead;
let p1 = pHead;
let p2 = pHead.next;
while(temp.next !== null) {
p1.next = p2.next;
p2.next = head;
head = p2;
p2 = p1.next;
}
return pHead;
}
复制代码输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路
两个指针，temp1,temp2分别指向链表的头部，先比较两个链表头部的大小，新链表的头部为两者之中小的那个结点head； 令临时结点temp = head;然后循环同时遍历两个链表，比较temp1和temp2的大小,temp为两者之间的较小者；如果其中一个链表遍历完，则temp的next为未遍历完的链表temp1 || temp2.
代码
function Merge(pHead1, pHead2)
{
let head, temp1, temp2;
if (!pHead1) return pHead2;
if (!pHead2) return pHead1;
if (pHead1.val >= pHead2.val) {
head = pHead2;
temp1 = pHead1;
temp2 = pHead2.next;
}else {
head = pHead1;
temp1 = pHead1.next;
temp2 = pHead2;
}
let temp = head; // 临时结点指向新链表的头部
while(temp1 !== null && temp2 !== null) {
if (temp1.val >= temp2.val) {
temp.next = temp2;
temp2 = temp2.next;
}else {
temp.next = temp1;
temp1 = temp1.next;
}
temp = temp.next;
}
if (temp1 !== null) { // temp1未遍历完，temp2遍历完
temp.next = temp1;
}
if (temp2 !== null) { // temp2未遍历完，temp1遍历完
temp.next = temp2;
}
return head;
}
复制代码输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路-递归
先比较整个树从根节点开始比较是否一样，如果一样，比较B是否为A的子结构；如果根节点值不一样，再分别递归比较A左右子树的根节点开始是否与B树的根节点一样；
代码
function HasSubtree(pRoot1, pRoot2)
{
// write code here
let result = false;
// 先比较A和B的根节点是否一样，如果一样递归判断左右子树;
// 如果不一样，在A的左子树里面找是否含有B树;
// 如果没有，再在A的右子树里面找是否含有B树;
// 如果都没有，代表B树不是A的子结构;
if (pRoot1 !== null && pRoot2 !== null) {
if (pRoot1.val === pRoot2.val) {
result = isSonTree(pRoot1, pRoot2);
}
if (!result) {
result = HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}
}
return result;
}
function isSonTree(tree1, tree2) {
if (tree2 === null) return true;
if (tree1 === null) return false;
if (tree1.val === tree2.val) {
return isSonTree(tree1.left, tree2.left) && isSonTree(tree1.right, tree2.right);
}
return false;
}
复制代码从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路-二叉树的按层遍历
按层次遍历二叉树即可，维护一个队列，遍历当前根节点的所有子节点推入队列，遍历当前出队队列的结点值即可；
代码
function PrintFromTopToBottom(root)
{
// write code here
// 维护一个容器队列，在打印一个根节点后，把他的左右子节点放入队列中，一次打印，先入先出
let result = [];
if(root === null) return result;
let temp = [];
temp.push(root);
let cur = null;
while(temp.length>0) {
cur = temp.shift();
result.push(cur.val)
if(cur.left){
temp.push(cur.left);
}
if(cur.right) {
temp.push(cur.right);
}
}
return result;
}
复制代码输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路
将每四次循环看成一个圈，按圈遍历，每一圈的一次循环最多分为四次遍历，第一次遍历最上方从左到右，第二次遍历最右边从上到下，第三次遍历最下方从右到左，第四次遍历最左边从下到上；
endX = rows - start - 1; endY = columns - start - 1;
- 第一次遍历肯定存在;
- 第二次遍历要满足
start < endX;- 第三次遍历要满足
start < endY && start < endX;- 第四次遍历要满足
start < endX-1 && start < endY;
代码
function printMatrix(matrix)
{
// write code here
if (matrix === null) return null;
let rows = matrix.length;
let columns = matrix[0].length;
if (rows <= 0 || columns <= 0) return null;
let start = 0;
let result = [];
while(rows > start*2 && columns > start*2) {
// 顺时针打印一圈
printMatrixCircle(result, matrix, rows, columns, start);
start++;
}
return result;
}
function printMatrixCircle(result, matrix, rows, columns, start) {
let endY = columns - start - 1;
let endX = rows - start - 1;
// 从左到右打印一行
for (let i = start; i <= endY; i++) {
result.push(matrix[start][i]);
}
// 从上到下打印一列
if (start < endX) {
for(let i = start + 1; i <= endX; i++) {
result.push(matrix[i][endY]);
}
}
// 从右向左打印
if (start < endY && start < endX) {
for(let i = endY-1; i >= start; i--) {
result.push(matrix[endX][i]);
}
}
// 从下至上打印
if(start < endX - 1 && start < endY) {
for (let i = endX-1; i > start; i--) {
result.push(matrix[i][start]);
}
}
}
复制代码HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
思路
维护一个当前子数组之和sum和最大和值res，如果sum<0，说明加上的子元素小于0，取下一个元素重新计算sum；如果sum>0,需要将sum+当前元素的值，每次循环sum与最大和比较取较大者；
代码
function FindGreatestSumOfSubArray(array)
{
let res = array[0];
let current = array[0];
let len = array.length;
for (let i = 1; i < len; i++) {
if (current < 0) {
current = array[i];
}else {
current += array[i];
}
res = Math.max(current, res);
}
return res;
}
复制代码输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路
先给每个链表结点复制出下一次无任意指针的结点，根据被复制的结点如果有任意指针，那么其复制后的结点任意指针必然是被复制结点的任意指针的下一个结点；这样就完全复制了一份复杂链表，要把该复制好的链表提取出来，采用断链法解除原链表与复制后的链表之间的指向关系；
代码
/*function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}*/
function Clone(pHead)
{
// write code here
// 复制无任意指针的链表
let temp1 = pHead;
while(temp1 !== null) {
let copyNode1 = new RandomListNode(temp1.label);
copyNode1.next = temp1.next;
copyNode1.random = null;
temp1.next = copyNode1;
temp1 = copyNode1.next;
}
// 给复制出来的链表添加对应的任意指针
let temp2 = pHead;
while(temp2 !== null) {
let copyNode2 = temp2.next;
if(temp2.random !== null) {
copyNode2.random = temp2.random.next;
}
temp2 = copyNode2.next;
}
// 将复制出来的链表与源链表解除联系，断链
let temp3 = null;
let copyNode3 = null;
let pHeadCopy = pHead;
if (pHeadCopy !== null) {
temp3 = copyNode3 = pHeadCopy.next;
pHeadCopy.next = temp3.next;
pHeadCopy = pHeadCopy.next;
}
while(pHeadCopy !== null) {
temp3.next = pHeadCopy.next;
temp3 = temp3.next;
pHeadCopy.next = temp3.next;
pHeadCopy = pHeadCopy.next;
}
return copyNode3;
}
复制代码输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路-递归
- 将左子树构造成双链表，并返回链表头节点。
- 定位至左子树双链表最后一个节点。
- 如果左子树链表不为空的话，将当前root追加到左子树链表。
- 将右子树构造成双链表，并返回链表头节点。
- 如果右子树链表不为空的话，将该链表追加到root节点之后。
- 根据左子树链表是否为空确定返回的节点。
代码
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Convert(pRootOfTree)
{
// write code here
// 由于不能创建任何新的节点，因此不能先中序遍历转化为数组再转化为双向链表
let head = null;
let pHead = null;
return convert(pRootOfTree);
function convert(root) {
if(root === null) return null;
convert(root.left);
if(head === null) {
head = root;
pHead = root;
}else {
head.right = root;
root.left = head;
head = root;
}
convert(root.right);
return pHead;
}
}
复制代码小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
思路
根据连续正数序列的和公式为：（首项+末项）项数/2，初始化首项为1（连续正数），末项为2，末项循环递增直到小于中间值（中间值middle2>sum）;每次找到符合条件的序列存入数组中；如出现末项小于middle并且当前序列和大于sum，则首项往前移位，start++;这样就可以找到所有的连续子序列之和为sum的序列；
代码
function FindContinuousSequence(sum)
{
if (sum <= 2) return [];
let start = 1, end = 2;
let middle = Math.floor((sum + 1) / 2);
let temp = (start + end) * (end - start + 1) / 2;
let res = [];
while (start < middle) {
while (temp > sum && start < middle) {
temp = temp - start;
start++;
}
if (temp === sum) {
res.push(Array.from({length: end - start + 1}, (item, index) => item = index + start));
}
end++;
temp += end;
}
return res;
}
复制代码每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
思路
维护一个栈(数组)，每次将数组中的报数报到m-1的那个项删除，最后返回数组中唯一一个项即为最后剩下的数。（当m大于数组的长度时，m取得是m%arr.length）；
代码
function LastRemaining_Solution(n, m)
{
// write code here
// 维护一个栈
if (m < 1) return -1;
let arr = Array.from({length: n}, (item, index) => item = index);
while (arr.length >= 2) {
let modNum = m%arr.length;
arr.splice(modNum-1, 1);
arr = modNum-1 > 0 ? reBuildArray(arr, modNum-1) : arr;
}
return arr[0];
function reBuildArray(arr, index) {
return arr.slice(index).concat(arr.slice(0,index));
}
}
复制代码求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
思路
遍历从1到n, 判断字符
n.toString()是否含有1，如果有的话，用1去切割该字符得到字符串数组的长度-1即为该字符含有1的个数，叠加即可；
代码
function NumberOf1Between1AndN_Solution(n)
{
let count = 0;
for(let i = 1; i <= n; i++) {
let str = String(i);
if (str.indexOf("1") > -1) {
count += str.split("1").length-1
}
}
return count;
}
复制代码把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路
丑数的质因子只包含2，3和5，所以一个丑数一定由另一个丑数乘以2或3或5得到，即
p=2^x*3^y*5^z,采用三个变量保存丑数基数的下标，每次判断三个丑数分别乘以2，3，5之和的最小值与哪个基数相乘2，3，5的值相等，该基数下标+1，将该最小值保至数组存；循环直至第N个丑数。
代码
function GetUglyNumber_Solution(index)
{
if(index < 7) return index;
let index1 = 0, index2 = 0, index3 = 0, num = 1;
let res = [num];
while (res.length < index) {
num = Math.min.call(null, res[index1]*2, res[index2]*3, res[index3]*5);
if (num === res[index1]*2) index1++;
if (num === res[index2]*3) index2++;
if (num === res[index3]*5) index3++;
res.push(num);
}
return num;
}
复制代码
转播
