class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 双指针
int res = 0;
unordered_map<char, int> heap;
for(int l = 0, r = 0; r < s.size(); r++)
{
heap[s[r]]++;
while (heap[s[r]] > 1) heap[s[l++]] --; // 逐渐删除
res = max(res, r - l + 1);
}
return res;
}
};
字符串哈希: base = 131或者13331, h[r] - h[l - 1] * p[r - l + 1]
记得初始化p[0] = 1（p是用来记录base的p次幂的）
typedef unsigned long long ULL;
class Solution {
public:
static const int N = 2020, base = 131;
ULL hl[N], hr[N], p[N];
char str[N];
public:
ULL get(ULL h[], int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
string longestPalindrome(string s) {
// 最长回文子串 - 马拉车 类似kmp o(n)
// 字符串哈希 + 二分 o(nlogn)
// 回文串 (左右对称的串)
int n = 2 * s.size(), res = 0, i_idx = 0;
p[0] = 1;
strcpy(str + 1, s.c_str());
for(int i = n; i > 0; i -= 2)
{
str[i] = str[i / 2];
str[i - 1] = 'a' + 27;
}
for(int i = 1, j = n; i <= n; i++, j--)
{
hl[i] = hl[i - 1] * base + str[i] - 'a' + 1;
hr[i] = hr[i - 1] * base + str[j] - 'a' + 1;
p[i] = p[i - 1] * base;
}
// 二分长度
// 记录长度与中间位置
for(int i = 1; i <= n; i++)
{
int l = 0, r = min(n - i, i - 1);
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(get(hl, i - mid, i - 1) != get(hr, n - (i + mid) + 1, n - (i + 1) + 1))
r = mid - 1;
else
l = mid;
}
// 判断原始长度(未加27)
if(str[i - l] <= 'z')
l ++;
if(res < l)
{
res = l;
i_idx = i;
}
}
return s.substr((i_idx - res) / 2, res);
}
};
另外补一个动态规划的o(n^2)算法，注意下遍历顺序是长度-> 起点即可
class Solution {
public:
static const int N = 1010;
bool f[N][N];
string longestPalindrome(string s) {
memset(f, false, sizeof f);
int n = s.size();
int max_len = 0, start = 0;
for(int l = 1; l <= n; l++)
for(int i = 0; i + l - 1 < n; i++){
int left = i, right = i + l - 1;
if(l == 1) f[left][right] = true;
else if(l == 2) f[left][right] = (s[left] == s[right]);
else f[left][right] = f[left + 1][right - 1] && (s[left] == s[right]);
if(f[left][right] && l > max_len) max_len = l, start = left;
}
return s.substr(start, max_len);
}
};
06 - Z字形变换
等差数列找规律的问题 注意开一个字符串数组 别用+
class Solution {
public:
string convert(string s, int k) {
int n = s.size(), cnt = 0;
char str[n + 1];
if(k == 1) return s;
for(int i = 0; i < k; i++)
{
if(i == 0 || i == k - 1)
{
for(int j = i; j < n; j += 2 * k - 2)
{
str[cnt++] = s[j];
}
}
else
{
for(int j = i, m = 2 * k - 2 - i; j < n || m < n; j += 2 *k - 2, m += 2 * k - 2)
{
if(j < n) str[cnt++] = s[j];
if(m < n) str[cnt++] = s[m];
}
}
}
str[cnt] = '0';
return string(str);
}
};
07 - 整数反转
注意的点在于 -4 % 10 = -4 （在c++中) 而python和数学的定义都是等于6的
所以下面的代码可以同时处理正数和负数的情况；
class Solution {
public:
int reverse(int x) {
// 溢出怎么搞?
long long res = 0;
while(x)
{
res = res * 10 + x % 10;
x /= 10;
}
if(res > INT_MAX || res < INT_MIN)
return 0;
else
return res;
}
};
08 - 实现atoi
模拟 判断是否为数字 isdigit()
class Solution {
public:
int myAtoi(string s) {
int k = 0;
// 1. 去掉字符串首的空格
while(k < s.size() && s[k] == ' ')
k++;
if(k == s.size()) return 0;
//2. 处理符号
int minus = 1;
if(s[k] == '-')
{
minus = -1;
k++;
}
else if(s[k] == '+')
k++;
long long res = 0;
// 直接处理数字
while(k < s.size() && isdigit(s[k]))
{
res = res * 10 + s[k] - '0';
if(res > INT_MAX) break;
k++;
}
res = res * minus;
if(res > INT_MAX) return INT_MAX;
if(res < INT_MIN) return INT_MIN;
return res;
}
};
09 - 回文数
字符串方法
记一下cpp中如何反转字符串
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0)
return false;
string s = to_string(x); // int转str
return s == string(s.rbegin(), s.rend());
}
};