今天算是把滑动窗口彻底弄清了，以后遇到应该不会有啥大问题了，至少思路是肯定够了(
(easy)28. 找出字符串中第一个匹配项的下标
以为要用KMP，但看了看数据范围，暴力即可。代码如下：
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
if(n<m)
return -1;
for(int i=0;i<n;i++)
{
int flag = 0;
for(int j=0;j<m&&i+j<n;j++)
{
if(haystack[i+j] != needle[j])
{
break;
}
else
flag = flag + 1;
}
if(flag == m)
return i;
}
return -1;
}
};(hard)68. 文本左右对齐
不说了，字符串苦手真的哭死😭。思路贪心倒是对的，就是啥批字符串一堆特判真给我整破防了，最后还是偷的题解的特判，思路很简单，就是恶心。抄的题解代码如下：
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int n = words.size();
vector<string> ans;
for(int i=0;i<n;i)
{
int cnt=0;
int num=0;
int length=0;
int j=i;
//小于表示可以插入至当前
if(cnt+words[j].size()<=maxWidth)
{
cnt = cnt+words[j].size();
num++;
length = length+words[j].size();
}
j++;
for(j;j<n;j++)
{
//同上，如果加入一个空格可以插入至当前
if(cnt+words[j].size()+1<=maxWidth)
{
cnt=cnt+words[j].size()+1;
length=length+words[j].size();
num++;
}
else
{
break;
}
}
string temp = "";
if(num==1)
{
//只有一个的话就在它后面全加空格
temp+=words[i];
for(int k=0;k<maxWidth-length;k++)
{
temp+=' ';
}
}
else if(num>1)
{
int diff=maxWidth-length;
//前n-1个需要多放的空格为extra,平均分的空格为kong
int extra_kong=diff%(num-1);
int kong=diff/(num-1);
for(int k=i;k<j;k++)
{
temp+=words[k];
//前n-1个
if(k!=j-1)
{
//如果现在需要多放空格
if(extra_kong)
{
for(int m=0;m<=kong;m++)
{
temp+=' ';
}
extra_kong--;
}
else
{
for(int m=0;m<kong;m++)
{
temp+=' ';
}
}
}
}
}
ans.push_back(temp);
i = j;
}
//特判最后一行的
string temp=ans[ans.size()-1];
string temp_ok="";
for(int k=0;k<temp.size();k++)
{
if(temp[k]!=' ')
{
temp_ok+=temp[k];
}
else if(k&&temp[k-1]!=' ')//即是单词结尾的第一个空格
{
temp_ok+=' ';
}
}
for(int k=temp_ok.size();k<maxWidth;k++)
temp_ok+=' ';
ans[ans.size()-1]=temp_ok;
return ans;
}
};(easy)125. 验证回文串
字符串苦手少见的一遍过的题😋。很简单的一个字符处理+回文判断。代码如下：
class Solution {
public:
bool isPalindrome(string s) {
int n=s.size();
int cnt=0;
int diff = 'A'-'a';
for(int i=0;i<n;i++)
{
if(isupper(s[i]))
{
s[cnt]=s[i]-diff;
cnt++;
}
else if(islower(s[i]))
{
s[cnt]=s[i];
cnt++;
}
else if(isalnum(s[i]))
{
s[cnt]=s[i];
cnt++;
}
}
for(int i=0;i<cnt/2;i++)
{
if(s[i]!=s[cnt-i-1])
return 0;
}
return 1;
}
};(easy)392. 判断子序列
虽然是easy题，但按进阶的要求做了下，感觉还行，用指针跑的，代码如下：
int nxt[10010][26];
//int h[10010][26];
//h[i][j]表示i之前的第一个(j+'a')字符的位置,nxt则是之后的第一个
class Solution {
public:
bool isSubsequence(string s, string t) {
//memset(h,0,sizeof(h));
memset(nxt,0,sizeof(nxt));
int n = s.size();
int m = t.size();
if(n==0&&m==0)
return 1;
for(int i=0;i<m;i++)
for(int j=0;j<26;j++)
{
//h[i][j] = -1;
nxt[i][j] = -1;
}
/*for(int i=1;i<m;i++)
{
for(int j=0;j<26;j++)
{
if(h[i-1][j])
h[i][j]=h[i-1][j];
else
h[i][j]=-1;
}
h[i][t[i-1]-'a']=i-1;
}*/
for(int i=m-2;i>=0;i--)
{
for(int j=0;j<26;j++)
{
if(nxt[i+1][j])
nxt[i][j]=nxt[i+1][j];
else
nxt[i][j]=-1;
}
nxt[i][t[i+1]-'a']=i+1;
}
for(int i=0;i<m;i)
{
if(m-i<n)
break;
int cnt=0;
int temp=i;
for(int j=0;j<n&&temp<m;j++)
{
if(t[temp] == s[j])
{
temp++;
cnt++;
}
else if(nxt[temp][s[j]-'a']!=-1)
{
temp=nxt[temp][s[j]-'a'];
j--;
}
else
{
break;
}
}
if(cnt == n)
return 1;
if(temp==i)
temp+=1;
i=temp;
}
return 0;
}
};(medium)209. 长度最小的子数组
写了半小时左右吧。思路其实很简单，就是预处理一个sum[i]表示i到最后一个点所有值的和，这样i到j的和就可以直接表示为sum[i]-sum[j]+nums[j]。然后经典双指针滑动窗口。当然，也可以预处理从最开始的点到i的和，只是我是用的这种方法。代码如下：
int sum[100010];
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
memset(sum,0,sizeof(sum));
int n = nums.size();
sum[n - 1] = nums[n - 1];
int minl = 1e9;
for(int i = n - 2; i >= 0; i--)
sum[i] = sum[i + 1] + nums[i];
int l=0;
int r=0;
while(r<=n-1&&l<=r)
{
if(sum[l]-sum[r]+nums[r] >= target)
{
minl = min(minl,r-l+1);
l++;
}
else
r++;
}
if(minl!=1e9)
return minl;
return 0;
}
};(medium)3. 无重复字符的最长子串
两个版本代码，一个是没有用任何自带数据结构，嗯判一个字符串中是否有重复字母的；另一个是用了hash的。
嗯判版本:
class Solution {
public:
bool check(string s,int l,int r)
{
for(int i=l;i<=r;i++)
{
for(int j=i+1;j<=r;j++)
{
if(s[i] == s[j])
return 0;
}
}
return 1;
}
int lengthOfLongestSubstring(string s) {
int n = s.size();
int l=0;
int r=0;
int maxn=0;
while(l<=r&&r<n)
{
if(r-l+1<maxn)
{
r++;
continue;
}
if(check(s,l,r) == 0)
{
l++;
}
else
{
maxn = max(maxn,r-l+1);
r++;
}
}
return maxn;
}
};hash版本:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> dic;
int res = 0, tmp = 0, len = s.size(), i;
for(int j = 0; j < len; j++) {
if (dic.find(s[j]) == dic.end()) i = - 1;
else i = dic.find(s[j])->second; // 获取索引 i
dic[s[j]] = j; // 更新哈希表
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
};(hard)30. 串联所有单词的子串
经典滑动窗口，最开始想死磕双指针，寄了才开始想滑动窗口。从某种意义上来说算是今天写的最久的一道题了(。
题解给了一个分起点滑动的思路，我觉得很好：即前num2个点都可作为滑动窗口的起点，跑num2次滑动窗口，每次滑动量为num3。我最开始觉得不优化可能寄，没想到写完出来速度比分起点滑动的题解还快？(
优化的思路我一直是想跑深搜，主要是每次dic减1的操作需要回溯，手动回溯感觉有点费时，最后看下来还好？不想用深搜主要是因为力扣这B平台只允许非ACM模式，我如果要深搜由于不是全局字符串，所以每次搜都需要传参，感觉有点得不偿失。代码如下：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int num1 = s.size();
int num2 = words.size();
int num3 = words[0].size();
if(num1<num2*num3)
return {};
vector<int> ans;
unordered_map<string, int> dic;
unordered_map<string, int> dic2;
int allnum = num2 * num3;
for(int i=0;i<num2;i++)
dic[words[i]]++;
for(int i=0;i<num3;i++)
{
//每次都初始化dic2
dic2 = dic;
//i作为滑动窗口的左起点
int r = i;
int cnt = 0;
//每次移动num3个窗口
for(int l = i;l<num1&&l+allnum<=num1;l+=num3)
{
if(r<l)
r = l;
while(r<num1 && dic2[s.substr(r,num3)]>0)
{
cnt++;
dic2[s.substr(r,num3)]--;
r = r + num3;
}
if(cnt == num2)
{
ans.push_back(l);
}
if(cnt)
{
dic2[s.substr(l,num3)]++;
cnt--;
}
}
}
return ans;
}
};(hard)76. 最小覆盖子串
算是滑动窗口自己完整做出来的第一道hard吧，思路就是滑动窗口，我唯一卡的点就在于什么时候移动左窗口，后面想到了移动的条件，但是每次只移动一次，就导致处理有问题，改成每次l都移动到不能再移动就行。尽力优化效率的代码如下：
class Solution {
public:
string minWindow(string s, string t) {
int num1 = s.size();
int num2 = t.size();
string ans = "";
if(num1<num2)
return ans;
int minl = 1e9;
int finall = -1;
unordered_map<char,bool> d;
unordered_map<char,int> d2;
for(int i=0;i<num2;i++)
{
d[t[i]]=1;
d2[t[i]]++;
}
int cnt=0;
int l=0;
int r=0;
int diff = num1-num2;
//while(l<=num1-num2&&r<num1)
while(l<=diff&&r<num1)
{
if(d2[s[r]]>0)
cnt++;
d2[s[r]]--;
if(cnt==num2)
{
while(d[s[l]]==0||d2[s[l]]<0)
{
d2[s[l]]++;
l++;
}
int temp = r-l+1;
if(minl>temp)
{
minl = temp;
finall = l;
}
}
r++;
}
//只在最后把子字符串赋值给ans，提高效率
if(finall!=-1)
ans=s.substr(finall,minl);
return ans;
}
};(medium)36. 有效的数独
纯纯的模拟，没啥好说的。代码如下：
int hang[10][10];
int lie[10][10];
class Solution {
public:
bool check(int i,int j,int toi,int toj)
{
if(i == toi && j == toj)
return 0;
if(abs(toi-i)<=2&&abs(toj-j)<=2)
{
int t1 = i / 3;
int t2 = j / 3;
if(toi<3*t1+3 && toi>=3*t1 && toj<3*t2+3 && toj>=3*t2 )
{
printf("%d %d %d %d\n",i,j,toi,toj);
return 1;
}
}
return 0;
}
bool isValidSudoku(vector<vector<char>>& board) {
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
hang[i][j]=-1;
lie[i][j]=-1;
}
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
putchar(board[i][j]);
putchar(' ');
if(board[i][j]<'1'||board[i][j]>'9')
continue;
int t=board[i][j]-'1';
if(hang[i][t]!=-1)
{
return 0;
}
if(lie[j][t]!=-1)
{
return 0;
}
hang[i][t] = j;
lie[j][t] = i;
}
putchar('\n');
}
for(int i=0;i<9;i+=1)
{
for(int j=0;j<9;j+=1)
{
if(board[i][j]<'1'||board[i][j]>'9')
continue;
int t=board[i][j]-'1';
for(int k=-2;k<=2;k++)
{
if(i+k>=0&&i+k<9&&hang[i+k][t])
{
if(check(i,j,(i+k),hang[i+k][t]))
return 0;
}
if(j+k>=0&&j+k<9&&lie[j+k][t])
{
if(check(i,j,lie[j+k][t],(j+k)))
return 0;
}
}
}
}
return 1;
}
};(medium)54. 螺旋矩阵
难度同上，代码如下：
bool vis[12][12];
int mx[4] = {0,1,0,-1};
int my[4] = {1,0,-1,0};
class Solution {
public:
int m,n,k;
int tempx,tempy;
void check(int i,int j)
{
int temp1 = i+mx[k];
int temp2 = j+my[k];
int cnt2=0;
while(cnt2<=4&&(temp1<0||temp1>=m||temp2<0||temp2>=n||vis[temp1][temp2]))
{
k = (k+1)%4;
cnt2++;
temp1 = i+mx[k];
temp2 = j+my[k];
}
tempx = i+mx[k];
tempy = j+my[k];
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
vector<int> ans;
memset(vis,0,sizeof(vis));
int i=0,j=0;
int cnt = 0;
while(cnt<n*m)
{
ans.push_back(matrix[i][j]);
vis[i][j] = 1;
cnt++;
check(i,j);
i = tempx;
j = tempy;
}
return ans;
}
};