剑指Offer：序列化二叉树
题目请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
思路 + 代码递归序列化与递归反序列化。
123456789101112131415161718192021222324252627282930313233343536373839/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solutio ...
剑指Offer：按之字形顺序打印二叉树
题目请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路 + 代码其实就是二叉树层次遍历的变体。
遍历过程中，如果是二叉树的偶数层，就顺序遍历；否则逆序遍历。
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<ArrayList&l ...
剑指Offer：二叉树的下一个结点
题目给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路 + 代码树的问题最容易想到的就是递归方法。
中序遍历顺序是左叶子节点、根节点、右叶子节点。
分为两种情况：
如果右子节点不为空，则递归寻找后面最左叶子节点。
如果右子节点为空，则递归在父级节点寻找。
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) { th ...
剑指Offer：删除链表中重复的节点
题目在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表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) re ...
剑指Offer：字符流中第一个不重复的字符
题目请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”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.add( ...
剑指Offer：表示数值的字符串
题目请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+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+)?"); ...
剑指Offer：正则表达式匹配
题目请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含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)
...
剑指Offer：扑克牌顺子
题目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 Solut ...
剑指Offer：翻转单词顺序列
题目牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
思路 + 代码先翻转每个单词，再重头到尾进行翻转。
1234567891011121314151617181920212223242526272829public class Solution { public String ReverseSentence(String str) { if(str==null || str.length()==0) return str; char[] chs = str.toCharArray(); int len = chs.length; int i=0, j=0; ...
剑指Offer：左旋字符串
题目汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
思路 + 代码先将 “abc” 和 “XYZdef” 分别翻转，得到 “cbafedZYX”，然后再把整个字符串翻转得到 “XYZdefabc”。
123456789101112131415161718192021222324public class Solution { public String LeftRotateString(String str,int n) { if(str==null || str.length()==0) return str; char[] chs = str.toCharArray(); int len = chs.length-1; inverse(chs ...
