【Leetcode】string类刷题

server/2024/12/22 22:22:09/

Alt

🔥个人主页：Quitecoder

🔥专栏：Leetcode刷题

Alt

目录

  • 1.仅反转字母
  • 2.字符串中第一个唯一字符
  • 3.验证回文串
  • 4.字符串相加
  • 5.反转字符串I I
  • 6.反转字符串中的单词III
  • 7.字符串相乘
  • 8.把字符串转换为整数

1.仅反转字母

题目链接：917.仅仅反转字母
题目描述：在这里插入图片描述

首先，这道题仅仅需要翻转字母，我们先写一个函数来判断是否为字母

bool Isletter(char ch){if (ch >= 'a' && ch <= 'z' || ch>='A' && ch <= 'Z')return true;elsereturn false;}

接着，创建两个索引，begin和end，一个从前往后找，找到一个字母停止，另一个从后面找，找到字母停止，然后进行交换，保证begin<end，比较简单，代码如下：

class Solution {
public:bool Isletter(char ch){if (ch >= 'a' && ch <= 'z' || ch>='A' && ch <= 'Z')return true;elsereturn false;}string reverseOnlyLetters(string s){size_t begin1 = 0;size_t  end1 = s.size() - 1;while (begin1 < end1){while (begin1 < end1 && !Isletter(s[begin1])){begin1++;}while (begin1 < end1 && !Isletter(s[end1])){end1--;}swap(s[begin1],s[end1]);begin1++;end1--;}return s;}
};

这里我们直接用了算法库中的swap函数，进行字符的交换

2.字符串中第一个唯一字符

题目链接：387.字符串中第一个唯一字符
题目描述：在这里插入图片描述

这道题主要目的就是找第一个唯一出现的字符，我们的思路就是类似于计数排序，构建一个存储字符出现次数的数组，最后按照新数组寻找出现一次的那个字符

class Solution {
public:int firstUniqChar(string s) {int arr[256]={0};for(int i=0;i<s.size();i++){arr[s[i]]+=1;}for(int i=0;i<s.size();i++){if(arr[s[i]]==1)return i;}return -1;}
};

解法简单，希望能够理解

3.验证回文串

题目链接：125.验证回文串
题目描述：在这里插入图片描述

题目描述，去掉非字母和非数字后的字符串，回文，则构成回文，我们的思路是先判断是否为字母字符或者数字字符：

 bool isLetterOrDigit(char ch) {return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9');}

接着我们设置两个索引，left，right来从左往右一次寻找字母，左边找到字符则停止，右边找到字符则停止，然后通过字符函数tolower使他们均变为小写字母进行比较

如果有一组不匹配，则返回false
代码如下：

class Solution {
public:bool isLetterOrDigit(char ch) {return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9');}bool isPalindrome(string s) {int left = 0;int right = s.size() - 1;while (left < right) {while (left < right && !isLetterOrDigit(s[left])) {left++;}while (left < right && !isLetterOrDigit(s[right])) {right--;}if (tolower(s[left]) != tolower(s[right])) {return false;}left++;right--;}return true;}
};

4.字符串相加

题目链接：415.字符串相加
题目描述：在这里插入图片描述

本题核心思想就是处理进位问题，从尾部依次相加，结果保留个位数与进位数（0或1），这个进位数进行下一次运算，保留的个位数以新的字符头插在字符串中

class Solution {
public:string addStrings(string num1, string num2) {string result;int end1=num1.size()-1,end2=num2.size()-1;int next=0;while(end1>=0||end2>=0){int val1=end1>=0?num1[end1--]-'0':0;int val2=end2>=0?num2[end2--]-'0':0;int ret=val1+val2+next;next=ret/10;ret=ret%10;result.insert(0,1,ret+'0');}if(next==1){result.insert(0,1,'1');}return result;}
};

函数逻辑

  1. 定义一个空字符串 result，它最终将存储相加后的结果

  2. 定义两个整型变量 end1 和 end2，分别表示 num1 和 num2 字符串的末位索引

  3. 定义变量 next，表示在每一步相加中可能产生的进位

  4. 使用一个 while 循环，条件是 end1 或 end2 中有一个或两个大于或等于0。这表示至少还有一个数字字符串有未处理的数字

  5. 在循环内部，分别计算 val1 和 val2，它们代表当前要相加的两个字符对应的数字值。如果索引小于0，则表示该数字字符串没有更多的位数可以处理，因此对应的值为0

  6. 计算 ret，它是 val1、val2 和前一步的进位 next 之和

  7. 更新 next 为 ret 除以10，因为手写加法中，超过10的部分产生进位

  8. 更新 ret 为 ret 对10取余，因为余数是当前位上的数字

  9. 将 ret 转换为对应的字符，然后将该字符插入 result 字符串的最前面

  10. 重复步骤5-9，直到处理完 num1 和 num2 的所有位数

  11. 循环结束后，检查是否还有未添加的进位 next。如果 next 为1，将字符 ‘1’ 插入 result 字符串的最前面（这一部分可以查阅函数库来了解insert的多种实现形式）

  12. 返回结果字符串 result

优化：
因为不断的头插，数据会挪动，使函数的时间复杂度来到了O(N2)

优化思路：

  • 尾插，再进行反转
class Solution {
public:string addStrings(string num1, string num2) {string result;int end1=num1.size()-1,end2=num2.size()-1;int next=0;while(end1>=0||end2>=0){int val1=end1>=0?num1[end1--]-'0':0;int val2=end2>=0?num2[end2--]-'0':0;int ret=val1+val2+next;next=ret/10;ret=ret%10;result+=ret+'0';}if(next==1){result+='1';}reverse(result.begin(), result.end());return result;}
};

5.反转字符串I I

题目链接：541.反转字符串I I
题目描述：在这里插入图片描述

这段代码意在实现根据指定的整数 k 来部分反转字符串 s 的功能。但是，代码中有几个问题需要解决才能正确实现这一功能。

首先，让我们明确正确的逻辑：

  1. 遍历字符串，步长为 2k 字符。
  2. 在每个步长内：
    • 如果剩余字符少于 k 个，则反转这些字符。
    • 如果剩余字符小于 2k 但至少有 k 个，则只反转前 k 个字符
    • 如果有足够的字符，则反转前 k 个字符，保持其余字符不变
class Solution {
public:string reverseStr(string s, int k) {int size = s.size();for (int start = 0; start < size; start += 2 * k) {// 如果剩余字符少于 k 个，则反转剩余的所有字符if (start + k > size) {reverse(s.begin() + start, s.end());} else {// 反转从 start 开始的 k 个字符reverse(s.begin() + start, s.begin() + start + k);// 其余字符保持原样，根据题目要求这部分不需要任何操作}}return s;}
};

  1. 使用一个 for 循环，步长为 2 * k，遍历字符串 s，每次移动2k步，检查并反转前k个字符

  2. 在循环中检查剩余字符的数目，根据这个数目适当地反转字符串的一部分

  3. 使用 reverse 方法来反转从 start 开始的字符。注意，reverse 方法的第二个参数是我们想要反转区间的结束位置的下一个迭代器。如果剩余字符少于 k 个，则 reverse 的参数是 s.end()，这样可以反转从 start 开始的所有剩余字符

  4. 如果 start + k 小于或等于 size，则只反转前 k 个字符，而其余字符保持原样

6.反转字符串中的单词III

题目链接：557.反转字符串中的单词III
题目描述：在这里插入图片描述

这道题主要思路就是找到每个空格位置对单词进行分割，逐个翻转

class Solution {
public:string reverseWords(string s) {int size = s.size();size_t pos = s.find(' ');int start = 0;while (pos != string::npos) {reverse(s.begin() + start, s.begin() + pos); start = pos + 1;pos = s.find(' ', start);}reverse(s.begin() + start, s.end()); return s; }
};

注意，reverse接收的参数应该是迭代器，我们应该使用 s.begin() 加上相应的索引来获取正确的迭代器位置，每次找到一个空格就更新索引往后寻找，直到找到最后一个单词结束，结束后，再对最后一个单词进行反转

7.字符串相乘

题目链接：43.字符串相乘
题目描述：在这里插入图片描述

思路一：

这道题与我们的字符串相加类似，我们需要做的就是用num2的每一位与num1相乘，每得到两个结果就进行字符串相加

class Solution {
public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0") return "0"; string result(num1.size() + num2.size(), '0');for (int i = num1.size() - 1; i >= 0; i--) {for (int j = num2.size() - 1; j >= 0; j--) {int mul = (num1[i] - '0') * (num2[j] - '0');int sum = (result[i + j + 1] - '0') + mul;result[i + j + 1] = (sum % 10) + '0';result[i + j] += sum / 10;}}size_t startpos = result.find_first_not_of("0");if (startpos != string::npos) {return result.substr(startpos);}return "0";}
};

这段代码理解起来十分简单，详细讲解：

此代码模拟了我们在纸上作乘法运算时的过程：

  1. 处理特殊情况
    如果 num1 或 num2 中任意一个是 “0”，那么乘积为 “0”
if (num1 == "0" || num2 == "0") return "0";
  1. 初始化结果字符串
    初始化结果字符串 result，长度为 num1.size() 加上 num2.size()，所以 result 的长度足以存储乘法得到的所有可能数字，包括合并进位。所有字符先被设置为 '0'
string result(num1.size() + num2.size(), '0');
  1. 嵌套循环
    外层循环以 num1.size() - 1 开始，即 num1 字符串的最后一个字符，向前遍历整个字符串。内层循环以 num2.size() - 1 开始，即 num2 字符串的最后一个字符，向前遍历整个字符串。循环索引 i 和 j 分别对应 num1 和 num2 的每个数位
for (int i = num1.size() - 1; i >= 0; i--) {for (int j = num2.size() - 1; j >= 0; j--) {// ...}
}
  1. 计算乘积
    对于每对数位(num1[i], num2[j])，计算它们值的乘积，另外再把结果 result 相应位置上的值加上去（需要先把result[i+j+1]字符转化为整数）。需要注意的是，计算中还会加上之前的进位
int mul = (num1[i] - '0') * (num2[j] - '0');
int sum = (result[i + j + 1] - '0') + mul;
  1. 处理结果和进位
    当前乘积mul与结果result当前位置上的数相加后，可能会大于等于10，即产生进位。将当前位的结果模上10得到最终结果，并把商加到下一位上
result[i + j + 1] = (sum % 10) + '0';
result[i + j] += sum / 10;
  1. 移除前导零
    由于乘积可能比 num1.size() + num2.size() 这么长要短，所以会在 result 最前面出现一些 ‘0’。我们需要找到第一个不是 ‘0’ 的字符的位置，并从那里开始返回子字符串
size_t startpos = result.find_first_not_of("0");
if (startpos != string::npos) {return result.substr(startpos);
}

如果整个字符串都是 ‘0’，说明两个数的乘积是 0，直接返回 “0”。

  1. 返回结果
    如果 result 中有非 ‘0’ 的字符，就从第一个非零字符开始返回剩余的子字符串，否则直接返回 “0”。

8.把字符串转换为整数

题目链接：LCR 192.把字符串转换为整数(atoi)
题目描述：在这里插入图片描述

首先，我们写两个函数来对空字符和正负号进行处理：

int i = 0;
int sign = 1;
int result = 0;
while (i < str.length() && str[i] == ' ') { i++;}if (i < str.length() && (str[i] == '+' || str[i] == '-')) {sign = (str[i] == '+') ? 1 : -1;i++;}

接着处理数字部分，如果超过32 位有符号整数范围，则进行截断：

class Solution {
public:int myAtoi(string str) {int i = 0;int sign = 1;int result = 0;while (i < str.size() && str[i] == ' ') { i++;}if (i < str.size() && (str[i] == '+' || str[i] == '-')) {sign = (str[i] == '+') ? 1 : -1;i++;}while (i < str.size() && isdigit(str[i])) { int digit = str[i] - '0';if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) {return sign == 1 ? INT_MAX : INT_MIN;}result = 10 * result + digit;i++;}return result * sign;}
};

 if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) {return sign == 1 ? INT_MAX : INT_MIN;}

这部分代码的目的是检查在将下一个数字添加到已解析的结果 result 之前，是否会导致整数溢出。溢出指的是整数的值超出了它能表示的最大范围。在C++中，对于32位 int 类型，能够表示的最大整数值定义在 <climits> 头文件中，称为 INT_MAX，通常为 2^31 - 1（即2147483647），最小整数值为 INT_MIN，通常为 -2^31（即-2147483648）
为了避免result在由字符串转换为整数时溢出，代码使用了下列条件检查：

  1. result > INT_MAX / 10
    这个检查确保将当前的 result 乘以 10（也就是添加新的数字之前）不会超过最大整数值 INT_MAX。如果 result 已经大于 INT_MAX 除以 10，那么在下一步乘以 10 时一定会发生溢出。

  2. (result == INT_MAX / 10 && digit > INT_MAX % 10)
    如果 result 已经达到了 INT_MAX 除以 10 的值，那么我们可以检查下一个要添加的数字（digit）是否会导致溢出。因为我们知道 result 乘以 10 刚好达到但不超过 INT_MAX，所以我们只需要保证添加的数字小于或等于 INT_MAX 最后一个数位的数字的值，即 INT_MAX % 10。如果 digit 大于这个值，那么加上 digit 之后会超出 INT_MAX，发生溢出

如果以上任何一种溢出条件满足，那么根据数字的正负符号，函数返回最大或最小的 int 值：

return sign == 1 ? INT_MAX : INT_MIN;

  • 当 sign 为 1，即正数的情况下，返回 INT_MAX。
  • 当 sign 为 -1，即负数的情况下，返回 INT_MIN。

本节内容到此结束，感谢大家阅读，可以多多交流！！


http://www.ppmy.cn/server/1680.html

相关文章

MapReduce——ReudceTask并行度决定机制

MapReduce——ReudceTask并行度决定机制

MapReduce——ReudceTask并行度决定机制 1. Reduce任务的数量&#xff08;reduce task count&#xff09;&#xff1a; 这是最基本的决定因素之一。在作业启动时&#xff0c;用户可以指定Reduce任务的数量。更多的Reduce任务意味着更多的并行度&#xff0c;因为每个Reduce任务…
阅读更多...
【数据结构】双向链表

【数据结构】双向链表

前言 这篇博客我们来继续探讨链表&#xff0c;上篇博客我们讨论了单链表&#xff0c;其实链表的种类有很多&#xff0c;但最常用的除了单链表之外&#xff0c;还有个双向链表&#xff0c;今天我们就来总结下双向链表 &#x1f493; 个人主页&#xff1a;小张同学zkf ⏩ 文章专栏…
阅读更多...
深入解析Tomcat的工作流程

深入解析Tomcat的工作流程

tomcat解析 Tomcat是一个广泛使用的开源Servlet容器&#xff0c;用于托管Java Web应用程序。理解Tomcat的工作流程对于开发人员和系统管理员来说是非常重要的。本文将深入探讨Tomcat的工作原理&#xff0c;包括请求处理、线程池管理、类加载、以及与Web服务器之间的通信。 ###…
阅读更多...
云服务器部署Springboot项目

云服务器部署Springboot项目

前端项目打包 修改ip地址 在控制台输入npm run build:prod 会产生dist文件 将dist文件中的内容移动至/usr/local/nginx/html目录下 后端项目打包 修改ip地址 执行clean操作 执行install操作 将生成的target文件中的jar包移动至/usr/local/src目录下 启动 注意⚠️&#xff…
阅读更多...
探索“人工智能+”战略下的企业切入点

探索“人工智能+”战略下的企业切入点

在“人工智能”的大战略框架下&#xff0c;企业正面临着巨大的发展机遇与挑战。本文将深入探讨在这一战略框架下&#xff0c;企业可以采取的具体切入点&#xff0c;以实现技术创新、提升竞争力和实现可持续发展。 --- 随着人工智能技术的不断发展和应用&#xff0c;以“人工智能…
阅读更多...
人工智能的未来会怎样？Gartner发布AI技术成熟度曲线

人工智能的未来会怎样？Gartner发布AI技术成熟度曲线

对于任何人来说&#xff0c;生成式人工智能和支持它的基础模型目前都处于Gartner所谓的「膨胀预期的顶峰」&#xff0c;这一点并不奇怪&#xff0c;在最新的「Gartner AI技术成熟度曲线」中。这意味着他们正在悬崖上摇摇欲坠&#xff0c;这可能会使他们陷入「幻灭的低谷」。 「…
阅读更多...
Java | Leetcode Java题解之第35题搜索插入位置

Java | Leetcode Java题解之第35题搜索插入位置

题目&#xff1a; 题解&#xff1a; class Solution {public int searchInsert(int[] nums, int target) {int n nums.length;int left 0, right n - 1, ans n;while (left < right) {int mid ((right - left) >> 1) left;if (target < nums[mid]) {ans mi…
阅读更多...
ASP.NET基于WEB的选课系统

ASP.NET基于WEB的选课系统

摘要 设计本系统的目的是对选课信息进行管理。学生选课系统维护模块主要完成的是系统管理与维护功能。课题研究过程中&#xff0c;首先对系统管理模块进行了详尽的需求分析&#xff0c;经分析得到系统管理模块主要完成如下的功能&#xff1a;用户基本信息、选课信息的录入,查看…
阅读更多...
最新文章

Copyright @ 2022~2023