剑指offer-牛客

数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000 0≤n≤10000

进阶：时间复杂度 O(n) ，空间复杂度 O(n)

输入：

1
[2,3,1,0,2,5,3]

返回值：

1
2

说明：

1
2或3都是对的

方法一：利用set集合
核心思想：
引入set集合，遍历数组元素，检查元素是否在集合中，不在则将元素插入到集合里面；否则表明当前元素在数组中重复，返回当前元素。

1
2
3
4
5
6
7
8
9
10
11
12
function duplicate(numbers) {
    const set = new Set();
    for (let i = 0; i < numbers.length; i++) {
        let item = numbers[i];
        if (set.has(item)) {
            return item;
        } else {
            set.add(item);
        }
    }
    return -1;
}

复杂度分析：
代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于引入额外的集合空间，因此空间复杂度为O(N)，最坏的情况是数组中的元素都不重复。

时间复杂度O(N)
空间复杂度O(N)

方法二：数据重排
核心思想：

重头到尾扫描数组S中的每一个元素，当扫描到第i个元素的时候，比较第i个元素位置的值m是否等于i，如果相等，则说明该元素已经在排好序的位置，继续扫描其他元素；如果不相等，先判断m是否等于S[m]，相等则说明不同位置上的元素值相等，即元素重复。直接返回元素；否则交换m和S[m]将他们放置到排好序的位置

image-20230906100606217

// 测试有问题

复杂度分析：
代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于没有采用额外的数组空间，空间复杂度为O(1)
时间复杂度O(N)
空间复杂度O(1)

二维数组中的查找

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n*,m≤500 ， 矩阵中的值满足 0≤val≤109
进阶：空间复杂度 O(1) ，时间复杂度O(n+*m)

1
2
3
4
5
6
输入：
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：
true
说明：
存在7，返回true

输入：

1
1,[[2]]

返回值：

1
false

输入：

1
3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：

1
false

说明：

1
不存在3，返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
function Find(target, array) {
    let n = array.length; // 行
    let m = array[0].length; // 列
    let x = n - 1,
        y = 0;
    while (x >= 0 && y < m) {
        let temp = array[x][y];
        if (temp == target) return true;
        else if (temp > target) x--;
        else y++;
    }
    return false;
}

解题思路：利用二维数组行列递增特性
主要思路：

  1. 由于行列递增，可以得出：
    a.在一列中的某个数字，其上的数字都比它小
    b.在一行中的某个数字，其右的数字都比它大
  2. 搜索流程：
    a.首先从数组左下角搜索.
    b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。
    c.查找到target,返回true; 如果越界，返回false;

替换空格

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。

例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

数据范围:0≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。

输入：

1
"We Are Happy"

返回值：

1
"We%20Are%20Happy"

输入：

1
" "

返回值：

1
"%20"
1
2
3
function replaceSpace(s) {
    return s.replaceAll(" ", "%20")
}

从尾到头打印链表

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

img

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

输入：

1
{1,2,3}

返回值：

1
[3,2,1]

输入：

1
{67,0,24,58}

返回值：

1
[58,24,0,67]
1
2
3
4
5
6
7
8
9
function printListFromTailToHead(head)
{
    let res = []
    while(head) {
        res.unshift(head.val)
        head = head.next
    }
    return res
}

重建二叉树

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

img

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围：n≤2000，节点的值 −10000≤val≤10000

要求：空间复杂度 O(n)，时间复杂度 O(n)

输入：

1
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

返回值：

1
{1,2,3,4,#,5,6,#,7,#,#,8}

说明：

1
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示

输入：

1
[1],[1]

返回值：

1
{1}

输入：

1
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

返回值：

1
{1,2,5,3,4,6,7}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function TreeNode(x) {
  this.val = x;
  this.left = null;
  this.right = null;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param preOrder int整型一维数组 
 * @param vinOrder int整型一维数组 
 * @return TreeNode类
 */
 function reConstructBinaryTree( preOrder ,  vinOrder ) {
    if(!preOrder.length||!vinOrder.length){
        return null;
    }
    // 前序第一个元素就是根元素
    let rootVal = preOrder.shift();
    let root = new TreeNode(rootVal);
    let index = vinOrder.indexOf(rootVal)
    root.left = reConstructBinaryTree(preOrder, vinOrder.slice(0, index))
    root.right = reConstructBinaryTree(preOrder, vinOrder.slice(index + 1))
    return root
}

二叉树的下一个结点

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

img

示例:

输入:{8,6,10,5,7,9,11},8

返回:9

解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

img

数据范围：节点数满足 1≤n≤50 ，节点上的值满足 1≤val≤100

要求：空间复杂度 O(1) ，时间复杂度O(n)

输入描述：

输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点

返回值描述：

返回传入的子树根节点的下一个节点，后台会打印输出这个节点

示例1

输入：

1
{8,6,10,5,7,9,11},8

返回值：

1
9

输入：

1
{8,6,10,5,7,9,11},6

返回值：

1
7

输入：

1
{1,2,#,#,3,#,4},4

返回值：

1
1

输入：

1
{5},5

返回值：

1
"null"

说明：

1
不存在，后台打印"null"

方法一：直接递归中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var arr = [];
function GetNext(pNode) {
    // 找到根节点
    let root = pNode;
    while (root.next !== null) {
        root = root.next;
    }
    df(root);
    let index = arr.indexOf(pNode);
    return arr[index + 1];
}
function df(pNode) {
    if (pNode == null) return;
    df(pNode.left);
    arr.push(pNode);
    df(pNode.right);
}

方法二：直接查找

  1. 如果给出的结点有右子节点，则最终要返回的下一个结点即右子树的最左下的结点
  2. 如果给出的结点无右子节点，且当前结点是其父节点的左子节点，则返回其父节点
  3. 如果给出的结点无右子节点，且当前结点是其父节点的右子节点，则先要沿着左上方父节点爬树，一直爬到当前结点是其父节点的左子节点为止，返回的就是这个父节点；或者没有满足上述情况的则返回为NULL

用两个栈实现队列

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围：n≤1000

要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)

输入：

1
["PSH1","PSH2","POP","POP"]

返回值：

1
1,2

说明：

1
2
3
4
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2

输入：

1
["PSH2","POP","PSH1","POP"]

返回值：

1
2,1

借助栈的先进后出规则模拟实现队列的先进先出

1、当插入时，直接插入 stack1

2、当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2 栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var stactk1 = []
var stactk2 = []
function push(node)
{
    stactk1.push(node)
}
function pop()
{
    if(stactk2.length == 0) {
        while(stactk1.length != 0) {
            stactk2.push(stactk1.pop())
        }
    }
    if (stactk2.length != 0) {
        return stactk2.pop()
    }
}
module.exports = {
    push : push,
    pop : pop
};

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 递归写法
function Fibonacci( n ) {
    if(n == 1 || n == 2) return 1
    else return Fibonacci(n - 1) + Fibonacci(n - 2)
}

// 迭代
function Fibonacci2( n ) {
    if(n == 1 || n == 2) return 1;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 0; dp[1] = 1;
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
console.log(Fibonacci2(5));

旋转数组的最小数字

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000

要求：空间复杂度：O*(1) ，时间复杂度：O(logn)

输入：

1
[3,4,5,1,2]

返回值：

1
1

输入：

1
[3,100,200,3]

返回值：

1
3
  • step 1：双指针指向旋转后数组的首尾，作为区间端点。
  • step 2：若是区间中点值大于区间右界值，则最小的数字一定在中点右边。
  • step 3：若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界。
  • step 4：若是区间中点值小于区间右界值，则最小的数字一定在中点左边。
  • step 5：通过调整区间最后即可锁定最小值所在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function minNumberInRotateArray( nums ) {
    for(let i = 0; i < nums.length - 1; i++) {
        if(nums[i] > nums[i+1]) {
            return nums[i+1];
        }
    }
    return nums[0];
}

function minNumberInRotateArray2( nums ) {
    let left = 0, right = nums.length - 1;
    while(left < right) {
        let mid = Math.floor((left + right) / 2);
        if(nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] == nums[right]) {
            right--;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

二分法总结

难点：

  1. 循环时 left < right 还是 left <= right
  2. nums[mid] > target时 right = mid 还是 mid - 1

区间可以是[left, right], 或者[left, right),也有其他情况，但是其他情况不常见

一开始区间是什么，while循环里面就要是什么

比如说left = 0, right = nums.length -1 ,那么区间就是左闭右闭，while循环里面也要坚持左闭右闭

左闭右闭

伪代码

1
2
3
4
5
6
7
8
9
10
11
let left = 0, right = nums.length; // 区间我们已经定义为左闭右闭 [left, right]
while(left <= right) { // 区间左闭右闭
    let mid = left + right >> 1
    if (nums[mid] > target) { // 已经明确了，mid对应的值是会大于target,的所以不需要mid这个值了
        right = mid - 1;
    } else if (nums[mid] < target) {
        left = mid + 1;
    } else {
        return mid;
    }
}

左闭右开

伪代码

1
2
3
4
5
6
7
8
9
10
11
let left = 0, right = nums.length; // 区间已经被定义为左闭右开  [left, right)
while(left < right) { // 这里也要遵守左闭右开，也就是最终left和right不能相等
    let mid = left + right >> 1
    if(nums[mid] > target) { // 说明target在left和mid中间，下一个搜索区间应该是[left, mid)
        right = mid
    } elft if (nums[mid] < target) {
        left = mid + 1 // 下一个搜索区间[mid + 1, right)
    } else {
        return mid
    }
}

矩阵中的路径

image-20230910095433899

输入：

1
[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"

返回值：

1
true

输入：

1
[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"

返回值：

1
false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function hasPath( matrix ,  word ) {
    let words = word.split("")
    for(let i = 0; i < matrix.length; i++) {
        for(let j = 0; j < matrix[0].length; j++) {
            if(dfs(matrix, words, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

function dfs(matrix, word, x, y, index) {

    // 越界或者不相等，直接返回false
    if(x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0 || matrix[x][y] != word[index]) {
        return false;
    }
    // 说明已经遍历完
    if(index == word.length - 1) {
        return true;
    }
    let temp = matrix[x][y];
    matrix[x][y] = '.'; // 代表matrix[x][y] 已经遍历过了
    let res = dfs(matrix, word, x + 1, y, index + 1) || dfs(matrix, word, x - 1, y, index + 1)
    || dfs(matrix, word, x, y + 1, index + 1) || dfs(matrix, word, x, y - 1, index + 1);
    matrix[x][y] = temp
    return res; 
}

let arr = [['a','b','c','e'],['s','f','c','s'],['a','d','e','e']], word = "abcced";
console.log(hasPath(arr, word))

二进制中1的个数

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

数据范围：−231<=n<=231−1

即范围为:−2147483648<=n<=2147483647

输入：

1
10

返回值：

1
2

说明：

1
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。

输入：

1
-1

返回值：

1
32

说明：

1
负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function NumberOf1( n ) {
    let count = 0;
    for(let i = 0; i < 32; i++) {
        // n = n >> i  提交有误
        // if(n & 1) {
        //     count ++;
        // }
        if((n & (1 << i)) != 0){
            count++;
        }
    } 
    return count;
}
// 方法二
function NumberOf2( n ) {
    let count = 0;
    while(n != 0) {
        n &= (n-1)
        count++
    }
    return count;
}

机器人的运动范围

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

数据范围：0≤threshold≤15 ，1≤rows,cols≤100

进阶：空间复杂度 O*(*nm) ，时间复杂度 O(nm)

输入：

1
1,2,3

返回值：

1
3

输入：

1
0,1,3

返回值：

1
1

输入：

1
10,1,100

返回值：

1
29

说明：

1
[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的

输入：

1
5,10,10

返回值：

1
21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

function movingCount(threshold, rows, cols)
{
    let isVitied = Array(rows).fill(false).map(() => Array(cols).fill(false))
    return dfs(threshold, rows, cols, 0, 0, isVitied)
    
}

function dfs(threshold, rows, cols, x, y, isVitied) {
    if(x < 0 || y < 0 || x >= rows || y >= cols || isVitied[x][y] || cal(x) + cal(y) > threshold) {
        return 0;
    }
    isVitied[x][y] = true
    return 1 + dfs(threshold, rows, cols, x + 1, y, isVitied) 
    + dfs(threshold, rows, cols, x - 1, y, isVitied) 
    + dfs(threshold, rows, cols, x, y + 1, isVitied) 
    + dfs(threshold, rows, cols, x, y - 1, isVitied);
}

function cal(n) {
    let sum = 0;
    while(n != 0) {
        sum += n % 10;
        n = parseInt(n/10);
    }
    return sum;
}
console.log(movingCount(5,10,10))

javascript创建二维数组

  1. 声明并初始化：

    1
    let arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];

  2. 使用数组的map方法：

    1
    let arr = Array(3).fill().map(() => Array(3).fill(0));

  3. 使用循环：

    1
    2
    3
    4
    let arr = new Array(3);
    for(let i = 0; i < arr.length; i++) {
      arr[i] = new Array(3).fill(0);
    }

剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m] 。请问 k[1]k[2]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

数据范围：2≤n≤60
进阶：空间复杂度 O(1) ，时间复杂度 O(n)

输入一个数n，意义见题面。

输出答案。

输入：

1
8

返回值：

1
18

说明：

1
8 = 2 +3 +3 , 2*3*3=18

输入：

1
2

返回值：

1
1

说明：

1
m>1，所以切成两段长度是1的绳子

// 用回溯会超时

// 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 动态规划
function cutRope2(number) {
    if(number <= 3) {
        return number - 1;
    }
    let dp = new Array(number + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    dp[4] = 4;
    for(let i = 5; i <= number; i++) {
        for(let j = 1; j < i; j++) {
            dp[i] = Math.max(dp[i], j * dp[i - j]);
        }
    }
    return dp[number];
}

// 贪心算法

知识点：贪心

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

思路：

image-20230912132728654

因此后续，使用贪心思想，不断将绳子分成每段长度为3即可，不足3的可以考虑，如果最后剩余的是2，直接乘上，如果最后剩余的是1，则取出一个3组成4分成长度为2的两段，因为2∗2>1∗32∗2>1∗3。

具体做法：

  • step 1：按照上述思路，不超过3的直接计算
  • step 2：超过3的不断累乘3，然后number不断减去3，直到最后不超过4。
  • step 3：最后乘上剩余的数字。
1
2
3
4
5
6
7
8
9
10
11
12
// 贪心算法
function cutRope3(number) {
    if(number <= 3) {
        return number - 1
    }
    let res = 1
    while(number > 4) {
        res *= 3;
        number -= 3;
    }
    return res * number
}

数值的整数次方

实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：

1.保证base和exponent不同时为0。

2.不得使用库函数，同时不需要考虑大数问题

3.有特殊判题，不用考虑小数点后面0的位数。

数据范围： ∣base∣≤100 ，∣exponent∣≤100 ,保证最终结果一定满足 ∣val∣≤104
进阶：空间复杂度 O(1) ，时间复杂度 O(n)

输入：

1
2.00000,3

返回值：

1
8.00000

输入：

1
2.10000,3

返回值：

1
9.26100

输入：

1
2.00000,-2

返回值：

1
0.25000

说明：

1
2的-2次方等于1/4=0.25    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function Power(base, exponent) {
    if(base == 0) {
        return 0;
    }
    if(exponent == 0) {
        return 1;
    }
    let sum = 1;
    if (exponent > 0) {
        for(let i = 0; i < exponent; i++) {
            sum *= base;
        }
    } else {
        for(let i = 0; i < (-exponent); i++) {
            sum = sum / base;
        }
    }
    return sum;
}

console.log(Power(2.00000,-2))

打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

  1. 用返回一个整数列表来代替打印
  2. n 为正整数，0 < n <= 5

输入：

1
1

返回值：

1
[1,2,3,4,5,6,7,8,9]
1
2
3
4
5
6
7
8
function printNumbers( n ) {
    let arr = []
    for(let i = 1; i < Math.pow(10, n); i++) {
        arr.push(i);
    }
    return arr
}
console.log(printNumbers(3))

删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

1.此题对比原题有改动

2.题目保证链表中节点的值互不相同

3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

数据范围:

0<=链表节点值<=10000

0<=链表长度<=10000

输入：

1
{2,5,1,9},5

返回值：

1
{2,1,9}

说明：

1
给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 2 -> 1 -> 9

输入：

1
{2,5,1,9},1

返回值：

1
{2,5,9}

说明：

1
给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 2 -> 5 -> 9   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function deleteNode(head, val) {
    // write code here
    if(head.val == val) return head.next;
    let p = head;
    let q = head.next;
    while(q != null) {
      if(q.val == val) {
        if(q.next) {
            p.next = q.next
        } else {
            p.next = null
        }
        break;
      }
      p = q;
      q = q.next;
    }
    
}

function deleteNode2(head, val) {
    if(head.val == val) return head.next;
    let curr = head;
    let prev = null;
    while(curr.val != val) {
        prev = curr;
        curr = curr.next
    }
    prev.next = curr.next;
    return head;
}

正则表达式匹配

请实现一个函数用来匹配包括’.’和’*’的正则表达式。

1.模式中的字符’.’表示任意一个字符

2.模式中的字符’*’表示它前面的字符可以出现任意次（包含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

数据范围:

1.str 只包含从 a-z 的小写字母。

2.pattern 只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘*’。

0≤str.length≤26
0≤pattern.length≤26

输入：

1
"aaa","a*a"

返回值：

1
true

说明：

1
中间的*可以出现任意次的a，所以可以出现1次a，能匹配上

输入：

1
"aad","c*a*d"

返回值：

1
true

说明：

1
因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。

输入：

1
"a",".*"

返回值：

1
true

说明：

1
".*" 表示可匹配零个或多个（'*'）任意字符（'.'）

输入：

1
"aaab","a*a*a*c"

返回值：

1
false

image-20230914110127831

dp数组的含义：

dp[i][j]当字符串长度为i,正则表达式字符串长度为j时，是否匹配

dp[n][m]为true就代表匹配，其中n为字符串长度,m为正则表达式长度

第一种情况

p[j]是普通字符串或者p[j] = ‘.’

  • 或者p[j] = ‘.’ , s[i] = p[j] 的话， dp[i][j] = dp[i-1][j-1],此时dp[i][j]就取决于``dp[i-1][j-1]`是否匹配,因为s[i]和p[j]是相等的
  • s[i] ≠ p[j]的话，dp[i][j]就是false了

第二种情况

p[j] = ‘*’

  • p[j-1]≠s[i]的话， dp[i][j] = dp[i][j-2]
  • p[j-1] = s[i]
    • 当*匹配0个(就相当于星号没起作用)，如果s[i]=p[j-1]的话，dp[i][j] = dp[i][j-2]
    • 当*匹配1个,如果s[i-1] = p[j-1],dp[i][j] = dp[i-1][j-1]
    • 当*匹配n个，dp[i][j] = dp[i-1][j]

调整数组顺序使奇数位于偶数前面(一)

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围：0≤n≤5000，数组中每个数的值 0≤val≤10000

要求：时间复杂度O(n)，空间复杂度 O(n)

进阶：时间复杂度O(n2)，空间复杂度O(1)

输入：

1
[1,2,3,4]

返回值：

1
[1,3,2,4]

输入：

1
[2,4,6,5,7]

返回值：

1
[5,7,2,4,6]

输入：

1
[1,3,5,6,7]

返回值：

1
[1,3,5,7,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 第一种做法，借助一个辅助数组
// 第二种做法，利用插入排序的思想
function reOrderArray( array ) {
    if(array && array.length == 0) return array;
    let j = 0;
    let temp = 0;
    for(let i = 0; i < array.length; i++) {
        let temp = array[i];
        if(array[i] % 2 == 0) { // 偶数跳过
            continue;
        } else { // 奇数
            let k = i;
            while(k > j) {
                // 整体向后移动一位
                array[k] = array[k - 1];
                k--;
            }
            array[k] = temp;
            j++;
        }
    }
    return array;
}
let arr = [1,2,3,4]
console.log(reOrderArray(arr))

链表中倒数最后k个结点

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤105，0≤≤ai≤109，0≤k≤109

要求：空间复杂度 O*(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

img

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

输入：

1
{1,2,3,4,5},2

返回值：

1
{4,5}

说明：

1
返回倒数第2个节点4，系统会打印后面所有的节点来比较。

输入：

1
{2},8

返回值：

1
{}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 function FindKthToTail( pHead ,  k ) {
    let slow = pHead, fast = pHead;
    let i = 0;
    while(i < k) {
        if(fast != null) {
            fast = fast.next;
        } else {
            return slow = null
        }
        
        i++;
    }
    while(fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

链表中环的入口结点

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

img

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

输出描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

输入：

1
{1,2},{3,4,5}

返回值：

1
3

说明：

1
返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

输入：

1
{1},{}

返回值：

1
"null"

说明：

1
没有环，返回对应编程语言的空结点，后台程序会打印"null"

输入：

1
{},{2}

返回值：

1
2

说明：

1
环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function EntryNodeOfLoop(pHead) {
    let slow = pHead;
    let fast = pHead;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            let index1 = pHead;
            let index2 = fast;
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index2;
        }
    }
    return null;
}

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

img

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

1
(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

动画如下：

142.环形链表II（求入口）

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

反转链表

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

img

输入：

1
{1,2,3}

返回值：

1
{3,2,1}

输入：

1
{}

返回值：

1
{}

说明：

1
空链表则输出空     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 方法一：借助栈
function ReverseList( head ) {
    let stack = [];
    let p = head;
    while(p != null) {
        stack.push(p);
        p = p.next;
    }
    if(stack.length > 0) {
        p = stack.pop();
    } else {
        return null;
    }
    let prevNode = p;
    while(stack.length > 0) {
        let temp = stack.pop();
        prevNode.next = temp;
        prevNode = temp;
    }
    // 最后一个结点的下一个要置空（关键）这个是头节点，否则会造成环
    prevNode.next = null;
    return p;
}
// 方法二：新建一个链表
function ReverseList( head ) {
    let newHead = null;
    while(head != null) {
        let temp = head.next;
        head.next = newHead;
        newHead = head;
        head = temp;
    }
    return newHead;
}

// 方法三：递归调用
function ReverseList( head ) {
    return reverse(null, head);
}
function reverse(prev, cur) {
    if (cur == null) return prev;
    let temp = cur.next;
    cur.next = prev;
    return reverse(cur, temp);
}

// 方法四：双指针法
function ReverseList( head ) {
    let cur = head;
    let prev = null;
    while(cur != null){
        let temp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = temp;
    }
    return prev;
}

img

合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

img

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

img

输入：

1
{1,3,5},{2,4,6}

返回值：

1
{1,2,3,4,5,6}

输入：

1
{},{}

返回值：

1
{}

输入：

1
{-1,2,4},{1,3,4}

返回值：

1
{-1,1,2,3,4,4}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
function Merge( pHead1 ,  pHead2 ) {
    let newHead = null;
    if(pHead1 == null) return pHead2;
    if(pHead2 == null) return pHead1;
    let p = pHead1;
    let q = pHead2;
    if(p.val < q.val) {
        newHead = p
        p = p.next;
    } else {
        newHead = q
        q = q.next;
    }
    let node = newHead;
    while(p != null && q != null) {
        if(p.val < q.val) {
            newHead.next = p;
            newHead = p;
            p = p.next;
        } else {
            newHead.next = q;
            newHead = q;
            q= q.next;
        }
    }
    // while(p != null) {
    //     newHead.next = p;
    //     newHead = p;
    //     p = p.next;
    // }
    // while(q != null) {
    //     newHead.next = q;
    //     newHead = q;
    //     q= q.next;
    // }
    if(p != null) newHead.next = p;
    if(q != null) newHead.next = q;
    return node;
}


递归

1
2
3
4
5
6
7
8
9
10
11
12
// 递归
function Merge( pHead1 ,  pHead2 ) {
    if(pHead1 == null) return pHead2;
    if(pHead2 == null) return pHead1;
    if(pHead1.val <= pHead2.val) {
        pHead1.next = Merge(pHead1.next, pHead2);
        return pHead1;
    } else {
        pHead2.next = Merge(pHead1, pHead2.next);
        return pHead2;
    }
}

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

img

数据范围:

0 <= A的节点个数 <= 10000

0 <= B的节点个数 <= 10000

输入：

1
{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

返回值：

1
true

输入：

1
{1,2,3,4,5},{2,4}

返回值：

1
true

输入：

1
{1,2,3},{3,1}

返回值：

1
false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function HasSubtree(pRoot1, pRoot2)
{
    // 空树
    if(pRoot2 == null ) {
        return false;
    }
    // 一个为空另一个不为空
    if(pRoot1 == null && pRoot2 != null) {
        return false
    }
    if(pRoot1 == null && pRoot2 == null) {
        return true;
    }
    let flag1 = dfs(pRoot1, pRoot2)
    // 递归树1的每个节点
    let flag2 = HasSubtree(pRoot1.left, pRoot2)
    let flag3 = HasSubtree(pRoot1.right, pRoot2)
    return flag1 || flag2 || flag3;
}

function dfs(node1, node2) {
    // 当一个节点存在，另一个不存在时
    if(node1 == null && node2 != null) {
        return false;
    }
    // 两个都为空则返回
    if(node1 == null || node2 == null) {
        return true;
    }
    if(node1.val != node2.val) {
        return false;
    }
    // 递归比较子树
    return dfs(node1.left, node2.left) && dfs(node1.right, node2.right)
}

二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

数据范围：二叉树的节点数 0≤n*≤1000 ， 二叉树每个节点的值 0≤val≤1000

要求： 空间复杂度 O(n) 。本题也有原地操作，即空间复杂度 O*(1) 的解法，时间复杂度O(n)

比如：

源二叉树

img

镜像二叉树

img

输入：

1
{8,6,10,5,7,9,11}

返回值：

1
{8,10,6,11,9,7,5}

说明：

1
如题面所示

输入：

1
{}

返回值：

1
{}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
// 方法一： 递归
function Mirror(pRoot) {
    // 空树返回
    if(pRoot == null) {
        return null;
    }
    let left = Mirror(pRoot.left);
    let right = Mirror(pRoot.right);
    // 交换
    pRoot.left = right;
    pRoot.right = left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 方法2： 借助栈
function Mirror(pRoot) {
    if(pRoot == null) return null;
    let stack = []
    stack.push(pRoot);
    while(stack.length > 0) {
        let node = stack.pop()
        // 左右结点入栈
        if(node.left != null) {
            stack.push(node.left)
        }
        if(node.right != null) {
            stack.push(node.right)
        }
        // 交换左右结点
        let temp = node.left;
        node.left = node.right;
        node.right = temp
    }
    return pRoot;
}

对称的二叉树

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如： 下面这棵二叉树是对称的
img
下面这棵二叉树不对称。
img

数据范围：节点数满足 0≤n≤1000，节点上的值满足 val∣≤1000

要求：空间复杂度O(n)，时间复杂度 O(n)

备注：

你可以用递归和迭代两种方法解决这个问题

输入：

1
{1,2,2,3,4,4,3}

返回值：

1
true

输入：

1
{8,6,9,5,7,7,5}

返回值：

1
false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 // 递归实现
function isSymmetrical( pRoot ) {
    // write code here
    return symmetrical(pRoot, pRoot)
}
function symmetrical(root1, root2) {
    // 可以两个都为空
    if(root1 == null && root2 == null) {
        return true;
    } 
    // 有一个为空，必不对称
    if (root1 == null || root2 == null) {
        return false;
    } 
    if (root1.val != root2.val) {
        return false;
    }
    return symmetrical(root1.left, root2.right) && symmetrical(root1.right, root2.left); 
}

层次遍历:

  • step 1：首先判断链表是否为空，空链表直接就是对称。
  • step 2：准备两个队列，分别作为从左往右层次遍历和从右往左层次遍历的辅助容器，初始第一个队列加入左节点，第二个队列加入右节点。
  • step 3：循环中每次从队列分别取出一个节点，如果都为空，暂时可以说是对称的，进入下一轮检查；如果某一个为空或是两个节点值不同，那必定不对称。其他情况暂时对称，可以依次从左往右加入子节点到第一个队列，从右往左加入子节点到第二个队列。（这里包括空节点）
  • step 4：遍历结束也没有检查到不匹配，说明就是对称的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 层次遍历
function isSymmetrical( pRoot ) {
    // 存储从左往右遍历的结果
    let queue1 = []
    // 存储从右往左遍历的结果
    let queue2 = []
    if(pRoot == null) return true;
    let p1 = p2 = pRoot;
    queue1.push(p1);
    queue2.push(p2);
    while(queue1.length > 0 && queue2.length > 0) {
        p1 = queue1.shift()
        p2 = queue2.shift()
        // 都为空暂时对称
        if(p1 == null && p2 == null) 
            continue
        if(p1 == null || p2 == null || p1.val != p2.val) {
            return false;
        }
        queue1.push(p1.left);
        queue1.push(p1.right);
        queue2.push(p2.right);
        queue2.push(p2.left);
    }
    return true;
}

包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

数据范围：操作数量满足 0≤n≤300 ，输入的元素满足 ∣val∣≤10000
进阶：栈的各个操作的时间复杂度是 O(1) ，空间复杂度是O(n)

示例:

输入: [“PSH-1”,”PSH2”,”MIN”,”TOP”,”POP”,”PSH1”,”TOP”,”MIN”]

输出: -1,2,1,-1

解析:

“PSH-1”表示将-1压入栈中，栈中元素为-1

“PSH2”表示将2压入栈中，栈中元素为2，-1

“MIN”表示获取此时栈中最小元素==>返回-1

“TOP”表示获取栈顶元素==>返回2

“POP”表示弹出栈顶元素，弹出2，栈中元素为-1

“PSH1”表示将1压入栈中，栈中元素为1，-1

“TOP”表示获取栈顶元素==>返回1

“MIN”表示获取此时栈中最小元素==>返回-1

输入：

1
["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

返回值：

1
-1,2,1,-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
let stack = [] // 原始栈
let minStack = [] // 最小栈
function push(node)
{
    if(stack.length == 0) {
        minStack.push(node)
    } else {
        // 如果比前一个数值小。就把这个数压入最小栈中
        // 否则就把上一个值压入最小栈
        let prev = minStack[minStack.length - 1]
        if(node <= prev) {
            minStack.push(node)
        } else {
            minStack.push(prev)
        }
    }
    stack.push(node)
}
function pop()
{
    if(stack.length == 0) {
        return null
    } else {
        minStack.pop()
        let ret = stack.pop()
        return ret;
    }
}
function top()
{
    let n = stack.length;
    if (n == 0) {
        return null
    } else {
        return stack[n-1];
    }
}
function min()
{
    let ret = minStack[minStack.length - 1];
    return ret;
}
module.exports = {
    push : push,
    pop : pop,
    top : top,
    min : min
};

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

  1. 0<=pushV.length == popV.length <=1000

  2. -1000<=pushV[i]<=1000

  3. pushV 的所有数字均不相同

输入：

1
[1,2,3,4,5],[4,5,3,2,1]

返回值：

1
true

说明：

1
2
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

输入：

1
[1,2,3,4,5],[4,3,5,1,2]

返回值：

1
false

说明：

1
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

具体做法：

  • step 1：准备一个辅助栈，两个下标分别访问两个序列。
  • step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
  • step 3：栈顶等于出栈数组当前元素就出栈。
  • step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function IsPopOrder( pushV ,  popV ) {
   let stack = []
   let n = pushV.length;
   let j = 0; // 入栈的下标
   for(let i = 0; i < n; i++) {
        // 入栈，栈为空或者栈顶不等于出栈数组
        while(j < n && (stack.length == 0 || stack[stack.length - 1] != popV[i])) {
            stack.push(pushV[j]);
            j++;
        }
        // 栈顶等于出栈数组
        if(stack[stack.length - 1] == popV[i]) {
            stack.pop();
        } else { 
            // 序列不匹配
            return false;
        }
   }
   return true;
}

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

数据范围： 节点数量 0≤n≤1000 ，节点上的值满足 1≤val≤105 ，保证节点上的值各不相同
要求：空间复杂度 O(n) ，时间时间复杂度 O(n2)

提示：

1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。

2.该题我们约定空树不是二叉搜索树

3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

4.参考下面的二叉搜索树，示例 1

img

输入：

1
[1,3,2]

返回值：

1
true

说明：

1
是上图的后序遍历 ，返回true

输入：

1
[3,1,2]

返回值：

1
false

说明：

1
不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false

输入：

1
[5,7,6,9,11,10,8]

返回值：

1
true

算法1（分治）

解题思路

  1. 二叉树的后序遍历顺序是：左子树 -> 右子树 -> 根节点

  2. 因此序列的最后一个数代表了根节点

  3. 因此我们可以将一个序列划分为3段, 左子树+右子树+根, 例如[4, 8, 6, 12, 16, 14, 10]可以根据根节点的值将其划分为左子树[4, 8, 6], 右子树[12, 16, 14], 根[10], 由于我们是先确定的右子树区间, 因此当左子树区间中出现大于根节点的值时, 序列不合法, 我们再采用分治的思想, 对于每段序列代表的子树, 检查它的左子树和右子树, 当且仅当左右子树都合法时返回true
    图片说明

  4. 步骤 数组序列 根节点 左子树 右子树
    1 【4,8,6,12,16,14,10】 【10】 【4，8，6】 【12，16，14】
    2 【4，8，6】 【6】 【4】 【8】
    3 【12，16，14】 【14】 【12】 【16】 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function VerifySquenceOfBST(sequence)
{
    if(sequence.length == 0) return false;
    return check(sequence, 0, sequence.length - 1);
}

function check(arr, l, r) {
    if(l >= r) return true;
    // 根结点
    let root = arr[r];
    // 寻找右子树区间, 二叉搜索树（左《 中 《 右）
    let j = r - 1;
    while(j >= 0 && arr[j] > root) {
        j--;
    }
    
    // 左区间 (如果左子树存在大于根的元素，就不是二叉搜索树)
    for(let i = l; i <= j; i++) {
        if(arr[i] > root) return false;
    }

    return check(arr, l, j) && check(arr, j + 1, r - 1);
}

算法2（栈）

  1. 实际上二叉树的中序遍历和后序遍历对应着一种栈的压入、弹出序列, 而对后序遍历序列从小到大排序就得到了中序遍历序列
  2. 我们得到中序遍历序列后, 将其作为入栈序列, 检查后序遍历序列是不是一个合法的出栈序列即可
  3. 对于检查栈的合法压入、弹出序列问题, 请看栈的压入、弹出序列题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 借助栈
function VerifySquenceOfBST(sequence)
{
    if(sequence.length == 0) return false;
    let inorder = sequence.slice();
    inorder = inorder.sort((a,b) => a-b)
    return check(inorder, sequence);
}
/**
 * 
 * @param {*} pushV 中序遍历序列
 * @param {*} popV 后序遍历序列
 */
function check(pushV, popV) {
    let n = popV.length;
    let stack = []
    let i = 0, j = 0;
    while(i < n) {
        stack.push(pushV[i]);
        while(stack.length > 0 && stack[stack.length - 1] == popV[j]) {
            j++;
            stack.pop();
        }
        i++;
    }
    return j == n;
}

数组复制

在JavaScript中，有多种方法可以复制一个数组。以下是其中的一些方法：

  1. 使用数组的 slice() 方法：
1
2
javascriptlet originalArray = [1, 2, 3, 4, 5];
let copiedArray = originalArray.slice();
  1. 使用数组的 concat() 方法：
1
2
javascriptlet originalArray = [1, 2, 3, 4, 5];
let copiedArray = Array.from(originalArray);
  1. 使用展开运算符 (...):
1
2
javascriptlet originalArray = [1, 2, 3, 4, 5];
let copiedArray = [...originalArray];
  1. 使用 Array.from() 方法并传递一个映射函数以保持数组中的原始值：
1
2
javascriptlet originalArray = [1, 2, 3, 4, 5];
let copiedArray = Array.from(originalArray, (value) => value);

以上所有的方法都将创建一个新的数组，新数组的内容与原数组完全相同，但它们并不共享任何引用。这意味着如果你更改原始数组，复制的数组不会受到影响，反之亦然。

二叉树中和为某一值的路径(二)

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22

img

则合法路径有[[10,5,7],[10,12]]

数据范围:

树中节点总数在范围 [0, 5000] 内

-1000 <= 节点值 <= 1000

-1000 <= expectNumber <= 1000

输入：

1
{10,5,12,4,7},22

返回值：

1
[[10,5,7],[10,12]]

说明：

1
返回[[10,12],[10,5,7]]也是对的

输入：

1
{10,5,12,4,7},15

返回值：

1
[]

输入：

1
{2,3},0

返回值：

1
[]

输入：

1
{1,3,4},7

返回值：

1
[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var result = []
var path = []
function FindPath( root ,  target ) {
    if(root == null) return result
    dfs(root, target);
    return result;
}
function dfs(root, target) {
    if(root == null) return;
    // 路径更新
    path.push(root.val);
    target -= root.val
    //  如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret
    if(root.left == null && root.right == null && target == 0) {
        result.push(path.slice())
    }
    dfs(root.left, target);
    dfs(root.right, target);
    path.pop();
}

数组中出现次数超过一半的数字

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：n≤50000，数组中元素的值 0≤val≤10000

要求：空间复杂度：O(1)，时间复杂度O(n)

保证数组输入非空，且保证有解

输入：

1
[1,2,3,2,2,2,5,4,2]

返回值：

1
2

输入：

1
[3,3,3,3,2,2,2]

返回值：

1
3

输入：

1
[1]

返回值：

1
1

方法一：借助辅助空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 方法一: 哈希法
function MoreThanHalfNum_Solution( numbers ) {
  const map = new Map()

  let max = 0

  for(let num of numbers) {
    if(map.has(num)) {
      map.set(num, map.get(num) + 1)
    } else {
      map.set(num, 1)
    }
    // Map(2) { 1024 => 500, 2048 => 501 } 预防这种情况
    max = map.get(num) > max ? map.get(num) : max
  }
  for(let entry of map.entries()) {
    if(entry[1] >= map.size / 2 && max == entry[1]) {
      return entry[0]
    }
  }
  return numbers[0]
}

方法二：排序

1
2
3
4
5
// 方法二: 排序
function MoreThanHalfNum_Solution2( numbers ) {
  numbers.sort()
  return numbers[parseInt(numbers.length / 2)]
}

方法三： 候选法（最优解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function MoreThanHalfNum_Solution3( numbers ) {
  let cond = -1 // 候选人
  let cnt = 0 // 候选人投票次数
  for(let i = 0; i < numbers.length; i++) {
    if(cnt == 0) {
      cond = numbers[i];
      cnt++;
    } else {
      if(cond == numbers[i]) cnt++
      else cnt--
    }
  }
  cnt = 0
  for(let k of numbers) {
    if(cond == k) cnt++;
  }
  if(cnt > numbers.length / 2) return cond
  return 0
}
算法
#剑指offer
剑指offer-牛客
http://example.com/2023/09/06/04.算法/03.剑指offer-牛客/
作者
Deng ErPu
发布于
2023年9月6日
许可协议