- 之字形遍历二叉树
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
List<TreeNode> queue = new ArrayList<TreeNode>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (pRoot != null) {
queue.add(pRoot);
}
else {
return result;
}
int level = 0; //层次为0, 1, 2...
ArrayList<Integer> curLevel = null;
while (!queue.isEmpty()) {
curLevel = new ArrayList<Integer>();
// curLevel.clear();//错误
int size = queue.size();
if (level %2 == 0) { //偶数层从左至右遍历
for (int i = 0; i < size; i++) {
curLevel.add(queue.get(i).val);
}
}
else { //奇数层从右至左遍历
for (int i = size - 1; i >= 0; i--) {
curLevel.add(queue.get(i).val);
}
}
result.add(curLevel); //将该层的遍历结果添加到result中
for (int i = 0; i < size; i++) {
TreeNode node = queue.remove(0);
if (node != null) {
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}
level++;
}
return result;
}
对curLevel的处理
这里对于curLevel的处理要格外注意,如果采用
ArrayList<Integer> curLevel = new ArrayList<Integer>();
...
while(...) {
...
curLevel.clear();
}
的方式,最后得到的结果result里面会全部是重复的最后一个curLevel。因为在result.add(curLevel)的语句中,只是把curLevel的引用传递进去了,每次clear都实际上会把之前层次的遍历结果都重新清除掉。
关于返回空值
对pRoot的判空处理,不能再pRoot为空的时候返回null,而是>
应该返回一个内容为空的ArrayList<ArrayList<Integr>>对象。
这道题其实困扰蛮久,其实比较根源的原因,来自于对于正常的层次遍历理解不够透彻。还一直停留在对队列中的元素遍历一个入队两个的这种方式中,其实遍历当前层次和入队下一层次并不需要间隔操作,间隔操作会导致队列中同时夹杂着两个不同层次的元素。实际上遍历和入队操作完全可以分开,先遍历当前层次的元素,然后再入队下一层次的元素。这样整个队列的内容会一直保持一个比较干净的状态。从这点出发再去思考利用双向队列之字形遍历二叉树,就会比较容易理解。遍历的时候我们判断层次的奇偶性来选择正向还是反向遍历,然后正向入队下一层次的元素即可。所有的不同之处只是在于遍历的时候方向有所区别而已~
- 查找有序的二维数组
判断出栈顺序
最简洁的做法,是直接借助一个栈,每次判断栈顶的元素是否和出栈序列的当前元素相同,相同则弹栈,并判断下一个,不同则继续压栈。当压栈的操作不合法的时候(下标超出范围),返回false。字符流中第一个不重复的字符
这题通过hashmap的方式可以比较方便地解决。
需要注意的几点,HashMap是无序的,需要用到LinkedHashMap来存储键值对,另外,对LinkedHashMap的遍历要用到迭代器,建议深入了解一下HashMap、LinkedHashMap的存储方式,同时注意迭代器对象需要制定泛型Map.Entry<Character, Integer>用两个栈实现一个队列
两个栈栈底拼接就可以形成一个队列。
用栈A作为出队栈,栈B作为入队栈。
dequeue()操作:如果栈B不为空,直接B.pop(),如果为空,则将栈A全部pop()并push()到栈B中,然后B.pop()
enqueue()操作:直接A.push()
用两个队列实现一个栈
- push()操作:对队列A入队
- pop()操作:
如果队列A只有一个元素,则直接出队,
如果队列A元素个数n大于1,则将队列A的元素出队到队列B,直到A中只剩下一个元素,也就是栈顶(队尾)的元素,将这个元素出栈,然后将B中的元素全部入队到A中
- 反向输出一个单向链表到ArrayList中
- 借助栈来保存链表中的数据,然后从栈中把元素输出到ArrayList中
- 使用递归的方法来做
- 使用ArrayList的add(int index, Collection c)来做,头插法
这种方式比较简单,但效率会比较低 - 使用Collections.reverse(List<?> list)方法
先把链表元素输出到ArrayList中,然后reverse这个ArrayList
除了Collections的reverse方法,还有Arrays的sort方法。需要知道的是,List本身就是一个Collection,List和Set都是Collection的不同实现,Arrays和Collections封装了很多比较有用的静态方法,可以对数组和List进行操作,比如sort和reverse等。
- 将字符串中的空格替换为%20
- 使用String中的replace方法,一定需要注意的是,由于String本身的不可变性(参考jvm中String不可变性的介绍),它所开放出来的很多函数比如subString、replace都是通过返回一个新的String来实现的,因此使用的时候要注意接收返回值。
StringBuilder没有replace方法,但是具有reverse方法
- 先正向遍历字符串,统计空格的个数,然后逆向进行替换操作。
用java语言解决的话,其实可以直接申请一个新的数组,填写完内容之后,将新数组的String返回。
先统计数量,然后统一进行移动操作,这其实是一类问题的解决思路
- 寻找旋转数组的最小值
- 直接通过遍历的方式来找最小值
- 优化的遍历,寻找比前一个元素小的元素,就是最小值
- 二分查找,在原数组不是严格递增的情况下,会出现一些问题
- 斐波那契数列
- 递归方式
- 迭代方式
- 变态青蛙跳台阶问题
2^(n-1) 这里需要注意移位操作的使用和含义
public int JumpFloorII(int target) {
return 1 << (target-1);
}
result << 2操作不会使result结果发生变化,就像result+2一样,需要通过result = result << 2才能改变result的值
- 扑克牌顺子
大小王数字为0,可以当做任何一个数,现在抓了一把牌,想要判断是不是顺子
方法:先排序,然后统计大小王的个数count,从第一个不是大小王的数字开始,计算它和下一个数的差值diff,如果diff为0,则直接返回false(两个数相等,不可能为顺子),否则每次更新count为count - (diff - 1),并判断更新后的count是否为小于零,是则返回false。 - 层次打印二叉树
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
ArrayList<Integer> level = null;
if (pRoot == null)
return result;
list.add(pRoot);
while (!list.isEmpty()) {
level = new ArrayList<Integer>();
int size = list.size();
for (int i = 0; i < size; i++) {
level.add(list.get(i).val);
}
result.add(level);
for (int i = 0; i < size; i++) {
TreeNode node = list.get(0);//注意这里不能写成list.get(i)
if (node.left != null)
list.add(node.left);
if (node.right != null)
list.add(node.right);
list.remove(0);//注意这里不能写成list.remove(i);
}
}
return result;
}
}
-
判断链表的环路入口
使用快慢指针的方式可以很方便地判断出来是否存在环路。
在判断环路入口的情况下,可以通过数学证明的方式,证明一个等式。推导过程如下所示
判别镜像二叉树
采用递归的思路,要判断一棵二叉树是不是镜像的,只需要判断两棵子树leftTree和rightTree是不是互为镜像的,判断两棵二叉树leftTree和rightTree是否互为镜像,只需要判断leftTree的左子树和rightTree的右子树是否互为镜像,leftTree的右子树和rightTree的左子树是否互为镜像。复制随机链表
- 简单的方式
首先只根据next复制一个新的链表,然后同步地检索每一个节点的random指向的节点,再对新链表的对应节点random赋值 - 先在每一个节点的后面插入一个该节点的复制节点,然后依次将每个节点的random值设置为之前节点的random的next值。最后通过修改next的方式拆分两个链表。