今天开始刷leetcode中文版，为什么，可能是因为无聊吧。按照顺序，全程使用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]);
}

第二题，机器人大冒险

我一开始的思路是：对于每个位置，检测是否碰撞。结果，我第一版提交的代码遇见了超时。第一版代码如下：

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);//指令数组长度获取
    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++;
    } 
}

很明显，第一版代码的复杂度是O(n^2)。在第二版中我稍稍修改了检测碰撞的函数。我去掉了一些第二版代码如下：

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);//指令数组长度获取
    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);
    //两个数组，分别存放x和y变动时对应的y和x值（视作两个函数）
    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;
}

非主流方法