怎么推广网站,做网站需要用到的符号语言,汽车网站哪个好,深圳本地招聘网站宫侑的发球最终进化为三刀流#xff0c;那么我的题解也未必要循规蹈矩! 1、验证回文串
题目描述#xff1a; 解法#xff1a; 这题官方给的关于双指针的题解都用到了多个库函数#xff0c;如 tolower(大写字母转小写)、isalnum(判断一个字符是否是 字母 或者 十进制数字 )…
宫侑的发球最终进化为三刀流那么我的题解也未必要循规蹈矩! 1、验证回文串
题目描述 解法 这题官方给的关于双指针的题解都用到了多个库函数如 tolower(大写字母转小写)、isalnum(判断一个字符是否是 字母 或者 十进制数字 ) 我想避免使用库函数所有就不用双指针的做法了而是使用栈 思路很简单 1、先将字符串中所有字母统一为小写字母 2、将数字和小写字母入栈同时将完整的、连续的字符都加入到一个新字符串newS中 3、再使用一个新字符串stkPop接收栈每一次pop出的字符 4、比较 newS 和 stkPop 是否相等 这道题的描述中提到了“字母和数字都属于字母数字字符”但示例中没有给出串中包含数字的情况导致测试用例 0P 没有通过这也是因为我忽略了串中还有数字的情况 要点 1、对于大写字母在 ASCII 码的基础上 32 就能转为小写字母 2、栈从top位置开始pop每次pop后栈中的元素会被删除 class Solution {
public:bool isPalindrome(string s) {stack char stk;string newS;string stkPop; // 接收栈中所有字符pop后的结果if(s.size() 1) return true;for(int i 0; i s.size(); i){if(s[i] A s[i] Z){s[i] 32; // 先将串中所有大写字母转为小写}// 只将串中的字母和数字入栈if((s[i] a s[i] z) || (s[i] 0 s[i] 9)){stk.push(s[i]); newS s[i];}}while(!stk.empty()){stkPop stk.top();stk.pop();}return stkPop newS;}
};
2、判断子序列
题目描述 解法 看到这种题第一反应就是2个 for 循环这种想法很不好 思路 为串 s 的首字符设置一个指针同理为串 t 的首字符也设置一个指针 我们是要在 t 中找出和 s 可以匹配上的子串当两个串中匹配上了同一个字符时两个指针都向后走一步以便进行下一个字符的匹配 若 s 的第2个字符与 t 的第2个字符没有匹配上此时指向 s 的指针不动指向 t 的指针继续向后移动直到找到匹配项 当 s 的指针走完整个 s 串时表示在 t 中有可以匹配上的子序列而 s 的指针没有走完 s 串时则没有匹配成功
class Solution {
public:bool isSubsequence(string s, string t) {// 指向字符串s、t首字符的指针int i 0, j 0;if(s.size() 0) return true;for(i, j; j t.size(); j){if(s[i] t[j]){i; // 匹配上了, i 和 j同走没匹配上,只有 j 往后走if(i s.size()) return true;}}return false;}
};
3、两数之和Ⅱ-输入有序数组
题目描述 解法 被题目描述中的“给你一个下标从1开始的整数数组”迷惑了一开始设定的指针是
int i 1;
int j numbers.size(); 哈哈哈哈果然溢出了不论何种描述数组容器的下标在计算机世界里永远是从0开始的 最终根据题目要求返回 {i 1, j 1} 就好了 之前只知道python中单个函数可以返回多个值还在想C怎么返回两个下标值呢刚开始甚至还定义了另一个 vectorint res 来接收下标最终看了题解后发现了 return {i 1, j 1} 这种写法
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int i 0; // 首指针int j numbers.size() - 1; // 尾指针for(i, j; i numbers.size(), j 0;){if((numbers[i] numbers[j]) target){j--; // 两数之和大于目标尾指针向前走}else if((numbers[i] numbers[j]) target){i;}else{if((numbers[i] numbers[j]) target) return {i 1, j 1};}}return {-1, -1};}
};
4、盛水最多的容器
题目描述 官方写的垂线、端点之类的术语属实费脑子推荐大家去看K神的题解——(传送门) 解法 实际上求解的正是矩形面积规定好 i j 后唯一要做的就是判断 i 和 j 代表的槽板哪个高哪个低因为较小的一方才能盛水而不漏 每次移动槽板较低的一方(此处可能用到了贪心的思想)通过不断比较原来面积和新面积的大小来返回最终的最大面积。
class Solution {
public:int maxArea(vectorint height) {int res 0;int i 0;int j height.size() - 1;while(i j){// 指针指向的水槽板高度分别为 h[i], h[j],两者中小的一方决定容纳面积res max(res, (min(height[i], height[j]) * (j - i)));if(height[i] height[j]) i;else j--;}return res;}
};
