2021.9.6

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;
    }
};
上一篇:JSP--监听HTTP会话


下一篇:Leetcode - 37. 解数独