Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitea9fe98

Browse files
author
haotf
committed
动态规划
1 parent599cf77 commitea9fe98

20 files changed

+450
-0
lines changed

‎1024.视频拼接.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
importjava.util.Arrays;
2+
3+
/*
4+
* @lc app=leetcode.cn id=1024 lang=java
5+
*
6+
* [1024] 视频拼接
7+
*/
8+
9+
// @lc code=start
10+
classSolution {
11+
publicintvideoStitching(int[][]clips,inttime) {
12+
if (time ==0)
13+
return0;
14+
// 按起点升序排列，起点相同的降序排列
15+
Arrays.sort(clips, (a,b) -> {
16+
if (a[0] ==b[0]) {
17+
returnb[1] -a[1];
18+
}
19+
returna[0] -b[0];
20+
});
21+
// 记录选择的短视频个数
22+
intres =0;
23+
24+
intcurEnd =0,nextEnd =0;
25+
inti =0,n =clips.length;
26+
while (i <n &&clips[i][0] <=curEnd) {
27+
// 在第 res 个视频的区间内贪心选择下一个视频
28+
while (i <n &&clips[i][0] <=curEnd) {
29+
nextEnd =Math.max(nextEnd,clips[i][1]);
30+
i++;
31+
}
32+
// 找到下一个视频，更新 curEnd
33+
res++;
34+
curEnd =nextEnd;
35+
if (curEnd >=time) {
36+
// 已经可以拼出区间 [0, T]
37+
returnres;
38+
}
39+
}
40+
// 无法连续拼出区间 [0, T]
41+
return -1;
42+
}
43+
}
44+
// @lc code=end

‎1109.航班预订统计.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/*
2+
* @lc app=leetcode.cn id=1109 lang=java
3+
*
4+
* [1109] 航班预订统计
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicint[]corpFlightBookings(int[][]bookings,intn) {
10+
int[]diff =newint[n];
11+
for (inti =0;i <bookings.length;i++) {
12+
intstart =bookings[i][0];
13+
intend =bookings[i][1];
14+
intvalue =bookings[i][2];
15+
diff[start -1] =diff[start -1] +value;
16+
if (end <n) {
17+
diff[end] =diff[end] -value;
18+
}
19+
}
20+
int[]res =newint[n];
21+
res[0] =diff[0];
22+
for (inti =1;i <diff.length;i++) {
23+
res[i] =diff[i] +res[i -1];
24+
}
25+
returnres;
26+
}
27+
}
28+
// @lc code=end

‎1143.最长公共子序列.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
/*
2+
* @lc app=leetcode.cn id=1143 lang=java
3+
*
4+
* [1143] 最长公共子序列
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicintlongestCommonSubsequence(Stringtext1,Stringtext2) {
10+
intlen1 =text1.length();
11+
intlen2 =text2.length();
12+
int[][]dp =newint[len1 +1][len2 +1];
13+
for (inti =1;i <=len1;i++) {
14+
for (intj =1;j <=len2;j++) {
15+
if (text1.charAt(i -1) ==text2.charAt(j -1)) {
16+
dp[i][j] =dp[i -1][j -1] +1;
17+
}else {
18+
dp[i][j] =Math.max(dp[i][j -1],dp[i -1][j]);
19+
}
20+
}
21+
}
22+
returndp[len1][len2];
23+
}
24+
}
25+
// @lc code=end

‎130.被围绕的区域.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/*
2+
* @lc app=leetcode.cn id=130 lang=java
3+
*
4+
* [130] 被围绕的区域
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicvoidsolve(char[][]board) {
10+
11+
}
12+
}
13+
// @lc code=end
14+

‎1514.概率最大的路径.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/*
2+
* @lc app=leetcode.cn id=1514 lang=java
3+
*
4+
* [1514] 概率最大的路径
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicdoublemaxProbability(intn,int[][]edges,double[]succProb,intstart,intend) {
10+
11+
}
12+
}
13+
// @lc code=end
14+
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/*
2+
* @lc app=leetcode.cn id=1584 lang=java
3+
*
4+
* [1584] 连接所有点的最小费用
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicintminCostConnectPoints(int[][]points) {
10+
11+
}
12+
}
13+
// @lc code=end
14+

‎1631.最小体力消耗路径.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/*
2+
* @lc app=leetcode.cn id=1631 lang=java
3+
*
4+
* [1631] 最小体力消耗路径
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicintminimumEffortPath(int[][]heights) {
10+
11+
}
12+
}
13+
// @lc code=end
14+

‎207.课程表.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/*
2+
* @lc app=leetcode.cn id=207 lang=java
3+
*
4+
* [207] 课程表
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicbooleancanFinish(intnumCourses,int[][]prerequisites) {
10+
11+
}
12+
}
13+
// @lc code=end
14+

‎210.课程表-ii.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/*
2+
* @lc app=leetcode.cn id=210 lang=java
3+
*
4+
* [210] 课程表 II
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicint[]findOrder(intnumCourses,int[][]prerequisites) {
10+
11+
}
12+
}
13+
// @lc code=end
14+

‎300.最长递增子序列.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/*
2+
* @lc app=leetcode.cn id=300 lang=java
3+
*
4+
* [300] 最长递增子序列
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
publicintlengthOfLIS(int[]nums) {
10+
int[]memo =newint[nums.length];
11+
12+
intmax =1;
13+
for (inti =0;i <memo.length;i++) {
14+
memo[i] =1;
15+
}
16+
17+
for (inti =0;i <memo.length;i++) {
18+
for (intj =i;j >=0;j--) {
19+
if (nums[j] <nums[i]) {
20+
memo[i] =Math.max(memo[j] +1,memo[i]);
21+
}
22+
}
23+
max =Math.max(max,memo[i]);
24+
}
25+
26+
returnmax;
27+
}
28+
}
29+
// @lc code=end

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp