C/C++教程
算法刷题（LeetCode 6-10）
文章目录
- [6. Z 字形变换 9/2](https://leetcode-cn.com/problems/zigzag-conversion/)
- [7. 整数反转 9/3](https://leetcode-cn.com/problems/reverse-integer/)
- [8. 字符串转换整数 (atoi) 9/4](https://leetcode-cn.com/problems/string-to-integer-atoi/)
- [9. 回文数 9/5](https://leetcode-cn.com/problems/palindrome-number/)
- [10. 正则表达式匹配 9/6](https://leetcode-cn.com/problems/regular-expression-matching/)
6. Z 字形变换 9/2
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N A P L S I I G Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
解析：
找出按 Z 形排列后字符的规律，然后直接保存起来。
可以看到，图形其实是有周期的，0，1，2 … 7 总共 8 个，然后就又开始重复相同的路径。周期(cycleLen)的计算就是：cycleLen = 2 × 行数(numRows) - 2 = 2 × 5 - 2 = 8 个。
我们发现第 0 行和最后一行一个周期内只有一个字符，所以第一个字符下标是 0 ，第二个字符下标是 0 + cycleLen = 8，第三个字符下标是 8 + cycleLen = 16 。
中间其他行一个周期内都是两个字符。
第 1 个字符和第 0 行的规律是一样的。
第 2 个字符其实就是下一个周期的第 0 行的下标减去当前行。什么意思呢？
我们求一下第 1 行第 1 个周期内的第 2 个字符，下一个周期的第 0 行的下标是 8 ，减去当前行 1 ，就是 7 了。
我们求一下第 1 行第 2 个而周期内的第 2 个字符，下一个周期的第 0 行的下标是 16 ，减去当前行 1 ，就是 15 了。
我们求一下第 2 行第 1 个周期内的第 2 个字符，下一个周期的第 0 行的下标是 8 ，减去当前行 2 ，就是 6 了。
当然期间一定要保证下标小于 字符串长度(n) ，防止越界。
Java实现：
class Solution {
public String convert(String s, int numRows) {
//如果只有一行，则直接返回字符串
if(numRows == 1){
return s;
}
//字符串长度
int len = s.length();
//用来存储输出字符串
StringBuilder ret = new StringBuilder();
//计算每个周期字符个数
int cycleLen = 2 * numRows - 2;
//遍历行
for(int i=0; i<numRows; i++){
//遍历周期数，每次加一个周期
for(int j=0; j+i<len; j+=cycleLen){
//添加的是每个周期的第一列
ret.append(s.charAt(j + i));
//添加的是 第i行 第j个 周期的第二个字符；即 除去第0行和最后一行
if(i != 0 && i != numRows - 1 && j+cycleLen-i < len){
ret.append(s.charAt(j + cycleLen - i));
}
}
}
return ret.toString();
}
}
时间复杂度：O（n），虽然是两层循环，但第二次循环每次加的是 cycleLen ，无非是把每个字符遍历了 1 次，所以两层循环内执行的次数肯定是字符串的长度。
空间复杂度：O（n），保存字符串。
7. 整数反转 9/3
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
解法一：
将整数转为字符串，字符串反转后再转为整数即可，需要主要负数的情况。
class Solution {
public int reverse(int x) {
String sx = Integer.toString(x); //可能带负号
String s = sx; //存储新的字符串
int flag = 1; //默认正数
//如果x为负数，则需乘 -1，设置flag为-1
if(x<0){
flag = -1; //负数
s = sx.substring(1); //去除负号
}
try{
//字符串反转后转整数
x = Integer.valueOf((new StringBuilder(s)).reverse().toString()) * flag;
return x;
}catch (Exception e){
return 0;
}
}
}
解法二：
将整数不断取余得到个位数，然后再除十去掉个位数；然后用一个变量来存放结果。
class Solution {
public int reverse(int x) {
long rev = 0; //存值变量
while(x != 0){
int pop = x % 10; //个位数
x /= 10; //取整, 去除个位数
rev = rev * 10 + pop;
}
//如果超过范围 就返回0
if(rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) return 0;
return (int)rev;
}
}
时间复杂度：循环多少次呢？数字有多少位，就循环多少次，也就是 log10(x)+1log_{10}(x) + 1log10(x)+1 次，所以时间复杂度是 O（log（x））。
空间复杂度：O（1）。
8. 字符串转换整数 (atoi) 9/4
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0。必要时更改符号（从步骤 2 开始）。
- 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1的整数应该被固定为 231 − 1 。
- 返回整数作为最终结果。
注意：
- 本题中的空白字符只包括空格字符 ’ ’ 。
- 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
解析：
主要是考虑好字符的处理方式。
Java实现：
class Solution {
public int myAtoi(String s) {
int i = 0;
int len = s.length(); //字符串长度
int sign = 1; //正数为1，负数为-1
int res = 0; //存储整数
while (i < len && s.charAt(i) == ' ') { //如果字符串前导位置为空格，循环到有数据的那一个位置
i++;
}
int start = i; //记录一下当前之后所有数据开始的位置
for (; i < len; i++) {
int c = s.charAt(i); //当前字符
if (i == start && c == '+') { //判断是否是+，并且+要在初始位置
sign = 1;
} else if (i == start && c == '-') { //判断是-
sign = -1;
} else if (Character.isDigit(c)) { //判断是数字
int num = c - '0';
//如果是数字，其他不用考虑，只需要考虑两种超限的情况
if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && num > Integer.MAX_VALUE % 10)) {
return Integer.MAX_VALUE;
} else if (res < Integer.MIN_VALUE / 10 || (res ==Integer.MIN_VALUE / 10 && -num < Integer.MIN_VALUE % 10)) {
return Integer.MIN_VALUE;
}
//计算整数值
res = res * 10 + sign * num;
} else { //如果有一次循环既不是数字，又不是'+'和'-'，那么立即退出循环，并返回当前res中已经储存的值
break;
}
}
return res;
}
}
9. 回文数 9/5
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
解法一：
将整数转为字符串，使用双指针解决。
class Solution {
public boolean isPalindrome(int x) {
String s = String.valueOf(x); //将整数转为字符串
int left = 0; //左指针
int right = s.length() - 1; //右指针
while(left < right){
if(s.charAt(left) != s.charAt(right)){ //如果左边字符不等于右边字符，不是回文
return false;
}
left++; //移动左指针
right--; //移动右指针
}
return true;
}
}
解法二：
将右半部分倒置然后和左半部比较就可以了。比如 1221 ，把 21 转置和 12 比较就行了。
class Solution {
public boolean isPalindrome(int x) {
if(x<0){
return false;
}
int n = (int) (Math.log(x) / Math.log(10) + 1); //总位数
int rev = 0; //存放右边反转的值
int pop = 0; //存放个位数值
//倒置右半部分
for(int i=0; i<n/2; i++){
pop = x % 10; //个位数
rev = rev * 10 + pop; //计算值
x /= 10; //取整，去除已计算的个位数
}
//如果是整数的总位数是偶数
if(n % 2 == 0 && x == rev){
return true;
}
//如果是整数的总位数是奇数，就将x去除一位再与右边比较
if(n % 2 != 0 && x/10 == rev){
return true;
}
return false;
}
}
时间复杂度：循环 x 的总位数的一半次，所以时间复杂度依旧是 O（log（x））。
空间复杂度：O（1），常数个变量。
10. 正则表达式匹配 9/6
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
- ‘.’ 匹配任意单个字符
- ‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
解法一：
递归
class Solution {
public boolean isMatch(String s, String p) {
//判断当p为空时，如果s也为空，就返回true，否则为false
if(p.isEmpty()) return s.isEmpty();
//当s不为空，并且 p与s的第一个字符相等 或 p为'.'时，为true
boolean first_match = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));
//当p长度大于等于2时，才考虑'*'
if(p.length() >= 2 && p.charAt(1) == '*'){
//两种情况
//1. p直接跳过两个字符：表示*前面的字符出现0次
//2. p不变，例如 s=aa,p=a* 第一个a匹配，然后s的第二个a接着和 p的第一个a匹配 ：表示 * 用前一个字符替代。
return (isMatch(s,p.substring(2))) || (first_match && isMatch(s.substring(1),p));
} else {
//递归
return first_match && isMatch(s.substring(1),p.substring(1));
}
}
}
解法二：
动态规划
class Solution {
public boolean isMatch(String text, String pattern) {
// 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况，
// 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了
boolean[][] dp = new boolean[2][pattern.length() + 1];
dp[text.length()%2][pattern.length()] = true;
// 从 len 开始减少
for (int i = text.length(); i >= 0; i--) {
for (int j = pattern.length(); j >= 0; j--) {
if(i==text.length()&&j==pattern.length()) continue;
boolean first_match = (i < text.length() && j < pattern.length()
&& (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
dp[i%2][j] = dp[i%2][j + 2] || first_match && dp[(i + 1)%2][j];
} else {
dp[i%2][j] = first_match && dp[(i + 1)%2][j + 1];
}
}
}
return dp[0][0];
}
}
-
Typescript 类型教程：轻松入门与实践指南11-15
-
AntDesign-icons项目实战：新手入门教程11-15
-
用Scratch编写语言模型：爪爪（Clawed）式简易教程11-14
-
用大型语言模型在Amazon Bedrock上分类Jira工单11-14
-
从数据到行动：亚马逊Bedrock代理如何自动化复杂工作流11-14
-
Databricks与优化后的Snowflake性能大比拼11-14
-
亚马逊 Inspector 解析：提升您的 AWS 负载安全的利器11-14
-
揭秘VS Code for Web - Azure：轻松开发云端应用的新利器11-14
-
揭秘指南：如何让Databricks中的数据为最终用户所用11-14
-
OpenTelemetry扩展进入CI/CD可观测性领域11-14
-
Fetch / Axios学习：入门教程与实战指南11-14
-
Typescript 类型课程入门教程11-14
-
Fetch / Axios课程：初学者必看的网络请求教程11-14
-
Styled-components课程：初学者指南11-14
-
pre-commit 自动化测试课程：入门教程与实践指南11-13
