LeetCode： 1024. 视频拼接
挺有意思的文字类答题游戏： 1024 程序员的奇幻冒险
1024 节日 >> 我应该自己先磨出这道题 >> 再去看解法
贪心
【×】动态规划【×】 >> 自己想了一段时间 >> dp[][] >> 表示加上该区间后的 最小数目
2.1 状态转移方程 >> dp[i][j] = dp[i – 1][j] == 0 && dp[i][j] == 1 ? dp[i][T + 1] = d[i – 1][T + 1] + 1 >> 错了
动态规划
3.1 dp[i] 为覆盖 [0, i) 区间所需要的最少区间数量。
3.2 状态转移方程：
思路
遍历所有的区间 0 – T ，因为 dp[i] 表示的是 [0, i) 范围所需要的最少数量，当我们遍历到 第 i + 1 的数时，表示我们要找 [0, i + 1) 的区间， 而 [0, i) 前面已经有相应的 dp[clips[0]] 了，所有我们找到满足 [i, i + 1] 的条件来更新状态 >> 状态转移， 在前面已有条件(dp[clips[i][0]])上 + 1 即可, 然后在与本身相比较 >> 取 min 的
贪心
这种写法也就当笨笨的饼干自定义排序吧。
假贪心 >> 面向调试编程 >> 还能优化
public int videoStitching(int[][] clips, int T) { int row = clips.length; int col = clips[0].length;// 自定义排序 Arrays.sort(clips, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if(o1[0] == o2[0]){ return o1[1] – o2[1]; } return o1[0] – o2[0]; } }); if(clips[0][0] != 0) return -1; int start = clips[0][0]; int end = clips[0][1]; int ans = 0; for (int i = 1; i < row; i++) { if(i != 1) i–; // 找到区间最大的 while (i < row && start == clips[i][0]){ if(end < clips[i][1]) end = clips[i][1]; i++; } ans++; int mxend = 0; int index = 0; // 找到与前一个 end 相交且相邻最近的 end 最大的 while (i < row && end >= clips[i][0]){ if(clips[i][1] – end > mxend) { mxend = clips[i][1] – end; index = i; } i++; } if(end >= T) return ans; if(mxend == 0 || i >= row && (end + mxend) < T) return -1; if((end + mxend )>= T) return ans + 1;// 更新 开始、结束区间下标 start = clips[index][0]; end = clips[index][1]; } return -1; }
结束条件那里卡了多次数据 >> 分析不到位…
if(end >= T) return ans; if(mxend == 0 || i >= row && (end + mxend) < T) return -1; if((end + mxend )>= T) return ans + 1;
编程题没有这种数据错误的信息 >> 就凉了…
dp
DP思路在上面
public int videoStitching(int[][] clips, int T) { int[] dp = new int[T + 1]; Arrays.fill(dp, Integer.MAX_VALUE – 1); dp[0] = 0; for (int i = 1; i < T + 1; i++) { for (int j = 0; j < clips.length; j++) { if(clips[j][0] < i && i <= clips[j][1]){ dp[i] = Math.min(dp[i], dp[clips[j][0]] + 1); } } } // for (int i = 0; i < T + 1; i++) { // System.out.print(dp[i] + ” “); // } return dp[T] == Integer.MAX_VALUE – 1? -1 : dp[T]; }
Arrays.fill(dp, Integer.MAX_VALUE – 1); 的原因
贪心
思路： 最终的答案的 左端点不可能出现相同的，所以在相同的左端点 i ， 其有端点越远越好。为左端点记录其最远的右端点
public int videoStitching(int[][] clips, int T) { // 记录当前i能被覆盖到的最远的右端点 int[] maxr = new int[T]; int right = 0, pre = 0, ans = 0; // 记录最远的右端点 for (int i = 0; i < clips.length; i++) { if(clips[i][0] < T){ maxr[clips[i][0]] = Math.max(maxr[clips[i][0]], clips[i][1]); } } // 选区间 for (int i = 0; i < T; i++) { // 当前 i 最右端点 right = Math.max(maxr[i], right); if(i == right) return -1; // 这里是根据上一次 right 的位置， 遍历到了才算 +1 个区间 if(i == pre){ ans++; // 更新下次 i 需要便利到 right 才算 +1 区间 pre = right; } } return ans; }
>> 解题思路
25505365
