剑指Offer算法学习

剑指Offer

Day03

剑指Offer0.5替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

字符串为不可变对象

示例 1：

1 2	输入：s = "We are happy." 输出："We%20are%20happy."

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

运用到String的toCharArray() 可以将字符串转换成字符数组

字符之间的拼接用StringBuffer,append()方法可以添加字符串或者字符

public String replaceSpace(String s) {
      StringBuffer res = new StringBuffer();
      for(Character c:s.toCharArray()){
          if(c==' '){
              res.append("%20");
          }else {
              res.append(c);
          }
      }
      return res.toString();
   	//String中的replace方法
      /*String res =  s.replace(" ","%20");
      return res;*/
  }

剑指Offer58- ||.左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例 1：

1 2	输入: s = "abcdefg", k = 2 输出: "cdefgab"

示例 2：

1 2	输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

String中的subString()切片函数。返回字符串的子字符串，参数为索引。

StingBuffer和StringBuffer区别：

StringBuilder 的方法不是线程安全的（不能同步访问）。
StringBuilder 相较于 StringBuffer 有速度优势，所以多数情况下建议使用 StringBuilder 类。

方法一：字符串切片

1
2
3

public String reverseLeftWords(String s, int n) {
      return s.substring(n, s.length()) + s.substring(0, n);
  }

方法二：列表遍历拼接

public String reverseLeftWords(String s, int n) {
       StringBuilder res = new StringBuilder();
       for(int i = n; i < s.length(); i++)
           res.append(s.charAt(i));
       for(int i = 0; i < n; i++)
           res.append(s.charAt(i));
       return res.toString();
   }

//取余化简。妙啊
public String reverseLeftWords(String s, int n) {
       StringBuilder res = new StringBuilder();
       for(int i = n; i < n + s.length(); i++)
           res.append(s.charAt(i % s.length()));
       return res.toString();
   }

方法二：字符串遍历拼接(只能用String时)

	public String reverseLeftWords(String s, int n) {
       String res = "";
       for(int i = n; i < s.length(); i++)
           res += s.charAt(i);
       for(int i = 0; i < n; i++)
           res += s.charAt(i);
       return res;
   }
//取余化简代码
public String reverseLeftWords(String s, int n) {
       String res = "";
       for(int i = n; i < n + s.length(); i++)
           res += s.charAt(i % s.length());
       return res;
   }

Day04

剑指Offer03.数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

1
2
3

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

知识点

可以用哈希表来做。直接使用是否contain方法查看是否包含，有包含则重复出现

HashSet基于 HashMap 来实现的，是一个不允许有重复元素的集合。

HashSet 允许有 null 值。

HashSet 是无序的，即不会记录插入的顺序。

HashSet主要针对单一元素。add()重复元素不会被添加。

使用原地条件主要条件**在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内。数组元素的 **索引和值是 一对多 的关系。

该方法不用占用空间。空间复杂度为O(1)。

方法一：哈希表/set

public static int findRepeatNumber1(int[] nums) {
    HashSet<Integer> map = new HashSet<>();
    for (int num : nums) {
        if (map.contains(num)) {
            return num;
        }
        map.add(num);
    }
    return -1;
}

方法二：原地交换

题目说明尚未被充分使用，即 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。此说明含义：数组元素的索引和值是 一对多 的关系。
因此，可遍历数组并通过交换操作，使元素的索引与值一一对应（即 nums[i] = i）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

public static int findRepeatNumber(int[] nums) {
   		int i = 0;
        while (i < nums.length) {
            //说明数字已经在对应的索引位置上。
            if (nums[i] == i) {
                i++;
                continue;
            }
            //判断索引值为nums[i]上是否存在于当前nums[i]相等的值，即找到一组重复值
            if (nums[nums[i]] == nums[i]) {
                return nums[i];
            }
            //将该元素交换到与之相等的索引位置上
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
}

剑指Offer53-|.在排序数组中查找数字|

统计一个数字在排序数组中出现的次数。

示例 1:

1 2	输入: nums = [5,7,7,8,8,10], target = 8 输出: 2

示例 2:

1 2	输入: nums = [5,7,7,8,8,10], target = 6 输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

排序数组中的搜索问题，首先想到 二分法 解决。

通过二分法找到target个数数组的左边界left和右边界right。应用了两次二分法可以得到target的数量为right-left-1。

public int search(int[] nums, int target) {
       //第一次二分
       // 搜索右边界 right
       int i = 0, j = nums.length - 1;
       while(i <= j) {
           int m = (i + j) / 2;
           if(nums[m] <= target) i = m + 1;
           else j = m - 1;
       }
       //找到右边界下标
       int right = i;
       //此时的j在i的前面，即有右边界的前面，所有如果j位置上的不等于目标值，说明没有该数
       //若数组中无 target ，则提前返回
       if(j >= 0 && nums[j] != target) return 0;
       //第二次二分
       // 搜索左边界 right
       i = 0; j = nums.length - 1;
       while(i <= j) {
           int m = (i + j) / 2;
           if(nums[m] < target) i = m + 1;
           else j = m - 1;
       }
       int left = j;
       return right - left - 1;
   }

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

1 2	输入: [0,1,3] 输出: 2

示例 2:

1 2	输入: [0,1,2,3,4,5,6,7,9] 输出: 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

主要点是缺失的数字等于“右子数组的首位元素” 对应的索引。因此考虑使用二分法查找 “右子数组的首位元素” 。

即是找到右边界

排序数组使用双指针和二分法是高频选择

二分法时，循环的最后j始终在i的左边。

public int missingNumber(int[] nums) {
       int i = 0, j = nums.length - 1;
       while(i <= j) {
           int m = (i + j) / 2;
           if(nums[m] == m) i = m + 1;
           else j = m - 1;
       }
       return i;
   }

Day05

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

若使用暴力法遍历矩阵 matrix ，则时间复杂度为 O(NM) 。暴力法未利用矩阵 “从上到下递增、从左到右递增” 的特点，

显然不是最优解法。

我们将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树 ，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target 。

若行索引或列索引越界，则代表矩阵中无目标值，返回 false

“根节点” 对应的是矩阵的 “左下角” 和 “右上角” 元素，本文称之为 标志数 ，以 matrix 中的 左下角元素 为标志数 flag ，则有:

若flag > target，则 target 一定在 flag 所在行的上方，即flag所在行可被消去。
若 flag < target ，则 target 一定在 flag 所在列的右方，即flag所在列可被消去。

方法一：暴力解法

public static boolean findNumberIn2DArray(int[][] matrix, int target) {

    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}

方法二：利用标志数求解

public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        //从二维数组的左下角开始往上走。
        int i = matrix.length - 1, j = 0;
        //行索引或列索引越界，则跳出循环
        while (i >= 0 && j < matrix[0].length) {
            //设置矩阵左下角为标志数
            int flag = matrix[i][j];
            if (target < flag) {
                //消去一列
                i--;
            } else if (target > flag) {
                //消去一行
                j++;
            } else {
                return true;
            }
        }
        return false;
    }

时间复杂度O(N+M)：其中，NN 和 MM 分别为矩阵行数和列数，此算法最多循环 M+N次。

空间复杂度O(1)。

二分法：

仔细看题（解题的关键在认真读题），分析清楚题目要找的答案需要满足什么性质。采用两边夹的方式，每一轮把待搜索区间分成两个部分，排除掉一定不是答案的区间，最后左右指针重合的地方就是我们要找的元素。

即是要分清搜索区间是在哪。在于我们能够根据题意：得到某种单调性，和可以逐步缩小搜索规模的条件，进而准确地设计可以使得搜索区间缩小的条件。只看到 while (left < right) 里的 < ，不能说明右边界不能取到。真正看区间表示应该看左右边界到底如何设置，如果我们分析出下一轮搜索的范围是 [left..mid] 而设置 right = mid + 1，才表示搜索区间为「左闭右开」区间。这是因为 [left..right) = [left..mid + 1) = [left..mid]。

while (left <= right) 表示在区间里只剩下一个元素的时候，我们还需要继续查找，因此循环可以继续的条件是 left <= right，这一行代码对应了二分查找算法的思路 1：在循环体中查找元素。

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

1 2	输入：[3,4,5,1,2] 输出：1

示例 2：

1 2	输入：[2,2,2,0,1] 输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

递增排序的数组的一个旋转的特性：该数组的最小值一定是数组旋转过去后的第一个数。

排序数组的查找问题首先考虑的是二分法解决。其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别 。

当numbers[mid] = numbers[j]时，只需要j-1即可，把j舍弃掉一个并不影响结果。

//利用二分法来解决
public static int minArray1(int[] numbers) {
    int i = 0, j = numbers.length - 1;
    while (i < j) {
        int mid = (i + j) / 2;
        if (numbers[mid] > numbers[j]) {
            //一定在右排序数组
            i = mid + 1;
        } else if (numbers[mid] < numbers[j]) {
            //一定
            j = mid;
        } else {
        //当numbers[mid] = numbers[j]时，只需要j-1即可，把j舍弃掉一个并不影响结果。
        //当出现 nums[m] = nums[j] 时，一定有区间 [i, m] 内所有元素相等 或 区间 [m, j] 内所有元素相等
            j--;
        }
    }
    //因为此时i=j,即是找到了最下数
    return numbers[i];
}

时间复杂度O(log2*N*)。

空间复杂度O(1)。

剑指 Offer 50. 第一次只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

1 2	输入：s = "abaccdeff" 输出：'b'

示例 2:

1 2	输入：s = "" 输出：' '

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

考察哈希表的使用。在字符串长度较大、重复字符很多时，“有序哈希表” 解法理论上效率更高。

方法一：哈希表

public static char firstUniqChar0(String s) {

    HashMap<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        map.put(s.charAt(i), map.getOrDefault(s.charAt(i),0) + 1);
    }
    for (int i = 0; i < s.length(); i++) {
        if(map.get(s.charAt(i))==1){
            return s.charAt(i);
        }
    }
    return ' ';
}

利用boolean类型

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character, Boolean> dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(char c : sc)
            if(dic.get(c)) return c;
        return ' ';
    }
}

时间复杂度O(N)：N 为字符串 s 的长度；需遍历 s 两轮，使用 O*(N) ；HashMap 查找操作的复杂度为O*(1) ；

空间复杂度O(1)：由于题目指出 s 只包含小写字母，因此最多有 26 个不同字符，HashMap 存储需占用 O*(26)=O(1) 的额外空间。

方法二：有序哈希表

知识点

在哈希表的基础上，有序哈希表中的键值对是 按照插入顺序排序 的。因此可以遍历有序哈希表来找到第一次出现的字符。

即第二次循环采用遍历有序哈希表的方式

哈希表是去重的，即哈希表中键值对数量 ≤ 字符串 s 的长度

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> dic = new LinkedHashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        //遍历有序哈希表
        for(Map.Entry<Character, Boolean> d : dic.entrySet()){
           if(d.getValue()) return d.getKey();
        }
        return ' ';
    }
}

时间复杂度和空间复杂度和方法一相同

Day06

剑指 Offer 32-| 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1	[3,9,20,15,7]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

广度优先搜索(BFS)通常借助队列的先入先出的特性来实现

public static int[] levelOrder(TreeNode root) {
       if (root == null) {
           return new int[0];
       }
       //队列先进先出存放结点
       Queue<TreeNode> queue = new LinkedList<>();
       ArrayList<Integer> arrayList = new ArrayList<>();
       queue.add(root);
       while (!queue.isEmpty()) {
           TreeNode node = queue.remove();
           arrayList.add(node.val);
           //将左右结点放入队列
           if (node.left != null) queue.add(node.left);
           if (node.right != null) queue.add(node.right);
       }
       int[] res = new int[arrayList.size()];
       for (int i = 0; i < res.length; i++) {
           res[i] = arrayList.get(i);
       }
       return res;
   }

时间复杂度O(N)：N 为二叉树的节点数量，即 BFS 需循环 N 次。

空间复杂度O(N)：最差情况下，即当树为平衡二叉树时，最多有 N*/2 个树节点同时在 queue 中，使用 O*(N) 大小的额外空间。

剑指 Offer 32-|| 从上到下打印二叉树 ||

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

主要重点是加入队列长度为循环条件，即是每层打印。

一次while即是二叉树的一层

public static List<List<Integer>> levelOrder0(TreeNode root) {
       Queue<TreeNode> queue = new LinkedList<>();
       List<List<Integer>> arrayList = new ArrayList<>();
       if (root != null) {
           queue.add(root);
       }
       while (!queue.isEmpty()) {
           //新建一个临时列表，存储当前的打印结果。
           List<Integer> arrayList1 = new ArrayList<>();
           //循环次数为当前层结点数
           for (int i = queue.size(); i > 0; i--) {
               TreeNode node = queue.remove();
               //向列表添加结果
               arrayList1.add(node.val);
               if (node.left != null) {
                   queue.add(node.left);
               }
               if (node.right != null) {
                   queue.add(node.right);
               }
           }
           arrayList.add(arrayList1);
       }
       return arrayList;
   }

时间复杂度O(N)：N 为二叉树的节点数量，即 BFS 需循环 N 次。

空间复杂度O(N)：最差情况下，即当树为平衡二叉树时，最多有 N*/2 个树节点同时在 queue 中，使用 O*(N) 大小的额外空间。

剑指 Offer 32-||| 从上到下打印二叉树 |||

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

利用双端队列添加数据

方法一：双端队列

public static List<List<Integer>> levelOrder(TreeNode root) {
    LinkedList<TreeNode> queue = new LinkedList<>();
    //辅助队列
    List<List<Integer>> arrayList = new ArrayList<>();
    int index = 1;
    if (root != null) {
        queue.add(root);
    }
    while (!queue.isEmpty()) {
        List<Integer> arrayList1 = new LinkedList<>();
        for (int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            if (index % 2 == 0) {
                //这里这样写就不用使用双端队列：add(0,node.val);
                //双端队列的写法是addFirst();
                //add(0, node.val);在列表的指定位置插入指定元素（可选操作）。
                //将当前处于该位置的元素（如果有的话）和所有后续元素向右移动（在其索引中加 1）。
                // 因为index是0，所以相当于不断向类别第一个位置插入元素
                arrayList1.add(0, node.val);
            } else {
                arrayList1.add(node.val);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        index++;
        arrayList.add(arrayList1);
    }
    return arrayList;
}

方法二：双端队列(奇偶层逻辑分离)

知识点

定死奇偶顺序，想比于方法一消除了冗余判断

循环打印奇偶层

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) deque.add(root);
        while(!deque.isEmpty()) {
            // 打印奇数层
            List<Integer> tmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从左向右打印
                TreeNode node = deque.removeFirst();
                tmp.add(node.val);
                // 先左后右加入下层节点
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
            res.add(tmp);
            if(deque.isEmpty()) break; // 若为空则提前跳出
            // 打印偶数层
            tmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从右向左打印
                TreeNode node = deque.removeLast();
                tmp.add(node.val);
                // 先右后左加入下层节点
                if(node.right != null) deque.addFirst(node.right);
                if(node.left != null) deque.addFirst(node.left);
            }
            res.add(tmp);
        }
        return res;
    }
}

时间复杂度等同上一个方法一样

方法三：倒序

public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    if(root != null) queue.add(root);
    while(!queue.isEmpty()) {
        List<Integer> tmp = new ArrayList<>();
        for(int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            tmp.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        if(res.size() % 2 == 1) Collections.reverse(tmp);
        res.add(tmp);
    }
    return res;
}

Day07

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

给定的树 B：

1
2
3

  4 
 /
1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1 2	输入：A = [1,2,3], B = [3,1] 输出：false

示例 2：

1 2	输入：A = [3,4,5,1,2], B = [4,1] 输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

recur(A, B) 函数：

终止条件：
当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回true ；
当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ；
当节点 A 和 B 的值不同：说明匹配失败，返回 false ；
返回值：
判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ；
判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；
isSubStructure(A, B) 函数：

特例处理： 当树 A 为空或树 B 为空时，直接返回 false ；
返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；

//这个方法就是判断B是否为A的子结构
public static boolean isSubStructure0(TreeNode A, TreeNode B) {
    //约定空树不是任意一个树的子结构
    if (A == null || B == null) {
        return false;
    }
    if (recur(A, B)) {
        return true;
    }
    //递归判断A树所有子树是否包含B树，判断A树根节点的左子结点和右子结点是否包含B树
    return isSubStructure0(A.left, B) || isSubStructure0(A.right, B);
}

//该函数的作用是：判断A树根节点值和B树根节点值是否相等，若不等，返回false，
//若相等再递归判断A树的孩子节点和B树的的孩子节点是否对应相等，
//如果对应相等了，就说明A的子结构包含B树，返回true。否者就不包含，返回false
public static Boolean recur(TreeNode A, TreeNode B) {
    //B为空说明B树已经完成匹配(越过叶子结点)
    if (B == null) {
        return true;
    }
    if (A == null || A.val != B.val) {
        //说明A树的根结点和B树的根结点不相等
        return false;
    }
    //上述条件都不满足时，即是根结点相等，走子结点
    //即看A树的左右子结点是否也跟跟B树的左右结点一样	
    return recur(A.left, B.left) && recur(A.right, B.right);
}

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

       4
    /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：

     4
    /   \
  7     2
 / \   / \
9   6 3   1

示例 1：

1 2	输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

二叉树镜像定义： 对于二叉树中任意节点 root ，设其左 / 右子节点分别为left,right ；则在二叉树的镜像中的对应 root 节点，其左 / 右子节点分别为 right,left 。

根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。

方法一：递归自上而下

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    //先交换左右子树
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    //遍历进去持续进行交换左右子树
    mirrorTree2(root.right);
    mirrorTree2(root.left);

    return root;
}

时间复杂度 O(N) ：其中 NN 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间。
空间复杂度 O(N) ：最差情况下（当二叉树退化为链表），递归时系统需使用 O(N) 大小的栈空间。

方法二：自己写的

知识点

整体思路是将子树的左节点拼接在新树的右子结点，将右子结点拼接在新树的左子结点。

public static TreeNode mirrorTree0(TreeNode root) {
    if (root == null) {
        return null;
    }
    //最终要输出的数
    TreeNode res = new TreeNode(root.val);
    recur(root, res);
    return res;
}

public static void recur(TreeNode root, TreeNode res) {
    if (root == null) {
        return;
    }
    //一直将左子结点拼接在新树的右子结点
    if (root.left != null) {
        res.right = new TreeNode(root.left.val);
    }
    recur(root.left, res.right);
    //一直将右子结点拼接在新树的左子结点
    if (root.right != null) {
        res.left = new TreeNode(root.right.val);
    }
    recur(root.right, res.left);
}

剑指 Offer 28.对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

示例 1：

1 2	输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：

1 2	输入：root = [1,2,2,null,3,null,3] 输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

对称二叉树定义：对于树中任意两个对称节点 LL 和 RR ，一定有：
L.val = R.val ：即此两对称节点值相等。
L.left.val = R.right.val：即 L 的左子节点和 R的右子节点对称；
L.right.val = R.left.val ：即 L 的右子节点和 R 的左子节点对称。

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    return recur(root.left, root.right);
}

public static boolean recur(TreeNode L, TreeNode R) {
    //当 L 和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回 true
    if (L == null && R == null) return true;
    if (L == null || R == null || L.val != R.val) return false;
    //向下递归，以上都不满足，说明满足L==R
    //精髓在于返回值
    return recur(L.left, R.right) && recur(L.right, R.left);
}

时间复杂度：O(N)

空间复杂度：O(N)

Day08

剑指 Offer 10-|.斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

1 2	F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1 2	输入：n = 2 输出：1

示例 2：

1 2	输入：n = 5 输出：5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

知识点

答案需要取模 1e9+7（1000000007）意思是每次计算都要取模1000000007

由于 F*(n) 只和F*(n−1) 与 F*(n−2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O*(1)

方法一：递推动态规划

public int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        c =c% 1000000007;
        //先得出后一个结果，然后往后交换
        a = b;
        b = c;
    }

    return b;
}

时间复杂度：O*(n)。
空间复杂度：O(1)。

方法二：递归动态规划

int[] cache = new int[110];

public int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    //递归调用，当n是之前出现过得数，则直接返回数组中存储的数值
    if (cache[n] != 0) {
        return cache[n];
    }
    cache[n] = fib(n - 1) + fib(n - 2);
    //每次计算都取模，防止超出限制
    cache[n] = cache[n] % 1000000007;

    return cache[n];
 }

时间复杂度：O*(*n)。
空间复杂度：O(n)。

剑指 Offer 10-||.青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1 2	输入：n = 2 输出：2

示例 2：

1 2	输入：n = 7 输出：21

示例 3：

1 2	输入：n = 0 输出：1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

同斐波那契数列的转移方程相同。唯一不同的是起始数字不同

青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 ；
斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。

int[] cache = new int[110];

    public int numWays(int n) {
        if (n < 2) {
            return 1;
        }
        if (n == 2) {
            return n;
        }
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = numWays0(n - 1) + numWays0(n - 2);
        cache[n] = cache[n] % 1000000007;
        return cache[n];
    }
}

时间复杂度：O*(*n)。
空间复杂度：O(n)。

剑指 Offer 63.股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

状态定义：设动态规划列表 dp ，dp[i] 代表以 prices[i] 为结尾的子数组的最大利润（以下简称为前 i 日的最大利润 ）。
转移方程：由于题目限定 “买卖该股票一次” ，因此前 i 日最大利润 dp[i] 等于前 i−1 日最大利润 dp[i−1] 和第 i 日卖出的最大利润中的最大值。

前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)
dp[i]=max(dp[i−1],prices[i]−min(prices[0:i]))

初始状态：dp[0]=0 ，即首日利润为 0 ；
返回值： dp[n−1] ，其中 n 为 dp 列表长度。

用一个变量代替dp数组降低空间复杂度

public int maxProfit(int[] prices) {
    if (prices.length == 0) {
            return 0;
        }
        //cost是i天前的最低价格
        int mincost = prices[0];
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            mincost = Math.min(mincost, prices[i]);
            //第i最大利润为i天前的最大利润和i天当天的利润最大值
            profit = Math.max(profit, prices[i] - mincost);
        }
        return profit;
	}
}

时间复杂度：O*(*n)。
空间复杂度：O(n)。

用到数组的动态规划

public static int maxProfit(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }
    //cost是i天前的最低价格
    int mincost = prices[0];
    int[] dp = new int[prices.length];
    for (int i = 1; i < prices.length; i++) {
        mincost = Math.min(mincost, prices[i]);
        //第i天最大利润为i天前的最大利润和i天当天的利润最大值
        dp[i] = Math.max(dp[i - 1], prices[i] - mincost);
    }
    return dp[prices.length - 1];
}

Day09

剑指Offer 42.连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

1
2
3

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

动态规划求解，原数组i下标数组下存放的是以i为结尾的连续数组最大和

转移方程：若nums[i-1]<=0，说明nums[i-1]对nums[i]产生负影响，即nums[i-1]+nums[i]还不如nums[i]本身大

又因为题目要求连续数组，此时可以直接舍弃前面的数，重新开始计数。nums[i] 值不变就是表明重新开始。

public int maxSubArray(int[] nums) {
     int max = nums[0];
     for (int i = 1; i < nums.length; i++) {
          if (nums[i - 1] > 0) {
              nums[i] = nums[i - 1] + nums[i];
          }
          max = Math.max(nums[i],max);
      }
      return max;
}

时间复杂度 O(N) ：线性遍历数组 nums 即可获得结果，使用 O(N) 时间。
空间复杂度 O(1) ：使用常数大小的额外空间。

前缀和

public int maxSubArray(int[] nums) {
        int preSum = 0;
        int minSum = 0;
        int maxSubSum = Integer.MIN_VALUE;
        for (int num : nums) {
            //前缀合，不断加上当前num值
            preSum += num;
            //前缀和减去最小的值，再和之前获得的最大值比较，取最大值
            maxSubSum = Math.max(maxSubSum, preSum - minSum);
            //得到最小值
            minSum = Math.min(minSum, preSum);
        }
        return maxSubSum;
    }

剑指 Offer 47.礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。

设 f(i, j) 为从棋盘左上角走至单元格 (i ,j) 的礼物最大累计价值，易得到以下递推关系：f(i,j) 等于 f(i,j-1) 和 f(i-1,j)中的较大值加上当前单元格礼物价值 grid(i,j) 。

因此用动态规划来做：转移方程 f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j)

通过增加一行和一列的空间来简化代码并解决边界问题，因为i-1和j-1在i和j都为0时越界。

public int maxValue(int[][] grid) {
    //设置多一个0值
    int[][] dp = new int[grid.length + 1][grid[0].length + 1];
    //设置初始值0
    for (int i = 0; i < dp[0].length; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i < dp.length; i++) {
        dp[i][0] = 0;
    }
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }
    return dp[dp.length - 1][dp[0].length - 1];
}

Daya10

剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

方法一：字符串遍历

public static int translateNum1(int num) {
    String s = String.valueOf(num);
    //b是第0位，a是第一位
    int b = 1, a = 1;
    for (int i = 2; i < s.length(); i++) {
        //此时不包括右边的i
        String temp = s.substring(i - 2, i);
        //a
        int c = temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0 ? a + b : a;
        //循环往后
        b = a;
        a = c;
    }
    //返回最后的值
    return a;
}

此题的动态规划计算是对称的，即从左向右遍历（从第 dp[2] 计算至 dp[n] ）和从右向左遍历（从第 dp[n - 2]dp[n−2] 计算至 dp[0]）所得方案数一致。

public int translateNum2(int num) {
    String s = String.valueOf(num);
    int a = 1, b = 1;
    for (int i = s.length() - 2; i > -1; i--) {
        String tmp = s.substring(i, i + 2);
        int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
        b = a;
        a = c;
    }
    return a;
}

public int translateNum3(int num) {
    int a = 1, b = 1, x;
    //先的得到个位数
    int y = num % 10;
    //当num还有数时
    while (num != 0) {
        //进入循环，减去一个数
        num /= 10;
        //得到y往前一个数
        x = num % 10;
        //将x，y合并变为十位数，用于判断
        int temp = x * 10 + y;
        int c = (temp >= 10 && temp <= 25) ? a + b : a;
        b = a;
        a = c;
        //往前走
        y = x;
    }
    return a;
}

剑指 Offer 48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

哈希表用来记录元素和其索引下标

左指针 start 更新左指针根据上轮左指针start和当前重复元素的下标的最大值，保证了区间 [ start+1, map.get[temp] ]内无重复元素

1	start = Math.max(start,map.get(tmp));

最终结果max：取上一轮max和滑动窗口i-start中的最大值

1	Math.max(max,i-start);

需要注意的是左指针必须是从-1开始

public int lengthOfLongestSubstring(String s) {
       //if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0;
       //划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0。
       int max = 0,start =-1;
       //使用哈希表map统计各字符最后一次出现的索引位置
       HashMap<Character,Integer> map = new HashMap<>();
       for(int i=0;i<s.length();i++){
           char tmp = s.charAt(i);

           //当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新:
           //当index>start时，start更新为当前的index,否则保持不变。
           //注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。
       
           if(map.containsKey(tmp)) start = Math.max(start,map.get(tmp));

           //如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新
           map.put(tmp,i);

           //i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新。
           //如果是上面没有进入if条件，是第一次出现的元素，i-start相当于增加了1
           max = Math.max(max,i-start);
       }
       return max;
   }

复杂度分析：
时间复杂度 O(N)：其中 N 为字符串长度，动态规划需遍历计算 dp列表。
空间复杂度 O(1)：字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128) = O(1)大小的额外空间。

Day11

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

1
2
3

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

1
2
3

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

知识点

关键在与要设置一个前置指针用于删除结点。

public static ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode cur = head.next;
        ListNode pre = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return head;
    }

时间复杂度 O(N)： N为链表长度，删除操作平均循环N/2次，最差N次。
空间复杂度 O(1)：占用常数个空间。

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

1
2
3

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

使用双指针。先初始化双指针都指向head。构建一个双指针的距离为k。然后共同移动双指针每轮都走一步。直到前指针走到链表尾结点时跳出（跳出后， latter 与尾节点距离为 k-1，即 latter 指向倒数第 k 个节点）。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //former为前指针，latter为后一个。
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++) {
            //判空
            if(former == null) return null;
            former = former.next;
        }
        //不为空时共同向后移动
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

普通方法：先计算长度然后得到目标结点

public ListNode getKthFromEnd(ListNode head, int k) {
    if (head == null) {
        return null;
    }
    int size = getLength(head);
    if (k < 0 || k - size > 0) {
        return null;
    }
    ListNode cur = head;
    for (int i = 0; i < size - k; i++) {
        cur = cur.next;
    }

    return cur;
}

public int getLength(ListNode head) {
    if (head == null) { //空链表
        return 0;
    }
    int length = 0;
    // 定义一个辅助变量
    ListNode cur = head;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

Day12

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

1 2	输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

因为两个链表是递增的，所以使用双指针L1和L2来遍历两个链表，根据两个指针所指向结点的大小关系来确定结点添加顺序

算法流程

首先初始化伪头节点，循环合并：当其中一个指针遍历到最后为空时，跳出循环。判断两个指针指向的节点值，将小的值添加到伪头节点后。当其中一个指针指向空时，则判断是哪个指针指向不为空，将该指针添加到结果链表后。

public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {

    //创建伪头节点
    ListNode res = new ListNode(0);
    ListNode head = res;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            res.next = l1;
            l1 = l1.next;
        } else {
            res.next = l2;
            l2 = l2.next;
        }
        res = res.next;
    }
    if (l1 != null) {
        res.next = l1;
    }
    if (l2 != null) {
        res.next = l2;
    }
    return head.next;
}

时间复杂度 O(M+N) ： M, N分别为链表 L1, L2的长度，合并操作需遍历两链表。
空间复杂度 O(1) ：节点引用 dum, cur 使用常数大小的额外空间。

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

1
2
3

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

1
2
3

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

这样，当它们相遇时，所指向的结点就是第一个公共结点。

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode curA = headA, curB = headB;
    while (curA != curB) {
        if (curA != null) {
            curA = curA.next;
        } else {
            //遍历完再去遍历B链表
            curA = headB;
        }
        if (curB != null) {
            curB = curB.next;
        } else {
            //遍历完再去遍历A链表
            curB = headA;
        }
    }
    //循环结束，相遇直接返回A指针
    return curA;
}

- 时间复杂度：O(M+N)。M和N为A,B链表的长度。
- 空间复杂度：O(1)。

Day13

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

1
2
3

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

双指针，在数组的头和尾分别定义一个指针,指针left从左往右寻找偶数，指针从右往左寻找奇数，将找到的偶数和奇数交换位置。

最终保证指针left左边都是奇数，指针right右边都是偶数。

指针left遇到奇数则执行left++跳过，直到找到偶数

指针right遇到偶数则执行right++跳过，直到找到奇数

public static int[] exchange0(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    //两个指针相遇的时候跳出
    while (left < right) {
        //找到偶数,还有加上left<right判断是因为肯提前遇到left==right
        //类似于[1,3,5]这个例子
        //可以直接使用nums[left] & 1，因为nums[left]等价与nums[left] % 2 != 0
        while (left < right && nums[left] % 2 != 0) {
            left++;
        }
        //遇到偶数则跳过
        while (left < right && nums[right] % 2 == 0) {
            right--;
        }
        //交换
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    return nums;
}

快慢指针

定义快慢双指针 fast 和 low ，fast 在前， low 在后 .
fast的作用是向前搜索奇数位置，low 的作用是指向下一个奇数应当存放的位置
fast 向前移动，当它搜索到奇数时，将它和 nums[low] 交换，此时 low向前移动一个位置 .
重复上述操作，直到 fast指向数组末尾

public static int[] exchange(int[] nums) {
    int fast = 0;
    int slow = 0;
    while (fast != nums.length - 1) {
        //遇到奇数进行交换
        if ((nums[fast] & 1) == 1){
            //交换
            int temp = nums[fast];
            nums[fast] = nums[slow];
            nums[slow] = temp;
            //向右走
            slow++;
        }
        //向右走
        fast++;
    }
    return nums;
}

时间复杂度为O(N)

空间复杂度为O(1)

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

1
2
3

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

1 2	输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

使用双指针完成分别在数组的头尾定义一个指针。因为是有序递增数组。

public static int[] twoSum1(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int s = nums[left] + nums[right];
        if (s < target) {
            left++;
        } else if (s > target) {
            right--;
        } else {
            return new int[]{nums[left], nums[right]};
        }
    }
    return new int[0];
}

时间复杂度O(N):遍历数组的长度

空间复杂度O(1)。

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

示例 1：

1 2	输入: "the sky is blue" 输出: "blue is sky the"

示例 2：

1
2
3

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

1
2
3

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

双指针实现

倒序遍历字符串 ss ，记录单词左右索引边界 ii , jj ；
每确定一个单词的边界，则将其添加至单词列表 resres ；
最终，将单词列表拼接为字符串，并返回即可。

class Solution {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}

使用库函数实现，先除去单词列表前后空格并分割字符。

public static String reverseWords0(String s) {
    //会将空格也删除并分割字符，只剩下字符，\\s+正则表达式
    String[] res = s.trim().split("\\s+");
    StringBuffer stringBuffer = new StringBuffer();

    //倒序遍历单词列表
    for (int i = res.length - 1; i >= 0; i--) {
        //拼接单词
        stringBuffer.append(res[i]).append(" ");
    }
    return stringBuffer.toString().trim();
}

时间复杂度O(N)

空间复杂度O(N):使用了StringBuffer占用线性大小空间。

Day14

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

1 2	输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true

示例 2：

1 2	输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

深度优先搜索（DFS）+ 剪枝 解决

深度优先搜索：可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝

递归参数：当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
返回 false ： (1) 行或列索引越界或 (2) 当前矩阵元素与目标字符不同或 (3) 当前矩阵元素已访问过（ (3) 可合并至 (2) ） 。
返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。
递推工作：
标记当前矩阵元素： 将 board[i][j]修改为空字符 “”，代表此元素已访问过，防止之后搜索时重复访问。 搜索下一单元格：朝当前元素的上、下、左、右四个方向开启下层递归，使用或连接（代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。还原当前矩阵元素：将 board [i][j] 元素还原至初始值，即 word[k] 。
返回值：返回布尔量 res ，代表是否搜索到目标字符串。

时间复杂度 O(3^KMN) 最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 O(3^K)；矩阵中共有 MN 个起点，时间复杂度为 O(MN) 。
方案数计算：设字符串长度为 KK ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 O(3^K) 。
空间复杂度 O(K)： 搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用 O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K = MN ，递归深度为 MN ，此时系统栈使用 O(MN) 的额外空间。

public static boolean exist0(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(helper(i,j,0,board,word))return true;
            }
        }
        return false;
    }
//递归函数，指的是当前下标下的字母是否与目标字母相同
//k为目标字符串word下标
public static boolean helper(int i, int j, int k, char[][] board, String word) {
    //超过界限就剪枝，说明不能继续。
    if (i >= board.length || i < 0 || j >= board[0].length || j < 0) {
        return false;
    }
    //判断是否是可行解
    if (board[i][j] != word.charAt(k)) {
        return false;
    }
    //说明找出全部字符
    if (k == word.length() - 1) {
        return true;
    }
    //将可行解的位置设置为空，防止再次进入该解
    board[i][j] = '\0';
    boolean res = helper(i - 1, j, k + 1, board, word) ||
            helper(i + 1, j, k + 1, board, word) ||
            helper(i, j - 1, k + 1, board, word) ||
            helper(i, j + 1, k + 1, board, word);
    //说明递归到最后没有找到结果，往前回溯
    //回溯，将可行解变为原来的值
    board[i][j] = word.charAt(k);
    return res;
}

剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

1 2	输入：m = 2, n = 3, k = 1 输出：3

示例 2：

1 2	输入：m = 3, n = 1, k = 0 输出：1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

递归参数：当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。
终止条件： 当 ① 行列索引越界或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过时，返回 0 ，代表不计入可达解。
递推工作：
标记当前单元格：将索引 (i, j) 存入 Setvisited 中，代表此单元格已被访问过。
搜索下一单元格： 计算当前元素的下、右两个方向元素的数位和，并开启下层递归 。
回溯返回值：返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。

也可以直接往上下左右四个方向都进行递归。方便理解

int m, n, k;
//用于表示当前元素是否被访问过
boolean[][] isvisited;

public int movingCount(int m, int n, int k) {
    this.m = m;
    this.n = n;
    this.k = k;
    isvisited = new boolean[m][n];
    return dfs(0, 0);
}

public int dfs(int i, int j) {
    //判断是否越界
    if (i < 0 || i >= m || j < 0 || j >= n || help(i) + help(j) > k || isvisited[i][j]) {
        return 0;
    }

    isvisited[i][j] = true;
    //向当前位置的四个方向进行递归，返回总的可达解数
    int last = dfs(i - 1, j)
            + dfs(i + 1, j)
            + dfs(i, j - 1)
            + dfs(i, j + 1);
    //成功则进行+1，即是加上当前位置
    return last + 1;

}

//计算一个数的数位之和
//必须将该坐标之和的方法提取出来，否则会出现栈溢出
public int help(int i) {
    int sum = 0;
    while (i > 0) {
        sum = sum + i % 10;
        i = i / 10;
    }
    return sum;
}

时间复杂度 O(MN) ：最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN) 。
空间复杂度 O(MN) ：最差情况下，Set visited 内存储矩阵所有单元格的索引，使用 O(MN)的额外空间。

Day15

剑指 Offer 34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

示例 1：

1 2	输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

1 2	输入：root = [1,2,3], targetSum = 5 输出：[]

示例 3：

1 2	输入：root = [1,2], targetSum = 0 输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

算法流程：
pathSum(root, sum) 函数：

初始化：结果列表 res ，路径列表 path 。
返回值：返回 res 即可。

recur(root, tar) 函数：

递推参数：当前节点 root ，当前目标值 tar 。
终止条件：若节点 root 为空，则直接返回。
递推工作：

路径更新：将当前节点值 root.val 加入路径 path ；
目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 00 ）；
路径记录：当 ① root 为叶节点且 ② 路径和等于目标值，则将此路径 path 加入 res 。
先序遍历：递归左 / 右子节点。
路径恢复：向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop()

1
2

值得注意的是，记录路径时若直接执行 res.append(path) ，则是将 path 对象加入了 res ；后续 path 改变时， res 中的 path 对象也会随之改变。
正确做法：res.append(list(path)) ，相当于复制了一个 path 并加入到 res 。

LinkedList<List<Integer>> list = new LinkedList<>();
LinkedList<Integer> integerList = new LinkedList<>();

public List<List<Integer>> pathSum(TreeNode root, int target) {
    dfs(root, target);
    return list;
}

public void dfs(TreeNode treeNode, int sum) {
    if (treeNode == null) {
        return;
    }
    integerList.add(treeNode.val);
    sum -= treeNode.val;
    //说明找到路径，到叶子结点。
    if (sum == 0 && treeNode.left == null && treeNode.right == null) {
        //必须这样写，如果是list.add(integerList)。之后添加路径值会改变integerList里的值
        //重新创建一个就不会出现错误
        list.add(new LinkedList(integerList));
    }
    //递归
    dfs(treeNode.left, sum);
    dfs(treeNode.right, sum);
    //路径恢复，向上回溯，需要从integerList删除节点
    integerList.removeLast();

}

时间复杂度 O(N)： N 为二叉树的节点数，先序遍历需要遍历所有节点。
空间复杂度 O(N) ：最差情况下，即树退化为链表时，path 存储所有树节点，使用 O(N) 额外空间。

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

二叉搜索树的中序遍历为 递增序列 。

根据以上性质，易得二叉搜索树的中序遍历倒序为递减序列。
因此，求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k个节点”。

递归解析：
终止条件：当节点 root为空（越过叶节点），则直接返回；
递归右子树：即 dfs(root.right)；
三项工作：
提前返回：若 k = 0 ，代表已找到目标节点，无需继续遍历，因此直接返回；
统计序号：执行 k = k - 1 （即从 k 减至 0 ）；
记录结果：若 k = 0 ，代表当前节点为第 kk 大的节点，因此记录 res = root.val ；
递归左子树：即 dfs(root.left) ；

//逆中序遍历
//res 存放结果值
int res, index;
public int kthLargest0(TreeNode root, int k) {
    index = k;
    dfs(root);
    return res;
}
public void dfs0(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    dfs(treeNode.right);
    //表示已经找到目标，不需要在继续之后的遍历
    if (index == 0) return;
    //--index 是先自-再使用，这个进入判断说明index此时==1
    //说明找到第k大的数,记录当前值
    if (--index == 0) {
        res = treeNode.val;
    }
    dfs(treeNode.left);
}

时间复杂度 O(N)：当树退化为链表时（全部为右子节点），无论 kk 的值大小，递归深度都为 NN ，占用 O(N) 时间。
空间复杂度 O(N)：当树退化为链表时（全部为右子节点），系统使用 O(N) 大小的栈空间。

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。

算法流程：
dfs(cur): 递归法中序遍历；

终止条件：当节点 cur 为空，代表越过叶节点，直接返回；
递归左子树，即 dfs(cur.left) ；
构建链表：

当 pre 为空时：代表正在访问链表头节点，记为 head ；
当 pre 不为空时：修改双向节点引用，即 pre.right = cur ， cur.left = pre ；
保存 cur ：更新 pre = cur ，即节点 cur 是后继节点的 pre ；

4. 递归右子树，即 dfs(cur.right) ；

//关键点：设前驱节点 pre 和当前节点 cur
//pre前驱节点一直保存二叉树中序遍历的前一个被访问的节点。
//所以中序遍历到最后pre存的一定是最后一个节点
//采用中序遍历二叉树，根据搜索树的性质
Node pre, head;

public Node treeToDoublyList(Node root) {
    if (root == null) {
        return null;
    }
    dfs(root);
    //pre最后一定是最后一个节点
    //进行头结点和尾结点的互相指向，顺序可颠倒
    head.left = pre;
    pre.right = head;
    return head;
}

public void dfs(Node cur) {
    if (cur == null) {
        return;
    }
    //中序遍历，先左递归。在左递归之后才做操作
    dfs(cur.left);
    //前驱节点为空，说明当前节点为
    if (pre == null) {
        head = cur;
    } else {
        //前驱结点的右指针指向后驱结点
        pre.right = cur;
    }
    //左指针指向前驱结点，创建循环，即往回指
    cur.left = pre;
    //保存当前结点为前驱结点
    pre = cur;
    dfs(cur.right);
}

时间复杂度 O(N) ： N 为二叉树的节点数，中序遍历需要访问所有节点。
空间复杂度 O(N)：最差情况下，即树退化为链表时，递归深度达到 N，系统使用 O(N) 栈空间。

Day16

剑指 Offer 61. 扑克牌中的顺子

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

1 2	输入: [1,2,3,4,5] 输出: True

示例 2:

1 2	输入: [0,0,1,2,5] 输出: True

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

根据题意，此 5 张牌是顺子的充分条件如下：

除大小王外，所有牌无重复；
设此 5 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足：max - min < 5

方法一：集合 Set + 遍历

public boolean isStraight(int[] nums) {

    HashSet<Integer> hashSet = new HashSet<>();
    int min = 13;
    int max = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) { //找到大小王
            continue;
        } else {
            //添加元素
            hashSet.add(nums[i]);
            //找到重复数直接返回
            if (hashSet.contains(nums[i])) {
                return false;
            }
            //找到最大值和最小值
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
    }
    //核心就是最大值和最小值之间的差值小于5
    if (max - min > 5) {
        return false;
    }
    return true;
}

时间复杂度 O(N) = O(5) = O(1)：其中 N 为 nums 长度，本题中 N≡5 ；遍历数组使用 O(N) 时间。
空间复杂度 O(N) = O(5) = O(1) ：用于判重的辅助 Set 使用 O(N) 额外空间。

方法二：排序 + 遍历

//判断是否是同花顺
public boolean isStraight0(int[] nums) {
    //大小王
    int joker = 0;
    //先进行一遍排序
    //花费时间复杂度O(NlogN)
    Arrays.sort(nums);
    //再计算大小个数和是否出现重复
    for (int i = 0; i < 4; i++) {
        if (nums[i] == 0) {
            joker++;
        } else if (nums[i] == nums[i + 1]) {
            //因为进行了排序，所以直接对相邻的两个数进行比较
            //有重复则不满足条件
            return false;
        }
    }
    //核心就是最大值和最小值之间的差值小于5
    return nums[nums.length - 1] - nums[joker] < 5;
}

时间复杂度 O(N log N) = O(5 log 5) = O(1)：其中 NN 为 nums 长度，本题中 5N≡5 ；数组排序使用 O(NlogN) 时间。
空间复杂度 O(1) ：变量 jokerr 使用O(1) 大小的额外空间。

剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

1 2	输入: [10,2] 输出: "102"

示例 2:

1 2	输入: [3,30,34,5,9] 输出: "3033459"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

此题求拼接起来的最小数字，本质上是一个排序问题。设数组 nums 中任意两数字的字符串为 x 和 y ，则规定排序判断规则为：

若拼接字符串 x + y > y + x ，则 x “大于” y ；
反之，若 x + y < y + x ，则 x “小于” y ；

初始化：字符串列表 strs，保存各数字的字符串格式；
列表排序：应用以上 “排序判断规则” ，对 strs 执行排序；
返回值：拼接 strs 中的所有字符串，并返回。

public String minNumber(int[] nums) {
    //先将数组转化为字符串数组
    String[] res = new String[nums.length];
    for (int i = 0; i < nums.length; i++) {
        res[i] = String.valueOf(nums[i]);
    }
    //进行快速排序
    quickSort(res, 0, res.length - 1);
    StringBuilder result = new StringBuilder();
    //拼接结果
    for (String s:res) {
        result.append(s);
    }
    return result.toString();


}

void quickSort(String[] res, int left, int right) {
    //保存原始下标
    int i = left;
    int j = right;
    String cur = "";
    if (left > right) {
        return;
    }
    //取一个基准点
    String temp = res[left];
    while (i < j) {
        //先从右边开始找比基准点小的
        while ((res[j] + temp).compareTo(temp + res[j]) >= 0 && i < j) {
            j--;
        }
        //从左边找比基准点大的
        while ((res[i] + temp).compareTo(temp + res[i]) <= 0 && i < j) {
            i++;
        }
        //交换两个数
        cur = res[j];
        res[j] = res[i];
        res[i] = cur;
    }
    //交换基准点
    res[left] = res[i];
    res[i] = temp;
    //递归
    quickSort(res, left, i - 1);
    quickSort(res, i + 1, right);

}

使用内置函数

public String minNumber0(int[] nums) {
    //先将数组转化为字符串数组
    String[] res = new String[nums.length];
    for (int i = 0; i < nums.length; i++) {
        res[i] = String.valueOf(nums[i]);
    }
    //内置函数排序
    Arrays.sort(res, (x, y) -> (x + y).compareTo(y + x));
    StringBuilder result = new StringBuilder();
    //拼接结果
    for (String s : res) {
        result.append(s);
    }
    return result.toString();
}

时间复杂度 O(NlogN) ： N 为最终返回值的字符数量（ strs 列表的长度≤N ）；使用快排或内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N^2)
空间复杂度 O(N)：字符串列表 strs 占用线性大小的额外空间。

Day17

剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

题目要求获取一个数据流排序后的中位数，那么可以使用两个优先队列（堆）实现。
该题使用一个大顶堆，一个小顶堆完成。

大顶堆的每个节点的值大于等于左右孩子节点的值，堆顶为最大值。
小顶堆的每个节点的值小于等于左右孩子节点的值，堆顶为最小值。

因此我们使用大顶堆(maxHeap) 来存储数据流中较小一半的值，用小顶堆(minHeap) 来存储数据流中较大一半的值。

即“大顶堆的堆顶”与“小顶堆的堆顶”就是排序数据流的两个中位数。
如图所示，大顶堆(maxHeap)置于下方，小顶堆(minHeap)倒置于上方，两个堆组合起来像一个沙漏的形状。
根据堆的性质，可以判断两个堆的值从下往上递增，即：
maxHeap堆底 <= maxHeap堆顶 <= minHeap堆顶 <= minHeap堆底。

题目要求获取数据流排序后的中位数，而根据数据流的奇偶性以及堆的性质，将获取中位数的情况分为两类：

数据流为奇数时，保证两个堆的长度相差1，那么长度较大的堆的堆顶就是中位数；
数据流为偶数时，保证两个堆的长度相等，两个堆的堆顶相加除二就是中位数。

那么我们要保证每次插入元素后，两堆维持相对长度。让minHeap为长度较大的堆，每次插入元素时进行判断：

当两堆总长度为偶数时，即两堆长度相等，将新元素插入到minHeap，插入后minHeap比maxHeap长度大1；
当两堆总长度为奇数时，即两堆长度不等，将新元素插入到maxHeap，插入后两堆长度相等；

还要保证插入元素后，两堆仍是保证从下往上递增的顺序性。如上面的偶数情况，将新元素x直接插入到minHeap，是有可能破坏两堆的顺序性的，例如：（minHeap是存储“较大一半”的值）

若x的值恰好为“较大一半”，直接将插入到“较大一半”的minHeap中，是不会破坏顺序的；
若x的值为“较小一半”，而此时却插入到“较大一半”的minHeap中，是会破坏顺序的。

结论
当两堆总大小为偶数时，即两堆大小相等，先将新元素插入maxHeap，重新排序后将新的最值拿出并插入到minHeap；
当两堆总大小为奇数时，即两堆大小不等，先将新元素插入minHeap，重新排序后将新的最值拿出并插入到maxHeap；

class MedianFinder {
        // 大顶堆存储较小一半的值
        PriorityQueue<Integer> maxHeap;
        // 小顶堆存储较大一般的值
        PriorityQueue<Integer> minHeap;
        /** initialize your data structure here. */
        public MedianFinder() {
            maxHeap = new PriorityQueue<Integer>((x, y) -> (y - x));
            minHeap = new PriorityQueue<Integer>();
        }

        public void addNum(int num) {
            // 长度为奇数时先放入小顶堆,重新排序后在插入到大顶堆
            if(maxHeap.size() != minHeap.size()) {
                minHeap.add(num);
                maxHeap.add(minHeap.poll());
            } else {
                // 长度为偶数时先放入大顶堆,重新排序后在插入到小顶堆
                maxHeap.add(num);
                minHeap.add(maxHeap.poll());
            }
        }

        public double findMedian() {
            if(maxHeap.size() != minHeap.size()) {
                return minHeap.peek();
            } else {
                return (maxHeap.peek() + minHeap.peek()) / 2.0;
            }
        }
    }

空间复杂度：O(N)，即为数据流中的元素数量。
时间复杂度：

获取中位数：O(1)。
添加元素：O(logN)，堆添加元素的时间复杂度为O(logN)。