X Tutup
Skip to content

Commit 02ae094

Browse files
frank-lamfrank-lam
committed
no message
1 parent f7ab48d commit 02ae094

File tree

3 files changed

+167
-4
lines changed

3 files changed

+167
-4
lines changed

‎interview/大厂之路.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@
3131
| 3 | 美团点评 | | | 上海 | | |
3232
| 4 | 百度 | | | 上海 | | |
3333
| 5 | 携程 | | | 上海 | | |
34-
| 6 | 贝壳 | | | 上海 | | |
34+
| 6 | 贝壳 | | | 上海 | 网站注册，填写表单，填写内推人及工号：曹蓉，23025254 | [官网](http://campus.ke.com/) |
3535
| 7 | 今日头条 | | | 北京/上海 | | |
3636
| 8 | ThoughtWorks | | | 上海 | [软件开发工程师](https://join.thoughtworks.cn/recruitment_process#jobs) | |
3737
| 9 | 哔哩哔哩 | | | 上海 | [后端研发工程师](http://campus.chinahr.com/2018/bilibili/index.html#t3) | |

‎notes/pics/LCS.png‎

26.6 KB
Loading

‎notes/数据结构与算法.md‎

Lines changed: 166 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1023,6 +1023,10 @@ public class Solution2 {
10231023

10241024
### 3. 最长上升子序列
10251025

1026+
**Longest Increasing Subsequence (LIS)**
1027+
1028+
**【Leetcode 300】最长上升子序列**
1029+
10261030
给定一个无序的整数数组，找到其中最长上升子序列的长度。
10271031

10281032
**示例:**
@@ -1042,24 +1046,183 @@ public class Solution2 {
10421046

10431047

10441048

1049+
1050+
10451051
LIS( i ) 表示以第 i 个数字为结尾的最长上升子序列的长度
10461052

10471053
LIS( i ) 表示 [0...i] 的范围内，选择数字nums[i]可以获得的最长上升子序列的长度
10481054

10491055
LIS ( i ) = max<sub>j<i</sub>( 1 + LIS( j ) if nums[i] > nums[j] )
10501056

1057+
```java
1058+
public class Solution {
1059+
1060+
public int lengthOfLIS(int[] nums) {
1061+
int n = nums.length;
1062+
if (n==0) {
1063+
return 0;
1064+
}
1065+
1066+
int res = 1;
1067+
int[] memo = new int[n];
1068+
1069+
Arrays.fill(memo, 1);
1070+
1071+
for (int i = 1; i < n; i++) {
1072+
for (int j = 0; j < i; j++) {
1073+
if (nums[j] < nums[i])
1074+
memo[i] = max(memo[i] , memo[j]+1);
1075+
}
1076+
}
1077+
1078+
for(int i = 0;i<n;i++){
1079+
res = max(memo[i],res);
1080+
}
1081+
return res;
1082+
}
1083+
1084+
private int max(int a, int b) {
1085+
return a > b ? a : b;
1086+
}
1087+
1088+
public static void main(String[] args) {
1089+
int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
1090+
System.out.println(new Solution().lengthOfLIS(arr));
1091+
}
1092+
}
1093+
```
1094+
1095+
这里思考一个问题：在上面的代码中只求解出了上升子序列的长度，那么如何求出具体的上升子序列呢？
1096+
1097+
```java
1098+
public class Solution2 {
1099+
private static List<Integer> LISindex = new ArrayList<>(); // 记录一下有几个上升子序列
10511100

1101+
public List<List<Integer>> lengthOfLIS(int[] nums) {
1102+
List<List<Integer>> resList = new ArrayList<>();
1103+
int n = nums.length;
1104+
if (n == 0) {
1105+
return null;
1106+
}
10521107

1108+
int res = 1;
1109+
int[] memo = new int[n];
10531110

1111+
Arrays.fill(memo, 1);
10541112

1113+
for (int i = 1; i < n; i++) {
1114+
for (int j = 0; j < i; j++) {
1115+
if (nums[j] < nums[i])
1116+
memo[i] = max(memo[i], memo[j] + 1);
1117+
}
1118+
}
10551119

1120+
for (int i = 0; i < n; i++) {
1121+
res = max(memo[i], res);
1122+
}
1123+
1124+
for (int i = 0; i < n; i++) {
1125+
if (memo[i] == res)
1126+
LISindex.add(i); // 遍历一下最长子序列最后一位是谁，统计一共有多少个子序列
1127+
}
1128+
1129+
for (int lastIndex : LISindex) {
1130+
ArrayList<Integer> list = new ArrayList<>();
1131+
int nowMemoCount = memo[lastIndex];
1132+
1133+
for (int i = lastIndex; i >= 0; i--) {
1134+
if (nowMemoCount - memo[i] == 1 || nowMemoCount - memo[i] == 0) {
1135+
list.add(nums[i]);
1136+
nowMemoCount--;
1137+
}
1138+
}
1139+
resList.add(reverseList(list));
1140+
}
1141+
1142+
return resList;
1143+
}
1144+
1145+
private int max(int a, int b) {
1146+
return a > b ? a : b;
1147+
}
1148+
1149+
private List<Integer> reverseList(ArrayList<Integer> list) {
1150+
List<Integer> newList = new ArrayList<>();
1151+
for (int i = list.size() - 1; i >= 0; i--) {
1152+
newList.add(list.get(i));
1153+
}
1154+
return newList;
1155+
}
1156+
1157+
public static void main(String[] args) {
1158+
int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
1159+
System.out.println(new Solution2().lengthOfLIS(arr));
1160+
}
1161+
}
1162+
```
1163+
1164+
1165+
1166+
### 4. 最长公共子序列
1167+
1168+
**Longest Common Sequence (LCS)**：给出两个字符串S1和S2，求这两个字符串的最长公共子序列的长度
1169+
1170+
1171+
1172+
LCS( m , n ) S1[0…m] 和 S2[0…n] 的最长公共子序列的长度
1173+
1174+
1175+
1176+
**S1[m] == S2[n] :**
1177+
1178+
LCS(m,n) = 1 + LCS(m-1,n-1)
1179+
1180+
**S1[m] != S2[n] :**
1181+
1182+
LCS(m,n) = max( LCS(m-1,n) , LCS(m,n-1) )
1183+
1184+
1185+
1186+
<div align="center"> <img src="pics/LCS.png" width=""/></div><br/>
1187+
1188+
```java
1189+
/**
1190+
* 最长公共子序列
1191+
*/
1192+
public class Solution3 {
1193+
1194+
public int LCS(String s1, String s2) {
1195+
return bestLength(s1, s2, s1.length() - 1, s2.length() - 1);
1196+
}
1197+
1198+
public int bestLength(String s1, String s2, int m, int n) {
1199+
if (m < 0 || n < 0)
1200+
return 0;
1201+
int lcs = 0;
1202+
if (s1.charAt(m) == s2.charAt(n)) {
1203+
lcs = 1 + bestLength(s1, s2, m - 1, n - 1);
1204+
} else {
1205+
lcs = max(bestLength(s1, s2, m - 1, n), bestLength(s1, s2, m, n - 1));
1206+
}
1207+
return lcs;
1208+
}
1209+
1210+
private int max(int a, int b) {
1211+
return a > b ? a : b;
1212+
}
1213+
1214+
public static void main(String[] args) {
1215+
System.out.println(new Solution3().LCS("ABCDEE", "ABDCEE"));
1216+
}
1217+
}
1218+
```
10561219

10571220

10581221

1059-
动态规划解决01背包问题 - Christal_R - 博客园
1060-
https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html
1222+
参考资料：
10611223

1062-
[【经典算法】01背包问题_土豆视频](http://new-play.tudou.com/v/XMTQ3MzI0NzI2OA==.html?spm=a2h0k.8191414.0.0&from=s1.8-1-1.2&f=28521433)
1224+
- [动态规划解决01背包问题 - Christal_R - 博客园](https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html)
1225+
- [【经典算法】01背包问题_土豆视频](http://new-play.tudou.com/v/XMTQ3MzI0NzI2OA==.html?spm=a2h0k.8191414.0.0&from=s1.8-1-1.2&f=28521433)
10631226

10641227

10651228

0 commit comments

Comments
 (0)
X Tutup