LeetCode 100天挑战 Day 1：字符串匹配与Z字形变换
目录
- 题目一：实现strStr函数
- 题目二：Z字形变换
- 总结
前言
欢迎来到我的LeetCode算法100天挑战专栏！在接下来的100天里，我会每天分享两道LeetCode题目的解析。今天我们来看两道字符串处理的题目。
题目一：实现strStr函数
题目描述
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0。示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1。解题思路
这道题的思路很直接：
- 遍历haystack字符串，从每个位置开始检查是否能匹配needle
- 如果找到匹配，返回当前位置
- 如果遍历完都没找到，返回-1
代码实现分析
classSolution{publicintstrStr(Stringhaystack,Stringneedle){intlen1=haystack.length();intlen2=needle.length();// 从haystack的每个位置开始检查for(inti=0;i<=len1-len2;i++){// 提取从i开始的长度为len2的子串，和needle比较if(needle.equals(haystack.substring(i,i+len2))){returni;}}return-1;}}代码逐行解释：
int len1 = haystack.length();- 获取haystack的长度int len2 = needle.length();- 获取needle的长度for(int i = 0; i <= len1 - len2; i++)- 遍历haystack- i代表当前检查的起始位置
- 循环条件确保不会越界
- 比如haystack长度是8，needle长度是3，只需要检查到位置5即可
haystack.substring(i, i + len2)- 提取子串needle.equals(...)- 比较字符串是否相等找到匹配返回位置，否则返回-1
测试用例
示例1：haystack = “sadbutsad”, needle = “sad”
- i = 0: substring(0, 3) = “sad”，匹配成功，返回 0
示例2：haystack = “leetcode”, needle = “leeto”
- 遍历所有可能位置都不匹配，返回 -1
题目二：Z字形变换
题目描述
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N A P L S I I G Y I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"示例 2：
输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释： P I N A L S I G Y A H R P I解题思路
这个题目需要模拟Z字形排列的过程：
- 首先计算需要多少列来容纳所有字符
- 创建一个二维数组来模拟Z字形排列
- 按照Z字形的规律填充字符
- 最后按行读取结果
Z字形排列的规律：
- 垂直向下：从第0行到第numRows-1行
- 斜向上：从第numRows-2行到第1行
- 重复这个过程
代码实现分析
classSolution{publicStringconvert(Strings,intnumRows){// 特殊情况：只有一行时直接返回原字符串if(numRows==1){returns;}intindex=0;// 当前处理到字符串的哪个位置intcycleLen=2*numRows-2;// 一个完整周期的长度intcycleCols=numRows-1;// 一个完整周期占的列数intfullCycles=s.length()/cycleLen;// 完整周期数intremainder=s.length()%cycleLen;// 剩余字符数// 计算需要的列数intlist=fullCycles*cycleCols;if(remainder>0){list++;if(remainder>numRows){list+=(remainder-numRows);}}// 创建二维数组存储Z字形char[][]temp=newchar[numRows][list];inthight=0;// 填充Z字形for(inti=0;i<list;i++){if(index>=s.length()){break;}// 垂直向下的列if(i%(numRows-1)==0){for(hight=0;hight<numRows&&index<s.length();hight++){temp[hight][i]=s.charAt(index);index++;}hight=numRows-1;continue;}else{// 斜向上的列hight--;temp[hight][i]=s.charAt(index);index++;}}// 按行读取结果Stringans="";for(inti=0;i<temp.length;i++){for(intj=0;j<list;j++){if(temp[i][j]!=0){ans+=temp[i][j];}}}returnans;}}代码逐行解释：
- 特殊情况处理：
if(numRows==1){returns;}只有一行时，Z字形就是原字符串。
- 计算基本参数：
intcycleLen=2*numRows-2;// 一个完整周期的长度intcycleCols=numRows-1;// 一个完整周期占的列数- 周期长度：向下numRows-1步，向上numRows-1步
- 周期列数：需要numRows-1列
- 计算所需列数：
intfullCycles=s.length()/cycleLen;intremainder=s.length()%cycleLen;intlist=fullCycles*cycleCols;计算完整周期和剩余字符需要的列数。
- 创建二维数组：
char[][]temp=newchar[numRows][list];- 填充Z字形：
if(i%(numRows-1)==0){// 垂直向下的列for(hight=0;hight<numRows&&index<s.length();hight++){temp[hight][i]=s.charAt(index);index++;}}else{// 斜向上的列hight--;temp[hight][i]=s.charAt(index);index++;}- 垂直列：从上到下填充
- 斜向列：只有一个字符，位置逐渐上移
- 按行读取结果：
Stringans="";for(inti=0;i<temp.length;i++){for(intj=0;j<list;j++){if(temp[i][j]!=0){ans+=temp[i][j];}}}示例分析
示例1：s = “PAYPALISHIRING”, numRows = 3
Z字形排列：
P A H N A P L S I I G Y I R按行读取：PAHNAPLSIIGYIR
总结
今天的两道题目都是字符串处理的基础题目：
- strStr函数：考察字符串的基本操作和边界处理
- Z字形变换：考察二维数组的模拟和规律发现
两道题都需要仔细处理边界条件，通过模拟实际过程来解决问题。这种思路在解决算法问题时很有用。
标签：#LeetCode #算法 #Java #字符串 #数组
