以下是 LCP 43. 十字路口的交通 的 Java 实现。题目分析- directions 长度为 4按 东、南、西、北 顺序记录各方向车辆从最靠近路口到最远离路口。- 每辆车通过路口恰好需要 1 秒。- 每秒交警可以指挥多个方向最靠近路口的车同时出发但必须满足1. 同一方向每秒只能驶出一辆车2. 同一方向每秒只能驶入一辆车3. 同一秒内车辆行驶路线不可相交。- 求所有车辆通过的最少秒数。算法思路四维动态规划 子集枚举1. 方向归一化将绝对方向E/S/W/N转换为相对方向L左转、R右转、S直行这样四个方向可以用统一的冲突规则判断。2. 状态定义dp[x0][x1][x2][x3] 表示四个方向分别还剩余 x0, x1, x2, x3 辆车时的最少秒数。3. 状态转移对于每个状态枚举当前所有还有车的方向的非空子集 mask用位运算快速枚举判断选中的车辆之间是否有冲突。若无冲突则这些车可以在同一秒内通过状态转移到剩余车辆更少的状态。4. 冲突检测根据相对方向判断选中车辆的行驶路线是否相交或驶入同一目标车道。Java 实现javaimport java.util.Arrays;class Solution {private char[][] dir;private int[] len;public int trafficCommand(String[] directions) {len new int[4];for (int i 0; i 4; i) {len[i] directions[i].length();}// 归一化将绝对方向 E/S/W/N 转为相对方向 L/R/Sdir new char[4][];for (int i 0; i 4; i) {dir[i] new char[len[i]];}// 东边来车(0): S-左转, N-右转, W-直行for (int t 0; t len[0]; t) {char c directions[0].charAt(t);dir[0][t] (c S) ? L : ((c N) ? R : S);}// 南边来车(1): W-左转, E-右转, N-直行for (int t 0; t len[1]; t) {char c directions[1].charAt(t);dir[1][t] (c W) ? L : ((c E) ? R : S);}// 西边来车(2): N-左转, S-右转, E-直行for (int t 0; t len[2]; t) {char c directions[2].charAt(t);dir[2][t] (c N) ? L : ((c S) ? R : S);}// 北边来车(3): E-左转, W-右转, S-直行for (int t 0; t len[3]; t) {char c directions[3].charAt(t);dir[3][t] (c E) ? L : ((c W) ? R : S);}int size0 len[0] 1, size1 len[1] 1;int size2 len[2] 1, size3 len[3] 1;int[][][][] dp new int[size0][size1][size2][size3];int INF Integer.MAX_VALUE / 2;for (int i 0; i size0; i) {for (int j 0; j size1; j) {for (int k 0; k size2; k) {Arrays.fill(dp[i][j][k], INF);}}}dp[0][0][0][0] 0;int[] x new int[4], y new int[4], index new int[4];for (x[0] 0; x[0] size0; x[0]) {index[0] len[0] - x[0];for (x[1] 0; x[1] size1; x[1]) {index[1] len[1] - x[1];for (x[2] 0; x[2] size2; x[2]) {index[2] len[2] - x[2];for (x[3] 0; x[3] size3; x[3]) {index[3] len[3] - x[3];int t (x[0] 0 ? 1 : 0) | (x[1] 0 ? 2 : 0)| (x[2] 0 ? 4 : 0) | (x[3] 0 ? 8 : 0);for (int mask t; mask 0; mask (mask - 1) t) {if (!checkConflict(index, mask)) {y[0] ((mask 1) ! 0) ? x[0] - 1 : x[0];y[1] ((mask 2) ! 0) ? x[1] - 1 : x[1];y[2] ((mask 4) ! 0) ? x[2] - 1 : x[2];y[3] ((mask 8) ! 0) ? x[3] - 1 : x[3];dp[x[0]][x[1]][x[2]][x[3]] Math.min(dp[x[0]][x[1]][x[2]][x[3]],1 dp[y[0]][y[1]][y[2]][y[3]]);}}}}}}int result dp[len[0]][len[1]][len[2]][len[3]];return result INF ? len[0] len[1] len[2] len[3] : result;}private boolean checkConflict(int[] index, int mask) {for (int x 0; (1 x) mask; x) {if ((mask (1 x)) ! 0) {int left (x 1) 0x03;int straight (x 2) 0x03;int right (x 3) 0x03;char action dir[x][index[x]];if (action L) {if (((mask (1 left)) ! 0 (dir[left][index[left]] S || dir[left][index[left]] L)) ||((mask (1 straight)) ! 0 (dir[straight][index[straight]] S || dir[straight][index[straight]] R)) ||((mask (1 right)) ! 0 (dir[right][index[right]] S || dir[right][index[right]] L))) {return true;}} else if (action S) {if (((mask (1 left)) ! 0 (dir[left][index[left]] S || dir[left][index[left]] L)) ||((mask (1 straight)) ! 0 dir[straight][index[straight]] L) ||((mask (1 right)) ! 0)) {return true;}} else {if (((mask (1 left)) ! 0 dir[left][index[left]] S) ||((mask (1 straight)) ! 0 dir[straight][index[straight]] L)) {return true;}}}}return false;}}复杂度分析- 时间复杂度O(len0 × len1 × len2 × len3 × 2^4)其中 leni ≤ 20最大状态数约为 21^4 × 16 ≈ 310万在可接受范围内。- 空间复杂度O(len0 × len1 × len2 × len3)最大约 21^4 ≈ 19.4万 个整数。下载完整代码[Solution.java](sandbox:///mnt/agents/output/Solution.java)
以下是 LCP 43. 十字路口的交通 的 Java 实现。题目分析- directions 长度为 4按 东、南、西、北 顺序记录各方向车辆从最靠近路口到最远离路口。- 每辆车通过路口恰好需要 1 秒。- 每秒交警可以指挥多个方向最靠近路口的车同时出发但必须满足1. 同一方向每秒只能驶出一辆车2. 同一方向每秒只能驶入一辆车3. 同一秒内车辆行驶路线不可相交。- 求所有车辆通过的最少秒数。算法思路四维动态规划 子集枚举1. 方向归一化将绝对方向E/S/W/N转换为相对方向L左转、R右转、S直行这样四个方向可以用统一的冲突规则判断。2. 状态定义dp[x0][x1][x2][x3] 表示四个方向分别还剩余 x0, x1, x2, x3 辆车时的最少秒数。3. 状态转移对于每个状态枚举当前所有还有车的方向的非空子集 mask用位运算快速枚举判断选中的车辆之间是否有冲突。若无冲突则这些车可以在同一秒内通过状态转移到剩余车辆更少的状态。4. 冲突检测根据相对方向判断选中车辆的行驶路线是否相交或驶入同一目标车道。Java 实现javaimport java.util.Arrays;class Solution {private char[][] dir;private int[] len;public int trafficCommand(String[] directions) {len new int[4];for (int i 0; i 4; i) {len[i] directions[i].length();}// 归一化将绝对方向 E/S/W/N 转为相对方向 L/R/Sdir new char[4][];for (int i 0; i 4; i) {dir[i] new char[len[i]];}// 东边来车(0): S-左转, N-右转, W-直行for (int t 0; t len[0]; t) {char c directions[0].charAt(t);dir[0][t] (c S) ? L : ((c N) ? R : S);}// 南边来车(1): W-左转, E-右转, N-直行for (int t 0; t len[1]; t) {char c directions[1].charAt(t);dir[1][t] (c W) ? L : ((c E) ? R : S);}// 西边来车(2): N-左转, S-右转, E-直行for (int t 0; t len[2]; t) {char c directions[2].charAt(t);dir[2][t] (c N) ? L : ((c S) ? R : S);}// 北边来车(3): E-左转, W-右转, S-直行for (int t 0; t len[3]; t) {char c directions[3].charAt(t);dir[3][t] (c E) ? L : ((c W) ? R : S);}int size0 len[0] 1, size1 len[1] 1;int size2 len[2] 1, size3 len[3] 1;int[][][][] dp new int[size0][size1][size2][size3];int INF Integer.MAX_VALUE / 2;for (int i 0; i size0; i) {for (int j 0; j size1; j) {for (int k 0; k size2; k) {Arrays.fill(dp[i][j][k], INF);}}}dp[0][0][0][0] 0;int[] x new int[4], y new int[4], index new int[4];for (x[0] 0; x[0] size0; x[0]) {index[0] len[0] - x[0];for (x[1] 0; x[1] size1; x[1]) {index[1] len[1] - x[1];for (x[2] 0; x[2] size2; x[2]) {index[2] len[2] - x[2];for (x[3] 0; x[3] size3; x[3]) {index[3] len[3] - x[3];int t (x[0] 0 ? 1 : 0) | (x[1] 0 ? 2 : 0)| (x[2] 0 ? 4 : 0) | (x[3] 0 ? 8 : 0);for (int mask t; mask 0; mask (mask - 1) t) {if (!checkConflict(index, mask)) {y[0] ((mask 1) ! 0) ? x[0] - 1 : x[0];y[1] ((mask 2) ! 0) ? x[1] - 1 : x[1];y[2] ((mask 4) ! 0) ? x[2] - 1 : x[2];y[3] ((mask 8) ! 0) ? x[3] - 1 : x[3];dp[x[0]][x[1]][x[2]][x[3]] Math.min(dp[x[0]][x[1]][x[2]][x[3]],1 dp[y[0]][y[1]][y[2]][y[3]]);}}}}}}int result dp[len[0]][len[1]][len[2]][len[3]];return result INF ? len[0] len[1] len[2] len[3] : result;}private boolean checkConflict(int[] index, int mask) {for (int x 0; (1 x) mask; x) {if ((mask (1 x)) ! 0) {int left (x 1) 0x03;int straight (x 2) 0x03;int right (x 3) 0x03;char action dir[x][index[x]];if (action L) {if (((mask (1 left)) ! 0 (dir[left][index[left]] S || dir[left][index[left]] L)) ||((mask (1 straight)) ! 0 (dir[straight][index[straight]] S || dir[straight][index[straight]] R)) ||((mask (1 right)) ! 0 (dir[right][index[right]] S || dir[right][index[right]] L))) {return true;}} else if (action S) {if (((mask (1 left)) ! 0 (dir[left][index[left]] S || dir[left][index[left]] L)) ||((mask (1 straight)) ! 0 dir[straight][index[straight]] L) ||((mask (1 right)) ! 0)) {return true;}} else {if (((mask (1 left)) ! 0 dir[left][index[left]] S) ||((mask (1 straight)) ! 0 dir[straight][index[straight]] L)) {return true;}}}}return false;}}复杂度分析- 时间复杂度O(len0 × len1 × len2 × len3 × 2^4)其中 leni ≤ 20最大状态数约为 21^4 × 16 ≈ 310万在可接受范围内。- 空间复杂度O(len0 × len1 × len2 × len3)最大约 21^4 ≈ 19.4万 个整数。下载完整代码[Solution.java](sandbox:///mnt/agents/output/Solution.java)
