第八十四天-背包问题，Spring事务管理

欢迎大家来到IT世界,在知识的湖畔探索吧!

学习笔记：

1.Spring 支持两种类型的事务管理:

编程式事务管理 ：这意味着你在编程的帮助下有管理事务。这给了你极大的灵活性，但却很难维护。

声明式事务管理 ：这意味着你从业务代码中分离事务管理。你仅仅使用注释或 XML 配置来管理事务。

2.Spring事务管理的五大属性：隔离级别、传播行为、是否只读、事务超时、回滚规则

3.编程式事务管理方法允许你在对你的源代码编程的帮助下管理事务。这给了你极大地灵活性，但是它很难维护。

4.声明式事务管理方法允许你在配置的帮助下而不是源代码硬编程来管理事务。这意味着你可以将事务管理从事务代码中隔离出来。你可以只使用注释或基于配置的 XML 来管理事务。 bean 配置会指定事务型方法。

5.下面是与声明式事务相关的步骤：

我们使用标签，它创建一个事务处理的建议，同时，我们定义一个匹配所有方法的切入点，我们希望这些方法是事务型的并且会引用事务型的建议。

如果在事务型配置中包含了一个方法的名称，那么创建的建议在调用方法之前就会在事务中开始进行。

目标方法会在 try / catch 块中执行。

如果方法正常结束，AOP 建议会成功的提交事务，否则它执行回滚操作。

6.Spring web MVC 框架提供了模型-视图-控制的体系结构和可以用来开发灵活、松散耦合的 web 应用程序的组件。

7.MVC 模式导致了应用程序的不同方面(输入逻辑、业务逻辑和 UI 逻辑)的分离，同时提供了在这些元素之间的松散耦合。

8.模型封装了应用程序数据，并且通常它们由 POJO 组成。视图主要用于呈现模型数据，并且通常它生成客户端的浏览器可以解释的 HTML 输出。控制器主要用于处理用户请求，并且构建合适的模型并将其传递到视图呈现。

9.Spring Web 模型-视图-控制（MVC）框架是围绕 DispatcherServlet 设计的，DispatcherServlet 用来处理所有的 HTTP 请求和响应。Spring Web MVC DispatcherServlet 的请求处理的工作流程如下图所示：

10.Markdown 是一种轻量级标记语言，它允许人们使用易读易写的纯文本格式编写文档。Markdown 编写的文档可以导出 HTML 、Word、图像、PDF、Epub 等多种格式的文档。

11.474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3

输出：4

解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10″,”0001″,”1″,”0”} ，因此答案是 4 。

其他满足题意但较小的子集包括 {“0001″,”1”} 和 {“10″,”1″,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

解题思路：创建一个方法来计算每个元素中的0和1的个数，使用滚动数组dp来存储当字符串里有最多j个0和k个1时，最大子集的长度，由于当前的状态只与前一行的状态有关，所以可以使用一个数组dp来存储，当前行从后往前更新，否则dp默认与上一行的值相同。遍历整个数组，计算当前元素所能得到的最大dp的值，有两种情况，一种是不选取当前元素，dp的值和在上一个元素时相同；一种是选取当前元素则dp[j][k]=dp[j-zeros][k-ones]+1。最后得到的dp[m][n]即为所求。

class Solution {
    //创建一个方法来计算每个元素中的0和1的个数，使用滚动数组dp来存储当字符串里有最多j个0和k个1时，最大子集的长度，由于当前的状态只与前一行的状态有关，所以可以使用一个数组dp来存储，当前行从后往前更新，否则dp默认与上一行的值相同。遍历整个数组，计算当前元素所能得到的最大dp的值，有两种情况，一种是不选取当前元素，dp的值和在上一个元素时相同；一种是选取当前元素则dp[j][k]=dp[j-zeros][k-ones]+1。最后得到的dp[m][n]即为所求。
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int dp[][] = new int[m+1][n+1];
        for(int i=0; i<len; i++){
            int zeroOnes[] = findZO(strs[i]);
            int zeros = zeroOnes[0], ones = zeroOnes[1];
            for(int j=m; j>=zeros; j--){
                for(int k=n; k>=ones; k--){
                    dp[j][k] = Math.max(dp[j][k], dp[j-zeros][k-ones]+1);
                }
            }
        }
        return dp[m][n];
    }
    public int[] findZO(String str){
        int zeroOnes[] = new int[2];
        for(int i=0; i<str.length(); i++){
            zeroOnes[str.charAt(i)-'0']++;
        }
        return zeroOnes;
    }
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

12.139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = “leetcode”, wordDict = [“leet”, “code”]

输出: true

解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

解题思路：将字典里的单词放到hashset里，使用数组dp[i]表示字符串中[0…i-1]个字符是否可以使用字典中出现的单词拼出。dp[i]的值取决于最后一个单词s[j,i]是否在字典里以及除去这个单词之后dp[i-j]的状态，只有当这两个值都为true时，dp[i]才等于true。最后得到的dp[s.length]即为答案。

欢迎大家来到IT世界,在知识的湖畔探索吧!class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //将字典里的单词放到hashset里，使用数组dp[i]表示字符串中[0...i-1]个字符是否可以使用字典中出现的单词拼出。dp[i]的值取决于最后一个单词s[j,i]是否在字典里以及除去这个单词之后dp[i-j]的状态，只有当这两个值都为true时，dp[i]才等于true。最后得到的dp[s.length]即为答案。
        boolean dp[] = new boolean[s.length()+1];
        Set<String> dict = new HashSet<String>(wordDict);
        dp[0] = true;
        for(int i=1; i<=s.length(); i++){
            for(int j=0; j<i; j++){
                if(dp[j] && dict.contains(s.substring(j, i))){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}