Closed. This question needs debugging details。它当前不接受答案。












想改善这个问题吗?更新问题,以便将其作为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;
    }
};
如果要面试,请确保以一致的风格编写简洁的代码。

引用文献
  • 有关更多详细信息,请参见Discussion Board。那里有许多公认的解决方案,解释,使用多种语言的有效算法以及时空复杂性分析。
  • ASCII Chart
  • 1366. Rank Teams by Votes
  • 1366. Rank Teams by Votes - Discussion Board
  • 10-07 15:21