leetcode419
很久 没用dfs了,有点陌生,稍微复习了一下。求连通分量的题,深搜的应用。
class Solution {
public:
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool visited[1001][1001];
void dfs(int x,int y,vector<vector<char>>& board)
{
int raws = board.size();
int cols = board[0].size();
for(int i=0;i<4;i++){
int a=x+dir[i][0];
int b=y+dir[i][1];
if(a<0||a>=raws||b<0||b>=cols) //越界处理
continue;
if(board[a][b]=='X'&&!visited[a][b]){
visited[a][b]=1;
dfs(a,b,board);
}
}
}
int countBattleships(vector<vector<char>>& board) {
int raws = board.size();
int cols = board[0].size();
int res=0;
for(int i=0;i<raws;i++)
{
for(int j=0;j<cols;j++)
{
if(board[i][j]=='X'&&!visited[i][j])
{
dfs(i,j,board);
res++;
}
}
}
return res;
}
};
leetcode189
很简单的一道题
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int length=nums.size();
int v[200005];
for(int i=0;i<length;i++)
{
v[(i+k)%length]=nums[i];
}
for(int i=0;i<length;i++)
nums[i]=v[i];
}
};
leetcode54
这是一道入门级别的模拟题 ,很早以前就写过
花费了好久时间 功力退步 今天看了以前的算法书 还是有许多需要熟练的地方
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rows=matrix.size();
int cols=matrix[0].size();
int left=0,right=cols-1;
int up=0,down=rows-1;
int x,y,u,v;
vector<int>cv;
while(true)
{
x=left;
while(x<=right){
cv.push_back(matrix[up][x++]);
}
if(++up>down)break;
y=up;
while(y<=down){
cv.push_back(matrix[y++][right]);
}
if(--right<left)break;
u=right;
while(u>=left)
{
cv.push_back(matrix[down][u--]);
}
if(--down<up)break;
v=down;
while(v>=up)
{
cv.push_back(matrix[v--][left]);
}
if(++left>right)break;
}
return cv;
}
};