Walking Robot Simulation 模擬行走機(jī)器人

問題描述：

機(jī)器人在一個(gè)無限大小的 XY 網(wǎng)格平面上行走，從點(diǎn) (0, 0) 處開始出發(fā)，面向北方。該機(jī)器人可以接收以下三種類型的命令 commands ：

-2 ：向左轉(zhuǎn) 90 度
-1 ：向右轉(zhuǎn) 90 度
$1<=x<=9$ ：向前移動(dòng) x 個(gè)單位長(zhǎng)度
在網(wǎng)格上有一些格子被視為障礙物 obstacles 。第 i 個(gè)障礙物位于網(wǎng)格點(diǎn) $obstacles[i]=(x_i,y_i)$。

機(jī)器人無法走到障礙物上，它將會(huì)停留在障礙物的前一個(gè)網(wǎng)格方塊上，但仍然可以繼續(xù)嘗試進(jìn)行該路線的其余部分。

返回從原點(diǎn)到機(jī)器人所有經(jīng)過的路徑點(diǎn)（坐標(biāo)為整數(shù)）的最大歐式距離的平方。（即，如果距離為 5 ，則返回 25 ）

$$\begin{gathered} 1<=commands.length<=10^4 \\ commands[i]isoneofthevaluesinthelist[?2,?1,1,2,3,4,5,6,7,8,9] \\ 0<=obstacles.length<=10^4 \\ ?3?10^4<=xi,yi<=3?10^4 \\ 答案保證小于2^{31} \end{gathered}$$

分析

模擬問題屬于看上去很簡(jiǎn)單，但是做起來處處是坑。

這個(gè)問題中，可以移動(dòng)的范圍可以看做是一個(gè)二維直角坐標(biāo)系。起始點(diǎn)是原點(diǎn)[0,0],這個(gè)移動(dòng)范圍是不受邊界限制的，它不同于一般的矩陣，有行列大小限制。

加速可以使用二分

當(dāng)然也可以使用二分，在移動(dòng)的過程中使用二分來快速判斷是否會(huì)遇到obstacle，整體時(shí)間復(fù)雜度$O(N+M?ClogX)$

代碼

二分

class Solution {
    int INF = Integer.MAX_VALUE;
    public int robotSim(int[] commands, int[][] obstacles) {
        Map<Integer,List<Integer>> mapx = new HashMap();
        Map<Integer,List<Integer>> mapy = new HashMap();
        for(int [] obs :obstacles){
            int x = obs[0],y = obs[1];
            List<Integer> xlist = mapx.getOrDefault(x,new ArrayList());
            List<Integer> ylist = mapy.getOrDefault(y,new ArrayList()); 
            xlist.add(y);
            ylist.add(x);
            mapx.put(x,xlist);
            mapy.put(y,ylist);        
        }
        for(int k : mapx.keySet()){
            List<Integer> list = mapx.get(k);
            Collections.sort(list);
            mapx.put(k,list);
        }
        for(int k : mapy.keySet()){
            List<Integer> list = mapy.get(k);
            Collections.sort(list);
            mapy.put(k,list);
        }
        int d = 0; // direction
        int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};// N,E,S,W

        int n = commands.length;
        int idx = 0,cx = 0,cy = 0,ans=0;
        while(idx<n){
            int c = commands[idx];
            if(c<0){ 
                if(c==-2) d = (d+3)%4;
                else d = (d+1)%4; 
            }
            else{                
                int nx = cx+ dir[d][0]*c;
                int ny = cy+ dir[d][1]*c;
                int obs = INF;
                if(d%2==0){
                    // N S 
                    if(d==0){
                        if(mapx.containsKey(cx)){
                            obs = find1(mapx.get(cx),cy);
                        }
                        if(obs!=INF&&obs<=ny){
                            ny = obs-1;
                        }
                    }
                    else{
                        if(mapx.containsKey(cx)){ 
                            obs = find2(mapx.get(cx),cy); 
                        }
                        if(obs!=INF&&obs>=ny){
                            ny = obs+1;
                        }
                    }  
                }
                else{
                    // E W
                    if(d==1){
                        if(mapy.containsKey(cy)){
                            obs = find1(mapy.get(cy),cx);
                        }
                        if(obs!=INF&&obs<=nx){
                            nx = obs-1;
                        }
                    }
                    else{
                        if(mapy.containsKey(cy)){

                            obs = find2(mapy.get(cy),cx);
                        }
                        if(obs!=INF&&obs>=nx){
                            nx = obs+1;
                        }
                    } 
                } 
                int res = nx*nx + ny*ny;
                ans = Math.max(ans,res); 
                cx = nx; cy = ny;
 
            }
            idx++; 
        } 
        return ans;    
    }
    // find first > tar
    public int find1(List<Integer> list,int tar){
        if(list.size()==0
        ||list.get(list.size()-1)<tar) return INF;
        if(list.get(0)>tar) return list.get(0);
        int n = list.size();
        // 0~n-1
        int l = 0,r = n-1,mid = 0;
        while(l<r){
            mid = l+(r-l)/2;
            if(list.get(mid)>tar) r = mid;
            else l = mid+1;
        }
        return list.get(l)>tar?list.get(l):INF;
    }
    // find first < tar
    public int find2(List<Integer> list,int tar){
        if(list.size()==0
        ||list.get(0)>tar) return INF;
        int n = list.size();
        if(list.get(n-1)<tar) return list.get(n-1);
        // 0~n-1
        int l = 0,r = n-1,mid = 0;
        while(l<r){
            mid = l+(r-l+1)/2;
            if(list.get(mid)>=tar) r = mid-1;
            else l = mid;
        } 
        return list.get(l)<tar?list.get(l):INF;
    }
}

時(shí)間復(fù)雜度$O(N+M?ClogX)$

空間復(fù)雜度$O(M)$

Tag

Array

Simulation文章來源地址http://www.zghlxwxcb.cn/news/detail-677138.html

到了這里，關(guān)于【LeetCode 算法】Walking Robot Simulation 模擬行走機(jī)器人 - 二分的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！