Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character Delete a character Replace a character Example 1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2:
Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i=0;i<=len1;i++){
dp[i][0] = i;
}
for(int j=0;j<=len2;j++){
dp[0][j] = j;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
//字符相等直接同时减小1个
dp[i][j] = dp[i - 1][j - 1];
} else {
//dp[i-1][j-1] 替换
//dp[i - 1][j] 删除第一个
//dp[i][j - 1] 删除第二个
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
return dp[len1][len2];
}
}if s1[i] == s2[j]:
啥都别做（skip）
i, j 同时向前移动
else:
三选一：
插入（insert）
删除（delete）
替换（replace）
这里 dp(i, j) 函数的定义是这样的：
def dp(i, j) -> int
# 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
记住这个定义之后，先来看这段代码：
if s1[i] == s2[j]:
return dp(i - 1, j - 1) # 啥都不做
# 解释：
# 本来就相等，不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小编辑距离等于
# s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
# 也就是说 dp(i, j) 等于 dp(i-1, j-1)
如果 s1[i]！=s2[j] ，就要对三个操作递归了，稍微需要点思考：
dp(i, j - 1) + 1, # 插入
# 解释：
# 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
# 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
# 别忘了操作数加一
dp(i - 1, j) + 1, # 删除
# 解释：
# 我直接把 s[i] 这个字符删掉
# 前移 i，继续跟 j 对比
# 操作数加一
dp(i - 1, j - 1) + 1 # 替换
# 解释：
# 我直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了
# 同时前移 i，j 继续对比
# 操作数加一dp[i][j] 的含义和之前的 dp 函数类似
def dp(i, j) -> int
## 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
dp[i-1][j-1]
## 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离Spring注解学习(二)
用来标记缓存查询。可用用于方法或者类中，当标记在一个方法上时表示该方法是支持缓存的，当标记在一个类上时则表示该类所有的方法都是支持缓存的。
| 参数 | 解释 | 例子 |
|---|---|---|
| value | 名称 | @Cacheable(value={"c1", "c2"}) |
| key | key | @Cacheable(value="c1", key="#id") |
| condition | 条件 | @Cacheable(value="c1",condition="#id=1") |
比如@Cacheable(value="UserCache") 标识的是当调用了标记了这个注解的方法时，逻辑默认加上从缓存中获取结果的逻辑，如果缓存中没有数据，则执行用户编写查询逻辑，查询成功之后，同时将结果放入缓存中。
但凡说到缓存，都是key-value的形式的，因此key就是方法中的参数（id），value就是查询的结果，而命名空间UserCache是在spring*.xml中定义.
// 使用了一个缓存名叫accountCache
@Cacheable(value="UserCache")
public Account getUserAge(int id){
//正常业务逻辑
int age = getUser(id);
return age;
}用来标记要清空缓存的方法，当这个方法被调用后，即会清空缓存。@CacheEvict(value=”UserCache”)
| 参数 | 解释 | 例子 |
|---|---|---|
| value | 名称 | @CacheEvict(value={"c1", "c2"}) |
| key | key | @CacheEvict(value="c1", key="#id") |
| condition | 缓存清空条件,可以为空 | |
| allEntries | 是否清空所有的缓存内容 | @CacheEvict(value="c1", allEntries=true) |
| beforeInvocation | 是否在方法执行前就清空 | @CacheEvict(value="c1", beforeInvocation=true) |
@Resource的作用相当于@Autowired 只不过@Autowired按byType自动注入， 而@Resource默认按 byName自动注入罢了。 @Resource有两个属性是比较重要的，分是name和type，Spring将@Resource注解的name属性解析为bean的名字，而type属性则解析为bean的类型。所以如果使用name属性，则使用byName的自动注入策略，而使用type属性时则使用byType自动注入策略。如果既不指定name也不指定type属性，这时将通过反射机制使用byName自动注入策略。
@Resource装配顺序:
1、如果同时指定了name和type，则从Spring上下文中找到唯一匹配的bean进行装配，找不到则抛出异常
2、如果指定了name，则从上下文中查找名称（id）匹配的bean进行装配，找不到则抛出异常
3、如果指定了type，则从上下文中找到类型匹配的唯一bean进行装配，找不到或者找到多个，都会抛出异常
4、如果既没有指定name，又没有指定type，则自动按照byName方式进行装配；如果没有匹配，则回退为一个原始类型进行匹配，如果匹配则自动装配；
用来标记是在项目启动的时候执行这个方法。用来修饰一个非静态的void()方法 也就是spring容器启动时就执行，多用于一些全局配置、数据字典之类的加载
被@PostConstruct修饰的方法会在服务器加载Servlet的时候运行，并且只会被服务器执行一次。PostConstruct在构造函数之后执行,init()方法之前执行。 PreDestroy（）方法在destroy()方法执行执行之后执
被@PreDestroy修饰的方法会在服务器卸载Servlet的时候运行，并且只会被服务器调用一次，类似于Servlet的destroy()方法。被@PreDestroy修饰的方法会在destroy()方法之后运行，在Servlet被彻底卸载之前
用于标注数据访问组件，即DAO组件
泛指组件，当组件不好归类的时候，我们可以使用这个注解进行标注
用来配置 spring bean 的作用域，它标识 bean 的作用域。
默认值是单例
1、singleton:单例模式,全局有且仅有一个实例
2、prototype:原型模式,每次获取Bean的时候会有一个新的实例
3、request:request表示该针对每一次HTTP请求都会产生一个新的bean，同时该bean仅在当前HTTP request内有效
4、session:session作用域表示该针对每一次HTTP请求都会产生一个新的bean，同时该bean仅在当前HTTP session内有效
5、global session:只在portal应用中有用，给每一个 global http session 新建一个Bean实例。
默认情况下Spring MVC将模型中的数据存储到request域中。当一个请求结束后，数据就失效了。如果要跨页面使用。那么需要使用到session。而@SessionAttributes注解就可以使得模型中的数据存储一份到session域中 参数：
1、names：这是一个字符串数组。里面应写需要存储到session中数据的名称。
2、types：根据指定参数的类型，将模型中对应类型的参数存储到session中
3、value：和names是一样的。
@Controller
@SessionAttributes(value=["names"], types={Integer.class})
public class ScopeService{
@RequestMapping("testSession")
public String test(Map<String, Object> map){
map.put("names", Array.asList("a","b","c"));
map.put("age", 12);
return "hello";
}
}适用于bean属性setter方法，并表示受影响的bean属性必须在XML配置文件在配置时进行填充。否则，容器会抛出一个BeanInitializationException异常。
@Qualifier 当你创建多个具有相同类型的 bean 时，并且想要用一个属性只为它们其中的一个进行装配，在这种情况下，你可以使用 @Qualifier 注释和 @Autowired 注释通过指定哪一个真正的 bean 将会被装配来消除混乱哦。
总的来说有 6 种生成 hashCode 的方式：
- 0: A randomly generated number
- 1: A function of memory address of the object
- 2: A hardcoded 1 (used for sensitivity testing.)
- 3: A sequence.
- 4: The memory address of the object, cast to int
- 5（else）: Thread state combined with xor-shift[1]
JDK1.8 中生成 hashCode 的方式是 5， 也就是走程序的 else 路径，即使用 Xorshift，并不是之前认为的对象内存地址「1」，以为老版本是采用对象内存地址的方式，所以继续查看其他版本
JDK1.6[2] 和 JDK1.7[3] 版本生成 hashCode 的方式「1」随机数的形式
hash 值是存在对象头中的，我们还知道对象头中还可能存储线程ID，所以他们在某些情形中还会存在冲突
jvm 启动时，可以使用 -XX:+UseBiasedLocking=true 开启偏向锁，（关于偏向锁，轻量级锁，重量级锁大家查阅 synchronized 相关文档就可以），这里引 OpenJDK Wiki[4] 里面的图片加以文字说明整个冲突过程
调用 Object 的 hashCode() 方法或者 System.identityHashCode() 方法会让对象不能使用偏向锁。到这里你也就应该知道了，如果你还想使用偏向锁，那最好重写 hashCode() 方法，避免使偏向锁失效.
Object.hashCode是一个native方法，看不到源码（Java代码，Oracle的JDK是看不到的，OpenJDK或其他开源JRE是可以找到对应的C/C++代码）。
Object.hashCode()在JRE（Java Runtime Library）中应该遵循的一些契约（contract）：
-
一致性（consistent），在程序的一次执行过程中，对同一个对象必须一致地返回同一个整数。
-
如果两个对象通过equals(Object)比较，结果相等，那么对这两个对象分别调用hashCode方法应该产生相同的整数结果。（PS：这里equals和hashCode说的都是Object类的）
-
如果两个对象通过java.lang.Object.equals(java.lang.Ojbect)比较，结果不相等，不必保证对这两个对象分别调用hashCode也返回两个不相同的整数。
实际上java.lang包里面的类，都是JRE必须的，属于运行时库（Runtime Library），这也是为什么很多JRE下该类的class文件被打包到rt.jar中的原因（应该是Runtime的简写）。
而这些运行时库一般都是跟JDK/JRE一起发布的；所以，对于不同的JRE环境，问题的答案未必相同。
[1] xor-shift算法: https://en.wikipedia.org/wiki/Xorshift
[2] JDK1.6代码: http://hg.openjdk.java.net/jdk6/jdk6/hotspot/file/5cec449cc409/src/share/vm/runtime/globals.hpp#l1128
[3] JDK1.7代码: http://hg.openjdk.java.net/jdk7u/jdk7u/hotspot/file/5b9a416a5632/src/share/vm/runtime/globals.hpp#l1100
[4] OpenJDK Wiki: https://wiki.openjdk.java.net/display/HotSpot/Synchronization
[5] 默认hashCode生成方式: https://srvaroa.github.io/jvm/java/openjdk/biased-locking/2017/01/30/hashCode.html
如果引入了Lombok包，可以在pojo类上面添加注解@Data，这样可以在运行时自动加入get set 以及toString方法，我们这里模拟一个注解+反射实现打印变量的方法。
- 新增一个注解
@Target({ElementType.TYPE}) //类注解
@Documented //将注解包含在Javadoc中
@Inherited //允许子类继承父类中的注解
@Retention(RetentionPolicy.RUNTIME) //VM将在运行期间保留注解，因此可以通过反射机制读取注解的信息
public @interface DataAnnotation {
boolean value() default false;
}- 新建一个Pojo类，并引入该注解
@DataAnnotation(value = true)
public class Student {
private String name = "zhangsan";
private Integer age = 12;
}- 测试注解的执行情况
public class AnnotationTest {
public static void main(String[] args) throws Exception {
// 新建Student
Student student = new Student();
// 获取Student的Class实例
Class<Student> studentClass = Student.class;
iteratorAnnotations(studentClass);
}
public static void iteratorAnnotations(Class clazz) throws IllegalAccessException, InstantiationException {
// 判断方法是否包含DataAnnotation注解
if(clazz.isAnnotationPresent(DataAnnotation.class)){
// 获取该方法的MyAnnotation注解实例
DataAnnotation testAnnotation = (DataAnnotation) clazz.getAnnotation(DataAnnotation.class);
// 获取 myAnnotation的值，并打印出来
boolean value = testAnnotation.value();
// 如果value为true，打印参数，否则直接返回
if(value){
Field[] fields = clazz.getDeclaredFields();
for( Field field : fields){
// 设置可见性，便于打印变量
field.setAccessible(true);
System.out.println( field.getName() + ":" +field.get(clazz.newInstance()));
}
}
System.out.println();
}
}
}