841. 钥匙和房间

class Solution {
public:bool canVisitAllRooms(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)return false;}return true;}
};

463. 岛屿的周长

class Solution {int xianglin(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++;return 4-count;}
public:int islandPerimeter(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算法，难点是构造理解前缀表数组，前缀表里面的数字代表和前一个比他的重复情况，前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

class Solution {void getnext(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:bool repeatedSubstringPattern(string s) {if(s.size()==0)return false;int next[s.size()];getnext(next,s);int len = s.size();if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {return true;}return false;}
};

28. 实现 strStr()

class Solution {void getnext(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:int strStr(string haystack, string needle) {if(needle.size()==0)return 0;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;}
};