剑指offer刷题记录

  1. 之字形遍历二叉树
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>>对象。

这道题其实困扰蛮久,其实比较根源的原因,来自于对于正常的层次遍历理解不够透彻。还一直停留在对队列中的元素遍历一个入队两个的这种方式中,其实遍历当前层次和入队下一层次并不需要间隔操作,间隔操作会导致队列中同时夹杂着两个不同层次的元素。实际上遍历和入队操作完全可以分开,先遍历当前层次的元素,然后再入队下一层次的元素。这样整个队列的内容会一直保持一个比较干净的状态。从这点出发再去思考利用双向队列之字形遍历二叉树,就会比较容易理解。遍历的时候我们判断层次的奇偶性来选择正向还是反向遍历,然后正向入队下一层次的元素即可。所有的不同之处只是在于遍历的时候方向有所区别而已~

  1. 查找有序的二维数组
  1. 判断出栈顺序
    最简洁的做法,是直接借助一个栈,每次判断栈顶的元素是否和出栈序列的当前元素相同,相同则弹栈,并判断下一个,不同则继续压栈。当压栈的操作不合法的时候(下标超出范围),返回false。

  2. 字符流中第一个不重复的字符
    这题通过hashmap的方式可以比较方便地解决。
    需要注意的几点,HashMap是无序的,需要用到LinkedHashMap来存储键值对,另外,对LinkedHashMap的遍历要用到迭代器,建议深入了解一下HashMap、LinkedHashMap的存储方式,同时注意迭代器对象需要制定泛型Map.Entry<Character, Integer>

  3. 用两个栈实现一个队列
    两个栈栈底拼接就可以形成一个队列。
    用栈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中
  1. 反向输出一个单向链表到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等。

  1. 将字符串中的空格替换为%20
  • 使用String中的replace方法,一定需要注意的是,由于String本身的不可变性(参考jvm中String不可变性的介绍),它所开放出来的很多函数比如subString、replace都是通过返回一个新的String来实现的,因此使用的时候要注意接收返回值。

StringBuilder没有replace方法,但是具有reverse方法

  • 先正向遍历字符串,统计空格的个数,然后逆向进行替换操作。
    用java语言解决的话,其实可以直接申请一个新的数组,填写完内容之后,将新数组的String返回。

先统计数量,然后统一进行移动操作,这其实是一类问题的解决思路

  1. 寻找旋转数组的最小值
  • 直接通过遍历的方式来找最小值
  • 优化的遍历,寻找比前一个元素小的元素,就是最小值
  • 二分查找,在原数组不是严格递增的情况下,会出现一些问题
  1. 斐波那契数列
  • 递归方式
  • 迭代方式
  1. 变态青蛙跳台阶问题
    2^(n-1) 这里需要注意移位操作的使用和含义
public int JumpFloorII(int target) {
        return 1 << (target-1);
}

result << 2操作不会使result结果发生变化,就像result+2一样,需要通过result = result << 2才能改变result的值

  1. 扑克牌顺子
    大小王数字为0,可以当做任何一个数,现在抓了一把牌,想要判断是不是顺子
    方法:先排序,然后统计大小王的个数count,从第一个不是大小王的数字开始,计算它和下一个数的差值diff,如果diff为0,则直接返回false(两个数相等,不可能为顺子),否则每次更新count为count - (diff - 1),并判断更新后的count是否为小于零,是则返回false。
  2. 层次打印二叉树
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;
    }
    
}
  1. 判断链表的环路入口
    使用快慢指针的方式可以很方便地判断出来是否存在环路。
    在判断环路入口的情况下,可以通过数学证明的方式,证明一个等式。推导过程如下所示


    推导过程
  2. 判别镜像二叉树
    采用递归的思路,要判断一棵二叉树是不是镜像的,只需要判断两棵子树leftTree和rightTree是不是互为镜像的,判断两棵二叉树leftTree和rightTree是否互为镜像,只需要判断leftTree的左子树和rightTree的右子树是否互为镜像,leftTree的右子树和rightTree的左子树是否互为镜像。

  3. 复制随机链表

  • 简单的方式
    首先只根据next复制一个新的链表,然后同步地检索每一个节点的random指向的节点,再对新链表的对应节点random赋值
  • 先在每一个节点的后面插入一个该节点的复制节点,然后依次将每个节点的random值设置为之前节点的random的next值。最后通过修改next的方式拆分两个链表。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342

推荐阅读更多精彩内容

  • leetcode刷题记录本文记录一下leetcode刷题记录,记录一下自己的解法和心得。 LeetCode Bin...
    EarthChen阅读 691评论 0 1
  • leetcode刷题记录本文记录一下leetcode刷题记录,记录一下自己的解法和心得。 LeetCode Two...
    EarthChen阅读 3,434评论 0 6
  • 1.二维数组中查找2.替换空格3.从尾到头打印链表4.重建二叉树5.用两个栈实现队列6.旋转数组的最小数字7.斐波...
    icecrea阅读 324评论 0 1
  • 渐渐的,渐渐的 我知道我没有忘了它 但我已经不去想她 这已经变得不困难 我对她的爱好像是陈年往事 而我像是个记忆差...
    文森林木阅读 198评论 0 0
  • 表妹生下宝宝第二天还没奶水,我和其他关心表妹的人一样着急。突然想起生完小妞之后写过一篇日志,记录了好多下奶汤,赶紧...
    诗涵Ady阅读 310评论 0 0