c++ beats 99.32% BFS+DFS solution


  • 0
    Y
    struct customLess{
        bool operator()(int *a, int *b)
        {   
            return a[2] > b[2];
        }   
    };
    class Solution {
    public:
    
        priority_queue <int*,vector<int*>,customLess> pq;
        int dfs(vector<vector<int>> &map,vector<vector<int>> &visited,int i,int j,int h, int st){
            int r=map.size(),c=map[0].size();
            if(i>=r||i<0||j>c-1||j<0||(visited[i][j]&&st!=0)) return 0;
            visited[i][j]=1;
            if(map[i][j]>h){
                pq.push(new int[3]{i,j,map[i][j]});
                return 0;
            }
            
            return dfs(map,visited,i+1,j,h,1)+dfs(map,visited,i,j+1,h,1)+dfs(map,visited,i-1,j,h,1)+dfs(map,visited,i,j-1,h,1)+h-map[i][j];
        }
        int trapRainWater(vector<vector<int>>& heightMap) {
            if(heightMap.size()<3) return 0;
            if(heightMap[0].size()<3) return 0;
            vector<int> tmpv(heightMap[0].size(),0);
            vector<vector<int>> visited(heightMap.size(),tmpv);
            int r=heightMap.size(),c=heightMap[0].size(),i,j,k,rst=0;
            int *tmp,*tmp2;
            for(i=0;i<r;i++){
                tmp=new int[3];
                tmp[0]=i,tmp[1]=0,tmp[2]=heightMap[i][0];
                pq.push(tmp);
                tmp=new int[3];
                tmp[0]=i,tmp[1]=c-1,tmp[2]=heightMap[i][c-1];
                pq.push(tmp);
            }
            for(j=1;j<c-1;j++){
                tmp=new int[3];
                tmp[0]=0,tmp[1]=j,tmp[2]=heightMap[0][j];
                pq.push(tmp);
                tmp=new int[3];
                tmp[0]=r-1,tmp[1]=j,tmp[2]=heightMap[r-1][j];
                pq.push(tmp);            
            }
            while(!pq.empty()){
                tmp2=pq.top();
                pq.pop();
                rst+=dfs(heightMap,visited,tmp2[0],tmp2[1],tmp2[2],0);
            }
            return rst;
        }
    };
    

  • 0
    S

    Memory Leak. I see new but no delete!


  • 0
    Y

    @simonwoo For interview questions, I would say that if you just run this algorithm several times and close it, it doesn't matter because operating system will take care of memory leaks once the process is terminated. It really depends on how you want to use the program.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.