蓝桥杯刷题——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) {ArrayList<Integer> 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) {ArrayList<String> 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);}
}

当然我这个方法肯定不是最优解，肯定有各位方便巧妙的方法，如果各位有什么想法或者建议欢迎私信＋评论，感谢大家的点赞和收藏！