剑指offer(Java版)day02:用两个栈实现队列|旋转数组的最小数字|斐波那契数列|跳台阶|变态跳台阶|矩形覆盖

    1用两个栈实现队列

【题目】用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

【考察点】栈和队列

【思路】入队:将元素进栈A

出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;

如果不为空,栈B直接出栈。

【错误1】当栈为空时我return了null,但是pop方法的返回值类型是int,所以报错了。因此我改成了-1。

【错误2】最后return stack2.pop()应该写在pop方法内的最外层,不要写在else里面,因为不管有没有经过从stack1出栈到stack2入栈,最后都是要pop出stack2的栈顶元素。

【错误3】是while(!stack1.empty())而不是if(!stack1.empty()),手误写错了,while一直pop出stack1中的所有元素,而if值pop出stack1当前栈顶的一个元素。

【代码】

    2旋转数组的最小数字

【题目】把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

【考察点】查找和排序

【思路】好气气,看了半天还是不懂二分法的思路!呜呜呜。这个就是比较普通的解法,当某一个位置的元素比下一个位置的元素大时,由旋转的规律,说明下一个元素就是最小值。

【错误】记得有返回值的方法一定要return,且return不能放在while、if这种语句中,要在所有情况下都能return到。

【代码】

    3斐波那契数列

【题目】大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39

【考察点】递归和循环

【思路】用循环,没有用递归。分别用f1、f2、f3存储前两个位置的元素值和当前要计算的位置的元素值。当n为1和2时,return 1。从3到以后就通过循环来计算f3=f1+f2,f1和f2的值随着计算的推进也一直往后推进,循环结束return f3。

【错误】刚开始int f3的时候忘记给它初始化了,后面return的时候就报错了。

【代码】

    4跳台阶

【题目】一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

【考察点】递归和循环

【思路】我用的是递归,当前可以选择跳1步或者2步,跳一步之后的跳法就变成了f(n-1),跳两步的跳法就变成了f(n-2),当n为1的时候只有1种跳法,当n为2的时候有2中跳法,这两个值是我们的递归终止条件。不过这种做法耗时比较长~

【代码】

    5变态跳台阶

【题目】一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

【考察点】递归和循环

【思路】每个台阶都有跳与不跳两种情况(除了最后一个台阶),最后一个台阶必须跳。所以共有2^(n-1)种情况。1左移target-1位,也就是2的(target-1)次方。

【代码】

    6矩形覆盖

【题目】我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

【考察点】递归和循环

【思路】有以下几种情形:

1.target <= 0 大矩形为<= 2*0,直接return 0;

2.target = 1大矩形为2*1,只有一种摆放方法,return1;

3.target = 2 大矩形为2*2,有两种摆放方法,return2;

4.target = n 分为两步考虑:

        第一次摆放一块 2*1 的小矩阵,则摆放方法总共为f(target - 1)。

        第一次摆放一块1*2的小矩阵,则摆放方法总共为f(target-2)。

所以还是一个斐波那契数列。

【代码】

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

推荐阅读更多精彩内容