深圳网站建设设计定做,吉林省级建设行政主管部门政务网站,美妆网站制作教程,质量最好的购物平台#x1f525;个人主页#xff1a;Quitecoder
#x1f525;专栏#xff1a;Leetcode刷题 目录 1.仅反转字母2.字符串中第一个唯一字符3.验证回文串4.字符串相加5.反转字符串I I6.反转字符串中的单词III7.字符串相乘8.把字符串转换为整数 1.仅反转字母 题目链接#xff1a;…
个人主页Quitecoder
专栏Leetcode刷题 目录 1.仅反转字母2.字符串中第一个唯一字符3.验证回文串4.字符串相加5.反转字符串I I6.反转字符串中的单词III7.字符串相乘8.把字符串转换为整数 1.仅反转字母 题目链接917.仅仅反转字母 题目描述 首先这道题仅仅需要翻转字母我们先写一个函数来判断是否为字母
bool Isletter(char ch){if (ch a ch z || chA ch Z)return true;elsereturn false;}接着创建两个索引begin和end一个从前往后找找到一个字母停止另一个从后面找找到字母停止然后进行交换保证beginend比较简单代码如下
class Solution {
public:bool Isletter(char ch){if (ch a ch z || chA 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 i0;is.size();i){arr[s[i]]1;}for(int i0;is.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);}接着我们设置两个索引leftright来从左往右一次寻找字母左边找到字符则停止右边找到字符则停止然后通过字符函数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 end1num1.size()-1,end2num2.size()-1;int next0;while(end10||end20){int val1end10?num1[end1--]-0:0;int val2end20?num2[end2--]-0:0;int retval1val2next;nextret/10;retret%10;result.insert(0,1,ret0);}if(next1){result.insert(0,1,1);}return result;}
};函数逻辑 定义一个空字符串 result它最终将存储相加后的结果 定义两个整型变量 end1 和 end2分别表示 num1 和 num2 字符串的末位索引 定义变量 next表示在每一步相加中可能产生的进位 使用一个 while 循环条件是 end1 或 end2 中有一个或两个大于或等于0。这表示至少还有一个数字字符串有未处理的数字 在循环内部分别计算 val1 和 val2它们代表当前要相加的两个字符对应的数字值。如果索引小于0则表示该数字字符串没有更多的位数可以处理因此对应的值为0 计算 ret它是 val1、val2 和前一步的进位 next 之和 更新 next 为 ret 除以10因为手写加法中超过10的部分产生进位 更新 ret 为 ret 对10取余因为余数是当前位上的数字 将 ret 转换为对应的字符然后将该字符插入 result 字符串的最前面 重复步骤5-9直到处理完 num1 和 num2 的所有位数 循环结束后检查是否还有未添加的进位 next。如果 next 为1将字符 ‘1’ 插入 result 字符串的最前面这一部分可以查阅函数库来了解insert的多种实现形式 返回结果字符串 result
优化 因为不断的头插数据会挪动使函数的时间复杂度来到了O(N2)
优化思路
尾插再进行反转
class Solution {
public:string addStrings(string num1, string num2) {string result;int end1num1.size()-1,end2num2.size()-1;int next0;while(end10||end20){int val1end10?num1[end1--]-0:0;int val2end20?num2[end2--]-0:0;int retval1val2next;nextret/10;retret%10;resultret0;}if(next1){result1;}reverse(result.begin(), result.end());return result;}
};5.反转字符串I I 题目链接541.反转字符串I I 题目描述 这段代码意在实现根据指定的整数 k 来部分反转字符串 s 的功能。但是代码中有几个问题需要解决才能正确实现这一功能。
首先让我们明确正确的逻辑
遍历字符串步长为 2k 字符。在每个步长内 如果剩余字符少于 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;}
};使用一个 for 循环步长为 2 * k遍历字符串 s每次移动2k步检查并反转前k个字符 在循环中检查剩余字符的数目根据这个数目适当地反转字符串的一部分 使用 reverse 方法来反转从 start 开始的字符。注意reverse 方法的第二个参数是我们想要反转区间的结束位置的下一个迭代器。如果剩余字符少于 k 个则 reverse 的参数是 s.end()这样可以反转从 start 开始的所有剩余字符 如果 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;}
};这段代码理解起来十分简单详细讲解
此代码模拟了我们在纸上作乘法运算时的过程
处理特殊情况 如果 num1 或 num2 中任意一个是 “0”那么乘积为 “0”
if (num1 0 || num2 0) return 0;初始化结果字符串 初始化结果字符串 result长度为 num1.size() 加上 num2.size()所以 result 的长度足以存储乘法得到的所有可能数字包括合并进位。所有字符先被设置为 0
string result(num1.size() num2.size(), 0);嵌套循环 外层循环以 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--) {// ...}
}计算乘积 对于每对数位(num1[i], num2[j])计算它们值的乘积另外再把结果 result 相应位置上的值加上去需要先把result[ij1]字符转化为整数。需要注意的是计算中还会加上之前的进位
int mul (num1[i] - 0) * (num2[j] - 0);
int sum (result[i j 1] - 0) mul;处理结果和进位 当前乘积mul与结果result当前位置上的数相加后可能会大于等于10即产生进位。将当前位的结果模上10得到最终结果并把商加到下一位上
result[i j 1] (sum % 10) 0;
result[i j] sum / 10;移除前导零 由于乘积可能比 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”。
返回结果 如果 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在由字符串转换为整数时溢出代码使用了下列条件检查 result INT_MAX / 10 这个检查确保将当前的 result 乘以 10也就是添加新的数字之前不会超过最大整数值 INT_MAX。如果 result 已经大于 INT_MAX 除以 10那么在下一步乘以 10 时一定会发生溢出。 (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。
本节内容到此结束感谢大家阅读可以多多交流
