2019 力扣杯全国秋季编程大赛

int game(int* guess, int guessSize, int* answer, int answerSize){
    int ans = 0 ;
    for (int i = 0 ; i < guessSize ; i++){
        if(answer[i]==guess[i])
            ans++;
    }
    return ans;
}

class Solution {
    static long gcd(long a , long b){
        long c = a % b;
        if(c == 0)return b;
        return gcd(b ,c );
    }
    public int[] fraction(int[] cont) {
        int len = cont.length-1;
        long temp1 = cont[len--];
        long temp2 = 1;
        int ans [] = new int [2];

        while(len>= 0){
            long flag = temp1 * cont[len] +temp2;     //核心一步
            temp2 = temp1;                            //核心一步
            temp1 = flag ;                            //核心一步
            len--;
        }
        long gcd = gcd(temp1 , temp2);
        ans[0] = (int)(temp1 / gcd);
        ans[1] = (int)(temp2 / gcd);
        return ans;
    }
}

第三题第一种做法 超时

class Solution {
    public boolean robot(String command, int[][] obstacles, int x, int y) {
        boolean [][] bool = new boolean [x+1][y+1];
        for(int i = 0 ; i < obstacles.length ; i ++){
            int x1 = obstacles[i][0];
            int y1 = obstacles[i][1];
            if(x1<=x&&y1<=y)
                bool[x1][y1] = true;
        }
        int x2 = 0 ;
        int y2 = 0 ;
        int flag = 0;
        int len = command.length();
        while(x2 < x && y2 < y){
            char temp = command.charAt(flag%len);
            if(temp == 'U')y2++;
            if(temp == 'R')x2++;
            if(bool[x2][y2]==true)return false;
            flag ++;
        }

        while(x2 < x){
            char temp = command.charAt(flag%len);

            if(temp == 'U')return false;
            if(temp == 'R')x2++;
            flag ++;
        }

        while( y2 < y){
            char temp = command.charAt(flag%len);
            if(temp == 'U')y2++;
            if(temp == 'R')return false;
            flag ++;
        }

        if(x2==x&&y2==y)return true;
        return false;
    }
}

第二种做法 ac 优化第一种

class Solution {
    public boolean robot(String command, int[][] obstacles, int x, int y) {
        Map<Integer,Set<Integer>>map = new HashMap();
        for(int i = 0 ; i < obstacles.length ; i ++){
            int a = obstacles[i][0];
            int b = obstacles[i][1];
            if (!map.containsKey(a)) map.put(a, new HashSet<>()); 
            map.get(a).add(b);
        }
        int r = 0, u = 0;
        while (true) {
            for (char ch: command.toCharArray()) {  //这一步处理得很好
                if (r == x && u == y) return true;
                switch (ch) {
                    case 'U': ++u; break;
                    case 'R': ++r; break;
                }
                if (map.containsKey(r) && map.get(r).contains(u)) return false;
                if (r > x || u > y) return false;
            }
        }
    }
}

第三种解法 比较实际点 判断前面障碍是否能达到，判断终点是否能到达

class Solution {
    private static char command_char[];
    private static int command_R;
    private static int command_U;
    public boolean robot(String command, int[][] obstacles, int x, int y) {
        init(command);
        if(!arrive(x,y))return false;
        for(int i = 0 ; i < obstacles.length ;i++){
            int dx = obstacles[i][0];
            int dy = obstacles[i][1];
            if(dx <= x && dy <= y&&arrive(dx,dy)) return false;
        }
        return true;
    }
    private static boolean arrive(int dx , int dy){
        int t = Math.min(dx/command_R,dy/command_U);
        dx -= t* command_R;
        dy -= t* command_U;
        if(dx==0&&dy==0)return true;
        for(char c : command_char ){
            if(c == 'U')dy--;
            else dx--;
            if(dx==0&&dy==0)return true;
        }
        return false;
    }
    private static void init(String command){
        command_R = 0;
        command_U = 0;
        command_char = command.toCharArray();
        for(char c :command_char){
            if(c=='U'){
                command_U++;
            }
            else command_R++;
        }
    }
}