网站定制开发,wordpress data,云seo关键词排名优化软件,软件开发公司规章制度蓝桥杯刷题——day2 题目一题干题目解析代码 题目二题干解题思路代码 题目一
题干
三步问题。有个小孩正在上楼梯#xff0c;楼梯有n阶台阶#xff0c;小孩一次可以上1阶、2阶或3阶。实现一种方法#xff0c;计算小孩有多少种上楼梯的方式。结果可能很大#xff0c;你需要… 蓝桥杯刷题——day2 题目一题干题目解析代码 题目二题干解题思路代码 题目一
题干
三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。 题目链接三步问题 示例1: 输入n 3 输出4 说明: 有四种走法 示例2: 输入n 5 输出13 题目解析
这条题目老生常谈了其实就是青蛙跳台的问题只不过从青蛙只能跳1格或者2格改成了可以跳1格或者2格或者3格而已青蛙跳台的问题可以看我的这个博客青蛙跳台。因此思想仍然是不变的也就是说可以用动态规划解决这个问题同样的初始情况是 f(1) 1 f(2) 2 f(3) 4 f(n) f(n-1)f(n-2) f(n-3) 下面是完整代码
代码
class Solution {//f(1) 1//f(2) 2//f(3) 4//f(n) f(n-1) f(n-2) f(n-3)public int waysToStep(int n) {ArrayListInteger list new ArrayList();if(n 1){return 1;}if(n 2){return 2;}if(n 3){return 4;}list.add(1);list.add(2);list.add(4);for(int i 3; i n;i){list.add(((list.get(i-1) list.get(i-2)) % 1000000007 list.get(i - 3)) % 1000000007) ;}return list.get(n-1);}
}有的同学要问了怎么感觉不对劲呀这个1000000007是个什么玩意这个当然是题目的要求因为我们在计算到后面的时候数字会越来越大因此很可能超出int的范围因此我们需要对结果进行取余而题目的要求是对1000000007取余那么满足他题目的要求就可以了还有一个问题(list.get(i-1) list.get(i-2)) % 1000000007这个是为什么当然是因为list.get(i-1)和list.get(i-2)单独的值都是在int范围内的但是两者相加就不一定了因此我们要对他俩和的结果进行取余。
题目二
题干
给你一个字符串 s找到 s 中最长的回文子串。 题目链接最长回文子串 示例一 输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。 示例二 输入s “cbbd” 输出“bb” 解题思路
这道题看起来无从下手其实并不难我们可以利用滑动窗口来解决什么意思例如求解s “babad”的最长回文子串我们画个图来理解一下 我们设置一个滑动窗口的长度为5那么我们在定义两个指针x和y两个指针同时向中间移动直到指针相遇如果都满足两指针指向的字符一样那么则证明长度为5就是最长回文子串如果指针在相遇之前不满足两指针指向的字符一样那么我们滑动窗口长度减去1变为4也就是一下两种情况 以此类推如此一来滑动窗口逐步减少总能够找到符合条件的最长回文子串。下面是完整代码
代码
import java.util.*;
class Solution {public boolean Palindrome(char[] array, int x,int y){while(x y){if(array[x] array[y]){x;y--;}else {break;}}if(x y){return true;}else {return false;}}public String longestPalindrome(String s) {ArrayListString list new ArrayList();char[] array s.toCharArray();int size array.length;int i 0;for(i size;i 0; i--){for(int j 0; j size - i 1 ;j){if(Palindrome(array,j, i -1 j)){char[] subArray Arrays.copyOfRange(array, j, i j);String result new String(subArray);list.add(result);break;}}}return list.get(0);}
}当然我这个方法肯定不是最优解肯定有各位方便巧妙的方法如果各位有什么想法或者建议欢迎私信评论感谢大家的点赞和收藏
