algorithm004-03 · kelly422 · Dec 10, 2019 · Dec 8, 2019 · Dec 10, 2019 · Dec 10, 2019
diff --git a/Week 08/id_613/NOTE2.md b/Week 08/id_613/NOTE2.md
@@ -0,0 +1,69 @@
+# NOTE
+
+# 字符串
+## java、python、go里的string是immutable的
+## c++里的string是mutable，如果要immutable，加const即可
+## immutable是线程安全的
+
+## 字符串比较
+Java:
+String x = "abb"
+String y = "abb"
+
+x == y --> false
+
+x.equals(y) --> true
+x.equalsIgnoreCase(y) --> true
+
+## 字符串匹配算法
+- 1、暴力法
+- 2、Robin-Karp算法
+- 3、KMP算法
+- Robin-Karp和KMP算法都是在暴力法的基础上进行的优化或加速
+
+### Rabin-Karp算法（在朴素算法的基础上增加了hash来做预判）
+Rabin-Karp算法思想：
+1、假设子串的长度为M(pat)，目标字符串的长度为N(txt)
+2、计算子串的hash值hash_pat
+3、计算目标字符串txt中每个长度为M的子串的hash值(共需要计算N-N+1次)
+4、比较hash值：如果hash值不同，字符串必然不匹配；如果hash值相同，还需要使用朴素算法再次判断
+
+### KMP算法
+KMP算法思想：当子串与目标字符串不匹配时，其实你已经知道了前面已经匹配成功的那一部分字符，然后
+设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。
+#### 算法视频
+https://www.bilibili.com/video/av11866460?from=search&seid=17425875345653862171
+
+
+课后了解：  
+Boyer-Moore算法：  
+http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html  
+Sunday算法：  
+https://blog.csdn.net/u012505432/article/details/52210975
+
+
+# 高级动态规划
+## DP顺推模板
+```python
+function DP():
+    dp = [][] # 二维情况
+
+    for i = 0 .. M {
+      for j = 0 .. N {
+        dp[i][j] = _Function(dp[i'][j']...)
+      }
+    }
+
+    return dp[M][N]
+```
+
+## DP解题思维方式
+- 把问题抽象化
+- 定义成状态（一维或多维状态），写出DP转移方程
+- 套用模板，写出嵌套循环及DP方程
+
+## 高阶DP复杂度来源
+- 状态拥有更多维度（二维、三维、或者更多、甚至需要压缩）
+- 状态方程更加复杂  
+本质：内功、逻辑思维、数学
+
diff --git a/Week 08/id_613/java/src/main/Leetcode541.java b/Week 08/id_613/java/src/main/Leetcode541.java
@@ -0,0 +1,45 @@
+/**
+ * 反转字符串II
+ *
+ * 执行用时 : * 2 ms * , 在所有 java 提交中击败了 * 55.35% * 的用户
+ * 内存消耗 : * 37.3 MB * , 在所有 java 提交中击败了 * 97.74% * 的用户
+ */
+public class Leetcode541 {
+  public String reverseStr(String s, int k) {
+    if (s == null) {
+      return null;
+    }
+
+    StringBuilder result = new StringBuilder();
+    for (int i = 0; i < s.length(); i += 2 * k) {
+      result.append(reverse(s.substring(i, Math.min(i + k, s.length()))));
+      result.append(s.substring(Math.min(i + k, s.length()), Math.min(i + 2 * k, s.length())));
+    }
+
+    return result.toString();
+  }
+
+  // 翻转字符串
+  private String reverse(String s) {
+    if (s == null) {
+      return null;
+    }
+
+    StringBuilder result = new StringBuilder();
+
+    for (int i = s.length() - 1; i >= 0; i--) {
+      result.append(s.charAt(i));
+    }
+
+    return result.toString();
+  }
+
+  public static void main(String[] args) {
+    String s = "hello, world!";
+    Leetcode541 so = new Leetcode541();
+    System.out.println(so.reverse(s));
+
+    s = "a";
+    System.out.println(so.reverse(s));
+  }
+}
diff --git a/Week 08/id_613/java/src/main/Leetcode746.java b/Week 08/id_613/java/src/main/Leetcode746.java
@@ -0,0 +1,42 @@
+/**
+ * 使用最小花费爬楼梯
+ *
+ * 执行用时 : * 1 ms * , 在所有 java 提交中击败了 * 100.00% * 的用户
+ * 内存消耗 : * 39.1 MB * , 在所有 java 提交中击败了 * 66.97% * 的用户
+ */
+public class Leetcode746 {
+  // dp[i]为从第i级台阶出发的最小花费
+  // DP方程：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
+  public int minCostClimbingStairs(int[] cost) {
+    int[] re = new int[cost.length + 1];
+
+    for (int i = 2; i < re.length; i++) {
+      re[i] = Math.min(re[i - 1] + cost[i - 1], re[i - 2] + cost[i - 2]);
+    }
+
+    return re[re.length - 1];
+  }
+
+  public int climbingStairs(int n) {
+    if (n < 2) {
+      return n;
+    }
+
+    int[] re = new int[n];
+    re[0] = 1;
+    re[1] = 2;
+    for (int i = 2; i < n; i++) {
+      re[i] = re[i - 1] + re[i - 2];
+    }
+
+    return re[re.length - 1];
+  }
+
+  public static void main(String[] args) {
+    Leetcode746 so = new Leetcode746();
+    System.out.println(so.climbingStairs(3));
+
+    int[] cost = new int[]{10, 15, 20};
+    System.out.println(so.minCostClimbingStairs(cost));
+  }
+}
diff --git a/Week 08/id_613/java/src/test/Leetcode541Test.java b/Week 08/id_613/java/src/test/Leetcode541Test.java
@@ -0,0 +1,24 @@
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+/**
+ *
+ */
+public class Leetcode541Test {
+  @Test
+  public void testSolution1() {
+    String s = "abcdefg";
+    Leetcode541 so = new Leetcode541();
+
+    assertEquals(so.reverseStr(s, 2), "bacdfeg");
+  }
+
+  @Test
+  public void testSolution2() {
+    String s = "a";
+    Leetcode541 so = new Leetcode541();
+
+    assertEquals(so.reverseStr(s, 2), "a");
+  }
+}
+
diff --git a/Week 08/id_613/java/src/test/Leetcode746Test.java b/Week 08/id_613/java/src/test/Leetcode746Test.java
@@ -0,0 +1,22 @@
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ *
+ */
+public class Leetcode746Test {
+  @Test
+  public void testSolution1() {
+    Leetcode746 so = new Leetcode746();
+    int[] cost = new int[]{10, 15, 20};
+    assertEquals(15, so.minCostClimbingStairs(cost));
+  }
+
+  @Test
+  public void testSolution2() {
+    Leetcode746 so = new Leetcode746();
+    int[] cost = new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
+    assertEquals(6, so.minCostClimbingStairs(cost));
+  }
+}