# 作业2

**Repository Path**: algorithm-group-AI1/assignment-2

## Basic Information

- **Project Name**: 作业2
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-04-08
- **Last Updated**: 2024-09-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 作业2

终于到了咱们的算法环节。在完成这次作业之前，您应该对于咱们的算法设计与分析有一定基本了解，比如：
- 冒泡排序算法的时间复杂度是$O(n^2)$
    - 您应该知道，如何实现冒泡排序算法
    - 您应该知道，为什么时间复杂度是这？
- 分治算法的基本概念
- 分治算法的优化策略
- 动态规划的基本概念
- 0-1背包问题

如果上面这些，您比较清楚，那么，可以去完成咱们的这次作业。如果还不清楚，好好看书、认真看视频，把基础打牢在去做本次作业吧。

## 要求

- 小组完成的题目数$\ge$你们组人数
- 工程中需包含
    - gen.py: 生成数据
    - alg.py: 算法
    - test.py: 测试数据
    - alg.md：解题报告
- 您应该按照实验报告的要求提交至畅课平台

- 规则

> 记 题库$P$ 为 [地址](https://leetcode-cn.com/tag/dynamic-programming/problemset/) 中 等级为困难的所有试题

    - 2人组： {1,2}至少选一题, $\{3, 4\}\cup P$至少选一题
    - 3人组： {1,2}至少选一题, $\{3, 4\}\cup P$至少选两题
    - 4人组： {1,2}至少选两题, $\{3, 4\}\cup P$至少选两题

## 作业内容

### 1. 矩阵的幂运算
**输入**：矩阵$A\in\mathbb{R}^{m\times m}$，矩阵的为$A$，包含$m$行$m$列， $n$矩阵的次幂

**输出**: 矩阵$A^n$

**要求**：

- 尝试暴力方法，时间复杂度可在$O(m^3 \times n)$
- 尝试优化算法，时间复杂度应在$O(m^3\times logn)$
- 尝试进一步优化算法，时间复杂度应在$O(m^2.74\times logn)$


### 2. 最大和连续子数组
**输入**：整数数组nums

**输出**: 找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和及子数组的开始索引及结束索引。

**要求**：

- 尝试暴力方法，时间复杂度可在$O(m^3 \times n)$
- 尝试进一步优化算法，时间复杂度应在$O(n\times logn)$
- 将代码提交至LeetCode上，并截图， [地址](https://leetcode-cn.com/problems/maximum-subarray/)

**举例**: 

```sh
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： [4,-1,2,1]  [3, 7)
```

### 3. 正则表达式匹配

**输入**：一个字符串$s$ 和 字符规律 $p$，字符规律包含 "." 和 "*"，表示
- ".": 匹配任意单个字符串
- "*": 匹配0个或多个前面的那个元素

**输出**: 
- True: 如果字符串$s$符合字符规律$p$
- False: 其他情况

**要求**:
- 尝试暴力算法
- 尝试动态规划
- 将代码提交至LeetCode上，并截图，[地址](https://leetcode-cn.com/problems/regular-expression-matching/)

**举例**：

```python
示例1
输入： "aa", "a"
输出：False

示例2
输入："a", "."
输出：True

示例3
输入："baa", ".a*"
输出：True
```


### 4. 数组等差子序列

**输入**: 一个整数数组
**输出**: 这个数组中的所有等差子数列 及 个数

> 如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。
> 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
> 例如，[1, 1, 2, 5, 7] 不是等差序列。

**要求**
- 尝试暴力算法
- 尝试动态规划
- 将代码提交至LeetCode上并截图, [地址](https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/)

**举例**：
```sh
输入：[2,4,6,7,8,10]
输出：8
    [2,4,6]
    [4,6,8]
    [4,7,10]
    [6,7,8]
    [6,8,10]
    [2,4,6,8]
    [4,6,8,10]
    [2,4,6,8,10]
    [2,6,10]

```