问题遇到的现象和发生背景
力扣76.最小覆盖子串,请用通俗的语言概括一下下边这段错误提示的意思。
同时,贴上我的代码
遇到的现象和发生背景,请写出第一个错误信息
报错内容:
Line 137: Char 23: runtime error: constructor call on misaligned address 0xbebebebebebec0ba for type 'int', which requires 4 byte alignment (new_allocator.h)
: note: pointer points here
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/ext/new_allocator.h:146:23
用代码块功能插入代码,请勿粘贴截图。 不用代码块回答率下降 50%
class Solution {
public:
static bool compSL(deque<int>& a,deque<int>& b)
{
if(a.empty()) return 0;
if(b.empty()) return 1;
return a.front()<b.front();
}
static bool compSR(deque<int>& c,deque<int>& d)
{
if(c.empty()) return 0;
if(d.empty()) return 1;
return c.back()>d.back();
}
void DFS(int k,string t,vector<int> sUCnt,vector<int> sLCnt,vector<deque<int>> sU,vector<deque<int>> sL)
{
if(k==n)
{
sort(tU.begin(),tU.end(),compSL);ul=tU[0].empty()? INT_MAX:tU[0].front();
sort(tU.begin(),tU.end(),compSR);ur=tU[0].empty()? INT_MIN:tU[0].back();
sort(tL.begin(),tL.end(),compSL);ll=tL[0].empty()? INT_MAX:tL[0].front();
sort(tL.begin(),tL.end(),compSR);lr=tL[0].empty()? INT_MIN:tL[0].back();
mx=max(ur,lr);mn=min(ul,ll);
tmp=mx-mn;
if(tmp+1<=len)
{
beg=mn;
len=tmp+1;
}
return;
}
int j=t[k]-'A',e;
if(j<26)
{
tUCnt[j]--;
while(!sU[j].empty())
{
sUCnt[j]--;
if(tUCnt[j]>sUCnt[j]) break;
e=sU[j].front();
tU[j].push_back(e);
sU[j].pop_front();
DFS(k+1,t,sUCnt,sLCnt,sU,sL);
tU[j].pop_back();
}
tUCnt[j]++;
}
else
{
j=t[k]-'a';
tLCnt[j]--;
while(!sL[j].empty())
{
sLCnt[j]--;
if(tLCnt[j]>sLCnt[j]) break;
e=sL[j].front();
tL[j].push_back(e);
sL[j].pop_front();
DFS(k+1,t,sUCnt,sLCnt,sU,sL);
tL[j].pop_back();
}
tLCnt[j]++;
}
}
string minWindow(string s, string t)
{
m=s.size();
n=t.size();
len=m;
vector<int> sUCnt(26),sLCnt;
vector<deque<int>> sU(26),sL;
tLCnt=sLCnt=tUCnt=sUCnt;
tL=sL=tU=sU;
for(int i=0,j;i<m;i++)
{
j=s[i]-'A';
if(j<26)
{
sUCnt[j]++;
sU[j].push_back(i);
}
else
{
j=s[i]-'a';
sLCnt[j]++;
sL[j].push_back(i);
}
}
for(int i=0,j;i<n;i++)
{
j=t[i]-'A';
if(j<26)
{
if(tUCnt[j]==sUCnt[j]) return {};
tUCnt[j]++;
}
else
{
j=t[i]-'a';
if(tLCnt[j]==sLCnt[j]) return {};
tLCnt[j]++;
}
}
DFS(0,t,sUCnt,sLCnt,sU,sL);
return s.substr(beg,len);
}
private:
int m,n,tmp,beg,len,ul,ur,ll,lr,mx,mn;
vector<int> tUCnt,tLCnt;
vector<deque<int>> tU,tL;
};
运行结果及详细报错内容
我的解答思路和尝试过的方法,不写自己思路的,回答率下降 60%
我的代码怎么改是次要的,最主要想请教错误提示想要表达什么?
如果可能,我还是希望能用回溯法解题
我先分别对字符串s、t包含的字母统计数量。然后定义4个队列数组,其中两个用于存储s中各字母在s中的位置序号,另外两个用于存储t中各字母在字符串s中可能的位置序号。假如t中某一个字母的剩余数大于s中的剩余数,则终止当前操作,回退数据状态,不再进入更深的一层搜索。只要sU、sL当前字母的队列里还存有序号,则while循环不会停止。当k==n时,说明t中每个字母都匹配到了一个序号,通过自定义sort函数对匹配得到的所有序号进行排序,然后使其中最大值和最小值相减,取得包含t中所有字母的字符串长度,最后通过回溯的方式,找到满足题意长度最小的字符串。