帝国建站程序,中铁建设门户网员工登录,2022年10月国内最新新闻,政务公开微信网站开发方案书2833.给你一个长度为 n 的字符串 moves #xff0c;该字符串仅由字符 ‘L’、‘R’ 和 ‘’ 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。 你的初始位置就在原点#xff08;0#xff09;#xff0c;第 i 次移动过程中#xff0c;你可以根据对应字符选择移动方… 2833.给你一个长度为 n 的字符串 moves 该字符串仅由字符 ‘L’、‘R’ 和 ‘’ 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。 你的初始位置就在原点0第 i 次移动过程中你可以根据对应字符选择移动方向 如果 moves[i] ‘L’ 或 moves[i] ’ 可以选择向左移动一个单位距离 如果 moves[i] ‘R’ 或 moves[i] ’ 可以选择向右移动一个单位距离 移动 n 次之后请你找出可以到达的距离原点 最远 的点并返回 从原点到这一点的距离 。 示例 1 输入moves “L_RL__R” 输出3 解释可以到达的距离原点 0 最远的点是 -3 移动的序列为 “LLRLLLR” 。 示例 2 输入moves “R__LL” 输出5 解释可以到达的距离原点 0 最远的点是 -5 移动的序列为 “LRLLLLL” 。 示例 3 输入moves ______ 输出7 解释可以到达的距离原点 0 最远的点是 7 移动的序列为 “RRRRRRR” 。 我的思路首先这可以看成一棵二叉树所以直接 dfs。首先入参为了知道遍历到哪里了用一个 int 表示当前 moves 下标。由于可以向左或者向右所以用两个 int 表示向两边移动的距离递归出口当遍历完这棵树也就是 moves 遍历到最后一个字符时返回 max(左距离右距离)。如果在遍历的过程中发现遍历到某个点时已经遇到过此时向(左右)移动了多少距离这种情况那可以直接返回 0 了因为这种可能性我们已经考虑过了比如 l__r_我们可能是 llrr_ 也可能是lrlr_那此时其实就是重复的情况了遍历到第五个点的 _ 时都是还在原点否则就看当前字符了为 L 说明向左走了一步左距离 加 1相对应的别忘了这就代表着右距离减了 1 R 同理如果为 _ 就返回 max(左右) char[] moves;// l[i][j] 遍历到第 i 个点并且此时往左走了长度 jint[][] l;// // l[i][j] 遍历到第 i 个点并且此时往右走了长度 jint[][] r;public int furthestDistanceFromOrigin(String moves) {this.moves moves.toCharArray();int n this.moves.length;lnew int[n][n];rnew int[n][n];return dfs(0,0,0);}// left 和 right 最多只可能有一个大于 0一正一负或者都为 0int dfs(int cur,int left,int right){// 遍历完了if(curmoves.length){return Math.max(left,right);}// 如果这种情况已经考虑过了 return 0if((left0 l[cur][left]1) || (right0 r[cur][right]1))return 0;// 如果在左边记录这种情况if(left0)l[cur][left]1;// // 如果在右边记录这种情况if(right0)r[cur][right]1;if(moves[cur]L)return dfs(cur1,left1,right-1);if(moves[cur]R)return dfs(cur1,left-1,right1);return Math.max(dfs(cur1,left1,right-1),dfs(cur1,left-1,right1));}其实这题我想的复杂了因为当遇到 _ 时你的选择丝毫不影响之后的选择。也就是说你只需要记录有几个 _ 然后看剩下的 L 和 R 会让你走到哪里如果在左边你就把 _ 都选择往左走在右边同理。 public int furthestDistanceFromOrigin(String moves) {int x0;int distance0;for(char c:moves.toCharArray()){if(c_)x;else distancecL?-1:1;}return xMath.abs(distance);}
