代码随想录算法训练营第九天|841. 钥匙和房间|463. 岛屿的周长|459. 重复的子字符串

841. 钥匙和房间

classSolution{public:boolcanVisitAllRooms(vector<vector<int>>& rooms){
        queue<vector<int>>que;
        vector<bool>visited(rooms.size(),false);
        que.push(rooms[0]);
        visited[0]=true;while(!que.empty()){
            vector<int>vec=que.front();
            que.pop();for(int i=0;i<vec.size();i++){if(visited[vec[i]]==false){
                    que.push(rooms[vec[i]]);
                    visited[vec[i]]=true;}}}for(int i=0;i<visited.size();i++){if(visited[i]==false)returnfalse;}returntrue;}};

463. 岛屿的周长

classSolution{intxianglin(vector<vector<int>>& grid,int i,int j){int count =0;if(i>0&&grid[i-1][j]==1)count++;if(i<grid.size()-1&&grid[i+1][j]==1)count++;if(j>0&&grid[i][j-1]==1)count++;if(j<grid[0].size()-1&&grid[i][j+1]==1)count++;return4-count;}public:intislandPerimeter(vector<vector<int>>& grid){int res=0;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[0].size();j++){if(grid[i][j]==1){
                    res+=xianglin(grid,i,j);}}}return res;}};

459. 重复的子字符串

考察kmp算法，难点是构造理解前缀表数组，前缀表里面的数字代表和前一个比他的重复情况，前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

classSolution{voidgetnext(int* next,const string& s){
        next[0]=0;int j=0;for(int i=1;i<s.size();i++){while(j>0&&s[i]!=s[j]){
                j=next[j-1];}if(s[i]==s[j]){j++;}
            next[i]=j;}}public:boolrepeatedSubstringPattern(string s){if(s.size()==0)returnfalse;int next[s.size()];getnext(next,s);int len = s.size();if(next[len -1]!=0&& len %(len -(next[len -1]))==0){returntrue;}returnfalse;}};

28. 实现 strStr()

classSolution{voidgetnext(int*next,const string&haystack){
        next[0]=0;int j=0;for(int i=1;i<haystack.size();i++){while(j>0&&haystack[i]!=haystack[j]){
                j=next[j-1];}if(haystack[i]==haystack[j])j++;
            next[i]=j;}}public:intstrStr(string haystack, string needle){if(needle.size()==0)return0;int next[needle.size()];getnext(next,needle);int j=0;for(int i=0;i<haystack.size();i++){while(j>0&&haystack[i]!=needle[j]){
                j=next[j-1];}if(haystack[i]==needle[j])j++;if(j==needle.size()){return i-j+1;}}return-1;}};