技术⽅案本质上需要回答两个问题：  
>* 其⼀，为什么该⽅案可⾏？  
>* 其⼆，在已有资源限制下，为什么该⽅案是最优的？  

为了回答第⼀个问题，我们需要在技术⽅案⾥补充架构图、接⼝设计和时间⼈⼒估算。  

⽽要回答第⼆个问题，需要我们在关键点或争议处提供⼆到三种⽅案，并给出建议⽅案，这样才有说服⼒。  

通常情况下，我们会花费很多的时间准备第⼀个问题，⽽忽略第⼆个问题。  
其实，回答好第⼆个问题很重要，⼤型项⽬的设计已经复杂到没⼈能够⼀次就想到最佳⽅案，⼀个仅仅“可⾏”的⽅案，可能会给系统增加额外的复杂性。  





# 项目技术方案模板

## 背景

讲清楚what+why，介绍项⽬的背景、相关系统的现状以及相关名词定义。

着重说明项⽬以下问题：

必要性（为什么要做）

⻛险（不做这个事情有哪些影响）


## ⽬标

要达成的效果，最好是与问题对应。

如果是产品的需求，这⾥直接贴需求对应的⽬标

业务需求是什么？项⽬产出是什么？衡量指标是什么？


## 整体设计

⼏个部分，分别是⼲什么的，系统的整体流程图和系统的分层架构图


## 详细设计

⽅案部分，重点讨论：How，怎么做。

如果是概览的⽅案，则需要描述清楚

宏观的架构，主要是模块的关系（组织⽅式）

模块的定义，定位、职责、边界、输⼊输出

对于技术中出现的⼀些具体的技术难点，则需要描述清楚怎么做的。


### 1、业务流程

业务流程的流程图，不同⻆⾊不同阶段的处理过程，以及各种分⽀情况的条件及处理逻辑。要覆盖

所有流程分⽀，不重不漏。

### 2、模型/数据库设计

表结构设计，包含：ER图、建表语句

### 3、关键逻辑/算法

业务流程图中 系统最关键逻辑的具体说明，重点说清楚本系统最关键部分的处理逻辑

### 4、数据产出逻辑

从原始数据 到 最终结果 过程中的关键计算逻辑说明，包括该逻辑在系统中的的应⽤场景，及具体

逻辑实现等。关键数据指标（需要⾃测和部分QA测试时验证正确性）

### 5、定时任务

定时任务的作⽤，时间选择，处理逻辑，是否需要失败重试等。数据重跑⽅案（重跑⽅案需要保证幂等性）

### 6、系统依赖

对上游系统或第三⽅系统的服务依赖，说明具体的依赖场景，围绕该依赖的设计思路等。


## 接⼝⽂档

涉及到的新增和修改的接⼝⽂档，可以附上⽂档链接6、稳定性保障系统相关的监控，降级，回滚，业务灰度⽅案等措施。

## 稳定性保障

系统相关的监控，降级，回滚，业务灰度⽅案等措施。

## ⻛险点

如有相关⻛险点，可以记下来。包括思考点，结论，备注等信息。

## 项⽬计划

精确到天的时间安排和⼈员分⼯，有明确的检查点。

:::danger{title="📌 使⽤⽅式"}
此模板旨在给⼤家编写技术⽅案以及做⽅案评审时查缺补漏，如有部分章节项⽬不涉及，可以不写，但是需要保留整体结构。
:::

工作经验分享 - 项目技术方案模板

说到 SpringBoot 自动装配的原理，可能有的人就要开始 @EnableAutoConfiguration 的长篇大论了，感觉在背源码一样，那么 `自动装配` 的含义你是真的了解吗？它是如何与 Spring 相结合的，又是如何被 Spring 管理的？接下来我将告诉你 `自动装配` 原理的真正打开方式。



# 自动装配的本质

自动装配的本质其实就是将 `starter` 快速依赖包中的 Bean 信息，自动的整合到 Spring IOC 容器中被 Spring 所管理，掌握此本质，就可自由实现自定义的 `starter` 的各种工具包，学习本文以前，需要掌握 Spring 容器中的 Bean 生命周期流程。

# 代码上的核心实现

其实现的方式就是通过 `@SpringApplication` 复合注解中的 `@EnableAutoConfiguration` 注解的 `AutoConfigurationImportSelector` 类中调用 `SpringFactoriesLoader #loadFactoryNames` 方法，加载 `META-INF/spring.factories` 文件实现的

大体了解流程以后，开始分析源码，流程掌握比较简单，但是如何**从 SpringBoot 启动后基于 Spring 扩展进行的自动装配的实现才是最核心重点**。

## 从源码上看实现

查看 `@SpringBootApplication` 源码，可以看到存在一个 `@EnableAutoConfiguration` 注解，此注解即为 SpringBoot 内部注解，为 Spring 上下文提供自动配置的

![image.png](/static/img/f3958c42bcf3202a0644b4c5148e6be8.image.webp)


接着看 `@EnableAutoConfiguration` 注解的实现，内部使用了 `@Import` 注解（Spring 的核心注解，其用于导入一个或多个 Bean 信息），导入了 `AutoConfigurationImportSelector` Bean 信息

![image.png](/static/img/f5171b10991b43bc7f0a6ff2880782f6.image.webp)


此时 `AutoConfigurationImportSelector` 实例已被注册成 Bean，被 Spring 容器所管理，此实例的接口实现了 `DeferredImportSelector` 接口， 查看下源码的实现

![image.png](/static/img/ed03aa97156c5c4b6b91490f86d02674.image.webp)


齿轮开始转动，自动装配的实现也是从此刻开始，一直常说 SpringBoot 启动时会加载 `META-INF/spring.factories` 文件，并且将文件中的实现类加载到 Spring 容器中，那么到的是如何加载的呢？源码看到这，接下来要如何查找呢？

很简单粗暴的方法，一个查找当前源码的类，一个从源码中全局搜索，去查找到 `spring.factories` 文件在哪被定义过，看是否被当前类引用过，就找到了当前的接口调用

![image.png](/static/img/ccd68795061d1c9455499d0bdf062eaf.image.webp)


查看 `SpringFactoriesLoader #loadFactoryNames` 方法，可以看到其内部加载 `META-INF/spring.factories` 文件

![image.png](/static/img/d6037180f4ebc11d863b4d376c2f4133.image.webp)

源码看到这基本就差不多了，在看一眼 `META-INF/spring.factories` 文件内容

![image.png](/static/img/cbdc314d49f29ec9dddfecedf6716dca.image.webp)


## 结合 Spring 的扩展看实现（核心）

看完上面的流程，你以为就这样结束了么，感觉一切这么理所当然，转动脑筋思考下，SpringBoot 启动的时候，是如何来执行到上述的流程呢？接下来我们继续断点分析


### 阅读源码

通过对调用 `SpringFactoriesLoader #loadFactoryNames` 的方法进行断点，发现一切奥秘尽在堆栈之中，有没有看到那个特殊眼熟的 `refresh` 方法，这个是 Spring 容器刷新的入口，不了解的小伙伴可以去看下文章：[Spring 源码分析之 Bean 的全生命周期](https://blog.liushigong.cn/post/11)

![image.png](/static/img/4a10fb63a20b99aa6bc547cfa29e1287.image.webp)


开始看上层堆栈方法的源码，首先将 `META-INF/spring.factories` 文件读取的的内容构建成 `AutoConfigurationEntry` 对象

![image.png](https://blog.liushigong.cn/static/img/577c12eab83775dc506d6e0e0e3dc789.image.webp)


将构建的 `AutoConfigurationEntry` 对象，存储到本地缓存的 `this.autoConfigurationEntries` 集合中

![image.png](/static/img/b95cd347a33a2b16c4f4204b3dfba52b.image.webp)


接着找上层的调用，又打开了新世界的大门，调用到了 `ConfigurationClassParser` 类，此类主要是对配置类的解析，以下是从掘金社区提供的图片

![image.png](/static/img/6b64f9d25517f61d2e787474745f8efb.image.webp)

![image.png](/static/img/084242a2bb010d87267aef20852c4732.image.webp)

了解了 `ConfigurationClassParser` 类的作用，发现其内部调用了 `processImports` 方法，此方法就是解析的核心方法，递归加载，有兴趣可以自行阅读源码

![image.png](/static/img/880d4beb88000db7cabd17db870b345c.image.webp)

可以看出此处进行的for循环，包含我们的核心类  `AutoConfigurationImportSelector` ，那么，其中 `this.groupings.values()` 数据从哪里来呢

![image.png](/static/img/5df88f2f6fe971224cbde4b8594e3c5f.image.webp)

找到上层方法，发现有一个 `register` 方法，内部果然是构建了 `this.groupings.values()` 数据

![image.png](/static/img/2f550935b8b213fd98e03bc094eec833.image.webp)

![image.png](/static/img/dc946c2df6b7cfcdd5579d9fc224bf68.image.webp)


看到此处，发现解析的核心逻辑实现，有兴趣可以自行阅读源码，这里就不再赘述了

![image.png](/static/img/fbcf9aba27beea28f38ff0409e1aeba3.image.webp)

继续查找进入到了 `ConfigurationClassPostProcessor` 类中，见名知意，此类为配置类后置处理的作用，扩展实现了 `BeanDefinitionRegistryPostProcessor` 接口，被调用了 `#postProcessBeanDefinitionRegistry` 方法

![image.png](/static/img/1f13d62a89d90005d24412d202badb6c.image.webp)

![image.png](/static/img/987459505f7ac006524e1ac8f9c4106a.image.webp)


接着往上层查找，走到了 `invokeBeanDefinitionRegistryPostProcessors` 方法，此处是调用 BeanDefinition 注册的后置处理的所有扩展接口，在联想到上述的 `ConfigurationClassPostProcessor` 类实现了其接口，可以理解是在此处将所有的配置类信息以及 `starter` 中的信息加载到了 Spring 容器中

![image.png](/static/img/0efcc4fa7b92f25ebfaad12f853e4fc2.image.webp)

![image.png](/static/img/c571bfd3af83dfb9204ec537abcfe258.image.webp)


找到这，终于看到非常眼熟的 `refresh` 方法，原来这一切都是在 Spring 容器刷新的时候，创建完 BeanFactory 以后，在调用 `invokeBeanFactoryPostProcessors` 方法，进行后置处理中操作的

![image.png](/static/img/ac4cb18857956b6185089a66306a67d3.image.webp)


### 总结

通过上面的源码追溯，我们总结一下 `自动装配` 的扩展流程实现

对于 `starter` 的中加载到的Bean信息，是通过 Spring 提供的 `DeferredImportSelector` 接口进行扩展的，通过 `BeanFactoryPostProcessor #postProcessBeanFactory` 后置处理中调用 `BeanDefinitionRegistryPostProcessor` 后置处理进行实现的

:::tip{title="思考一下"}
根据上面的源码思路，如何实现动态Bean加载呢？ 如何基于Nacos配置中心来实现动态线程池的管理呢？
:::


## SpringBoot 2.7 版本以后得实现

在 `AutoConfigurationImportSelector #getCandidateConfigurations` 方法，由调用的 `SpringFactoriesLoader #loadFactoryNames` 方法变成了 `ImportCandidates #load` 方法，查找的文件也从 `META-INF/spring.factories` 改为了 `META-INF/spring/org.springframework.boot.autoconfigure.AutoConfiguration.imports`

![image.png](/static/img/8961d29b9f830c53a042b78eb2de58b3.image.webp)

其中文件的内容也进行了调整

```yaml
# 变更前 META-INF/spring.factories

org.springframework.boot.autoconfigure.EnableAutoConfiguration=\
  cn.liushigong.cache.redis.RedisCacheAutoConfig

# 变更后 META-INF/spring/org.springframework.boot.autoconfigure.AutoConfiguration.imports

cn.liushigong.cache.redis.RedisCacheAutoConfig

```

# 结尾

我们所了解的 SpringBoot 不是一个全新的框架，而是对 Spring 的一种扩展，回答 `自动装配` 这个问题，除了 @SpringApplication 这千篇一律的逻辑以外，我们还需要能结合 Spring 源码进行有条理的分析出来，才能更好的体现自己的深度。

SpringBoot - 自动装配原理的满分解读

日常开发中使用Map时经常会遇到很多复杂的处理场景，例如：多个键的Map、不仅可以根据键获取值也可以根据值获取键且不用遍历、重复键的Map、数字等范围内映射相同的值、内存中缓存对象等，Guava提供了以上场景的解决方案。





## 实现

根据不同的场景，使用不用的解决方案


|场景	|解决方案	|具体实现|
| --- | --- |--- |
|多个键的Map	|Table	|HashBasedTable、TreeBasedTable、ImmutableTable|
|不仅可以根据键获取值也可以根据值获取键且不用遍历	|BiMap	|HashBiMap、ImmutableBiMap|
|重复键的Map	|Multimap	|ArrayListMultimap、LinkedListMultimap、LinkedHashMultimap、ImmutableListMultimap、ImmutableSetMultimap|
|数字等范围内映射相同的值	|RangeMap	|TreeRangeMap、ImmutableRangeMap|
|内存中缓存对象	|ClassToInstanceMap	|MutableClassToInstanceMap、ImmutableClassToInstanceMap|


## 依赖
截止到今年最新的依赖包版本是 `33.4.6-jre`，很多人不知道如何找maven依赖，提供个[官方仓库地址](https://mvnrepository.com/) `https://mvnrepository.com/`

```xml

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.4.6-jre</version>
</dependency>
```

## 示例

以下为具体使用的 Demo

### Table

官方注释翻译：将一对有序键（称为行键和列键）与单个值相关联的集合。


```java
// HashMap
Map<String, Integer> deptMap = new HashMap<>();
deptMap.put("A部门", 10);
deptMap.put("B部门", 20);
Map<String, Map<String, Integer>> companyMap = new HashMap<>();
companyMap.put("xx公司", deptMap);
// HashMap 获取值
Integer val = companyMap.get("xx公司").get("A部门");
System.out.println("HashMap 获取值: " + val);

// 创建Hash类型Table, 基于Hash表实现
// Table<R, C, V>中三个泛型: R-行, C-列, V-值
Table<String, String, Integer> hashTable = HashBasedTable.create();
hashTable.put("xx公司", "A部门", 10);
hashTable.put("xx公司", "B部门", 20);
hashTable.put("xx公司", "C部门", 30);

System.out.println("\nHash Table: " + hashTable);

// 创建Tree类型Table, 基于红黑树实现
Table<String, String, Integer> treeTable = TreeBasedTable.create();
treeTable.put("xx公司", "C部门", 30);
treeTable.put("xx公司", "B部门", 20);
treeTable.put("xx公司", "A部门", 10);

System.out.println("\nTree Table: " + treeTable);

// 创建不可变Table, 无法新增、更新或删除
Table<String, String, Integer> immutableTable = ImmutableTable.<String, String, Integer>builder()
        .put("xx公司", "C部门", 30)
        .put("xx公司", "B部门", 20)
        .put("xx公司", "A部门", 10)
        .build();

System.out.println("\nImmutable Table: " + immutableTable);

// Table 获取值
Integer val2 = hashTable.get("xx公司", "A部门");
System.out.println("\nTable 获取值: " + val2);

// Table 删除值
Integer remove = hashTable.remove("xx公司", "C部门");
System.out.println("\nTable 删除值: " + remove);

// 根据行获取列和值映射
Map<String, Integer> columnvalueMap = hashTable.row("xx公司");
System.out.println("\nTable 列和值 映射: " + columnvalueMap);

// 根据列获取行和值映射
Map<String, Integer> rowvalueMap = hashTable.column("A部门");
System.out.println("\nTable 行和值 映射: " + rowvalueMap);

// 获取key集合
Set<String> rowKeySet = hashTable.rowKeySet();
System.out.println("\nTable Row key 集合: " + rowKeySet);
Set<String> columnKeySet = hashTable.columnKeySet();
System.out.println("\nTable Column key 集合: " + columnKeySet);

// 获取值集合
Collection<Integer> values = hashTable.values();
System.out.println("\nTable 值集合: " + values);

// 判断包含行
boolean containsRow = hashTable.containsRow("xx公司");
System.out.println("\nTable 包含行: " + containsRow);

// 判断包含列
boolean containsColumn = hashTable.containsColumn("A部门");
System.out.println("\nTable 包含列: " + containsColumn);

// 判断包含行和列
boolean contains = hashTable.contains("xx公司", "A部门");
System.out.println("\nTable 包含行和列: " + contains);

// 判断包含值
boolean containsValue = hashTable.containsValue(10);
System.out.println("\nTable 包含值: " + containsValue);

// 行和列转置 - 行 转 列
Table<String, String, Integer> transposeTable = Tables.transpose(hashTable);

// 获取所有的行
Set<Table.Cell<String, String, Integer>> cells = transposeTable.cellSet();

// 遍历输出
System.out.println("\n遍历输出开始----------------------------");
cells.forEach(cell -> System.out.println(cell.getRowKey() + ", " + cell.getColumnKey() + ", " + cell.getValue()));
System.out.println("\n遍历输出结束----------------------------");

// 转换为嵌套的Map
Map<String, Map<String, Integer>> rowMap = hashTable.rowMap();
System.out.println("\nTable RowMap: " + rowMap);
Map<String, Map<String, Integer>> columnMap = hashTable.columnMap();
System.out.println("\nTable ColumnMap: " + columnMap);
```

输出结果

![image.png](/static/img/8f932973adc45ebbb7b86e276c915055.image.webp)


### BiMap

双映射（或“双向映射”）是一种保留其值及其键的唯一性的映射。此约束使双映射能够支持“反向视图”，即另一个双映射，其中包含与此双映射相同的条目，但具有相反的键和值。

```java
//创建BiMap, 底层为两个Hash表的Map
BiMap<Integer, String> biMap = HashBiMap.create();
biMap.put(1, "one");
biMap.put(2, "two");
biMap.put(3, "three");
biMap.put(4, "four");
biMap.put(5, "five");

System.out.println("BiMap: " + biMap);

//创建不可变BiMap, 无法新增、更新或删除
BiMap<Object, Object> immutableBiMap = ImmutableBiMap.builder().put(1, "one").put(2, "two").put(3, "three").put(4, "four").put(5, "five").build();

System.out.println("\nImmutable BiMap: " + immutableBiMap);

//通过key获取value
String value = biMap.get(1);
System.out.println("\nBiMap 根据key获取value: " + value);

Integer key = biMap.inverse().get("one");
System.out.println("\nBiMap 根据value获取key: " + key);

//翻转后修改
biMap.inverse().put("six", 6);
//返回双映射的逆视图, 并没有创建新对象, 还是之前的对象, 所以操作翻转后的BiMap会影响之前的BiMap
System.out.println("\nBiMap 被影响: " + biMap);

//底层是HashMap, key不可重复
//value不可重复
try {
    biMap.put(11, "one");
} catch (Exception e) {
    System.err.println("BiMap 替换value异常: " + e.getMessage());
}

//翻转后key不能重复
try {
    biMap.inverse().put("first", 1);
} catch (Exception e) {
    System.err.println("BiMap 替换key异常: " + e.getMessage());
}

//key和value可为null
biMap.put(null, null);
System.out.println("\nBiMap 根据Null key获取Null value: " + biMap.get(null));
System.out.println("\nBiMap 根据Null value获取Null key: " + biMap.inverse().get(null));

//强制替换key
biMap.forcePut(11, "one");
System.out.println("\nBiMap 获取新key: " + biMap.inverse().get("one"));

//values为Set集合
Set<String> values = biMap.values();
System.out.println("\nBiMap 不重复的value: " + values);
```

输出结果

![image.png](/static/img/4085eecb9e7275d6d4e20e57b7ed4781.image.webp)

### Multimap

将键映射到值的集合，类似于 Map，但其中每个键可能与多个值相关联。

```java
// 创建Multimap, key为HashMap, value为ArrayList
Multimap<String, Integer> arrayListMultimap = ArrayListMultimap.create();
arrayListMultimap.put("张三", 90);
arrayListMultimap.put("张三", 80);
arrayListMultimap.put("张三", 100);
arrayListMultimap.put("李四", 88);

System.out.println("Multimap key为HashMap, value为ArrayList: " + arrayListMultimap);

// 创建Multimap, key为HashMap, value为HashSet
Multimap<String, Integer> hashMultimap = HashMultimap.create();
hashMultimap.put("张三", 90);
hashMultimap.put("张三", 80);
hashMultimap.put("张三", 100);
hashMultimap.put("李四", 88);

System.out.println("Multimap key为HashMap, value为HashSet: " + hashMultimap);

// 创建Multimap, key为LinkedHashMap, value为LinkedList
Multimap<String, Integer> linkedListMultimap = LinkedListMultimap.create();
linkedListMultimap.put("张三", 90);
linkedListMultimap.put("张三", 80);
linkedListMultimap.put("张三", 100);
linkedListMultimap.put("李四", 88);

System.out.println("Multimap key为LinkedHashMap, value为LinkedList: " + linkedListMultimap);

// 创建Multimap, key为LinkedHashMap, value为LinkedHashMap
Multimap<String, Integer> linkedHashMultimap = LinkedHashMultimap.create();
linkedHashMultimap.put("张三", 90);
linkedHashMultimap.put("张三", 80);
linkedHashMultimap.put("张三", 100);
linkedHashMultimap.put("李四", 88);

System.out.println("Multimap key为LinkedHashMap, value为LinkedHashMap: " + linkedHashMultimap);

// 创建Multimap, key为TreeMap, value为TreeSet
Multimap<String, Integer> treeMultimap = TreeMultimap.create();
treeMultimap.put("张三", 90);
treeMultimap.put("张三", 80);
treeMultimap.put("张三", 100);
treeMultimap.put("李四", 88);

System.out.println("Multimap key为TreeMap, value为TreeSet: " + treeMultimap);

// 创建不可变Multimap, 无法新增、更新或删除, key为ImmutableMap, value为ImmutableList
Multimap<String, Integer> immutableListMultimap = ImmutableListMultimap.<String, Integer>builder()
        .put("张三", 90)
        .put("张三", 80)
        .put("张三", 100)
        .put("李四", 88)
        .build();

System.out.println("Multimap key为ImmutableMap, value为ImmutableList: " + immutableListMultimap);

// 创建不可变Multimap, 无法新增、更新或删除, key为ImmutableMap, value为ImmutableSet
Multimap<String, Integer> immutableSetMultimap = ImmutableSetMultimap.<String, Integer>builder()
        .put("张三", 90)
        .put("张三", 80)
        .put("张三", 100)
        .put("李四", 88)
        .build();

System.out.println("Multimap key为ImmutableMap, value为ImmutableSet: " + immutableSetMultimap);

// 获取值
Collection<Integer> values = arrayListMultimap.get("张三");
System.out.println("Multimap 获取值集合: " + values);

// 获取不存在key的值, 返回的是空集合, 而不是null
Collection<Integer> valuesByNotExistsKey = arrayListMultimap.get("王五");
System.out.println("Multimap 获取不存在的Key值集合: " + valuesByNotExistsKey);

// 获取值集合添加值
// 返回的是多重映射中关联的值的视图集合, 并没有创建新对象, 还是之前的对象, 所以操作值集合会影响之前的Multimap
values.add(60);
System.out.println("Multimap 被影响: " + arrayListMultimap);

// 获取大小
System.out.println("Multimap 大小:" + arrayListMultimap.size());

// 判断是否为空
System.out.println("Multimap 是否为空: " + arrayListMultimap.isEmpty());

// 包含key
System.out.println("Multimap 包含key: " + arrayListMultimap.containsKey("张三"));

// 包含value
System.out.println("Multimap 包含value: " + arrayListMultimap.containsValue(60));

// 包含key-value键值对
System.out.println("Multimap 包含key-value对: " + arrayListMultimap.containsEntry("张三", 60));

// 替换value
arrayListMultimap.replaceValues("张三", Arrays.asList(10, 20, 30));
System.out.println("Multimap 替换value: " + arrayListMultimap);

// 根据key-value删除
arrayListMultimap.remove("张三", 10);
System.out.println("Multimap 根据key-value删除: " + arrayListMultimap);

// 根据key删除
Collection<Integer> removeAll = arrayListMultimap.removeAll("张三");
System.out.println("Multimap 根据key删除: " + removeAll);

// 获取key集合
Set<String> keySet = arrayListMultimap.keySet();
System.out.println("Multimap 获取key集合(HashSet): " + keySet);
Multiset<String> keys = arrayListMultimap.keys();
System.out.println("Multimap 获取key集合(MultiSet): " + keys);

// 获取所有的key-value
Collection<Map.Entry<String, Integer>> entries = arrayListMultimap.entries();
System.out.println("遍历key-value开始--------------------------");
entries.forEach(entry -> System.out.println(entry.getKey() + " : " + entry.getValue()));
System.out.println("遍历key-value结束--------------------------");

// 转换为Map<K, Collection<V>>
Map<String, Collection<Integer>> collectionMap = arrayListMultimap.asMap();
System.out.println("Multimap 转换为Map<K, Collection<V>>: " + collectionMap);
```

输出结果

![image.png](/static/img/510345cdc98e33d2aa226e2ed404b541.image.webp)


### RangeMap

从不相交的非空范围到非 null 值的映射。查询查找与包含指定键的范围（如果有）关联的值。

```java
// if-else
int score = 88;
String rank;
if (0 <= score && score < 60) {
    rank = "不及格";
} else if (60 <= score && score <= 84) {
    rank = "及格";
} else if (84 < score && score <= 100) {
    rank = "优秀";
} else {
    rank = "无效";
}

System.out.println("if-else 获取值: " + rank);

// 创建RangeMap, 基于TreeMap（红黑树）实现
RangeMap<Integer, String> treeRangeMap = TreeRangeMap.create();
treeRangeMap.put(Range.closedOpen(0, 60), "不及格");
treeRangeMap.put(Range.closed(60, 84), "及格");
treeRangeMap.put(Range.openClosed(84, 100), "优秀");
treeRangeMap.put(Range.lessThan(0), "无效");
treeRangeMap.put(Range.greaterThan(100), "无效");

rank = treeRangeMap.get(score);
System.out.println("RangeMap 获取值: " + rank);

// 创建不可变RangeMap, 无法新增、更新或删除
ImmutableRangeMap<Integer, String> immutableRangeMap = ImmutableRangeMap.<Integer, String>builder()
        .put(Range.closedOpen(0, 60), "不及格")
        .put(Range.closed(60, 84), "及格")
        .put(Range.openClosed(84, 100), "优秀")
        .put(Range.lessThan(0), "无效")
        .put(Range.greaterThan(100), "无效")
        .build();

rank = immutableRangeMap.get(score);
System.out.println("ImmutableRangeMap 获取值: " + rank);

// 获取key-value对
Map.Entry<Range<Integer>, String> entry = treeRangeMap.getEntry(88);
System.out.println("RangeMap 获取key-value对: " + entry.getKey() + " : " + entry.getValue());

// 返回不可变的升序的Map
Map<Range<Integer>, String> asMapOfRanges = treeRangeMap.asMapOfRanges();
System.out.println("RangeMap 不可变的升序的Map: " + asMapOfRanges);

// 返回不可变的降序的Map
Map<Range<Integer>, String> asDescendingMapOfRanges = treeRangeMap.asDescendingMapOfRanges();
System.out.println("RangeMap 不可变的降序的Map: " + asDescendingMapOfRanges);

// 相连范围合并
RangeMap<Integer, String> treeRangeMap2 = TreeRangeMap.create();
treeRangeMap2.putCoalescing(Range.closedOpen(0, 60), "不及格");
treeRangeMap2.putCoalescing(Range.closed(60, 84), "及格");
treeRangeMap2.putCoalescing(Range.openClosed(84, 100), "及格"); // 或者 [60..84]范围合并
treeRangeMap2.putCoalescing(Range.lessThan(0), "无效");
treeRangeMap2.putCoalescing(Range.greaterThan(100), "无效");
System.out.println("RangeMap 不合并相连范围: " + treeRangeMap.asMapOfRanges());
System.out.println("RangeMap 合并相连范围: " + treeRangeMap2.asMapOfRanges());

// 最小范围
Range<Integer> span = treeRangeMap.span();
System.out.println("RangeMap 最小范围: " + span);

// 子范围Map
RangeMap<Integer, String> subRangeMap = treeRangeMap.subRangeMap(Range.closed(70, 90));
System.out.println("RangeMap 子范围Map: " + subRangeMap);

// 合并范围
treeRangeMap.merge(Range.closed(60, 100), "及格", (s, s2) -> s2);
System.out.println("RangeMap 合并Map: " + treeRangeMap);

// 移除范围
treeRangeMap.remove(Range.open(90, 95));
System.out.println("RangeMap 移除范围: " + treeRangeMap);

// 清除所有范围
treeRangeMap.clear();
System.out.println("RangeMap 清除所有范围: " + treeRangeMap);
```

输出结果

![image.png](/static/img/c71f907f9c6ad4edd542dffdfd1c3800.image.webp)


### ClassToInstanceMap

映射，其每个条目将一个 Java 原始类型 映射到该类型的实例。除了实现 Map之外，还提供额外的类型安全操作 putInstance 和 getInstance 。与任何其他 Map<Class, Object>映射一样，此映射可能包含基元类型的条目，并且基元类型及其相应的包装器类型可以映射到不同的值。

```java
static class UserBean {
    private final Integer id;
    private final String username;

    public UserBean(Integer id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return "UserBean{" + "id=" + id + ", username='" + username + '\'' + '}';
    }
}
public static void main(String[] args) {
    // 创建Bean
    UserBean userBean = new UserBean(1, "张三");

    // HashMap
    HashMap<Class, Object> hashMap = new HashMap<>();
    hashMap.put(UserBean.class, userBean);

    // 获取值，需要强转
    UserBean value = (UserBean) hashMap.get(UserBean.class);
    System.out.println("HashMap 获取对象实例: " + value);
    System.out.println("HashMap 获取对象实例等于创建的Bean: " + (value == userBean));

    // 创建ClassToInstanceMap
    ClassToInstanceMap<Object> classToInstanceMap = MutableClassToInstanceMap.create();
    classToInstanceMap.putInstance(UserBean.class, userBean);

    // 获取值，无需强转
    UserBean value2 = classToInstanceMap.getInstance(UserBean.class);
    System.out.println("\nClassToInstanceMap 获取对象实例: " + value2);
    System.out.println("ClassToInstanceMap 获取对象实例等于创建的Bean: " + (value2 == userBean));

    // 创建不可变ClassToInstanceMap, 无法新增、更新或删除
    ClassToInstanceMap<UserBean> immutableClassToInstanceMap = ImmutableClassToInstanceMap.<UserBean>builder()
        .put(UserBean.class, userBean)
        .build();

    // 获取值，无需强转
    UserBean value3 = immutableClassToInstanceMap.getInstance(UserBean.class);
    System.out.println("\nImmutableClassToInstanceMap 获取对象实例: " + value3);
    System.out.println("ImmutableClassToInstanceMap 获取对象实例等于创建的Bean: " + (value3 == userBean));


    // 限制类型，避免使用HashMap存储对象时，因为使用Object值类型而在添加缓存时需要今天类型校验
    ClassToInstanceMap<Collection> classToInstanceMap1 = MutableClassToInstanceMap.create();
    classToInstanceMap1.put(ArrayList.class, new ArrayList());
    classToInstanceMap1.put(HashSet.class, new HashSet());
    // 编译保存: 'put(java.lang.Class<? extends java.util.@org.checkerframework.checker.nullness.qual.NonNull Collection>, java.util.Collection)' in 'com.google.common.collect.MutableClassToInstanceMap' cannot be applied to '(java.lang.Class<java.util.HashMap>, java.util.HashMap)'
    //        classToInstanceMap1.put(HashMap.class, new HashMap());
}
```

输出结果

![image.png](/static/img/196274a8601760add8f03875a4b66478.image.webp)

Guava - Map增强工具类

算法-经典排序算法

# 经典算法思想

## 分治法（Divide and Conquer）

分治法(Divide and Conquer，也称为“分而治之法”)是一种很重要的算法，我们可以应用分治法来逐一拆解复杂的问题，核心思想就是将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题，以便名个击破。

![image.png](/static/img/4fb979feaafa2aace274a299c4616224.image.webp)

其实任何一个可以用程序求解的问题所需的计算时间都与其规模与复杂度有关，问题的规模越小，越容易直接求解，因此可以不断分解问题，使子问题规模不断缩小,让这些子问题简单到可以直接解决，再将各子问题的解合并，最后得到原问题的解答。


### 特点与应用

- 子问题相互独立
- 递归实现
- 归并排序：将数组拆分为两半，递归排序后合并有序子数组。
- 快速排序：通过基准值分割数组，递归处理左右分区


### 代码实现（归并排序）

```java
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);      // 分解左半部分
            mergeSort(arr, mid + 1, right); // 分解右半部分
            merge(arr, left, mid, right);   // 合并有序子数组
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // 输出[2, 3, 4, 5, 8]
    }
}
```

**代码解读：**

分解：递归将数组分为左右两半

合并：将两个有序子数组合并为一个有序数组


## 递归法（Recursion）

递归是一种很特殊的算法，分治法和递归法很像一对孪生兄弟，都是将一个复杂的算法问题进行分解，让规模越来越小，最终使子问题容易求解。只不过递归法通过函数调用自身解决问题，需定义基线条件和递归条件。


![image.png](https://blog.liushigong.cn/static/img/4a68bcefd142ee2600c0599c942798f5.image.webp)


### 特点与应用

- 代码简洁
- 经典应用：树遍历、汉诺塔

### 汉诺塔问题

> 给定三根柱子，记为 A,B,C，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。问：将 A 柱上的盘子经由 B 柱移动到 C 柱最少需要多少次？打印出每个步骤
> 
> 移动时应注意：
> - 一次只能移动一个盘子
> - 大的盘子不能压在小盘子上


**思路**

先从简单的三个盘子试试，可以先不看答案自己画一画，挺好玩的，注意规则噢

![image.png](/static/img/6ec28eba4b4fb3b7ad9b0b6af3a29077.image.webp)

n个盘子从A柱到C柱最少移动次数

![image.png](/static/img/ba88aa37d5b721c8ae115a3b5b303891.image.webp)

**代码实现**

```java
public class HanoiTower {
    public static void move(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("移动盘子1从" + from + "到" + to);
            return;
        }
        move(n - 1, from, aux, to);
        System.out.println("移动盘子" + n + "从" + from + "到" + to);
        move(n - 1, aux, to, from);
    }

    public static void main(String[] args) {
        move(3, 'A', 'C', 'B'); // 3层汉诺塔解法
    }
}
```

**代码解读**

将n个盘子分解为移动n-1个盘子的子问题

时间复杂度：O(2ⁿ)


## 动态规划（Dynamic Programming, DP）

通过记录子问题的解避免重复计算，适用于有重叠子问题和最优子结构的问题。

动态规划法(Dynamic Programming Algorithm，DPA)类似于分治法，核心思想是如果一个问题的答案与子问题相关，就将大问题拆解成各个小问题，与分治法最大的不同是可以让每一个子问题的答案被存储起来，以供下次求解时直接取用。这样的做法不但可以减少再次计算的时间，而且可以将这些解组合成大问题的解，故而使用动态规划可以解决重复计算的问题。

动态规划法是分治法的延伸。当用递归法分割出来的问题“一而再，再而三”出现时，就可以运用记忆(Memorization)法来存储这些问题。与分治法不同的地方在于，动态规划法增加了记忆机制的使用，将处理过的子问题的答案记录下来，避免重复计算。


### 特点与应用

- 自底向上或自顶向下（记忆化搜索）
- 时间复杂度优化显著
- 最短路径问题（Floyd-Warshall算法）
- 斐波那契数列
- 背包问题
- 最长公共子序列
- 最长公共子串
- 矩阵最大值（和以及积）


### 斐波那契数列

斐波那契数列是指这样一个数列：0，1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。


![image.png](/static/img/ecba5aa12fb2385f5676c8f4e29c3f5c.image.webp)

对于斐波那契数列采用的是动态规划法，那么已计算过的数据就不必重复计算了，也不会再往下递归，这样可以提高性能。

![image.png](https://blog.liushigong.cn/static/img/e22182c57ec9087706bce5e8db376cc2.image.webp)

**代码实现**

```java
public class Fibonacci {
    // 动态规划实现
    public static int fibDP(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibDP(10)); // 输出55
    }
}
```

**代码解读：**

使用数组 dp 存储中间结果

递推公式：dp[i] = dp[i-1] + dp[i-2]


## 枚举法（Brute Force）

枚举法(又称为穷举法)，是我们在日常工作中使用最多的一种算法，核心思想是列举所有的可能。根据问题的要求，逐一列举问题的解答，或者为了便于解决问题把问题分为不重复、不遗漏的有限种情况，逐一列举各种情况，并加以解决，最终达到解决整个问题的目的。像枚举法这种分析问题、解决问题的方法，得到的结果总是正确的，缺点是速度太慢。


### 特点与应用

- 实现简单
- 时间复杂度：O(n)
- 适合小规模的问题
- 密码破解：尝试所有可能的字符组合


### 代码实现

使用穷举法来实现以下题目

> 今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？

```java
public class Permutations {
    public static void enumeratingAlgorithm() {
        int head = 35, foot = 94;
        int j;
        for (int i = 0; i <= 35; i++) {
            // i代表鸡的数量        
            j = head - i;
            // j代表兔子的数量
            if (i * 2 + j * 4 == foot) {
                System.out.printf("鸡的个数为[ %d ]只,兔子的个数为[ %d ]只。", i, j);
                return;
            }
        }
        System.out.println("此题无解！你家鸡和兔子有三只脚的吧？");
    }
}
```

**代码解读：**

通过题目可以知道，鸡和兔的总数量为0-35只(每个动物都是一个脑袋，这就不用说了吧)，我们可以假设鸡为0，兔子为35，用鸡的个数*2+兔子的个数*4就可以得到总的脚的数量，如果等于94，那么便是答案，如果不等，则鸡的数量+1，兔子数量-1，依次类推，穷举所有情况直到得到答案


## 回溯法（Backtracking）

回溯法(Backtracking)也是枚举法的一种，对于某些问题而言，回溯法是一种可以找出所有(或一部分)解的一般性算法，同时避免枚举不正确的数值。一旦发现不正确的数值，就不再递归到下一层，而是回溯到上一层，以节省时间，是一种走不通就退回再走的方式。它的特点主要是在搜索过程中寻找问题的解，当发现不满足求解条件时就回湖(返回)，尝试别的路径，避免无效搜

![image.png](/static/img/b5b06d0bb66eb9de8e87da9303a75d7e.image.webp)

### 特点

- 递归实现
- 时间复杂度高（指数级）
- 数独求解
- 组合数生成
- A*寻路算法（了解）
- 地图着色算法
- N 皇后问题
- 最优加工顺序
- 旅行商问题

回溯法可以应用于以下类型的问题：

- 排列和组合问题：例如求解全排列、子集合等问题，回溯法可以系统地生成所有可能的组合并逐一验证。
- 决策问题：如八皇后问题、数独填充、图的着色问题等，这些问题需要在多个选择中找到符合特定约束的解。
- 优化问题：如旅行商问题（TSP）和其他需要找到最优解的问题，回溯法可以遍历所有可能的解，找到成本最低或收益最高的解。
- 分割问题：例如分割等和子集、装箱问题等，需要将集合分割成满足特定条件的多个子集。


### N皇后问题

八皇后问题，是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法?


![image.png](https://blog.liushigong.cn/static/img/1ecce3e32c9cedaf6a4faa5d212e53c4.image.webp)

将8皇后问题推演一下，就可以得到我们的N皇后问题了。

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，使其不能互相攻击。(同一行、同一列、同一斜线上的皇后都会自动攻击)那么问，有多少种摆法？


**代码解读：**

```java
public class NQueens {
    private static List<List<String>> result = new ArrayList<>();

    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(board, 0);
        return result;
    }

    private static void backtrack(char[][] board, int row) {
        if (row == board.length) {
            result.add(convertBoard(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1);
                board[row][col] = '.'; // 回溯
            }
        }
    }

    private static boolean isValid(char[][] board, int row, int col) {
        // 检查列、左上对角线、右上对角线
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
            int left = col - (row - i), right = col + (row - i);
            if (left >= 0 && board[i][left] == 'Q') return false;
            if (right < board.length && board[i][right] == 'Q') return false;
        }
        return true;
    }

    private static List<String> convertBoard(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) res.add(new String(row));
        return res;
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(4).size()); // 输出2（4皇后有2种解法）
    }
}
```

**代码解读：**

逐行放置皇后，检查冲突

回溯时重置棋盘状态（board[row][col] = '.'）



## 贪心法（Greedy Algorithm）

贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

### 思路

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，其选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时， 就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

> 贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。
> 
> 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

**题解思路可分为3个步骤**

1. 将问题分解为多个子问题。
2. 选择合适的贪心策略，得到每一个子问题的局部最优解。
3. 将子问题的局部最优解合并成原问题的最优解。


:::tip{title="贪心算法存在的问题"}
贪心算法是把求解的问题分成若干个子问题求最优解，不能保证 **最终解是最佳的**。

因为贪心算法总是从局部出发，并没从整体考虑，贪心算法容易过早做出决定，所以只能求出满足某些约東条件的解，而有时在某些问题上还是可以得到最优解的。
:::


### 解题策略

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解，使用贪心策略解题需要考虑以下两个问题：

- 该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质
- 制定贪心策略，以达到问题的最优解或较优解

:::info{title="证明的大致过程"}
首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。
:::

### 经典应用

贪心策略的经典算法

#### 分数背包问题

给定 n 个物品，每个物品都有重量 w[i] 和价值 v[i]，同时有一个容量为 C 的背包。与 0-1 背包问题不同的是，在分数背包问题中，物品可以分割成任意比例放入背包，目标是在背包容量限制内选择物品放入背包，使得背包中物品的总价值最大。

![image.png](/static/img/8c15c03393444bb99308bcead4f4228d.image.webp)


**贪心策略确定**

最大化背包内物品总价值，本质上是最大化单位重量下的物品价值。由此便可推理出贪心策略。

1. 将物品按照单位价值从高到低进行排序。
2. 遍历所有物品，每轮贪心地选择单位价值最高的物品。
3. 若剩余背包容量不足，则使用当前物品的一部分填满背包。


![image.png](/static/img/e0230fbd5ca18a3c29b3f060ba1f2d36.image.webp)


**代码实现**

建立了一个物品类 Item ，以便将物品按照单位价值进行排序。循环进行贪心选择，当背包已满时跳出并返回解：

```java
/* 物品 */
class Item {
    int w; // 物品重量
    int v; // 物品价值

    public Item(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

/* 分数背包：贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
    // 创建物品列表，包含两个属性：重量、价值
    Item[] items = new Item[wgt.length];
    for (int i = 0; i < wgt.length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // 按照单位价值 item.v / item.w 从高到低进行排序
    Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
    // 循环贪心选择
    double res = 0;
    for (Item item : items) {
        if (item.w <= cap) {
            // 若剩余容量充足，则将当前物品整个装进背包
            res += item.v;
            cap -= item.w;
        } else {
            // 若剩余容量不足，则将当前物品的一部分装进背包
            res += (double) item.v / item.w * cap;
            // 已无剩余容量，因此跳出循环
            break;
        }
    }
    return res;
}
```

内置排序算法的时间复杂度通常为O(logn) ，空间复杂度通常为 O(logn) 或 O(n)，取决于编程语言的具体实现。除排序之外，在最差情况下，需要遍历整个物品列表，因此时间复杂度为O(n)，其中n为物品数量。由于初始化了一个 Item 对象列表，因此空间复杂度为 O(n)。


**正确性证明**

采用反证法。假设物品 x 是单位价值最高的物品，使用某算法求得最大价值为 res ，但该解中不包含物品 x。

现在从背包中拿出单位重量的任意物品，并替换为单位重量的物品x。由于物品x的单位价值最高，因此替换后的总价值一定大于 res 。这与 res 是最优解矛盾，说明最优解中必须包含物品x。

对于该解中的其他物品，我们也可以构建出上述矛盾。总而言之，单位价值更大的物品总是更优选择，这说明贪心策略是有效的。

将物品重量和物品单位价值分别看作一张二维图表的横轴和纵轴，则分数背包问题可转化为“求在有限横轴区间下围成的最大面积”。这个类比可以帮助我们从几何角度理解贪心策略的有效性。

![image.png](/static/img/e5edc129ada714199246facf20cc74e3.image.webp)


#### 找零问题

给定一个总金额和一系列不同面额的零钱，如何以最少的零钱数量来支付这个金额。‌在找零问题中，贪心算法的核心思想是每一步尽可能使用面值最大的零钱，从而减少使用的零钱数量。

**贪心策略确定**

将原问题分解为一系列子问题，每个子问题对应一个具体的找零操作。

- 贪心选择‌：对每个子问题求解时，选择当前看起来“最优”的解法，即尽可能使用面值最大的零钱。
- 合并解‌：累计局部最优解形成全局解，最终得到最少的零钱数量。

**代码实现**

```java
public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins); // 需降序排序
        int count = 0, index = coins.length - 1;
        while (amount > 0 && index >= 0) {
            if (coins[index] <= amount) {
                int num = amount / coins[index];
                count += num;
                amount -= num * coins[index];
            }
            index--;
        }
        return (amount == 0) ? count : -1;
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25}; // 美分硬币
        System.out.println(minCoins(coins, 63)); // 输出6（25+25+10+1+1+1）
    }
}
```

**正确性证明‌**

通过数学归纳或替换论证验证算法的正确性，尽管贪心策略不一定总是正确的，但在许多情况下能够提供足够好的解决方案。


## 总结

掌握这些算法思想可覆盖90%的编程问题，实际应用中需根据问题特点灵活组合使用。

| 算法思想 |	适用场景	| 时间复杂度 |
| --- | --- | --- |
| 分治法	| 大规模问题分解	| O(n log n)| 
| 递归法	| 树形结构问题	| 取决于问题规模| 
| 动态规划	| 重叠子问题优化	| O(n²) ~ O(n³)| 
| 枚举法	| 小规模暴力求解	| O(2ⁿ) ~ O(n!)| 
| 回溯法	| 组合优化问题	| O(n!)| 
| 贪心法	| 局部最优解场景	| O(n) ~ O(n log n)|

算法-核心算法思想

baidu-site-verification

本人自己的博客，对工作与学习过程中的总结、一些场景设计的实现方案、遇到过的疑难问题与解决、以及面试总结等。