surrounded-regions merge-intervals

最近刷了leetcode上有关数组的题，在这里做一个总结。

1. surrounded-regions

思路：将所有能被包围的'O'全部转化为’X‘ => 除了边界上以及所有与边界上的’O‘相连的’O‘全部被转化。

知识点：dfs深度遍历边界上以及所有与边界上的’O‘相连的’O‘

class Solution {
public:
    int rownum = 0;
    int colnum = 0;
    void solve(vector<vector<char>> &board) {
        if(board.size()==0)return;
        if(board.at(0).size()==0)return;
        rownum = board.size();
        colnum = board[0].size();
        for(int i=0;i<rownum;i++){
            dfs(board,i,0);
            dfs(board,i,colnum-1);
        }
        for(int i=0;i<colnum;i++){
            dfs(board,0,i);
            dfs(board,rownum-1,i);
        }
        for(int i=0;i<rownum;i++){
            for(int j=0;j<colnum;j++){
                if(board[i][j]=='O')
                    board[i][j]='X';
            }
        }
        for(int i=0;i<rownum;i++){
            for(int j=0;j<colnum;j++){
                if(board[i][j]=='*')
                    board[i][j]='O';
            }
        }
    }
    void dfs(vector<vector<char>> &board,int row,int col){
        if(board[row][col]=='O'){
            board[row][col]='*';
            if(row<rownum-1)dfs(board,row+1,col);
            if(row>0)dfs(board,row-1,col);
            if(col<colnum-1)dfs(board,row,col+1);
            if(col>0)dfs(board,row,col-1);
        }
        
    }
};

2. merge-intervals

思路：思路很简单先按每个数组起始位置的大小顺序排列好，然后不断从前往后合并即可。这种题一定要考虑特殊情况，比如如果输入为空或只输入一个数组的时候，不要只考虑普遍情况而出现数组越界。

 1 class Solution {
 2 public:
 3     static bool compare(Interval a,Interval b){
 4         return (a.start<b.start);
 5     }
 6     vector<Interval> merge(vector<Interval> &intervals) {
 7         int num=0;
 8         if(intervals.size()==0||intervals.size()==1)return intervals;10         sort(intervals.begin(),intervals.end(),compare);
11         for(int i=1;i<intervals.size();i++){
12             if(intervals[i].end>=intervals[i-1].start&&intervals[i].start<=intervals[i-1].end){
13                 intervals[i].start=min(intervals[i].start,intervals[i-1].start);
14                 intervals[i].end=max(intervals[i].end,intervals[i-1].end);
15                 intervals[i-1].start=-1000000;
16                 num++;
17             }
18        }
19         vector<Interval> res;
20         for(int i=0;i<intervals.size();i++){
21             if(intervals[i].start!=-1000000)
22                 res.push_back(intervals.at(i));
23         }           
24         return res;
25     }
26 };