算法题

刷题

二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

1
2
3
4
5
6
7

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

1
2
3

//从右上角开始查找，左下角也是可以的。
//为什么能这样查？如果当前元素大于目标值，往下是不可能查找到的，只能往左。如果当前元素小于目标值，左边的元素也都小于目标值，只能向下。
//时间复杂度O(m+n),空间复杂度O(1)

从头到尾打印链表

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

1
2

输入：head = [1,3,2]
输出：[2,3,1]

1
2
3

//用栈，先压栈，再pop到数组
//递归法
//也可以先反转过来，再输出

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

1
2
3
4
5
6
7
8
9
10

例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

1