图森最新OA截图+思路

上周收到的OAHackerrank 1道

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

要怎么从上一步算出来

唉。。。做不出OA的感觉真的烦23333求大米安慰！

是用dp嗎?

匿名者 发表于 2021-2-8 10:55
是用dp嗎?

对 唉我都没来得及做完 还是挺tricky的

多谢分享，obstacle的判定还挺tricky呢。

请问楼主这是test 几啊？

jackeee1shy 发表于 2021-2-12 06:04
请问楼主这是test 几啊？

现在已经不分test几了 没有写

看完第一感觉这个题是不是有一点点类似涂色问题？dp[step][lane]如果当前step所在lane是有障碍的，就需要变道+1这样，类推的话我的current lane取决于前一步有没有变道，如果有就+1，没有就等于dp[step-1][same lane]

试着写了下代码，感觉压缩dp到一维也可以

1. public static int racing_cars(int[] obstacleLanes) {
   
2.     int n = obstacleLanes.length;
   
3.     int[] dp = new int[4];
   
4.     for (int i = 0; i < n; ++i) {
   
5.         int min = n;
   
6.         // 当前行障碍所处位置
   
7.         int curr_obstacle = obstacleLanes[i];
   
8.         // 如果car向左移一位仍在赛道上，更新最小值
   
9.         if (curr_obstacle-1 >= 1) {
   
10.             min = Integer.min(min, dp[curr_obstacle-1]);
    
11.         }
    
12.         // 如果car向左移两位仍在赛道上，更新最小值
    
13.         if (curr_obstacle-2 >= 1) {
    
14.             min = Integer.min(min, dp[curr_obstacle-2]);
    
15.         }
    
16.         // 以下向右同理
    
17.         if (curr_obstacle+1 <= 3) {
    
18.             min = Integer.min(min, dp[curr_obstacle+1]);
    
19.         }
    
20.         if (curr_obstacle+2 <= 3) {
    
21.             min = Integer.min(min, dp[curr_obstacle+2]);
    
22.         }
    
23.         // 更新当前行障碍所在位置需要移动的最小次数
    
24.         dp[curr_obstacle] = min+1;
    
25.     }
    
26.     // 输出中间lane的结果
    
27.     return dp[2];
    
28. }

复制代码