Skip to content

Commit 5789855

Browse files
g29timesg29times
committed
第二周作业#25 
1 parent 934713b commit 5789855

2 files changed

Lines changed: 346 additions & 0 deletions

File tree

‎Week_01/id_25/LeetCode_24_025.java‎

Lines changed: 168 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
package com.mootal.algo.day8_24;
2+
3+
/**
4+
* Medium
5+
* (注解文档查看快捷键 选中类名或方法名 按ctrl + Q)
6+
* <p>
7+
* 思维全过程记录方案：<p>
8+
* 1 背基础结构和算法 | 记录在课程笔记<p>
9+
* 2 看题 -> 悟题 思考过程 | 记录在wiki<p>
10+
* 3 悟题 -> 写题 实现难点 | 记录在代码注解<p>
11+
* 4 写题 -> 优化 多种解法 | 记录在leetcode提交
12+
* <p>
13+
* 问题：
14+
* Given a linked list, swap every two adjacent nodes and return its head.
15+
* You may not modify the values in the list's nodes, only nodes itself may be changed.
16+
* 1->2->3->4 | 2->1->4->3
17+
* <p>
18+
* 题解方案topics：
19+
* linked list
20+
*
21+
* @author li tong
22+
* @date 2019/6/10 9:41
23+
* @see Object
24+
* @since 1.0
25+
*/
26+
public class SwapNodes24 {
27+
28+
private static class ListNode {
29+
int val;
30+
31+
ListNode next;
32+
33+
ListNode(int x) {
34+
val = x;
35+
}
36+
37+
@Override
38+
public String toString() {
39+
return "{" + val +
40+
", next=" + next +
41+
'}';
42+
}
43+
}
44+
45+
public static void main(String[] args) {
46+
ListNode a = new ListNode(1);
47+
ListNode b = new ListNode(2);
48+
ListNode c = new ListNode(3);
49+
ListNode d = new ListNode(4);
50+
a.next = b;
51+
b.next = c;
52+
c.next = d;
53+
// System.out.println(swapListRecursive(a));
54+
// understandSwapListRecursive(a);
55+
System.out.println(swapPairs(a));
56+
// System.out.println(swapPairs2(a));
57+
}
58+
59+
/**
60+
* 解法1 递归法<p>
61+
* 看题解，主干思路：<p>
62+
* &nbsp;&nbsp; 定义后序二步节点 找到返回方程<p>
63+
* 自己学习 思考 实践时的难点(难点是如何突破的见wiki)：<p>
64+
* &nbsp;&nbsp; 如何找到返回方程 把单链表反转递归法又理解了一遍
65+
*
66+
* @param head
67+
* @return
68+
*/
69+
public static ListNode swapPairs(ListNode head) {
70+
if (head == null || head.next == null) {
71+
System.out.println();
72+
return head;
73+
}
74+
ListNode after = head.next;
75+
// 1 难点1 定义后序二步节点
76+
ListNode nextTwo = after.next;
77+
System.out.println(head + "就位，交代去程工作后，" + head.val + "睡眠，" + nextTwo + "进入到下一层");
78+
ListNode back = swapPairs(nextTwo);
79+
System.out.println("after=" + after + "返回到上一层，head=" + head + "唤醒，开始第一步：before指向back=" + back);
80+
// 2 难点2 谁指向谁？
81+
head.next = back;
82+
System.out.println("第一步完成后，head=" + head + "，开始第二步：after" + after + "指向before");
83+
// 3 难点3
84+
after.next = head;
85+
System.out.println("第二步完成后，after=" + after);
86+
System.out.println();
87+
// 4 难点4 返回什么？back 还是 after？
88+
return after;
89+
}
90+
91+
/**
92+
* 解法2 遍历法<p>
93+
* 看题解，主干思路：<p>
94+
* &nbsp;&nbsp; 关键是要理解两步两步走<p>
95+
* 自己学习 思考 实践时的难点(难点是如何突破的见wiki)：<p>
96+
* &nbsp;&nbsp; 想不到定义两个Node
97+
*
98+
* @param head
99+
* @return
100+
*/
101+
public static ListNode swapPairs2(ListNode head) {
102+
if (head == null || head.next == null) {
103+
return head;
104+
}
105+
ListNode newHead = new ListNode(0);
106+
newHead.next = head;
107+
ListNode temp = newHead;
108+
ListNode one = null;
109+
ListNode two = null;
110+
// {dummy->1->2->3->4->null}
111+
while (temp.next != null && temp.next.next != null) {
112+
// one -> 1
113+
one = temp.next;
114+
// two -> 2
115+
two = temp.next.next;
116+
// 1-> = 2.next = 3;
117+
one.next = two.next;
118+
// 2-> = 1
119+
two.next = one;
120+
// now newHead should point to 2
121+
// if the below is not done newHead->1;
122+
temp.next = two;
123+
// temp was pointing to newHead
124+
// temp->1
125+
temp = one;
126+
// now { dummy->2->1->3->4 }
127+
}
128+
return newHead.next;
129+
}
130+
131+
/**
132+
* ！重要 完整笔记 自己理解递归方式链表反转
133+
* 4->3->2->1
134+
*
135+
* @param before
136+
* @return
137+
*/
138+
public static ListNode understandSwapListRecursive(ListNode before) {
139+
if (before == null || before.next == null) {
140+
System.out.println("最底层的世界空无一物，" + before + "返回");
141+
System.out.println();
142+
return before;
143+
}
144+
ListNode after = before.next;
145+
System.out.println("before=" + before + "就位，交代去程工作后，before=" + before.val + "睡眠，after=" + after + "进入到下一层");
146+
ListNode back = understandSwapListRecursive(after);
147+
System.out.println("back=" + back + "返回到上一层，before=" + before + "唤醒，开始第一步：before指向null");
148+
/**
149+
* 回归这里是难点
150+
* 第一次失败 back.next = before; before.next = null; 第二次失败 before.next = null; back.next = before;
151+
* 模板中这里不写，也能正常执行，先调试看看
152+
*/
153+
before.next = null;
154+
System.out.println("第一步完成后，before=" + before + "，开始第二步：after" + after + "指向before");
155+
after.next = before;
156+
System.out.println("第二步完成后，after=" + after + "，back=" + back);
157+
System.out.println();
158+
return back;
159+
}
160+
161+
public static void print(ListNode n) {
162+
while (n != null) {
163+
System.out.print(n.val);
164+
n = n.next;
165+
}
166+
}
167+
168+
}

‎Week_01/id_25/LeetCode_72_025.java‎

Lines changed: 178 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,178 @@
1+
package com.mootal.algo.day9_72;
2+
3+
/**
4+
* Hard
5+
* (注解文档查看快捷键 选中类名或方法名 按ctrl + Q)
6+
* <p>
7+
* 思维全过程记录方案：<p>
8+
* 1 背基础结构和算法 | 记录在课程笔记<p>
9+
* 2 看题 -> 悟题 思考过程 | 记录在wiki<p>
10+
* 3 悟题 -> 写题 实现难点 | 记录在代码注解<p>
11+
* 4 写题 -> 优化 多种解法 | 记录在leetcode提交
12+
* <p>
13+
* 问题：
14+
* Given two words word1 and word2,
15+
* find the minimum number of operations required to convert word1 to word2.
16+
* <p>
17+
* 题解方案topics：
18+
* string、dp
19+
*
20+
* @author li tong
21+
* @date 2019/6/11 10:06
22+
* @see Object
23+
* @since 1.0
24+
*/
25+
public class EditDistance72 {
26+
27+
public static void main(String[] args) {
28+
// String word1 = "abc", word2 = "abc";
29+
// String word1 = "horse", word2 = "rose";
30+
String word1 = "rose", word2 = "horse";
31+
System.out.println(minDistance(word1, word2));
32+
System.out.println(minDistanceDP(word1, word2));
33+
}
34+
35+
/**
36+
* 递归解法 <p>
37+
* 自己思考结合题解提示，主干思路：<p>
38+
* &nbsp;&nbsp;1.先过一遍所有可能的解决方案 找到递归思路 2 用mem优化<p>
39+
* 自己学习 思考 实践时的难点(难点是如何突破的见wiki)：<p>
40+
* &nbsp;&nbsp;1 看题解思路 自己尝试实现代码 写出相似度50% 再看答案
41+
* &nbsp;&nbsp;2 边界条件处理
42+
* &nbsp;&nbsp;3 多种路径组合出正确的递归写法
43+
* &nbsp;&nbsp;4 如何合并到最终结果<p>
44+
*
45+
* @param word1
46+
* @param word2
47+
* @return
48+
*/
49+
public static int minDistance(String word1, String word2) {
50+
char[] w1 = word1.toCharArray();
51+
char[] w2 = word2.toCharArray();
52+
int l1 = w1.length, l2 = w2.length;
53+
int[][] mem = new int[l1][l2];
54+
// return help(0, w1, 0, w2, mem);
55+
return helpWithMem(0, w1, 0, w2, mem);
56+
}
57+
58+
private static int help(int i, char[] w1, int j, char[] w2, int[][] mem) {
59+
int insertCnt, deleteCnt, replaceCnt;
60+
if (i == w1.length) {
61+
// 长短不一致的情况 例如 rose -> horse
62+
// 这里自己实现起来很困难 很难想到
63+
return w2.length - j;
64+
}
65+
if (j == w2.length) {
66+
// 长短不一致的情况 例如 horse -> rose
67+
// 这里自己实现起来很困难 很难想到
68+
return w1.length - i;
69+
}
70+
int res = 0;
71+
if (w1[i] == w2[j]) {
72+
// 直接return
73+
// System.out.println("i=" + i);
74+
res = help(i + 1, w1, j + 1, w2, mem);
75+
// System.out.println("i=" + i);
76+
return res;
77+
} else {
78+
deleteCnt = help(i + 1, w1, j, w2, mem);
79+
System.out.println(deleteCnt);
80+
insertCnt = help(i, w1, j + 1, w2, mem);
81+
System.out.println(insertCnt);
82+
replaceCnt = help(i + 1, w1, j + 1, w2, mem);
83+
System.out.println(replaceCnt);
84+
// 这里很难想到是取三者的最小值，还要加1是什么意思
85+
res = Math.min(insertCnt, Math.min(deleteCnt, replaceCnt)) + 1;
86+
// 自己写的代码 意思接近了
87+
// if (w1[i + 1] == w2[j]) {
88+
// i = i + 1;
89+
// help(i + 1, w1, j, w2);
90+
// deleteCnt++;
91+
// } else if (w1[i] == w2[j + 1]) {
92+
// j = j + 1;
93+
// help(i, w1, j, w2);
94+
// insertCnt++;
95+
// } else {
96+
// i = i + 1;
97+
// j = j + 1;
98+
// help(i, w1, j, w2);
99+
// replaceCnt++;
100+
// }
101+
}
102+
return res;
103+
}
104+
105+
private static int helpWithMem(int i, char[] w1, int j, char[] w2, int[][] mem) {
106+
int insertCnt, deleteCnt, replaceCnt;
107+
if (i == w1.length) {
108+
return w2.length - j;
109+
}
110+
if (j == w2.length) {
111+
return w1.length - i;
112+
}
113+
if (mem[i][j] > 0) {
114+
return mem[i][j];
115+
}
116+
int res = 0;
117+
if (w1[i] == w2[j]) {
118+
// System.out.println("i=" + i);
119+
res = helpWithMem(i + 1, w1, j + 1, w2, mem);
120+
// System.out.println("i=" + i);
121+
return res;
122+
} else {
123+
deleteCnt = helpWithMem(i + 1, w1, j, w2, mem);
124+
// System.out.println(deleteCnt);
125+
insertCnt = helpWithMem(i, w1, j + 1, w2, mem);
126+
// System.out.println(insertCnt);
127+
replaceCnt = helpWithMem(i + 1, w1, j + 1, w2, mem);
128+
// System.out.println(replaceCnt);
129+
mem[i][j] = Math.min(insertCnt, Math.min(deleteCnt, replaceCnt)) + 1;
130+
}
131+
return mem[i][j];
132+
}
133+
134+
/**
135+
* DP解法 <p>
136+
* 看题解，主干思路：<p>
137+
* &nbsp;&nbsp; dp[i][j] 表示从 word1 的前i个字符转换到 word2 的前j个字符所需要的步骤<p>
138+
* 自己学习 思考 实践时的难点(难点是如何突破的见wiki)：<p>
139+
* &nbsp;&nbsp;找出状态转移方程 思路：手写例子 简化变量
140+
* DP特点
141+
* 1 求极值
142+
* 2 子问题最优解
143+
* 3 dp和递归不同的是 dp是循环 递归是栈
144+
* 4 dp倾向于倒序<p>
145+
* . Ø a b c d<p>
146+
* Ø 0 1 2 3 4<p>
147+
* b 1 1 1 2 3<p>
148+
* b 2 2 1 2 3<p>
149+
* c 3 3 2 1 2<p>
150+
*
151+
* @param word1
152+
* @param word2
153+
* @return
154+
*/
155+
public static int minDistanceDP(String word1, String word2) {
156+
char[] w1 = word1.toCharArray();
157+
char[] w2 = word2.toCharArray();
158+
int l1 = w1.length, l2 = w2.length;
159+
int[][] dp = new int[l1 + 1][l2 + 1];
160+
for (int i = 0; i <= l1; ++i) {
161+
dp[i][0] = i;
162+
}
163+
for (int i = 0; i <= l2; ++i) {
164+
dp[0][i] = i;
165+
}
166+
for (int i = 1; i <= l1; ++i) {
167+
for (int j = 1; j <= l2; ++j) {
168+
if (w1[i - 1] == w2[j - 1]) {
169+
dp[i][j] = dp[i - 1][j - 1];
170+
} else {
171+
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
172+
}
173+
}
174+
}
175+
return dp[l1][l2];
176+
}
177+
178+
}

0 commit comments

Comments
 (0)