题目描述:实现 FreqStack,模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数:

  • push(int x),将整数 x 推入栈中。
  • pop(),它移除并返回栈中出现最频繁的元素。
    如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。
阅读全文 »

题目描述:运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
阅读全文 »

题目描述:给你一个 m x n 的矩阵 board ,由若干字符 'X''O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

阅读全文 »

题目描述:中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

阅读全文 »

题目描述:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

阅读全文 »

题目描述:给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数,要么是一个列表;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化,使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator :

  1. NestedIterator(List nestedList) 用嵌套列表 nestedList 初始化迭代器。
  • int next() 返回嵌套列表的下一个整数。

  • boolean hasNext() 如果仍然存在待迭代的整数,返回 true ;否则,返回 false 。
    你的代码将会用下述伪代码检测:

1
2
3
4
5
initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配,那么你的代码将会被判为正确。

阅读全文 »

题目描述:序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

提示:

  • 树中结点数在范围 [0, 104]
  • -1000 <= Node.val <= 1000
阅读全文 »

题目描述:给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。提示:

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] != i
  • 保证输入为有向无环图 (GAD)

代码实现

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private List<List<Integer>> allPaths = new ArrayList<>();

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<Integer> path = new ArrayList<Integer>();
path.add(0);
allPathsSourceTarget(graph, 0, graph.length - 1, path);
return allPaths;
}

public void allPathsSourceTarget(int[][] graph, int k, int n, List<Integer> path) {
List<Integer> currentPath = new ArrayList<>(path);
if (k == n) {
allPaths.add(currentPath);
return;
}
for (int i : graph[k]){
currentPath.add(i);
allPathsSourceTarget(graph, i, n, currentPath);
currentPath.remove(currentPath.size() - 1);
}
}
}

题目描述:给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
阅读全文 »

题目描述:给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

提示:

阅读全文 »