强烈推荐
变态跳台阶

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)
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
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");
}
}
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
程序员的“二”人世界
世界上每一个程序员都是一个标准二货,彻彻底底完完全全的二货,二的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
找不到对象毫不诡异
茶不思饭不想视死如归
寂寞的时候干什么?
写程序写程序
失恋的时候干什么?
写程序写程序写程序
发骚的时候干什么?
写程序写程序
剩下的时候干什么?
调程序调程序调程序
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
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)区间内的数字 —— 或者是地球文,或者是火星文。
输出格式:
对应输入的每一行,在一行中输出翻译后的另一种语言的数字。
输入样例:
4
29
5
elo nov
tam
输出样例:
hel mar
may
115
13
包含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)
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
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