蓝桥杯刷题——day1
- 题目一
- 题干
- 题目解析
- 代码
- 题目二
- 题干
- 题目解析
- 代码
题目一
题干
给定一个字符串 s ,验证 s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。本题中,将空字符串定义为有效的 回文串 。
题目链接:验证回文串
示例 1:
输入: s = “A man, a plan, a canal: Panama”
输出: true
解释:“amanaplanacanalpanama” 是回文串
示例 2:
输入: s = “race a car”
输出: false
解释:“raceacar” 不是回文串
题目解析
这条题目是一个基础题,我们可以设置两个指针,left和right,分别指向字符串的起点和终点,两指针同时向中间运动,如果left指向的不是字符或者数字,那么left++,如果right指向的不是字符或者数字,那么right–,如果两者指向的是字符或者数字那么进一步判断,如果两者指向的字符相同,那么left++,并且right–;如果指向的不同,但是只是大小写的区别,那么left++,并且right–;否则的话跳出循环,这条题目并没有什么难度,其实考察的只是循环的嵌套,下面是完整代码:
代码
java">class Solution {public boolean isPalindrome(String s) {char[] array = s.toCharArray();int left = 0;int right = array.length - 1;while(left < right){if(((array[left] <= 57 && array[left] >= 48) || (array[left] >= 65 && array[left] <= 90) || (array[left] <= 122 && array[left] >= 97))&& ((array[right] <= 57 && array[right] >= 48) ||(array[right] >= 65 && array[right] <= 90) || (array[right] <= 122 && array[right] >= 97))){if(array[left] == array[right]){right--;left++;}else {if(array[left] > 57 && array[right] >57 && Math.abs(array[left] - array[right]) == 32){right--;left++;}else {break;}}}else if((array[left] <= 57 && array[left] >= 48) || (array[left] >= 65 && array[left] <= 90) || (array[left] <= 122 && array[left] >= 97)){right--;}else if((array[right] <= 57 && array[right] >= 48) ||(array[right] >= 65 && array[right] <= 90) || (array[right] <= 122 && array[right] >= 97)){left++;}else {right--;left++;}}if(left < right){return false;}else {return true;}}
}
这里要说一下,这条题目还考察了Ascii码表,其他的可以不用记忆,但是这三个关键的是最好要记下来的:
字符 | Ascii值 |
---|---|
0 | 48 |
A | 65 |
a | 97 |
下面附上一张完整的Ascii表:
题目二
题干
给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。如图所示:
题目链接:杨辉三角
示例一:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例二:
输入: numRows = 1
输出: [[1]]
题目解析
这条题目相对难一点,但是理解其中的计算过程也就不那么难了,首先我们可以看到,每行的第一个数和最后一个数都是1,因此我们在考虑每行计算的时候先把这个考虑进去,其次除了每行的第一个数字和最后一个数字,中间的数字都满足以下的计算方式(i表示第i行,j表示第j个数):
f(i,j)=f(i-1,j-1) + f(i-1,j)
例如f(5,2)(第5行,第2个数)为4,他就是由f(4,1)+f(4,2)得到的,因此我们就完成了杨辉三角的代码了,下面是完整的代码:
代码
java">import java.util.*;
class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> lists = new ArrayList<>();for(int i = 1;i <= numRows;i++){List<Integer> list = new ArrayList<>();for(int j = 1;j <= i;j++){ //4,2 3,1 + 3,2if(j == 1 || j == i){list.add(1);}else {List<Integer> tmplist = lists.get(i-2);int first = tmplist.get(j-2);int second = tmplist.get(j-1);list.add(first+second);}}lists.add(list);}return lists;}
}
有细心的同学发现,我的计算方法好像是f(i-2,j-2) + f(i-2,j-1),这是因为我的i和j是从1开始的,而lists和list都是数组,他们使用get方法拿数据,下标都是从0开始的,因此我需要对应的多减去一个1。好了,今天的蓝桥刷题就到这里,如果对你有所帮助,别忘了点赞和收藏,谢谢各位!当然有问题也欢迎各位评论或者私信!