我目前正在尝试 LeetCode-Merge Strings Alternately 问题。这个问题的描述如下:
“给定两个字符串 word1 和 word2。通过以交替顺序添加字母来合并字符串,从 word1 开始。如果一个字符串比另一个字符串长,则将附加字母附加到合并字符串的末尾。
返回合并后的字符串。”
其中一个测试用例是这样的:
word1 =“rlvrpyrhcxbceffrgiy”; word2 =“ktqi”;
当我在计算机上尝试此测试用例时(我使用的是 CLion 2022.3.3),它工作正常,但是当我尝试运行我的解决方案并在 LeetCode 上测试 tbis 用例时,它会出现运行时错误。
这是我的解决方案:
class Solution {
public:
string mergeAlternately(string word1, string word2) {
string merged;
char *p1,*p2;
string longstring;
if(word1.length() >= word2.length()){
longstring = word1;
}
else{
longstring = word2;
}
for (int i = 0; i < longstring.length(); i++) {
p1 = &word1[i];
p2 = &word2[i];
if(*p1 != '\0' && *p2 != '\0'){
merged += *p1;
merged += *p2;
}
else if(*p1 != '\0' && *p2 == '\0'){
merged += *p1;
}
else if(*p1 == '\0' && *p2 != '\0'){
merged += *p2;
}
}
return merged;
}
};
这是我在 LeetCode 上遇到的错误:
=================================================================
==22==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fa4c5900390 at pc 0x559334397d01 bp 0x7ffebc3d6450 sp 0x7ffebc3d6448
READ of size 1 at 0x7fa4c5900390 thread T0
#3 0x7fa4c7591d8f (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
#4 0x7fa4c7591e3f (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
Address 0x7fa4c5900390 is located in stack of thread T0 at offset 144 in frame
This frame has 3 object(s):
[32, 33) 'ref.tmp'
[48, 80) 'agg.tmp'
[112, 144) 'agg.tmp8' <== Memory access at offset 144 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
(longjmp and C++ exceptions *are* supported)
Shadow bytes around the buggy address:
0x7fa4c5900100: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
0x7fa4c5900180: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
0x7fa4c5900200: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
0x7fa4c5900280: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
0x7fa4c5900300: f1 f1 f1 f1 01 f2 00 00 00 00 f2 f2 f2 f2 00 00
=>0x7fa4c5900380: 00 00[f3]f3 f3 f3 f3 f3 00 00 00 00 00 00 00 00
0x7fa4c5900400: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7fa4c5900480: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7fa4c5900500: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7fa4c5900580: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7fa4c5900600: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==22==ABORTING
请解释为什么会出现这种情况?
如果字符串长度不同,那么您将直接从其中一个字符串的末尾开始运行,因为您始终使用值
i
来获取指向每个字符串的指针,其中 i
迭代最长的字符串.
您可能会在一个字符串中遇到 NULL 终止符,但如果继续循环,您将跳转到内存中的下一个字节并进入未定义行为的领域。
for (int i = 0; i < longstring.length(); i++) {
p1 = &word1[i];
p2 = &word2[i];
// ...
}
您确实应该在一个循环中迭代两个字符串的最短,然后再进行两个循环after来复制剩余的字符。
使用迭代器来完成此操作更干净,完全避免了指针:
string merged;
merged.reserve(word1.size() + word2.size());
// Interleave characters
string::const_iterator p1 = word1.cbegin(), p2 = word2.cbegin();
while (p1 != word1.cend() && p2 != word2.cend()) {
merged += *p1++;
merged += *p2++;
}
// Append remaining characters
merged.append(p1, word1.cend());
merged.append(p2, word2.cend());