小景哥哥

世界很大,而我们还需要再成长!

强烈推荐

变态跳台阶

    9.变态跳台阶

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

    解题思路:

    关于本题,前提是n个台阶会有一次n阶的跳法。分析如下:

            f(1) = 1

            f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。

            f(3) = f(3-1) + f(3-2) + f(3-3) 

            ...

            f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 

            说明: 

            1)这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。

            2)n = 1时,只有1种跳法,f(1) = 1

            3) n = 2时,会有两个跳得方式,一次1阶或者2阶,这回归到了问题(1) ,f(2) = f(2-1) + f(2-2) 

            4) n = 3时,会有三种跳得方式,1阶、2阶、3阶,

                那么就是第一次跳出1阶后面剩下:f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3)

                因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

            5) n = n时,会有n中跳的方式,1阶、2阶...n阶,得出结论:

                f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)  

            6) 由以上已经是一种结论,但是为了简单,我们可以继续简化:

                f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

                f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

                可以得出:

                f(n) = 2*f(n-1)

            7) 得出最终结论,在n阶台阶,一次有1、2、...n阶的跳的方式时,总得跳法为:

                       | 1       ,(n=0 ) 

            f(n) =  | 1       ,(n=1 )

                       | 2*f(n-1),(n>=2)

    //java代码实现
      public class Solution {

      public int JumpFloorII(int target) {
            if (target <= 0) {
                return -1;
            } else if (target == 1) {
                return 1;
            } else {
                return 2 * JumpFloorII(target - 1);
            }
        }

        //Another solution
        public int JumpFloorII2(int target){
            int a=1; 
            return a<<(target-1);
        }
    }

    阅读全文>>

作者:Jason分类:【offer浏览(310评论(0

2018-08-10

1017. A除以B (20)-PAT乙级真题-PAT乙级真题-浙大PAT乙级真题java实现

    1017. A除以B (20) 
    本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R, 
    使得A = B * Q + R成立。 
    输入格式: 
    输入在1行中依次给出A和B,中间以1空格分隔。 
    输出格式: 
    在1行中依次输出Q和R,中间以1空格分隔。 
    输入样例: 
    123456789050987654321 7 
    输出样例: 
    17636684150141093474 3


    阅读全文>>

作者:Jason分类:【pat浏览(344评论(0

2018-01-11

1067. 试密码(20)–PAT乙级真题java实现

    1067. 试密码(20)–PAT乙级真题java实现
     
    当你试图登录某个系统却忘了密码时,系统一般只会允许你尝试有限多次,当超出允许次数时,账号就会被锁死。本题就请你实现这个小功能。 
    输入格式: 
    输入在第一行给出一个密码(长度不超过20的、不包含空格、Tab、回车的非空字符串)和一个正整数N(<= 10),分别是正确的密码和系统允许尝试的次数。随后每行给出一个以回车结束的非空字符串,是用户尝试输入的密码。输入保证至少有一次尝试。当读到一行只有单个#字符时,输入结束,并且这一行不是用户的输入。 
    输出格式: 
    对用户的每个输入,如果是正确的密码且尝试次数不超过N,则在一行中输出“Welcome in”,并结束程序;如果是错误的,则在一行中按格式输出“Wrong password: 用户输入的错误密码”;当错误尝试达到N次时,再输出一行“Account locked”,并结束程序。 
    输入样例1: 
    Correct%pw 3 
    correct%pw 
    Correct@PW 
    whatisthepassword! 
    Correct%pw 

    输出样例1: 
    Wrong password: correct%pw 
    Wrong password: Correct@PW 
    Wrong password: whatisthepassword! 
    Account locked 
    输入样例2: 
    cool@gplt 3 
    coolman@gplt 
    coollady@gplt 
    cool@gplt 
    try again 

    输出样例2: 
    Wrong password: coolman@gplt 
    Wrong password: coollady@gplt 
    Welcome in

    分析: 
    1.如果已经是”#”了就不要继续下面的判断了,不然可能输出Wrong password: “#” 
    2.如果密码错误并且达到了尝试的次数,是先输出Wrong password那句紧接着输出Account locked那句 
    3.Wrong password: 后面有个空格。
     
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    public class Main {
        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] s = br.readLine().split(" ");
            String pwd = s[0];
            int times = Integer.parseInt(s[1]);
            while(times > 0) {
                String pass = br.readLine();
                if(pass.equals(pwd)) {
                    System.out.println("Welcome in");
                    break;
                }else if(pass.equals("#")) {
                    break;
                }else {
                    System.out.println("Wrong password: " + pass);
                    times--;
                }
            }
            if(times <= 0)
                System.out.println("Account locked");
        }
    }
    阅读全文>>

作者:小景哥哥分类:【pat浏览(390评论(0

2018-09-09

1038. 统计同成绩学生(20)-浙大PAT乙级真题java实现

    1038. 统计同成绩学生(20) 
    本题要求读入N名学生的成绩,将获得某一给定分数的学生人数输出。 
    输入格式: 
    输入在第1行给出不超过 10^5 的正整数N,即学生总人数。随后1行给出N名学生的百分制整数成绩,中间以空格分隔。最后1行给出要查询的分数个数K(不超过N的正整数),随后是K个分数,中间以空格分隔。 
    输出格式: 
    在一行中按查询顺序给出得分等于指定分数的学生人数,中间以空格分隔,但行末不得有多余空格。 
    输入样例: 
    10 
    60 75 90 55 75 99 82 90 75 50 
    3 75 90 88 
    输出样例: 
    3 2 0


    阅读全文>>

作者:Jason分类:【pat浏览(341评论(0

2018-01-23

程序员的“二”人世界

    世界上每一个程序员都是一个标准二货,彻彻底底完完全全的二货,二的63次方减一,这可是世界上最大的整数了(由此暴露了一个Java程序员的身份),再大就要溢出,它全是由2组成的。计算机是二进制的,计算机是程序员的梦中情人,由此而来程序员的世界就是一个2和情人的世界,从而组成了完美的“二”人世界。

    程序员的脑子都是二进制的,他们数数就是2,4,8,16,32,64,128,256,512,1024,…,就像你张口就来的0,1,2,3,4,5,6,7,8,9,10,他们对1024极其敏感,就像你每次买东西都想凑个整数,不管是10还是100. 有一次,一个哥们借我1000块钱,好像过了很久打算还我,但是觉得时间那么长了,有点不好意思,于是就说,给你凑个整给你1024好了,也不差那点钱。

    程序员有种职业病,就是看到啥缩写字母都会想到编程语言里的简写。有一次,我们大家在一起讨论一个热播美剧《破产姐妹》,因为剧情尺度确实有点大,而且还需要了解很深的美国文化才能get到他们的笑点,当有人谈论到Max整天挂在嘴边的hang、ball、gc的时候,旁边一哥们不假思索地就问他们也那么积极的垃圾回收么?看来美国文明程度确实很高啊。啥?啥垃圾回收?Garbage Collection啊,一看你就Java基础没学好,回去赶紧恶补Java虚拟机啊。

    在程序员眼里,世界上最高尚的职业就是人民教师,从古自今教师都是被世人尊敬的群体,为人师表的教师之所以那么伟大,不就是因为他们每年都有一个属于自己的节----教师节么,其他任何职业都没有这种优厚的待遇吧。但是只有一个例外,10.24是我们程序员的节日(此处应该有2的63次方减一个赞),哈哈哈,大笑三声,独属、专属、唯一的一个属于这个特定职业的节日,虽然没法和过节假日的老师们相提并论,但是程序员们已经相当满足、相当满意。

    程序员们都有强迫症----灭bug大神。不管是遇到404,还是500,还是303,他们一句fuck之后就开始蛮干,直到修复为止,从不放弃。当他们看到你电脑还在用着过时的win7、win8的时候,总是情不自禁的想帮你换成win10,他们总想给你插内存条、电脑清灰、换SSD。不是说他们有多热情,而是…因为职业病。他们的电脑手机iPad每个都是最新款最高配,每个软件都是最新版,还会强迫你去更新最新软件,强迫你去更新最新系统。所以不要在程序员面前显摆你的电子设备有多牛逼,他们都不屑去看你那些过时的电子古董。

    程序员们都有一个梦中情人,那就是华丽炫酷顶配的电脑。CPU肯定是八代intel i7 8700k标配(脑残发烧友上i9),搭载英伟达显卡1080Ti或Titan,主板不用玩家国度ROG就觉得对不起自己小小的内心,内存条上美商海盗船或耀眼的芝奇3200Hz,而且一上来就32G或64G,360分体式水冷,纯透明钢化玻璃机箱配备炫酷灯,4K超清曲面显示屏,炫酷的一逼,不管是玩游戏吃鸡还是撸代码,这都是刚需。他们看高配电脑的眼神,就像你们看到美女一样,远远的凝视不愿离去。

           咳,咳,程序员都很自恋,请为IT小哥哥们打call!

           一人我编程累

    碎过了节操心沉醉

    两眼是Code相随

    不求他日能早归

    鼠标我轻点屏

    键盘我手速行

    痴情代码

    心甘情愿

    千里把那个bug寻

    说项目呵呵笑

    PM主意太奇妙

    我轻狂那太高傲

    我懵懂的无知太年少

    赶进度,没班下

    上线了产品还牵挂

    千古的留名传佳话

    我三年架构已白发

    天天加班何人陪

    谁是谁非谁相随

    全栈通吃为了谁

    我能写几回,测几回

    败硬件,斗时间

    提高了并发已成仙

    豪情万丈天地间

    我续写了另类码农篇

    红尘事我已斩断

    久居帝都人心乱

    当年房价没上万

    我 为这了没买留遗憾

    创业我愁断肠

    眼中我泪两行

    多年为君早日上市

    一朝敲钟把名扬

     

    爱情是什么鬼

    谁信谁就脑进水

    谁错谁对谁是谁非

    深夜我把代码怼

    性能我心头事

    此生我怀大志

    为了老板回眸一笑

    我立下这毒誓

    VR我常相伴

    AI我深度上

    回眸沧海

    一曲忧伤

    感触盒饭香

    项目实施人在外

    我归来之日谁还在

    兄弟写码论豪迈

    我驰骋职场求一败

    程序员我们都是傻逼

    编程语言改变了哥的口味

    C++,JAVA,PHP

    许多年前还要学VB

    找不到对象毫不诡异

    茶不思饭不想视死如归

    寂寞的时候干什么?

    写程序写程序

    失恋的时候干什么?

    写程序写程序写程序

    发骚的时候干什么?

    写程序写程序

    剩下的时候干什么?

    调程序调程序调程序

     

    阅读全文>>

作者:Jason分类:【纪念浏览(734评论(0

2018-04-12

1042. 字符统计(20)-浙大PAT乙级真题java实现

    1042. 字符统计(20) 
    请编写程序,找出一段给定文字中出现最频繁的那个英文字母。 
    输入格式: 
    输入在一行中给出一个长度不超过1000的字符串。字符串由ASCII码表中任意可见字符及空格组成,至少包含1个英文字母,以回车结束(回车不算在内)。 
    输出格式: 
    在一行中输出出现频率最高的那个英文字母及其出现次数,其间以空格分隔。如果有并列,则输出按字母序最小的那个字母。统计时不区分大小写,输出小写字母。 
    输入样例: 
    This is a simple TEST. There ARE numbers and other symbols 1&2&3……….. 
    输出样例: 
    e 7


    阅读全文>>

作者:Jason分类:【pat浏览(340评论(0

2018-01-23

1044. 火星数字(20)-浙大PAT乙级真题java实现

    1044. 火星数字(20) 
    火星人是以13进制计数的:地球人的0被火星人称为tret。地球人数字1到12的火星文分别为:jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。火星人将进位以后的12个高位数字分别称为:tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。例如地球人的数字“29”翻译成火星文就是“hel mar”;而火星文“elo nov”对应地球数字“115”。为了方便交流,请你编写程序实现地球和火星数字之间的互译。 
    输入格式: 
    输入第一行给出一个正整数N(<100),随后N行,每行给出一个[0, 169)区间内的数字 —— 或者是地球文,或者是火星文。 
    输出格式: 
    对应输入的每一行,在一行中输出翻译后的另一种语言的数字。 
    输入样例: 

    29 

    elo nov 
    tam 
    输出样例: 
    hel mar 
    may 
    115 
    13


    阅读全文>>

作者:Jason分类:【pat浏览(395评论(0

2018-01-24

包含min函数的栈

    20.包含min函数的栈

    题目描述:

    定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

    解题思路:利用一个辅助栈,来存放最小元素的值。当弹栈弹出最小元素时,辅助栈也弹出栈顶元素(当前栈中最小元素值)


    import java.util.Stack;


    public class Solution {
        
        private Stack<Integer> dataStack = new Stack<Integer>();
        private Stack<Integer> minStack = new Stack<Integer>();
        
        public void push(int node) {
            dataStack.push(node);
            if(minStack.isEmpty() || node <= minStack.peek())
                minStack.push(node);
        }
        
        public void pop() {
            if(dataStack.peek() == minStack.peek())
                minStack.pop();
            dataStack.pop();
            
        }
        
        public int top() {
            return dataStack.peek();
        }
        
        public int min() {
            return minStack.peek();
        }
    }

    阅读全文>>

作者:Jason分类:【offer浏览(282评论(0

2018-08-13

1013. 数素数 (20)-PAT乙级真题-浙大PAT乙级真题java实现

    1013. 数素数 (20) 
    令Pi表示第i个素数。现任给两个正整数M <= N <= 10^4,请输出PM到PN的所有素数。 
    输入格式: 
    输入在一行中给出M和N,其间以空格分隔。 
    输出格式: 
    输出从PM到PN的所有素数,每10个数字占1行,其间以空格分隔,但行末不得有多余空格。 
    输入样例: 
    5 27 
    输出样例: 
    11 13 17 19 23 29 31 37 41 43 
    47 53 59 61 67 71 73 79 83 89 
    97 101 103


    阅读全文>>

作者:Jason分类:【pat浏览(360评论(0

2018-01-06

1035. 插入与归并(25)-浙大PAT乙级真题java实现

     

    1035. 插入与归并(25) 
    根据维基百科的定义: 
    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。 
    归并排序进行如下迭代操作:首先将原始序列看成N个只包含1个元素的有序子序列,然后每次迭代归并两个相邻的有序子序列,直到最后只剩下1个有序的序列。 
    现给定原始序列和由某排序算法产生的中间序列,请你判断该算法究竟是哪种排序算法? 
    输入格式: 
    输入在第一行给出正整数N (<=100);随后一行给出原始序列的N个整数;最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。 
    输出格式: 
    首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序;然后在第2行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔,且行末不得有多余空格。 
    输入样例1: 
    10 
    3 1 2 8 7 5 9 4 6 0 
    1 2 3 7 8 5 9 4 6 0 
    输出样例1: 
    Insertion Sort 
    1 2 3 5 7 8 9 4 6 0 
    输入样例2: 
    10 
    3 1 2 8 7 5 9 4 0 6 
    1 3 2 8 5 7 4 9 0 6 
    输出样例2: 
    Merge Sort 
    1 2 3 8 4 5 7 9 0 6


    阅读全文>>

作者:Jason分类:【pat浏览(387评论(0

2018-01-23