# geektime-algo

**Repository Path**: z_rp/geektime-algo

## Basic Information

- **Project Name**: geektime-algo
- **Description**: 极客时间 - 数据结构与算法之美
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 5
- **Created**: 2024-06-11
- **Last Updated**: 2024-06-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构与算法

## 算法

### 二叉树

#### [124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/)

- 题目：二叉树中的 **路径** 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 **至多出现一次** 。该路径 **至少包含一个** 节点，且不一定经过根节点。

  **路径和** 是路径中各节点值的总和。

  给你一个二叉树的根节点 `root` ，返回其 **最大路径和** 。

- 难度：困难

- 题解

  ```java
  public class _124_二叉树中的最大路径和 {
  
      int ans = Integer.MIN_VALUE;
  
      public int maxPathSum(TreeNode root) {
          maxGain(root);
          return ans;
      }
  
      /**
       * 获取当前节点的最大贡献值
       *
       * 前置概念
       * 树中最大路径和：从任意节点出发 的最大路径和（可以不包括当前节点），也是本题的解
       * 最大贡献值：从当前节点出发 的最大路径和（一定包含当前节点）
       *
       * 采用后续遍历，会遍历树中所有节点，并在遍历的过程中求 树中最大路径和。
       * 时间复杂度：O(n)
       * 空间复杂度：O(n)
       * @param node
       * @return 当前节点最大路径和 = 当前节点的贡献值 + max(左子节点最大路径和, 右子节点最大路径和)
       */
      private int maxGain(TreeNode node) {
          if (node == null) return 0;
  
          // 递归计算左右子节点的最大贡献值（如果为负数，返回 0）
          int leftSum = Math.max(maxGain(node.left), 0);
          int rightSum = Math.max(maxGain(node.right), 0);
  
          // 当前节点的最大贡献值 取决于该节点的值与该节点的左右子节点的 最大贡献值
          int tmpMax = node.val + leftSum + rightSum;
          // 更新 树中最大路径和
          ans = Math.max(ans, tmpMax);
  
          // 返回当前节点的最大贡献值
          return node.val + Math.max(leftSum, rightSum);
      }
  }
  ```



#### [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

- 题目：给定两个整数数组 `preorder` 和 `inorder` ，其中 `preorder` 是二叉树的**先序遍历**， `inorder` 是同一棵树的**中序遍历**，请构造二叉树并返回其根节点。

- 难度：中等

- 题解：

  ```java
  public class _105_从前序与中序遍历序列构造二叉树 {
  
      public TreeNode buildTree(int[] preorder, int[] inorder) {
  
          int n = preorder.length;
          // 存储中序遍历值与位置，用于快速定位中序遍历根节点位置
          Map<Integer, Integer> iMap = new HashMap<>();
          for (int i = 0; i < n; i++) {
              iMap.put(inorder[i], i);
          }
          
          // 确认好迭代边界很重要（到底是 左闭右开 还是 左闭右闭）
          return build(preorder, 0, n - 1, inorder, 0, n - 1, iMap);
      }
  
      /**
       * 根据 preorder[pStart, pEnd] 和 inorder[iStart, iEnd] 创建根节点，并构建子树（将子树连接到根节点）
       *
       * 解法：前序遍历
       * 时间复杂度：O(n)
       * 空间复杂度：O(n)
       *
       * 提示：前序遍历有课找到根节点，中序遍历可以获取左右子树大小
       *
       * @param pArray 前序遍历
       * @param pStart 前序遍历起始索引
       * @param pEnd 前序遍历终止索引
       * @param iArray 中序遍历
       * @param iStart 中序遍历起始索引
       * @param iEnd 中序遍历终止索引
       * @param iMap key：中序遍历中的值， val：对应索引
       * @return 构建树的根节点
       */
      public TreeNode build(int[] pArray, int pStart, int pEnd, int[] iArray, int iStart, int iEnd, Map<Integer, Integer> iMap) {
          if (pStart > pEnd) return null;
  
          // 前序遍历中的第一个节点就是根节点
          // 获取中序遍历跟节点索引
          int iRoot = iMap.get(pArray[pStart]);
  
          // 创建根节点
          TreeNode root = new TreeNode(pArray[pStart]);
  
          // 获取左子树节点数量
          int leftSize = iRoot - iStart;
  
          // 构造左子树，并连接到根节点
          // pStart: 前序遍历，根节点索引
          // pStart + 1: 前序遍历，左子树起始位置
          // pStart + leftSize: 前序遍历，左子树终止位置
          // iStart: 中序遍历，左子树起始位置
          // rootIdxInIn: 中序遍历，根节点索引
          // rootIdxInIn - 1: 中序遍历，左子树终止位置
          root.left = build(pArray, pStart + 1, pStart + leftSize, iArray, iStart, iRoot - 1, iMap);
  
          // 构造右子树，并连接到根节点
          // pStart: 前序遍历，根节点索引
          // pStart + leftSize + 1: 前序遍历，右子树起始位置
          // pEnd: 前序遍历，右子树终止位置
          // rootIdxInIn + 1: 中序遍历，右子树起始位置
          // rootIdxInIn: 中序遍历，根节点索引
          // iEnd: 中序遍历，右子树终止位置
          root.right = build(pArray, pStart + leftSize + 1, pEnd, iArray, iRoot + 1, iEnd, iMap);
  
          return root;
      }
  }
  ```



#### [99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree/)

- 题目：给你二叉搜索树的根节点 `root` ，该树中的 **恰好** 两个节点的值被错误地交换。*请在不改变其结构的情况下，恢复这棵树* 。

- 难度：中等

- 题解1

  ```
  
  ```

  





### 滑动窗口

#### [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/)

- 题目：给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""`
- 难度：困难

```java

```

极客时间 - 数据结构与算法之美

#### 数据结构
1.  数组
2.  链表
3.  [栈](https://gitee.com/Karson-Wang/geektime-algo/tree/master/src/main/java/com/karson/geektime/algo/stack)
4.  [队列](https://gitee.com/Karson-Wang/geektime-algo/tree/master/src/main/java/com/karson/geektime/algo/queue)
5.  [跳表]
6.  [散列表]

#### 排序
1.  [冒泡](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Bubble.java)
2.  [插入](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Insertion.java)
3.  [选择](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Selection.java)
4.  [快排](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Quick.java)
5.  [归并](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Merge.java)
6.  桶
7.  [计数](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Counting.java)
8.  基数

#### 查找
1.  [二分查找](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/search/BinarySearch.java)
4.  [哈希算法]
12.  [字符串匹配]
13.  [Trie树]
14.  [AC自动机]
15.  [贪心算方法]
16.  [分治算法]
17.  [回溯算法]
18.  [动态规划]

#### 树
1.  [二叉树](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/tree/BinaryTree.java)
2.  [二叉查找树](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/tree/BinarySearchTree.java)
3.  [红黑树]
4.  [递归树]
5.  [堆和堆排序]

#### 图
1.  [图]

#### 搜索
1.  [深度优先搜索]
2.  [广度优先搜索]