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];
}
}
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
