【蓝桥杯备战】Day 1

1.基础题目

LCR 018.验证回文串

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串

提示：

• 1 <= s.length <= 2 * 105
• 字符串 s 由 ASCII 字符组成

分析：

        本题目主要考察回文串判断，所谓回文串：就是从右向左和从左向右遍历的字符完全相等

        对此，我采用双指针法，两个指针分别为 i 和 j ，从左右同时出发，i=0，j=s.length()-1；

        在这里还要进行的是有效字符判断，题目要求字母与数字为有效字符且不区分大小写，对于条件的判断为：

• 字母与数字为有效字符 Character.isLetterOrDigit()
• 全部字母转小写Character.toLowerCase()

        除此之外题目还要求空串也为回文串，在程序开始要加上判断条件

注意

• 判断字符串是否相等采用A.equals(B)
• 判断字符或者数字表达式是否相等采用==

        当字符串中遇到非有效数字，采用while循环直到找到有效字符，当左右都为有效字符才能进行比较

        这里要注意在内循环寻找有效字符也要进行 i < j 的判断，防止进来时候符合，在寻找有效字符时超过范围

代码：

class Solution {public boolean isPalindrome(String s) {if (s.equals("")) {return true;}int i = 0;int j = s.length() - 1;while (i < j) {while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {i++;}while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {j--;}if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {return false;}i++;j--;}return true;}
}

 🌟基础题目地址：LCR 018. 验证回文串 - 力扣（LeetCode）

2.进阶题目： 

118.杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

分析：

首先观察返回值要返回一个二维数组List<List<Integer>>，那么首先要生成二维数组用于存储，二维数组可以看成每个元素存储一个数组的一维数组

因此，我采用一行一行进行填充，首行为一个1元素，从第二行开始，每一行相当于第一个元素为1，最后一个元素为1，中间元素为上一行上方元素与左上方元素之和，采用add方法先将元素填充至curRow再把整个数组填充至triangle。

存储上一行元素这里用到了一个新数组prevrow[],这个数组的值采用二维数组上一个元素，这个地方有些难以理解，但实质使用起来却很简单。 

List类中获得元素采用get方法，添加采用add方法

代码：

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> triangle=new ArrayList();List<Integer> Firstrow=new ArrayList();Firstrow.add(1);triangle.add(Firstrow);int i=1;while(i<numRows){List<Integer> curRow=new ArrayList();curRow.add(1);List<Integer> prevRow=triangle.get(i-1);for(int j=1;j<i;j++){curRow.add(prevRow.get(j-1)+prevRow.get(j));}curRow.add(1);triangle.add(curRow);i++;}return triangle;}
}

118. 杨辉三角 - 力扣（LeetCode）🌟进阶题目地址：118. 杨辉三角 - 力扣（LeetCode）