- 之字形遍历二叉树
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的方式拆分两个链表。
网友评论