孙云增的博客

题目如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 思路 + 代码参考CyC 12345678910111213141516171819202122232425import java.util.*;public class Solution { // left-最大堆 right-最小堆 private PriorityQueue<Integer> left = new PriorityQueue<Integer>((o1, o2)->o2-o1); private PriorityQueue<Integer> right = new PriorityQueue<Integer>(); private int N = 0; public void Ins...

题目给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。 思路 + 代码其实就是二叉搜索树的中序遍历翻版。 1234567891011121314151617181920212223242526272829303132333435/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { private int cnt; private TreeNode node; TreeNode KthNode(TreeNode pRoot, int k) { if(k<1) return null...

题目请实现两个函数，分别用来序列化和反序列化二叉树 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。 思路 + 代码递归序列化与递归反序列化。 123456789101112131415161718192021222324252627282930313233343536373839/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solu...

题目请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 思路 + 代码其实就是二叉树层次遍历的变体。 遍历过程中，如果是二叉树的偶数层，就顺序遍历；否则逆序遍历。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import java.util.ArrayList;/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/import java.util.*;public class Solution { public ArrayList<ArrayLis...

题目给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 思路 + 代码树的问题最容易想到的就是递归方法。 中序遍历顺序是左叶子节点、根节点、右叶子节点。 分为两种情况： 如果右子节点不为空，则递归寻找后面最左叶子节点。 如果右子节点为空，则递归在父级节点寻找。 2.1 如果父节点为空，则返回 null。 2.2 如果父节点左节点等于该节点，则返回父节点。 2.3 如果父节点右节点等于该节点，则继续递归寻找。 123456789101112131415161718192021222324252627282930313233343536373839/*public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { ...

题目在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 思路 + 代码利用递归求解，问题分解为去除下一个节点开始链表中重复的节点。 123456789101112131415161718192021222324252627/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/import java.util.*;public class Solution { public ListNode deleteDuplication(ListNode pHead) { if(pHead==null || pHead.next==null) ...

题目请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。 如果当前字符流没有存在出现一次的字符，返回#字符。 思路 + 代码利用队列进行结果的存储，利用一个数组进行出现次数的统计。 队列对于其中所有出现超过两次的字符进行出栈。 123456789101112131415161718import java.util.*;public class Solution { private char[] tmp = new char[256]; private Queue<Character> queue = new LinkedList<Character>(); //Insert one char from stringstream public void Insert(char ch) { tmp[ch]++; queue.a...

题目请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。 思路 + 代码方法1: 正则匹配123456789101112131415161718/*[] ： 字符集合() ： 分组? ： 重复 0 ~ 1 次+ ： 重复 1 ~ n 次* ： 重复 0 ~ n 次. ： 任意字符\\. ： 转义后的 .\\d ： 数字*/public class Solution { public boolean isNumeric(char[] str) { if(str == null || str.length == 0) return false; return new String(str).matches("[+-]?\\d*(\\.\\d+)?([Ee][+-]?\\d+)?"...

题目请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配。 思路 + 代码动态规划：利用一个dp(x, y)的数组表示原字符串 s[0, x) 与匹配字符串 p[0, y)是否匹配。 状态转移： 对于dp(x, y)： 如果 p(y) == ‘.’ || p(y) == s(x-1), dp(x, y)= dp(x-1, y-1)。 如果 p(y) == ‘*’ 2.1 如果 p(y-1) == s(x) || p(y-1) == ‘.’ 1) ‘‘ 复制多个：dp(x, y) = dp(x-1, y) 2) ‘‘ 复制一个：dp(x, y) = dp(x, j-1) 3) ‘*’ 复制零个：dp(x, y) = dp(x, j-2) 2.2 如果 s 为空且不满足 2.1，则 ‘*’ 复制零个：dp(x, y) = dp(x, j-2)...

题目LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。 思路 + 代码首先用一个长度为13的数组统计每个数字出现的次数。 然后满足以下条件为顺子： 除大小王外所有数字出现一次。 最大值与最小值差值小于等于4，例如存在 1 跟 6 无法形成顺子。 四个癞子稳赢。 12345678910111213141516171819202122232425public class So...