著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：
实现 track(int x) 方法，每读入一个数字都会调用该方法；
实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。
注意：本题相对原题稍作改动
示例:
输入: ["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"] [[], [1], [0], [0]] 输出: [null,0,null,1]
提示：
x <= 50000track 和 getRankOfNumber 方法的调用次数均不超过 2000 次树状数组结构直接套模板使用
在该题中，树状数组对应下标表意为当前下标数字的出现次数
track(int x) 方法，每读入一个数字都会调用该方法, 等价于在给树状数组对应下标数值加1，即当前下标出现次数加1getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数，等价于求下标0到当前下标的前缀和，即从0到当前下标的所有数字出现次数之和class StreamRank {
private FenwickTree fenwickTree;
public StreamRank() {
fenwickTree = new FenwickTree(50001);
}
public void track(int x) {
fenwickTree.add(x+1,1);
}
public int getRankOfNumber(int x) {
return fenwickTree.query(x+1);
}
class FenwickTree{
int[] arr;
public FenwickTree(int num){
arr = new int[num+1];
}
int lowBit(int x){
return x & ( -x );
}
public void add(int idx, int num){
while (idx < arr.length){
arr[idx] += num;
idx += lowBit(idx);
}
}
public int query(int idx){
int sum = 0;
while (idx > 0){
sum += arr[idx];
idx -= lowBit(idx);
}
return sum;
}
}
}给你一个数组 nums ，请你完成两类查询。
nums 下标对应的值nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right实现 NumArray 类：
NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值 更新 为 valint sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）
示例 1：
输入： ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] 输出： [null, 9, null, 8] 解释： NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1,2,5] numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
提示：
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.lengthupdate 和 sumRange 方法次数不大于 3 * 104 树状数组套模板
class NumArray {
private FenwickTree fenwickTree;
public NumArray(int[] nums) {
fenwickTree = new FenwickTree(nums.length);
for (int i = 0; i < nums.length; i++) {
fenwickTree.add(i+1,nums[i]);
}
}
public void update(int index, int val) {
fenwickTree.add(index+1,val - fenwickTree.queryIndex(index+1));
}
public int sumRange(int left, int right) {
return fenwickTree.rangeSum(left,right+1);
}
class FenwickTree{
int[] arr;
public FenwickTree(int n){
arr = new int[n+1];
}
public int lowBit(int x){
return x & (- x);
}
public void add(int idx, int num){
while (idx < arr.length){
arr[idx] += num;
idx += lowBit(idx);
}
}
public int querySum(int idx){
int res = 0;
while (idx > 0){
res += arr[idx];
idx -= lowBit(idx);
}
return res;
}
public int queryIndex(int idx){
return querySum(idx) - querySum(idx-1);
}
public int rangeSum(int left, int right){
if (left > right){
int tmp = right;
right = left;
left = tmp;
}
return querySum(right) - querySum(left);
}
}
}Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000word 和 prefix 仅由小写英文字母组成insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次字典树基本模板操作
class Trie {
Node root = new Node();
public Trie() {
}
public void insert(String word) {
int idx = -1;
Node cur = root;
while (++idx < word.length()){
if (cur.children[word.charAt(idx)-'a'] == null){
cur.children[word.charAt(idx)-'a'] = new Node();
}
cur = cur.children[word.charAt(idx)-'a'];
}
cur.flag = true;
}
public boolean search(String word) {
int idx = -1;
Node cur = root;
while (++idx < word.length()){
if (cur.children[word.charAt(idx)-'a'] != null){
cur = cur.children[word.charAt(idx)-'a'];
}else{
return false;
}
}
return cur.flag;
}
public boolean startsWith(String prefix) {
int idx = -1;
Node cur = root;
while (++idx < prefix.length()){
if (cur.children[prefix.charAt(idx)-'a'] != null){
cur = cur.children[prefix.charAt(idx)-'a'];
}else{
return false;
}
}
return true;
}
class Node{
boolean flag = false;
Node[] children = new Node[26];
public Node(){}
}
}给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。
机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。
如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。
请你实现 Robot 类：
Robot(int width, int height) 初始化一个 width x height 的网格图，机器人初始在 (0, 0) ，方向朝 "East" 。void move(int num) 给机器人下达前进 num 步的指令。int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [x, y] 表示。String getDir() 返回当前机器人的朝向，为 "North" ，"East" ，"South" 或者 "West" 。
示例 1：
输入：
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]
解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.move(2); // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.move(2); // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.move(2); // 朝东移动 1 步到达 (5, 0) ，并朝东。
// 下一步继续往东移动将出界，所以逆时针转变方向朝北。
// 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.move(1); // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.move(4); // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
// 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"
提示：
2 <= width, height <= 1001 <= num <= 105move ，getPos 和 getDir 总共 调用次数不超过 104 次。JAVA模拟
模拟得有点费劲
move()方法的时候并不去实际模拟走动，而是增加步数并取模getPos()和getDir()的时候才去模拟走动direction定义为SOUTH，后面取模为0的话不用另算SOUTH初始查询方向的时候就不对了，所以再加一个moved判断，只要执行过move()就返回真实的direction，没执行过moved的话，就返回向东可能还是数学计算的方法简单点吧，
class Robot {
int[][] matrix;
private static String NORTH = "North";
private static String EAST = "East";
private static String SOUTH = "South";
private static String WEST = "West";
private int[] position;
private static String[] dirArr;
{
dirArr = new String[]{ EAST, NORTH, WEST, SOUTH };
}
private int direction = 3;
private int perimeter = 0;
private int count = 0;
boolean moved = false;
public Robot(int width, int height) {
matrix = new int[width][height];
position = new int[2];
perimeter = (width * 2 + height * 2) - 4;
}
public void move(int num) {
count += num;
count %= perimeter;
moved = true;
}
/**
*
* 西 ↑
* 南 北
* ← →
* 东 ↓
*
*/
private void goNext(){
int[] next;
switch (direction){
case 0:
next = new int[]{position[0]+1,position[1]};
break;
case 1:
next = new int[]{position[0],position[1]+1};
break;
case 2:
next = new int[]{position[0]-1,position[1]};
break;
case 3:
next = new int[]{position[0],position[1]-1};
break;
default:
return;
}
if (next[0] >= matrix.length || next[1] >= matrix[0].length || next[0]<0 ||next[1] <0){
direction = (direction+1)%4;
goNext();
return ;
}
position = next;
}
private void __move(){
while (count>0){
goNext();
count--;
}
}
public int[] getPos() {
__move();
return position;
}
public String getDir() {
__move();
return moved?dirArr[direction]:dirArr[0];
}
}请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]
示例 2：
输入: ["MaxQueue","pop_front","max_value"] [[],[],[]] 输出: [null,-1,-1]
限制：
1 <= push_back,pop_front,max_value的总操作数 <= 100001 <= value <= 10^5双队列空间换时间
Queue<Integer> queueDeque<Integer> deque ,从队尾插入的时候时候需要从队列尾部往前删除比自己小的值，直到遇到一个大于等于当前需要插入的值的时候停止deque从队头读取的时候，能保证，对头元素是当前所有插入的值中的最大值queue中删除头部的元素的时候，对比下deque中队首的元素是否是当前被从queue中删除的那个，如果是的话，则同时删除双端队列deque的队首元素deque删除队首元素的时候，下一个小于等于当前删除的队首元素的，且位置是位于当前queue队首那个元素到结尾这个区间内的最大元素，那么符合题意的设计就完成了class MaxQueue {
Queue<Integer> queue;
Deque<Integer> deque;
public MaxQueue() {
queue = new ArrayDeque<>();
deque = new ArrayDeque<>();
}
public int max_value() {
if (queue.isEmpty()){
return -1;
}
return deque.peekFirst();
}
public void push_back(int value) {
queue.add(value);
while (!deque.isEmpty() && deque.peekLast() < value){
deque.pollLast();
}
deque.offer(value);
}
public int pop_front() {
if (queue.isEmpty()){
return -1;
}
if (queue.peek().equals(deque.peekFirst())){
deque.pollFirst();
}
return queue.poll();
}
}请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]
注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
Java层序遍历【联动 1028. 从先序遍历还原二叉树】
就我们在力扣上做二叉树相关的题目的时候，例子说明中常用到的[1,2,3,null,null,4,5]这种写法，
两边方括号可以直接省略，
序列化
Queue反序列化
Queue保存上一层的节点内容Queue中需要拼接上去的上层节点的时候需要先从Queue中找到最先的那个不是空节点的节点中序遍历+前序遍历 或者中序遍历+后序遍历这样的处理办法，但是序列化获得的字符串相应的应该会变大public class Codec {
private String NULL = "N";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null){
return "";
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
StringBuffer sb = new StringBuffer();
while (!queue.isEmpty()){
TreeNode node = queue.poll();
sb.append(node == null?NULL:node.val).append(",");
if (node != null){
queue.offer(node.left);
}
if (node != null){
queue.offer(node.right);
}
}
sb.delete(sb.length()-1,sb.length());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length()==0){
return null;
}
String[] arr = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int idx = 0;
while (++idx < arr.length){
while (!queue.isEmpty() && queue.peek()==null){
queue.poll();
}
TreeNode curr = queue.poll();
TreeNode left = arr[idx].equals(NULL)?null:new TreeNode(Integer.parseInt(arr[idx]));
queue.offer(left);
curr.left = left;
if (idx+1 < arr.length){
idx++;
TreeNode right = arr[idx].equals(NULL)?null:new TreeNode(Integer.parseInt(arr[idx]));
curr.right = right;
queue.offer(right);
}
}
return root;
}
}如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
示例 1：
输入： ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]] 输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入： ["MedianFinder","addNum","findMedian","addNum","findMedian"] [[],[2],[],[3],[]] 输出：[null,null,2.00000,null,2.50000]
限制：
addNum、findMedian 进行 50000 次调用。注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/
【双薯片桶算法】又见薯片桶
本来其实看到困难题有点多想，不过回想了下之前做的这题，我的题解剑指 Offer 09. 用两个栈实现队列（简单） ， 再想想这题，好像….也没那么复杂了
借一次之前的图
我们需要的其实是一个队列。但是和之前不同的是这次是有序的，我们要从这个有序队列中取中间那个值。
这样，我们把原来的两个栈换成两个堆，一个大顶堆，一个小顶堆，那么对应这上面这个图
class MedianFinder {
PriorityQueue<Integer> left;
PriorityQueue<Integer> right;
/** initialize your data structure here. */
public MedianFinder() {
left = new PriorityQueue<>((a,b)-> b-a);
right = new PriorityQueue<>();
}
public void addNum(int num) {
if (left.size()==0||num<=left.peek()){
left.offer(num);
}else{
right.offer(num);
}
if (left.size() - right.size()>1){
right.offer(left.poll());
}else if (right.size() > left.size()){
left.offer(right.poll());
}
}
public double findMedian() {
if (left.size() == right.size()){
return ((double) (left.peek() + right.peek()))/2;
}else{
return (double)left.peek();
}
}
}