# AlgorithmsStudy

**Repository Path**: wzlove521/algorithms-study

## Basic Information

- **Project Name**: AlgorithmsStudy
- **Description**: 自我的算法的学习
- **Primary Language**: Unknown
- **License**: MulanPSL-2.0
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-05-08
- **Last Updated**: 2024-04-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 算法练习

之前学习算法也是断断续续的，没有系统的学习，在我看来，算法其实就是数据结构 + 数学推理，有的时候带着一些技巧，也就是模版，所以想要学习好算法，
要先了解必要的数据结构，最起码数组、链表、栈、队列、堆、树、图等数据结构先了解一下，很多的算法就是基于数据结构展开的，不同的数据结构在同一个
场景下，性能也可能是千差万别的，这次就统一过一遍的，大学学的数据结构都有点遗忘了都。

## 数据结构

### 数组

在介绍数组之前，先了解一下集合和列表，集合是由一个或多个元素所构成的整体，集合中的元素是没有顺序的，并且元素类型不一定相同。集合在编程语言中是不存在的，Java
中所说的集合严格意义上算是列表。

列表的定义是按照一定的顺序，排列而成的数据集，在列表的基础上形成的概念，列表中的元素是同一类型且长度可变的。

数组是列表的实现方式之一，是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。大部分编程语言的数组下标是从
0
开始的，所以数组的第一个元素的下标是 0，最后一个元素的下标是 n-1，n 表示数组的长度。

数组的优点是可以随机访问，根据下标随机访问的时间复杂度是 O(1)，但是数组的缺点也很明显，那就是插入和删除的时间复杂度是 O(n)
，因为数组是连续的内存空间，所以在插入和删除的时候，需要移动后面的元素，所以时间复杂度是 O(n)。

#### 二维数组

二维数组是一种特殊的数据结构，本质是一个一个的一维数组组成，也就是说二维数组的每一个元素其实是一个一维数组，可以将其看做一个矩阵来处理。

例题：

1. [1991. 找到数组的中间位置](https://leetcode.cn/problems/find-the-middle-index-in-array/)
   ：这道题目让我学到了算法和数学是息息相关的，不要看做两件事情，数学推理在算法中往往是非常有用的。
2. [35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/)：这道题目让我学到了什么呢？算是二分查找的使用，二分查找关键的是边界问题，看
   right 如何定义，如果是等于数组长度，则 middle 在 right 对比的时候就不需要 - 1，直接看模板更好理解。
   ```
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1; // 注意
        while(left <= right) { // 注意
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                // 相关逻辑
            } else if(nums[mid] < target) {
                left = mid + 1; // 注意
            } else {
                right = mid - 1; // 注意
            }
        }
        // 相关返回值
        return 0;
    }

   public int searchInsert ( int[] nums, int target){
      int left = 0, right = nums.length; // 注意
      while (left < right) { // 注意
          int mid = (left + right) / 2; 
          if (nums[mid] == target) {
              // 相关逻辑
          } else if (nums[mid] < target) {
              left = mid + 1; // 注意
          } else {
              right = mid; // 注意
          }
      }
      // 相关返回值
      return 0;
   }
   ```
3. [56. 合并区间](https://leetcode.cn/problems/merge-intervals/)
   ：这倒题目让我学到了什么呢？一个是数组结构的使用，我发现我有的时候太死板了，不会灵活使用数据结构，其次思想有些固化，排序等
   api 使用的不太好，这可不太好。
4. [48. 旋转图像](https://leetcode.cn/problems/rotate-image/)：这道题目独立做出，就是花费的时间有点久，找规律花费太久了，不过算是有所成果
5. [面试题 01.08. 零矩阵](https://leetcode.cn/problems/zero-matrix-lcci/): 这道题目其实并不难理解，双层 for 循环就可以解决，比较容易
6. [498. 对角线遍历](https://leetcode.cn/problems/diagonal-traverse/):
   这道题目难住我了，就是找规律，从对角线找规律，而且逻辑比较复杂，关键难点其实在于到了下三角应该如何去转换，记住了大部分数组题目都要用到长度的。

数组的其它例题：

1. [118. 杨辉三角](https://leetcode.cn/problems/pascals-triangle/): 找到规律，也就是当前元素等于什么，边界如何考虑就很容易做出来了
2. [119. 杨辉三角 II](https://leetcode.cn/problems/pascals-triangle-ii/): 递归的方式解决，感觉代码写的复杂，但是时间复杂度很低，原因在于计算量少了一半
3. [153. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/):
   二分查找的变种，学到了在没有相等判断的时候，边界问题需要重新考虑
4. [26. 删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/):
   快慢指针解决，思路没有问题，但是写出来的代码还是千差万别，最后还有一个可优化的地方，就是复制元素的时候如果距离为 1 就不需要复制
5. [283. 移动零](https://leetcode.cn/problems/move-zeroes/): 

### 字符串

将字符串放在数组的下面，是因为字符串的实现与数组相关，查看 Java 中 String 的源码就可以发现，String 的存储底层是 char 数组。

字符串的定义是由零个或多个字符组成的有限序列，字符串的长度是有限的，字符串的长度是不可变的。

字符串的常见操作就是比较和连接，在不同的编程语言中，所使用的函数也是不同的，在 Java 中的字符串的比较使用`equals()`
方法，而不是`==`;连接操作在 Java
中，由于字符串的长度是不可变的，所以每次连接都会生成一个新的字符串，所以在连接的时候，可以使用`StringBuilder`
和`StringBuffer`来进行连接，这两个类的底层都是使用数组来实现的，所以效率比较高。

1. [14. 最长公共前缀](https://leetcode.cn/problems/longest-common-prefix/)
   ：暴力破解，没有什么难度，这道题目唯一的收获就是还可以使用分治的思想来解决，这个思想还是很有意思的。
2. [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/)：中心扩散的思想，get
3. [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/)
   ：这道题目同 [151. 反转字符串中的单词](https://leetcode.cn/problems/reverse-words-in-a-string/)
   ，题目看似不难，但是细节挺多，不认真写一个还真是不知道呀，所以 talk is cheap，show me the code 是没有错的呀！换一种思路，使用
   O(1) 的空间复杂度效果更好呀
4. [实现 strStr()](https://leetcode.cn/leetbook/read/array-and-string/cm5e2/)：这道题目应该用 KMP 算法来解决，后面认真学习一下
   KMP，现在先暴力破解看看，暴力破解完成，KMP 算法加入待办列表
5. [557. 反转字符串中的单词 III](https://leetcode.cn/problems/reverse-words-in-a-string-iii/):
   分别使用原地算法和额外的空间来解决，原地算法的空间复杂度低

### 链表

链表是一种线性表数据结构，它用一组任意的内存空间，来存储一组具有相同类型的数据。链表的每个元素都是一个节点，节点分为两部分，一部分是存储数据的，另一部分是指向下一个节点的指针。

链表的优点是插入和删除的时间复杂度是 O(1)，因为链表的节点是任意的内存空间，所以在插入和删除的时候，只需要改变指针的指向就可以了，但是链表的缺点也很明显，那就是随机访问的时间复杂度是
O(n)，因为链表的节点是任意的内存空间，所以不能像数组一样，根据下标随机访问，只能从头节点开始遍历，直到找到对应的节点。

上面说的是单向链表，还有双链链表，双链表的每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。

循环链表是一种特殊的单链表，它的尾节点指向头节点，形成一个环。

双向循环链表是双向链表和循环链表的结合。

还有更多，当然，总体来说链表的特性是不发生改变的，也就是插入删除快，随机访问慢。

### 栈

栈是一种特殊的线性表数据结构，它只能在一端进行插入和删除操作，这一端称为栈顶，另一端称为栈底。栈的特点是先进后出(FILO)。

栈的应用场景有函数调用栈、表达式求值、括号匹配、浏览器前进后退等。

### 队列

队列是一种特殊的线性表数据结构，它只能在一端进行插入操作，另一端进行出对操作，插入端称为队头，出对端称为队尾。队列的特点是先进先出(
FIFO)。

队列的应用场景有消息队列、阻塞队列、并发队列等。

### 堆

堆是一种特殊的完全二叉树(除了最后一层，其他层的节点数都是满的，最后一层节点从左到右依次填满)
，它分为大顶堆和小顶堆，大顶堆的每个节点的值都大于等于其左右子节点的值，小顶堆的每个节点的值都小于等于其左右子节点的值。

PriorityQueue 是 Java 中的堆的实现。

堆的应用场景有优先级队列、Top K 问题、求中位数等。

> 使用对来实现求中位数的描述
> 使用两个堆来维护数据集合的左侧部分和右侧部分。左侧部分使用一个大根堆来维护，右侧部分使用一个小根堆来维护。假设现在已经有了一个大根堆
> leftMaxHeap 和一个小根堆 rightMinHeap，它们分别维护了数据集合的左侧部分和右侧部分。此时需要将一个新元素 num
> 加入到数据集合中，具体步骤如下：
> 1. 将 num 插入到 leftMaxHeap 中。
> 2. 如果 leftMaxHeap 的元素个数大于 rightMinHeap 的元素个数，将 leftMaxHeap 的堆顶元素弹出，并插入到 rightMinHeap 中。
> 3. 如果 rightMinHeap 的堆顶元素小于 leftMaxHeap 的堆顶元素，交换两个堆顶元素。
>
> 重复上述步骤，直到数据集合中的所有元素都被加入到堆中。这样，左侧部分的元素个数始终不小于右侧部分的元素个数，而且左侧部分的最大值不大于右侧部分的
> 最小值。当数据集合元素个数为偶数时，中位数为左侧部分的最大值和右侧部分的最小值的平均值；当数据集合元素个数为奇数时，中位数为左侧部分的最大值。

### 树

树是一种非线性表数据结构，它是由 n(n>=1) 个有限节点组成一个具有层次关系的集合。树的第一个节点称为根节点，除了根节点之外的其他节点都有且只有一个父节点，每个节点可以有多个子节点。

树的应用场景有文件系统、二叉搜索树、堆、图等。

#### 二叉树

二叉树是一种特殊的树，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的应用场景有二叉搜索树、堆、表达式树等。

#### 二叉搜索树

二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于其左子树的所有节点的值，小于其右子树的所有节点的值。

二叉搜索树的应用场景有快速查找、快速插入、快速删除等。

## 技巧

技巧指的是在算法中经常使用的一种方法，针对于特定的场景，可以使用特定的技巧来解决问题。

### 双指针

双指针的技巧在数组和字符串中经常使用，核心思想是使用两个指针，分别指向数组或者字符串的不同位置，然后协同完成任务，当然不仅仅适用于数组和字符串，链表、树等也可以使用双指针技巧。

技巧一：左右指针：

1. [344. 反转字符串](https://leetcode.cn/problems/reverse-string/): 典型的左右指针，没有什么难度
2. [561. 数组拆分](https://leetcode.cn/problems/array-partition/): 先排序后偶数下标之和，就是感觉和双指针没有关系呢？
3. [167. 两数之和 II - 输入有序数组](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/): 没什么难度，双指针飘过，那如果是三数之和，四数之和呢？

技巧二：快慢指针，两个指针通向移动，前提也基本需要给数组排序：

1. [27. 移除元素](https://leetcode.cn/problems/remove-element/): 没什么难度，代码简单，思路简单，快慢指针搞定
2. [485. 最大连续 1 的个数](https://leetcode.cn/problems/max-consecutive-ones/): 也基本简单，就是长度判断以及 ++
   的时候出了点小问题，问题不大
3. [209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/)：滑动窗口，边界问题搞定就好，两层 for
   循环，看似复杂其实简单

后续的刷题过程放在下面这个链接了，https://changeable-leotard-0e2.notion.site/805947672bc34fdfb4ef16c7e75e0f5c