剑指offer新版

linwt · linwt · commit cc6c9766ed67 · 2022-04-23T15:39:23.000+08:00
diff --git a/leetcode_Java/Solution0121.java b/leetcode_Java/Solution0121.java
@@ -79,4 +79,19 @@ public int maxProfit(int[] prices) {
         }
         return maxProfit;
     }
+}
+
+public class Solution {
+    public int maxProfit (int[] prices) {
+        int n = prices.length;
+        if (n < 2) {
+            return 0;
+        }
+        int minPrice = prices[0], profit = 0;
+        for (int i = 1; i < n; i++) {
+            profit = Math.max(profit, prices[i] - minPrice);
+            minPrice = Math.min(minPrice, prices[i]);
+        }
+        return profit;
+    }
 }
diff --git a/剑指Offer_新版_java/DoneType.txt b/剑指Offer_新版_java/DoneType.txt
@@ -63,6 +63,7 @@
 
 五、动态规划
 10. 斐波那契数列
+14. 剪绳子
 19. 正则表达式匹配
 42. 连续子数组的最大和
 46. 把数字翻译成字符串
diff --git a/剑指Offer_新版_java/JZ14.java b/剑指Offer_新版_java/JZ14.java
@@ -1,18 +1,81 @@
 // 14. 剪绳子
 
 
+/*
+动态规划：
+1、题目简化：求长度为n的绳子能得到的最大乘积
+2、定义dp数组：dp[i] 表示长度为i的绳子能得到的最大乘积
+3、初始化：dp[0]=1, dp[1]=1
+4、状态转移方程
+  先把长度为i的绳子拆成两部分，一部分是j，另一部分是i-j，那么会有下面4种情况
+  1）j和i-j都不能再拆了  dp[i] = j * (i-j);
+  2）j能拆，i-j不能拆   dp[i] = dp[j] * (i-j);
+  3）j不能拆，i-j能拆   dp[i] = j * dp[i-j];
+  4）j和i-j都能拆      dp[i] = dp[j] * dp[i-j];
+  取上面4种情况的最大值即可，即两部分在能拆和不能拆时取最大值，然后相乘。由于有多种分段方式，所以多结果再进行比较取最大，整理得到递推公式
+  dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
+5、遍历dp数组填表
+  1）长度为i的绳子能得到的最大乘积，即dp[i]，需要先计算dp[1]到dp[i-1]的值，自底向上计算
+  2）第一个for循环遍历绳子长度，从小到大，从2开始到目标值
+  3）第二个for循环遍历绳子分段后左半部分的长度，遍历到绳子长度一半即可，因为再往后遍历的情况前面已经计算了
+6、返回结果
+ */
 public class Solution {
-    public int cutRope(int target) {
-        if (target == 2) {
-            return 1;
+    public int cutRope (int target) {
+        int[] dp = new int[target + 1];
+        dp[1] = 1;
+        for (int i = 2; i <= target; i++) {
+            for (int j = 1; j <= i / 2; j++) {
+                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
+            }
+        }
+        return dp[target];
+    }
+}
+
+
+/*
+数学：
+1、一个整数先把他分成两部分，x+y=n（假设x>=y并且x-y<=1,也就是说x和y非常接近）那么乘积是x*y。
+  然后我们再把这两部分的差放大(x+1)+(y-1)=n(假设x>=y)；他们的乘积是（x+1）*(y-1)=x*y-(x-y)-1，很明显是小于x*y的。
+  所以我们得出结论，如果把整数n分为两部分，那么这两部分的值相差越小乘积越大。
+  同理还可以证明如果分成3部分，4部分……也是相差越小乘积会越大。
+2、如果我们把长度为n的绳子分为x段，则每段只有在长度相等的时候乘积最大，那么每段的长度是n/x。所以他们的乘积是(n/x)^x。
+  我们来对这个函数求导 y=(n/x)^x
+  通过对函数求导我们发现，当x=n/e的时候，也就是每段绳子的长度是n/x=n/(n/e)=e的时候乘积最大。
+  我们知道e=2.718281828459。而题中我们的绳子剪的长度都是整数，所以不可能取e，我们只能取接近e的值，也就是3的时候乘积最大。
+3、但也有例外，当n<=4的时候会有特殊情况，因为2*2>1*3
+4、如果n大于4，我们不停的把绳子减去3，并且结果不断乘3，最终结果再乘剩余的target
+ */
+public class Solution {
+    public int cutRope (int target) {
+        if (target == 2 || target == 3) {
+            return target - 1;
         }
-        if (target == 3) {
-            return 2;
+        int res = 1;
+        while (target > 4) {
+            target -= 3;
+            res *= 3;
+        }
+        return res * target;
+    }
+}
+
+
+/*
+1、以上解法通过公式直接计算
+2、x表示余数，余1时跟一个3凑成4进行乘积更大，余2时最后乘上即可，余0则刚好等分直接计算
+3、y表示有多少段3,
+ */
+public class Solution {
+    public int cutRope(int target) {
+        if (target == 2 || target == 3) {
+            return target - 1;
         }
         int x = target % 3;
         int y = target / 3;
         if (x == 1) {
-            return (int) Math.pow(3, y - 1) * 2 * 2;
+            return (int) Math.pow(3, y - 1) * 4;
         } else if (x == 2) {
             return (int) Math.pow(3, y) * 2;
         } else {
diff --git a/剑指Offer_新版_java/JZ42.java b/剑指Offer_新版_java/JZ42.java
@@ -1,6 +1,34 @@
 // 42. 连续子数组的最大和
 
 
+/*
+动态规划：
+1、题目简化：求连续子数组最大和
+定义dp数组：dp[i] 表示以索引i结尾的连续子数组的最大和
+2、初始化：dp[0] = array[0] 表示首元素结尾的最大和是对应元素值
+3、状态转移方程
+  1）每次遇到一个新元素，如果前面的连续子数组如果为正数，能提供收益，那么加上后当前元素结尾的连续子数组会变得更大，
+    如果前面的连续子数组如果为负数，不能提供收益，那么直接丢弃，单独它本身会更大
+  2）dp[i] = Math.max(dp[i - 1] + array[i], array[i])
+4、遍历dp数组填表：从索引1开始遍历，根据状态转移方程填表
+5、返回结果：最大的状态就是结果
+ */
+public class Solution {
+    public int FindGreatestSumOfSubArray(int[] array) {
+        int n = array.length;
+        int[] dp = new int[n];
+        dp[0] = array[0];
+        for (int i = 1; i < n; i++) {
+            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
+        }
+        return Arrays.stream(dp).max().getAsInt();
+    }
+}
+
+
+/*
+贪心
+ */
 public class Solution {
     public int FindGreatestSumOfSubArray(int[] array) {
         int maxNum = Arrays.stream(array).max().getAsInt();
diff --git a/剑指Offer_新版_java/JZ46.java b/剑指Offer_新版_java/JZ46.java
@@ -1,25 +1,44 @@
-// 46. 把数组排成最小的数
+// 46. 把数字翻译成字符串
 
 
+/*
+动态规划：
+1、先排除几种特殊情况
+  1）排除0，无法译码
+  2）排除只有一种可能的10和20
+  3）排除当0的前面不是1或2时，无法译码
+2、定义dp数组：dp[i] 表示前i个字符的译码方式数
+3、初始化：填表为1，表示每个字符的译码方式数为1
+4、状态转移方程
+  1）对于一个字符，如果直接译码，则dp[i] = dp[i - 1]；如果组合译码，则dp[i] = dp[i - 2]
+  2）当前字符与前一字符构成 11-19 21-26时，有两种译码方式，则dp[i] = dp[i - 1] + dp[i - 2]
+     否则只有一种译码方式，则dp[i] = dp[i - 1]
+5、遍历dp数组填表：一个for循环遍历dp数组，根据状态转移方程填表
+6、返回结果：最后一个状态就是结果
+ */
 public class Solution {
-    public String PrintMinNumber(int[] numbers) {
-        List<Integer> list = new ArrayList<Integer>();
-        for (int i : numbers) {
-            list.add(i);
+    public int solve (String nums) {
+        if ("0".equals(nums)) {
+            return 0;
         }
-        Collections.sort(list, new Comparator<Integer>() {
-            // 返回负数则第一个参数放在前面，正数或零则第一个参数放在后面
-            @Override
-            public int compare(Integer o1, Integer o2) {
-                String str1 = o1 + "" + o2;
-                String str2 = o2 + "" + o1;
-                return str1.compareTo(str2);
+        if (nums == "10" || nums == "20") {
+            return 1;
+        }
+        int n = nums.length();
+        for (int i = 1; i < n; i++) {
+            if (nums.charAt(i) == '0' && nums.charAt(i - 1) != '1' && nums.charAt(i - 1) != '2') {
+                return 0;
+            }
+        }
+        int[] dp = new int[n + 1];
+        Arrays.fill(dp, 1);
+        for (int i = 2; i <= n; i++) {
+            if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) >= '1' && nums.charAt(i - 1) <= '6')) {
+                dp[i] = dp[i - 1] + dp[i - 2];
+            } else {
+                dp[i] = dp[i - 1];
             }
-        });
-        StringBuilder sb = new StringBuilder();
-        for (Integer i : list) {
-            sb.append(i);
         }
-        return sb.toString();
+        return dp[n];
     }
-}
+}
diff --git a/剑指Offer_新版_java/JZ47.java b/剑指Offer_新版_java/JZ47.java
@@ -0,0 +1,51 @@
+// 47. 礼物的最大价值
+
+
+// 64. 最小路径和（力扣，思路相同，本题是 最大路径和）
+/*
+1、题目简化：求从 (0,0) 到达 (m-1,n-1) 位置的最大路径和
+2、定义dp数组：本题可以直接在原数组操作。grid[i][j] 表示到达 (i,j) 位置的最大路径和
+3、初始化：
+  1）二维dp数组不用扩容，直接根据dp数组的定义就可以直观地对应进行初始化
+  2）首行首列的路径和进行累加初始化
+4、状态转移方程：grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]); 即上方或左方的最大路径和
+5、遍历顺序：两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最大路径和并填表，直到终点，获得结果
+ */
+class Solution {
+    public int minPathSum(int[][] grid) {
+        int n = grid.length, m = grid[0].length;
+        for (int i = 1; i < n; i++) {
+            grid[i][0] += grid[i - 1][0];
+        }
+        for (int j = 1; j < m; j++) {
+            grid[0][j] += grid[0][j - 1];
+        }
+        for (int i = 1; i < n; i++) {
+            for (int j = 1; j < m; j++) {
+                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
+            }
+        }
+        return grid[n - 1][m - 1];
+    }
+}
+
+
+public class Solution {
+    public int maxValue (int[][] grid) {
+        int m = grid.length, n = grid[0].length;
+        int[][] dp = new int[m][n];
+        dp[0][0] = grid[0][0];
+        for (int i = 1; i < m; i++) {
+            dp[i][0] = dp[i - 1][0] + grid[i][0];
+        }
+        for (int j = 1; j < n; j++) {
+            dp[0][j] = dp[0][j - 1] + grid[0][j];
+        }
+        for (int i = 1; i < m; i++) {
+            for (int j = 1; j < n; j++) {
+                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
+            }
+        }
+        return dp[m - 1][n - 1];
+    }
+}
diff --git a/剑指Offer_新版_java/JZ48.java b/剑指Offer_新版_java/JZ48.java
@@ -0,0 +1,55 @@
+// 48. 最长不含重复字符的子字符串
+//同“3. 无重复字符的最长子串”（力扣）
+
+
+/*
+索引定位收缩左区间：
+1、HashMap保存滑动窗口中的字符的索引
+2、如果右指针移动过程新的字符 出现 在滑动窗口中，则更新左指针位置
+3、更新当前字符在HashMap中的索引
+4、右指针每移动一次后，计算新窗口的长度，比较并保存最大长度
+ */
+public class Solution {
+    public int lengthOfLongestSubstring (String s) {
+        int maxLen = 0, start = 0;
+        Map<Character, Integer> map = new HashMap<>();
+        for (int i = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+            if (map.containsKey(c)) {
+                start = Math.max(start, map.get(c) + 1);
+            }
+            map.put(c, i);
+            maxLen = Math.max(maxLen, i - start + 1);
+        }
+        return maxLen;
+    }
+}
+
+
+/*
+左指针右移收缩左区间：
+1、HashMap保存滑动窗口中的字符的出现次数
+2、如果右指针移动过程新的字符 没有 在滑动窗口中，则将字符添加到HashMap中，次数记为1
+3、如果右指针移动过程新的字符 出现 在滑动窗口中，则移动左指针直到同样该字符的下一位，移动过程指向的字符在HashMap中出现次数减1
+4、右指针每移动一次后，计算新窗口的长度，比较并保存最大长度
+ */
+class Solution {
+    public int lengthOfLongestSubstring(String s) {
+        int maxLen = 0, start = 0;
+        Map<Character, Integer> map = new HashMap<>();
+        for (int i = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+            if (map.getOrDefault(c, 0) == 0) {
+                map.put(c, 1);
+            } else {
+                while (s.charAt(start) != c) {
+                    map.put(s.charAt(start), map.get(s.charAt(start)) -1);
+                    start++;
+                }
+                start++;
+            }
+            maxLen = Math.max(maxLen, i - start + 1);
+        }
+        return maxLen;
+    }
+}
diff --git a/剑指Offer_新版_java/JZ56.java b/剑指Offer_新版_java/JZ56.java
@@ -0,0 +1,63 @@
+// 56. 数组中只出现一次的两个数字
+
+
+/*
+集合：用HashSet存放元素，存在则移除，不存在则添加，最终只剩下出现一次的数字，遍历集合元素加到数组，最后数组排序
+ */
+public class Solution {
+    public int[] FindNumsAppearOnce (int[] array) {
+        int[] res = new int[2];
+        Set<Integer> set = new HashSet();
+        for (int i = 0; i < array.length; i++) {
+            if (set.contains(array[i])) {
+                set.remove(array[i]);
+            } else {
+                set.add(array[i]);
+            }
+        }
+        int i = 0;
+        for (Integer num : set) {
+            res[i++] = num;
+        }
+        Arrays.sort(res);
+        return res;
+    }
+}
+
+
+/*
+异或运算：
+1、异或公式
+  1）一个数和 0 做 XOR 运算等于本身：a⊕0 = a
+  2）一个数和其本身做 XOR 运算等于 0：a⊕a = 0
+  3）XOR 运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
+2、先将整个数组元素进行异或运算，结果是 只出现一次的两个数字的异或运算结果
+3、对两个数字的异或结果进行1的与运算，从最低位开始找，找到二进制位首个两者不同的位置
+4、对所有数进行分组并异或运算，最终得到两个数字
+5、存入结果数组，并排序
+ */
+public class Solution {
+    public int[] FindNumsAppearOnce (int[] array) {
+        int temp = 0;
+        for (int num : array) {
+            temp ^= num;
+        }
+        int mask = 1;
+        while ((temp & mask) == 0) {
+            mask <<= 1;
+        }
+        int x = 0, y = 0;
+        for (int num : array) {
+            if ((num & mask) == 0) {
+                x ^= num;
+            } else {
+                y ^= num;
+            }
+        }
+        int[] res = new int[2];
+        res[0] = x;
+        res[1] = y;
+        Arrays.sort(res);
+        return res;
+    }
+}
diff --git a/剑指Offer_新版_java/JZ63.java b/剑指Offer_新版_java/JZ63.java
diff --git a/剑指Offer_新版_java/JZ83.java b/剑指Offer_新版_java/JZ83.java
diff --git a/剑指Offer_新版_java/JZ85.java b/剑指Offer_新版_java/JZ85.java
