蓝桥杯刷题—

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