algorithm004-03 · kelly422 · Dec 12, 2019 · Dec 6, 2019 · Dec 9, 2019 · Dec 9, 2019
diff --git a/Week 08/id_713/LeetCode_14_LongestCommonPrefix.java b/Week 08/id_713/LeetCode_14_LongestCommonPrefix.java
@@ -0,0 +1,49 @@
+package id_713;
+
+/**
+ * 14. 最长公共前缀
+ */
+public class LeetCode_14_LongestCommonPrefix {
+
+
+    /*
+    编写一个函数来查找字符串数组中的最长公共前缀。
+
+    如果不存在公共前缀，返回空字符串 ""。
+
+    示例 1:
+
+    输入: ["flower","flow","flight"]
+    输出: "fl"
+
+    示例 2:
+
+    输入: ["dog","racecar","car"]
+    输出: ""
+    解释: 输入不存在公共前缀。
+
+
+    来源：力扣（LeetCode）
+    链接：https://leetcode-cn.com/problems/longest-common-prefix
+    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
+     */
+
+
+    /*
+    水平扫描法
+     */
+    public String longestCommonPrefix(String[] strs) {
+        if (strs == null || strs.length == 0) return "";
+
+        for (int i = 0; i < strs[0].length(); i++) {
+            char c = strs[0].charAt(i);
+            for (int j = 0; j < strs.length; j++) {
+                if (i == strs[j].length() || strs[j].charAt(j) != c) {
+                    return strs[0].substring(0, i);
+                }
+            }
+        }
+
+        return strs[0];
+    }
+}
diff --git a/Week 08/id_713/LeetCode_14_ReverseString.java b/Week 08/id_713/LeetCode_14_ReverseString.java
@@ -0,0 +1,48 @@
+package id_713;
+
+/**
+ * 344. 反转字符串
+ */
+public class LeetCode_14_ReverseString {
+
+
+    /*
+    编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
+
+    不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
+
+    你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
+
+
+
+    示例 1：
+
+    输入：["h","e","l","l","o"]
+    输出：["o","l","l","e","h"]
+
+    示例 2：
+
+    输入：["H","a","n","n","a","h"]
+    输出：["h","a","n","n","a","H"]
+
+    来源：力扣（LeetCode）
+    链接：https://leetcode-cn.com/problems/reverse-string
+    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
+     */
+
+
+    public void reverseString(char[] s) {
+        if (s == null || s.length == 0) return;
+
+        int i = 0, j = s.length - 1;
+
+        while (i < j) {
+            char tmp = s[i];
+            s[i] = s[j];
+            s[j] = tmp;
+            i++;
+            j--;
+        }
+    }
+
+}
diff --git a/Week 08/id_713/LeetCode_151_ReverseWordsInAString.java b/Week 08/id_713/LeetCode_151_ReverseWordsInAString.java
@@ -0,0 +1,133 @@
+package id_713;
+
+import java.util.Arrays;
+import java.util.Collections;
+
+/**
+ * 151. 翻转字符串里的单词
+ */
+public class LeetCode_151_ReverseWordsInAString {
+
+    /*
+    给定一个字符串，逐个翻转字符串中的每个单词。
+
+
+
+    示例 1：
+
+    输入: "the sky is blue"
+    输出: "blue is sky the"
+
+    示例 2：
+
+    输入: "  hello world!  "
+    输出: "world! hello"
+    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
+
+    示例 3：
+
+    输入: "a good   example"
+    输出: "example good a"
+    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
+
+
+
+    说明：
+
+        无空格字符构成一个单词。
+        输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
+        如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
+
+
+
+    进阶：
+
+    请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。
+
+    来源：力扣（LeetCode）
+    链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
+    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
+     */
+
+    public String reverseWords(String s) {
+        if (s == null) return null;
+
+        String[] words = s.trim().split(" +");
+        Collections.reverse(Arrays.asList(words));
+        return String.join(" ", words);
+    }
+
+
+    public String reverseWords2(String s) {
+        StringBuilder sb = new StringBuilder();
+        int i = s.length() - 1;
+
+        while (i >= 0) {
+            if (s.charAt(i) == ' ') {
+                i--;
+                continue;
+            }
+
+            int start = s.lastIndexOf(' ', i);
+            sb.append(" ");
+            sb.append(s.substring(start + 1, i + 1));
+            i = start - 1;
+
+
+        }
+
+        if (sb.length() > 0) {
+            sb.deleteCharAt(0);
+        }
+
+        return sb.toString();
+    }
+
+
+    public String reverseWords3(String s) {
+        if (s == null) return null;
+
+        char[] chars = s.toCharArray();
+        int n = chars.length;
+
+        reverse(chars, 0, n - 1);
+        reverseWord(chars, n);
+        return cleanSpaces(chars, n);
+
+    }
+
+    private void reverseWord(char[] chars, int n) {
+        int i = 0, j = 0;
+
+        while (i < n) {
+            while (i < j || i < n && chars[i] == ' ') i++;
+            while (j < i || j < n && chars[j] == ' ') j++;
+            reverse(chars, i, j - 1);
+        }
+    }
+
+    private void reverse(char[] chars, int i, int j) {
+        while (i < j) {
+            char tmp = chars[i];
+            chars[i] = chars[j];
+            chars[j] = tmp;
+        }
+    }
+
+
+    private String cleanSpaces(char[] chars, int n) {
+        int i = 0, j = 0;
+        while (j < n) {
+            while (j < n && chars[j] == ' ') j++;
+            while (j < n && chars[j] != ' ') chars[i++] = chars[j++];
+            while (j < n && chars[j] == ' ') j++;
+
+            if (j < n) {
+                chars[i++] = ' ';
+            }
+        }
+
+        return new String(chars).substring(0, i);
+    }
+
+}
diff --git a/Week 08/id_713/LeetCode_300_LongestIncreasingSubsequence.java b/Week 08/id_713/LeetCode_300_LongestIncreasingSubsequence.java
@@ -0,0 +1,103 @@
+package id_713;
+
+/**
+ * 300. 最长上升子序列
+ */
+public class LeetCode_300_LongestIncreasingSubsequence {
+
+    /*
+    给定一个无序的整数数组，找到其中最长上升子序列的长度。
+
+    示例:
+
+    输入: [10,9,2,5,3,7,101,18]
+    输出: 4
+    解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
+
+    说明:
+
+        可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
+        你算法的时间复杂度应该为 O(n2) 。
+
+    进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
+
+    来源：力扣（LeetCode）
+    链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
+    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
+     */
+
+
+
+    /*
+
+
+    参考: https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
+
+    朴素动态规划:
+        状态定义:
+            dp[i]的值表示 nums 前i个数字的最长子序列长度
+        转移方程
+            设 j 属于 [0, i), 考虑每轮计算新的dp[i]时, 遍历[0, i)列表区间, 做以下判断
+            1. 当 nums[i] > nums[j]时, nums[i]可以接在nums[j]之后, 此情况下最长上升子序列长度为 dp[j] + 1
+            2. 当 nums[i] <= nums[j]时, nums[i] 无法接在nums[i]之后, 此情况上升序列不成立, 跳过
+
+            上述所有1情况下 计算出的 dp[j] + 1的最大值, 为直到i的上升子序列长度(dp[i])
+                实现方式为 遍历j时, 每轮执行 dp[i] = max(dp[i], dp[j] + 1)
+
+            转移方程: dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)
+            初始状态: dp[i]所有元素置1, 含义是: 每个元素都至少可以单独成为子序列, 长度为1
+            返回值: 返回dp数组中最大值, 即可得到全局最长上升子序列长度
+
+    高级动态规划
+        1. 动态规划中, 通过线性遍历来计算dp的复杂度无法降低
+        2. 每轮计算中, 需要通过线性遍历 [0, k)区间元素来得到 dp[k]. 考虑, 是否可以通过重新设计状态定义, 使整个dp为一个排序列表
+            这样在计算每个dp[k]时, 就可以通过二分查找法遍历 [0, k)区间元素, 将此部分复杂度有 O(N) 降低至 O(logN)
+
+        新状态定义
+            维护一个列表 dp, 其中每个元素 dp[k]的值代表 长度为 k+1的子序列尾部元素值
+            如 [1,4,6]序列, 长度为1,2,3的子序列尾部元素值分别为 dp = [1,4,6]
+
+        状态转移设计
+            设常量数字N, 和随机数x, 可以推出: 当N越小时, N < x的纪律越大
+                如 N = 0 比 N = 1000更可能满足  N < x
+
+            在遍历计算每个 tails[k]，不断更新长度为 [1,k]的子序列尾部元素值，始终保持每个尾部元素值最小 （例如 [1,5,3]]， 遍历到元素 555 时，长度为 222 的子序列尾部元素值为 555；当遍历到元素 333 时，尾部元素值应更新至 333，因为 333 遇到比它大的数字的几率更大）。
+
+
+
+
+
+    [10  9   2   5   3   7   21  18]
+
+    [0  0   0   0   0   0   0   0]
+    [10  0   0   0   0   0   0   0]
+    [9  0   0   0   0   0   0   0]
+    [2  0   0   0   0   0   0   0]
+    [2  5   0   0   0   0   0   0]
+    [2  3   0   0   0   0   0   0]
+    [2  3   7   0   0   0   0   0]
+    [2  3   7   21   0   0   0   0]
+    [2  3   7   18   0   0   0   0]
+
+    数组的长度, 即为最大上升子序列
+     */
+
+    public int lengthOfLIS(int[] nums) {
+
+        int[] tails = new int[nums.length];
+        int res = 0;
+
+        for (int num : nums) {
+            int i = 0, j = res;
+            while (i < j) {
+                int m = (i + j) / 2;
+                if (tails[m] < num) i = m + 1;
+                else j = m;
+            }
+            tails[i] = num;
+            if (res == j) res++;
+        }
+
+        return res;
+    }
+}
diff --git a/Week 08/id_713/LeetCode_387_FirstUniqueCharacterInAString.java b/Week 08/id_713/LeetCode_387_FirstUniqueCharacterInAString.java
@@ -0,0 +1,42 @@
+package id_713;
+
+import java.util.HashMap;
+
+/**
+ * 387. 字符串中的第一个唯一字符
+ */
+public class LeetCode_387_FirstUniqueCharacterInAString {
+
+    /*
+    给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
+
+    案例:
+
+    s = "leetcode"
+    返回 0.
+
+    s = "loveleetcode",
+    返回 2.
+
+    来源：力扣（LeetCode）
+    链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string
+    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
+     */
+
+    public int firstUniqChar(String s) {
+        HashMap<Character, Integer> map = new HashMap<>();
+
+        for (int i = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+            map.put(c, map.getOrDefault(c, 0) + 1);
+        }
+
+        for (int i = 0; i < s.length(); i++) {
+            if (map.get(s.charAt(i)) == 1) {
+                return i;
+            }
+        }
+
+        return -1;
+    }
+}