# algorithm

**Repository Path**: bascker/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: 算法之旅
- **Primary Language**: Java
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-07-15
- **Last Updated**: 2024-12-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# algorithm
## 一、简介
使用 Java 进行算法实现，项目源码基础结构
```
algorithm
|- base                                 # 基础数据结构的实现
    |- bag                              # 背包
    |- queue                            # 队列
    |- stack                            # 栈
    |- tree                             # 树
    |- sort                             # 排序算法
|- common                               # 工具类等
|- practice                             # 练习, 其中 @from 标识题目来源
    |- arr              
        |- BookFlight                   # 差分数组技巧 leetcode T1109
        |- FindContinuousSeq            # 剑指 Offer 57
        |- FindMaxConsecutiveOne        # T485 最大连续1的个数
        |- FindMaxLength                # T525 相同0和1数量的最长连续子数组
    |- backtrack                        # 回溯
    |- bfs                              # 广度搜索
        |- MinDepth                     # T111 二叉树最小深度
        |- OpenLock                     # T705 打开轮盘锁 
    |- dp                               # 动态规划
        |- MinPath                      # T64 最小路径和
        |- UniquePathII                 # T63 不同路径
        |- BuyStock                     # 剑指 Offer T63  股票最大利润
    |- greed                            # 贪心算法
        |- AssignCookie                 # T455 分发饼干
    |- list                             # 链表
        |- AddTwoNums                   # T445 两数相加II
        |- RemoveLinkedListElements     # T203 移除链表元素
        |- Reverse                      # 原地反转链表
        |- ReverseLinkedListII          # T92 反转链表
    |- recursion                        # 递归
        |- Fib                          # T509 斐波那契数列
        |- LookAndSaySequence           # T38 外观数列
    |- stack                            # 栈
        |- BracketMatch                 # 括号匹配
        |- CompleteExpression           # 补齐中序表达式
    |- tree                             # 树
        |- LowestCommonAncestor         # T236 二叉树最近公共祖先
        |- PathSum                      # T112 路径和
        |- BuildTree                    # T106 根据中序和后序序列构建一颗二叉树
```
测试工程结构类似, 包路径保持与源码包路径一致，且所有测试类均以`Test`为前缀, 其中 data 包下存放通用的测试数据。

---

Jdk 中的数据结构
1. 使用 LinkedList 作为 java.util.Stack 的实现
2. 使用 LinkedList 作为 java.util.Queue 的实现
```Java
final Queue queue = new LinkedList<>();
// 入队
queue.offer(x);
// 出队
queue.poll(); 
```

---

常见思路:  

1、逆序, 先进后出: 优先考虑栈
```
AddTwoNums
```          
2、结点操作: 考虑哨兵结点  
```        
RemoveLinkedListElements
```
3、动态规划：多考虑以空间换时间，自底向上
```
UniquePathII            # 从递归实现改循环, 见 https://gitee.com/bascker/algorithm/issues/I1PJOB
```
4、BFS: (场景)从起点 start 到终点 end 之间的**最近/最小/最少**XXX 的最值问题 
> 因为 BFS 每次只往前进一步，所以保证第一次到达终点时，部署最小
```
MinDepth
```

## 二、运行
项目中使用的很多工具类依赖于 [bsutil](https://github.com/bascker/bsutil) 库。
```
<dependency>
    <groupId>com.baskcer.util</groupId>
    <artifactId>bsutil</artifactId>
    <version>1.0-SNAPSHOT</version>
</dependency>
```
项目中已添加该依赖，可`git clone https://github.com/bascker/bsutil.git`后，根据以下步骤引入 jar。
1. 执行 `mvn install`编译 bsutil-1.0-SNAPSHOT.jar 包。
2. 将 jar 包放到 mvn 配置的本地 repo 路径内
```
λ ls -al repo\mvn-repo\com\baskcer\util\bsutil\1.0-SNAPSHOT
total 22
drwxr-xr-x 1 bascker 197121     0 12月 29 19:53 ./
drwxr-xr-x 1 bascker 197121     0 12月 29 19:53 ../
-rw-r--r-- 1 bascker 197121 18879 12月 29 19:41 b
```

## 三、单元测试
代码修改后，本地 mvn 进行 test 测试, 测试套件会自动触发项目中的单元测试。
> 本项目使用 testng 作为单元测试套件

```
[INFO] --- maven-surefire-plugin:2.8.1:test (default-test) @ algorithm ---
[INFO] Surefire report directory: D:\..\code\algorithm\target\surefire-reports

-------------------------------------------------------
 T E S T S
-------------------------------------------------------
Running TestSuite
Tests run: 11, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.268 sec

Results :

Tests run: 11, Failures: 0, Errors: 0, Skipped: 0
```

## 四、复杂度
时间复杂度常见计算
### 4.1 递归解法
时间复杂度 = 子问题个数 * 解决子问题的耗时
* 子问题个数 = 递归树节点总数
> 凡是递归的问题，都可转为树的问题 ==> 递归树