Closed. This question needs debugging details。它当前不接受答案。
想改善这个问题吗?更新问题,以便将其作为on-topic用于堆栈溢出。
5个月前关闭。
Improve this question
这是我的Leetcode 1366,代码,不适用于某些测试用例,例如[“XYZ”,“XZY”]
我对算法很确定,即使用成对的字符 vector 和 vector 作为 map 。我认为代码有问题,而不是算法有问题。
特别是,错误消息显示-
引用文献
有关更多详细信息,请参见Discussion Board。那里有许多公认的解决方案,解释,使用多种语言的有效算法以及时空复杂性分析。 ASCII Chart 1366. Rank Teams by Votes 1366. Rank Teams by Votes - Discussion Board
想改善这个问题吗?更新问题,以便将其作为on-topic用于堆栈溢出。
5个月前关闭。
Improve this question
这是我的Leetcode 1366,代码,不适用于某些测试用例,例如[“XYZ”,“XZY”]
我对算法很确定,即使用成对的字符 vector 和 vector 作为 map 。我认为代码有问题,而不是算法有问题。
class Solution {
public:
string rankTeams(vector<string>& votes) {
int n = votes.size();
int m = votes[0].length();
if(n==1) return votes[0];
if(m==1) return votes[0];
string temp = votes[0];
sort(temp.begin(), temp.end());
vector<pair<char,vector<int>>> map(m);
vector<int> vec(m,0);
for(int i=0;i<m;i++){
map[i].first = temp[i];
map[i].second = vec;
}
//initialize the map
for(int i=0;i<n;i++){ //pick a voter
for(int j=0;j<m;j++){ //pick votes
map[votes[i][j] - 'A'].second[j]++;
}
}
sort(map.begin(), map.end(), [&](pair<char,vector<int>> pair1, pair<char,vector<int>> pair2){
for(int pos=0;pos<m;pos++){
if((pair1.second)[pos] > (pair2.second)[pos]) return true;
else if((pair1.second)[pos] < (pair2.second)[pos]) return false;
//else if((pair1.second)[pos] == (pair2.second)[pos]) continue;
}
return pair1.first < pair2.first;
});
string result;
for(int i=0;i<m;i++) result[i] = map[i].first;
return result;
}
};
特别是,错误消息显示-
Runtime Error
=================================================================
==33==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x608000000308 at pc 0x00000038d06a bp 0x7ffe00621720 sp 0x7ffe00621718
READ of size 8 at 0x608000000308 thread T0
#4 0x7f57283cd82f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
Address 0x608000000308 is a wild pointer.
Shadow bytes around the buggy address:
0x0c107fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c107fff8060: fa[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff80a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff80b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
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
Shadow gap: cc
==33==ABORTING
最佳答案
这个问题的“在线裁判”中存在一个错误,我想LeetCode应该对此进行修复。除此之外,以下解决方案是可以接受的解决方案,并且简单得多:
class Solution {
public:
string rankTeams(vector<string> &votes) {
vector<vector<int>> count_map(26, vector<int>(27));
for (char &character : votes[0])
count_map[character - 65][26] = character;
for (string &vote : votes)
for (int index = 0; index < vote.length(); index++)
count_map[vote[index] - 65][index]--;
sort(count_map.begin(), count_map.end());
string sorted_teams;
for (int index = 0; index < votes[0].length(); index++)
sorted_teams += count_map[index][26];
return sorted_teams;
}
};
如果要面试,请确保以一致的风格编写简洁的代码。引用文献
10-07 15:21