剑指offer新版

linwt · linwt · commit 217a393f6cfd · 2022-04-23T20:30:22.000+08:00
diff --git a/leetcode_Java/Solution0110.java b/leetcode_Java/Solution0110.java
@@ -30,7 +30,7 @@
   1）方法功能：入参是一个节点，返回该节点的左右子树是否平衡
   2）终止条件：节点为空时返回true
   3）递归逻辑：调用计算深度的方法得到左右节点的深度，计算高度差是否不超过1，是则平衡返回true，否则不平衡返回false。左右节点同样需要判断是否平衡，因此调用同样的方法
-  4）返回值：
+  4）返回值：节点为根的树是否平衡 且 左节点为根的树是否平衡 且 右节点为根的树是否平衡
  */
 class Solution {
     public boolean isBalanced(TreeNode root) {
diff --git a/剑指Offer_新版_java/DoneType.txt b/剑指Offer_新版_java/DoneType.txt
@@ -8,7 +8,9 @@
 七、排序
 八、位运算
 九、模拟
-十、其他算法
+十、数组
+十一、字符串
+十二、数学
 
 
 一、链表
@@ -82,7 +84,6 @@
 
 
 七、排序
-3. 数组中重复的数字
 40. 最小的K个数
 41. 数据流中的中位数
 51. 数组中的逆序对
@@ -103,21 +104,28 @@
 67. 把字符串转换成整数(atoi)
 
 
-十、其他算法
-5. 替换空格（增删、构造、替换）
-14. 剪绳子
+十、数组
+3. 数组中重复的数字（哈希，集合，排序）
 17. 打印从1到最大的n位数
 21. 调整数组顺序使奇数位于偶数前面
 39. 数组中出现次数超过一半的数字
-43. 整数中1出现的次数（从1到n整数中1出现的次数）
 45. 把数组排成最小的数
 49. 丑数
-50. 第一个只出现一次的字符
 57. 和为S的两个数字
-58. 左旋转字符串
 62. 孩子们的游戏(圆圈中最后剩下的数)
 66. 构建乘积数组
 74. 和为S的连续正数序列
-75. 字符流中第一个不重复的字符
 81. 调整数组顺序使奇数位于偶数前面(二)
+
+
+十一、字符串
+5. 替换空格（增删、构造、替换）
+43. 整数中1出现的次数（从1到n整数中1出现的次数）
+50. 第一个只出现一次的字符
+58. 左旋转字符串
+75. 字符流中第一个不重复的字符
+
+
+十二、数学
+14. 剪绳子
 83. 剪绳子(进阶版)
diff --git a/剑指Offer_新版_java/JZ03.java b/剑指Offer_新版_java/JZ03.java
@@ -0,0 +1,67 @@
+// 3. 数组中重复的数字
+
+
+/*
+原地哈希：把数字交换到正确的位置上
+1、由于数字都在0到n-1的范围内，所以数字和索引可以一一对应，不对应时说明重复了
+2、遍历数组，如果索引与数字相同，说明该数字已经排序好了，继续下一个数字判断
+3、如果索引与数字不同，则将数字交换到正确的位置上
+4、当第二次碰到重复数字时，由于在正确的位置上已经有该值了，则返回该重复数字
+
+元素：3 1 2 3 4
+索引：0 1 2 3 4
+ */
+public class Solution {
+    public int duplicate (int[] numbers) {
+        for (int i = 0; i < numbers.length; i++) {
+            if (i == numbers[i]) {
+                continue;
+            }
+            if (numbers[i] == numbers[numbers[i]]) {
+                return numbers[i];
+            }
+            swap(numbers, i, numbers[i]);
+        }
+        return -1;
+    }
+
+    private void swap(int[] numbers, int x, int y) {
+        int temp = numbers[x];
+        numbers[x] = numbers[y];
+        numbers[y] = temp;
+    }
+}
+
+
+/*
+集合：用HashSet存放元素，存在则返回，不存在则添加，遍历完没找到则返回-1
+ */
+public class Solution {
+    public int duplicate (int[] numbers) {
+        Set<Integer> set = new HashSet<>();
+        for (int num : numbers) {
+            if (set.contains(num)) {
+                return num;
+            } else {
+                set.add(num);
+            }
+        }
+        return -1;
+    }
+}
+
+
+/*
+排序：排序后判断当前数字与前一数字是否相同，相同则返回
+ */
+public class Solution {
+    public int duplicate (int[] numbers) {
+        Arrays.sort(numbers);
+        for (int i = 1; i < numbers.length; i++) {
+            if (numbers[i] == numbers[i - 1]) {
+                return numbers[i];
+            }
+        }
+        return -1;
+    }
+}
diff --git a/剑指Offer_新版_java/JZ06.java b/剑指Offer_新版_java/JZ06.java
@@ -13,7 +13,7 @@ class ListNode {
 
 
 /*
-递归
+递归：递归到尾部后，逐层将节点值添加到列表
  */
 public class Solution {
     private ArrayList<Integer> list = new ArrayList<Integer>();
diff --git a/剑指Offer_新版_java/JZ07.java b/剑指Offer_新版_java/JZ07.java
@@ -13,6 +13,17 @@ class TreeNode {
 */
 
 
+/*
+递归：
+1、方法功能：入参是前序和中序数组，获取前序数组首元素，构造节点，然后返回该节点
+2、终止条件：两个数组为空，结束
+3、递归逻辑：
+  1）由于需要构造左右节点，所以要将数组拆分成左右子树的两部分数组
+  2）先找到头节点在中序数组的位置，将中序数组拆分成左右两部分，根据中序数组左半部分的长度 将前序数组也拆分成左右两部分
+  3）需要构造左右节点，调用同样的方法，把两个数组传进去，得到左右节点
+  4）根节点连接左右节点，返回根节点
+4、返回值：两个数组构造出来的头节点
+ */
 public class Solution {
     public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
         if (pre.length == 0 || in.length == 0) {
diff --git a/剑指Offer_新版_java/JZ50.java b/剑指Offer_新版_java/JZ50.java
@@ -1,4 +1,4 @@
-// 50.第一个只出现一次的字符
+// 50. 第一个只出现一次的字符
 
 
 public class Solution {
diff --git a/剑指Offer_新版_java/JZ56.java b/剑指Offer_新版_java/JZ56.java
@@ -7,7 +7,7 @@
 public class Solution {
     public int[] FindNumsAppearOnce (int[] array) {
         int[] res = new int[2];
-        Set<Integer> set = new HashSet();
+        Set<Integer> set = new HashSet<>();
         for (int i = 0; i < array.length; i++) {
             if (set.contains(array[i])) {
                 set.remove(array[i]);

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,4 @@`
`1`		`-// 50.第一个只出现一次的字符`
	`1`	`+// 50. 第一个只出现一次的字符`
`2`	`2`
`3`	`3`
`4`	`4`	`public class Solution {`