Leetcode exercise record --- STRING 9 exercises

?Leetcode exercise record? STRING 9 exercises

****刷题小结****
1.字符串的问题，数学思维考察还是栾多的
2.双端队列
3.逆序调用
4.时间复杂度和空间复杂度的分析
6.折半比较
7.代码要不断优化
8.待练习 1. 字符串循环移位包含 2. 字符串循环移位

151. 翻转字符串里的单词 ?

? MEDIUM

Q&A
给定一个字符串，逐个翻转字符串中的每个单词。

示例:
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 ：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

?Language: C++

算法五个重要的特征：

有输入，有输出（题目已经给了）

可行性（复杂问题转化成熟悉子问题）

有穷性（在算法描述体现）

确切性（在算法描述体现）
split 和reverse的方法

导入头文件#include < deque >
deque<int> d;  //创建一个双端队列d
push_back()   //在队尾插入元素
push_front()   //在队首插入元素
insert(d.begin()+1,10);   //第一个元素之后插入10
size()   //双端队列的大小
empty()   //判断是否为空
begin()   //队首的指针，指向队首元素
end()   //队尾元素的下一位作为指针
rbegin()  //以最后一个元素作为开始
rend()   //以第一个元素的上一位作为指针
erase()   //删除某一个元素
clear()   //删除所有元素
pop_front()   //删除队首元素
pop_back()   //删除队尾元素deque<int>::iterator it;   //迭代器
deque<int>::reverse_iterator rit;   //反向迭代器
[原文链接](https://blog.csdn.net/weixin_44915226/article/details/105224513?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159541368319725250102503%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=159541368319725250102503&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v3~pc_rank_v3-1-105224513.pc_ecpm_v3_pc_rank_v3&utm_term=C%2b%2b%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97%E7%9A%84%E7%89%B9%E7%82%B9&spm=1018.2118.3001.4187)

??【WAY1 C++ 】

class Solution {
public:string reverseWords(string s) {//时间复杂度和空间复杂度都为O(n)vector<string> strs;//数组存单词string ans = "";string sub = "";for(int i =0 ; i < s.size(); i ++){if(s[i] == ' '){if(sub.size() > 0){strs.push_back(sub);sub = "";}}else{sub += s[i];if(i == s.size() - 1) strs.push_back(sub);}}for(int i = strs.size() - 1; i >= 0; i --){//逆序取数组中的单词，拼ans += strs[i];if(i != 0) ans += " ";}return ans;}
};

??【WAY2 C++ 】 双端队列 or 栈
双端队列：相比循环队列来说，
队头：取，进队，出队 队尾：取，进队，出队

class Solution {
public:string reverseWords(string s) {int left = 0,right = s.size() - 1;//去掉字符串首尾的空白字符while(left <= right && s[left] == ' ') ++left;while(left <= right && s[right] == ' ') --right;deque<string> d;//双端队列存储string word;while(left <= right){char c = s[left];if(word.size() && c == ' '){//分隔一个单词，从队列头部入队d.push_front(move(word));word = "";}else if(c != ' '){//注意此处处理word += c;}++ left;}d.push_front(move(word));string ans;while(!d.empty()){ans += d.front();//此时队列单词逆序d.pop_front();if(!d.empty()) ans += ' ';}return ans;}
};

??【WAY3 C++ 】 官方题解
翻转整个数组 翻转单个单词 清除多余空格
双指针操作字符数组

class Solution {
public:string reverseWords(string s) {reverse(s.begin(),s.end());//整体翻转int n = s.size();int idx = 0;for(int start = 0;start < n; ++start){if(s[start] != ' '){if(idx != 0) s[idx++] = ' ';int end = start;while(end < n && s[end] != ' ') s[idx++] = s[end++];//查找句子中的一个单词reverse(s.begin() + idx - (end - start),s.begin() + idx);start = end;}}s.erase(s.begin() + idx,s.end());return s;}
};

242. 有效的字母异位词

? EASY

Q&A
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 ：
输入: s = “rat”, t = “car”
输出: false

分析：
只是将原单词中的字母改变未知，单词长度保持不变
??【WAY1 C++ 】 桶排序

class Solution {
public:bool isAnagram(string s, string t) {if(s.size() != t.size()){return false;}char cmp[26] = {0};//设置一个能存放26个字母的比较桶/*for(int i = 0;i < s.size();i++){cmp[s[i] - 'a']++;}for(int i = 0;i < t.size();i++){cmp[t[i] - 'a']--;}*///改进for(int i = 0;;i++){if(i < s.size()){cmp[s[i] - 'a']++;}else if(i > s.size()){break;}if(i < t.size()){cmp[t[i] - 'a']--;}}for(int i = 0;i < 26;i ++){if(cmp[i] != 0){return false;}}return true;}
};

??【WAY2 C++ 】 哈希数组

class Solution {
public:bool isAnagram(string s, string t) {if(s.size() != t.size()) return false;int hash[26] = {0};//哈希数组for(auto n : s)hash[n - 'a']++;for(auto n : t)hash[n - 'a']--;for(int i = 0;i < 26;i++)if(hash[i] != 0) return false;return true;}
};

??【WAY3 C++ 】 排序，调用API

class Solution {
public:bool isAnagram(string s, string t) {if(s.size() != t.size()) return false;sort(s.begin(),s.end());sort(t.begin(),t.end());return s == t;             }
};

409. 最长回文串

计算一组字符集合可以组成的回文字符串的最大长度

? EASY

Q&A
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。
示例：
输入: “abccccdd”
输出: 7
解释:
构造的最长的回文串是"dccaccd", 它的长度是 7。

官方分析
贪心算法
??【WAY1 C++ 】

class Solution {
public:int longestPalindrome(string s) {unordered_map<char,int> count;//哈希表，存放每个字符出现的对应次数int ans = 0;//记录最长回文串的长度for(char c : s){count[c]++;}for(auto p : count){int v = p.second;// 哈希：键(key)是first，值(value)是secondans += v / 2 * 2;if(ans % 2 == 0 && v % 2 == 1){ans++;}}return ans;}
};

??【WAY2 C++ 】 用哈希映射（HashMap）即键值对 来存储每个字符出现的次数

class Solution {
public:int longestPalindrome(string s) {int hashmap[52];//存储52个字母memset(hashmap,0,sizeof(int) * 52);//初始化哈希表int odd_mark = 0;//设置奇数标记for(int i = 0;i < s.length();i ++){char c = s[i];if(c >= 'a' && c <= 'z'){hashmap[int(c - 'a')]++;}else if(c >= 'A' && c <= 'Z'){hashmap[int(c - 'A') + 26]++;}}int ans = 0;for(int i =0;i < 52;i++){ans += hashmap[i];if(hashmap[i] % 2){ans--;odd_mark = 1;}}if(odd_mark){ans++;}return ans;}
};

205. 同构字符串

同构：同种结构 just like 汉字中叠词 红彤彤 懒洋洋

? EASY

Q&A
给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 :
输入: s = “egg”, t = “add”
输出: true

输入: s = “paper”, t = “title”
输出: true

??【WAY1 C++ 】 映射

class Solution {
public:bool isIsomorphic(string s, string t) {//find(char c):返回c第一次出现的索引,if(s.length() != t.length()) return false;if(s.empty() && t.empty()) return true;if(s.empty() || t.empty()) return false;for(int i = 0;i < s.size();i++){if(s.find(s[i] ) != t.find(t[i]))return false;}return true;}
};

??【WAY2 C++ 】

class Solution {
public:bool isIsomorphic(string s, string t) {//哈希表中存储每个字符第一次出现的位置，后续遍历比较unordered_map<char,int> sHash;unordered_map<char,int> tHash;for(int i = 0;i < s.size();i++){//algorithm头文件定义了一个count的函数，其功能类似于find。//这个函数使用一对迭代器和一个值做参数，返回这个值出现次数的统计结果。if(sHash.count(s[i]) && tHash.count(t[i])){if(sHash[s[i]] != tHash[t[i]])return false;}else if(sHash.count(s[i]) || tHash.count(t[i]))return false;else{sHash[s[i]] = i;tHash[t[i]] = i;}}return true;       }
};

647. 回文子串

? MEDIUM

Q&A

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 :

输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.
示例 2:

输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

注意:
输入的字符串长度不会超过1000。

??【WAY1 C++ 】 中心检测法

class Solution {
public:int countSubstrings(string s) {//中心检测法，从字符串的开始依次检测，向两侧扩散//查找的子回文字符串长度可以是奇数的，也可是偶数长度//子回文字符串长度为奇数：中心位为当前字符//子回文字符串长度为偶数：中心位为当前字符和下一个字符int length = s.length();int res = 0;for(int i = 0;i < length;i++){helper(s,i,i,res);helper(s,i,i + 1,res);}return res;}void helper(string &s,int left,int right,int &res ){while(left >= 0 && right <= s.length() && s[left] == s[right]){left--;right++;res++;}}
};

??【WAY2 C++ 】 动态规划

class Solution {
public:int countSubstrings(string s) {if(s.empty()) return 0;int length = s.length();int res = 0;vector<vector<bool>> dp(length,vector<bool>(length));for(int i = length - 1; i >= 0; --i){for(int j = i;j < length; ++j){dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);if(dp[i][j]) ++res;}}return res;}
};

9. 回文数

? EASY

Q&A
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 :

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:
你能不将整数转为字符串来解决这个问题吗？

??【WAY C++ 】 翻转一半的数字

class Solution {
public:bool isPalindrome(int x) {//所有负数不可能是回文，末位为0的不是回文//对自己的代码进行了优化，进步很慢，一定坚持，多吸收一些，看大神代码对于语法规范，代码风格，思路实现都有很大的收获if(x < 0 || (x % 10 == 0 && x != 0)) return false;//if(x == 0) return true;//注意避免overflow，以及额外空间问题int revertNumber = 0;while(x > revertNumber){//翻转一半的数字revertNumber = revertNumber * 10 + x % 10;x /= 10;}//注意数字长度奇偶的比较处理return x == revertNumber || x == revertNumber / 10;//时间复杂度O(log n),每次迭代，除以10//空间复杂度O(1),只需要常数空间存放若干变量 }
};

696. 计数二进制子串

? EASY

Q&A
给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。

示例 :
输入: “00110011”
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

输入: “10101”
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
注意：

s.length 在1到50,000之间。
s 只包含“0”或“1”字符。

??【WAY C++ 】 遍历，两侧扩张

class Solution {
public:int countBinarySubstrings(string s) {int res = 0;for(int i = 0;i < s.length() - 1;i++){//从前向后遍历if(s[i] != s[i + 1]){//寻找 0，1相邻，向两侧扩张int left = i;int right = i + 1;while(left > 0 && right < s.length() -1){if((s[left] != s[left - 1]) || (s[right] != s[right + 1]) ){break;}left--;right++;}res += right - i;//符合条件的数量为长度的一半i = right - 1;//直接调到下一个}}return res;}
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-binary-substrings