今天開始刷leetcode中文版，為什么，可能是因?yàn)闊o聊吧。按照順序，全程使用C語言（不排除真香警告）。

第一題，找不同

這個題比較簡單，不過還是擊敗了100% 2333。

int game(int* guess, int guessSize, int* answer, int answerSize){
    return (guess[0]==answer[0])+(guess[1]==answer[1])+(guess[2]==answer[2]);
}

第二題，機(jī)器人大冒險

我一開始的思路是：對于每個位置，檢測是否碰撞。結(jié)果，我第一版提交的代碼遇見了超時。第一版代碼如下：

bool arrived(int currentX, int currentY, int targetX, int targetY ){
    if(currentX==targetX&&currentY==targetY)
        return true;
    return false;    
}

bool collision(int currentX, int currentY, int** obstacles, int obstaclesSize){
    int i=0,j=0;
    for(i=0;i<obstaclesSize;i++){
        if(currentX==obstacles[i][0]&&currentY==obstacles[i][1])
            return true;
    }
    return false;
}

bool robot(char* command, int** obstacles, int obstaclesSize, int* obstaclesColSize, int x, int y){
    int i=0;
    int currentX=0,currentY=0;
    int command_length=strlen(command);//指令數(shù)組長度獲取
    int command_index=0;
    while(true){
        if(arrived(currentX,currentY,x,y))
            return true;
        if(currentX>x||currentY>y)
            return false;
        if(collision(currentX, currentY, obstacles, obstaclesSize))
            return false;
        command_index=i%command_length;
        if(command[command_index]=='U')
            currentY++;
        else
           currentX++;
        i++;
    } 
}

很明顯，第一版代碼的復(fù)雜度是O(n^2)。在第二版中我稍稍修改了檢測碰撞的函數(shù)。我去掉了一些第二版代碼如下：

void move_tail(int i, int** obstacles, int *obstaclesSize){
    int x=0,y=0;
    x=obstacles[i][0];
    y=obstacles[i][1];
    obstacles[i][0]=obstacles[(*obstaclesSize)-1][0];
    obstacles[i][1]=obstacles[(*obstaclesSize)-1][1];
    obstacles[(*obstaclesSize)-1][0]=x;
    obstacles[(*obstaclesSize)-1][1]=y; 
}

bool arrived(int currentX, int currentY, int targetX, int targetY ){
    if(currentX==targetX&&currentY==targetY)  
        return true;
    return false;    
}

bool collision(int currentX, int currentY, int** obstacles, int *obstaclesSize){
    int i=0,j=0;

    for(i=0;i<(*obstaclesSize);i++){
        if(currentX==obstacles[i][0]&&currentY==obstacles[i][1])
            return true;
        if(currentX>obstacles[i][0]||currentY>obstacles[i][1]){
            move_tail(i, obstacles,obstaclesSize);
            (*obstaclesSize)--;
        }
    }
    return false;
}

bool robot(char* command, int** obstacles, int obstaclesSize, int* obstaclesColSize, int x, int y){
    int i=0;
    int currentX=0,currentY=0;
    int command_length=strlen(command);//指令數(shù)組長度獲取
    int command_index=0;
    while(true){
        if(arrived(currentX,currentY,x,y))
            return true;
        if(currentX>x||currentY>y)
            return false;
        if(collision(currentX, currentY, obstacles, &obstaclesSize))
            return false;
        command_index=i%command_length;
        if(command[command_index]=='U')
            currentY++;
        else
           currentX++;
        i++;
    } 
}

然而還是超時?？磥恚业牡谝粋€思路是不適合的。
第三版：

bool robot(char * command, int** obstacles, int obstaclesSize, int* obstaclesColSize, int x, int y){
    int i=0;
    int currentX=0,currentY=0;
    int command_index=0;
    //命令長度
    int command_length=strlen(command);
    //兩個數(shù)組，分別存放x和y變動時對應(yīng)的y和x值（視作兩個函數(shù)）
    int* position_x_array=(int *)calloc(sizeof(int),x+1);
    int* position_y_array=(int *)calloc(sizeof(int),y+1);

    while(true){
        command_index=i%command_length;
        if(command[command_index]=='U'){
            currentY++;
            if(currentY>y)
                break;
            position_y_array[currentY]=currentX;
        } 
        else{
            currentX++;
            if(currentX>x)
                break;
            position_x_array[currentX]=currentY;
        }
        i++;
    }
    
   
    if((position_x_array[x]!=y)&&(position_y_array[y]!=x))
        return false;
    
    for(i=0;i<obstaclesSize;i++){
        if(obstacles[i][0]>x||obstacles[i][1]>y)
            continue;
        if(position_x_array[obstacles[i][0]]==obstacles[i][1]||position_y_array[obstacles[i][1]]==obstacles[i][0])
            return false;
    }
    return true;
}

非主流方法