2024年11月

spring boot中配置日志归档的模板

作者: zorth
时间: 2024-11-26
分类: 默认分类
评论

![](https://zorth-1305096201.cos.ap-guangzhou.myqcloud.com/undefined20241126143027.png)
SLF4J (Simple Logging Facade for Java) 实际上是一个日志门面框架，它本身并不提供日志实现，而是需要与具体的日志实现框架配合使用。Logback 就是 SLF4J 的一个原生实现。

1. **SLF4J + Logback 的关系**：

- SLF4J 是接口（门面模式）
- Logback 是实现
- Logback 的作者就是 SLF4J 的作者，所以它们是完全兼容的

1. **使用方式**：
   需要添加以下依赖：

```xml
  
<dependencies>  
      
    <dependency>  
        <groupId>org.slf4j</groupId>  
        <artifactId>slf4j-api</artifactId>  
        <version>1.7.36</version>  
    </dependency>  
    
      
    <dependency>  
        <groupId>ch.qos.logback</groupId>  
        <artifactId>logback-classic</artifactId> 
        <version>1.2.11</version>  
    </dependency>  
</dependencies>  
```

1. **代码中的使用**：

```java
import org.slf4j.Logger;  
import org.slf4j.LoggerFactory;

public class YourClass {  
    private static final Logger logger = LoggerFactory.getLogger(YourClass.class);  
    
    public void someMethod() {  
        logger.info("This is an info message");  
        logger.error("This is an error message");  
    }  
}  
```

1. **配置文件**：
   完全可以使用之前提到的 logback.xml 配置文件来进行日志归档配置。实际上，使用 SLF4J + Logback 的组合时，Logback 会按以下顺序查找配置文件：
2. logback-test.xml
3. logback.xml
4. 如果都没找到，使用默认配置

```xml
<?xml version="1.0" encoding="UTF-8"?>  
<configuration>  
    <property name="log.path" value="/logs" />  
    
      
    <appender name="CONSOLE" class="ch.qos.logback.core.ConsoleAppender">  
        <encoder>  
            <pattern>%d{yyyy-MM-dd HH:mm:ss.SSS} [%thread] %-5level %logger{50} - %msg%n</pattern>  
        </encoder>  
    </appender>  
    
      
    <appender name="FILE" class="ch.qos.logback.core.rolling.RollingFileAppender">  
        <file>${log.path}/app.log</file>  
        <rollingPolicy class="ch.qos.logback.core.rolling.TimeBasedRollingPolicy">  
            <fileNamePattern>${log.path}/app.%d{yyyy-MM-dd}.log</fileNamePattern>  
            <maxHistory>30</maxHistory>  
            <totalSizeCap>3GB</totalSizeCap>  
        </rollingPolicy>  
        <encoder>  
            <pattern>%d{yyyy-MM-dd HH:mm:ss.SSS} [%thread] %-5level %logger{50} - %msg%n</pattern>  
        </encoder>  
    </appender>  
    
    <root level="INFO">  
        <appender-ref ref="CONSOLE" />  
        <appender-ref ref="FILE" />  
    </root>  
</configuration>  
```

1. **注意事项**：

- 确保没有引入其他日志实现框架的依赖，避免冲突
- 如果项目中有其他依赖间接引入了其他日志框架，需要排除它们：

```xml
<dependency>  
    <groupId>some.group</groupId>  
    <artifactId>some-artifact</artifactId>  
    <version>1.0.0</version>  
    <exclusions>  
        <exclusion>  
            <groupId>commons-logging</groupId>  
            <artifactId>commons-logging</artifactId>  
        </exclusion>  
    </exclusions>  
</dependency>  
```

---

# 自用的`logback`的配置

1. 按天归档
2. 归档文件自动压缩为 .gz 格式
3. ERROR 级别日志单独存放
4. 普通日志和错误日志都按天归档并压缩

```xml
<?xml version="1.0" encoding="UTF-8"?>  
<configuration>  
      
    <property name="log.path" value="/logs" />  
      
    <property name="app.name" value="myapp" />  
    
      
    <appender name="CONSOLE" class="ch.qos.logback.core.ConsoleAppender">  
        <encoder>  
            <pattern>%d{yyyy-MM-dd HH:mm:ss.SSS} [%thread] %-5level %logger{50} - %msg%n</pattern>  
            <charset>UTF-8</charset>  
        </encoder>  
    </appender>

<appender name="INFO_FILE" class="ch.qos.logback.core.rolling.RollingFileAppender">  
        <file>${log.path}/${app.name}.log</file>  
        <rollingPolicy class="ch.qos.logback.core.rolling.TimeBasedRollingPolicy">  
              
            <fileNamePattern>${log.path}/${app.name}.%d{yyyy-MM-dd}.log.gz</fileNamePattern>  
              
            <maxHistory>30</maxHistory>  
              
            <totalSizeCap>2GB</totalSizeCap>  
        </rollingPolicy>  
        <encoder>  
            <pattern>%d{yyyy-MM-dd HH:mm:ss.SSS} [%thread] %-5level %logger{50} - %msg%n</pattern>  
            <charset>UTF-8</charset>  
        </encoder>  
          
        <filter class="ch.qos.logback.classic.filter.LevelFilter">  
            <level>ERROR</level>  
            <onMatch>DENY</onMatch>  
            <onMismatch>ACCEPT</onMismatch>  
        </filter>  
    </appender>

<appender name="ERROR_FILE" class="ch.qos.logback.core.rolling.RollingFileAppender">  
        <file>${log.path}/${app.name}-error.log</file>  
        <rollingPolicy class="ch.qos.logback.core.rolling.TimeBasedRollingPolicy">  
              
            <fileNamePattern>${log.path}/${app.name}-error.%d{yyyy-MM-dd}.log.gz</fileNamePattern>  
              
            <maxHistory>30</maxHistory>  
              
            <totalSizeCap>1GB</totalSizeCap>  
        </rollingPolicy>  
        <encoder>  
            <pattern>%d{yyyy-MM-dd HH:mm:ss.SSS} [%thread] %-5level %logger{50} - %msg%n</pattern>  
            <charset>UTF-8</charset>  
        </encoder>  
          
        <filter class="ch.qos.logback.classic.filter.LevelFilter">  
            <level>ERROR</level>  
            <onMatch>ACCEPT</onMatch>  
            <onMismatch>DENY</onMismatch>  
        </filter>  
    </appender>

<appender name="ASYNC_INFO" class="ch.qos.logback.classic.AsyncAppender">  
          
        <discardingThreshold>0</discardingThreshold>  
          
        <queueSize>512</queueSize>  
          
        <appender-ref ref="INFO_FILE"/>  
    </appender>

<logger name="org.springframework" level="WARN" />  
    <logger name="org.hibernate" level="WARN" />  
    
      
    <root level="INFO">  
        <appender-ref ref="CONSOLE" />  
        <appender-ref ref="ASYNC_INFO" />  
        <appender-ref ref="ASYNC_ERROR" />  
    </root>

</configuration>
```

1. 两数之和

作者: zorth
时间: 2024-11-25
分类: 算法
评论

给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** *`target`* 的那 **两个** 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

**示例 1：**

```
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
```

**示例 2：**

```
输入：nums = [3,2,4], target = 6
输出：[1,2]
```

**示例 3：**

```
输入：nums = [3,3], target = 6
输出：[0,1]
```

**提示：**

- `2 <= nums.length <= 104`
- `-109 <= nums[i] <= 109`
- `-109 <= target <= 109`
- **只会存在一个有效答案**

---

这里直接不考虑通过暴力枚举来实现，靠谱的方法是通过哈希表：
1. 创建哈希表`hashtable`
2. 遍历整个`nums`数组，
3. 如果哈希表中不包含`target - x`，则把当前元素放入哈希表中；
4. 如果哈希表中包含`target - x`，则得出答案为`hashtable.get(target - nums[i]), i`

```java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}
```

2024.11.25日记

作者: zorth
时间: 2024-11-25
分类: 日记
评论

5. 最长回文子串

作者: zorth
时间: 2024-11-24
分类: 算法
评论

中等题 | 动态规划 |

给你一个字符串 `s`，找到 `s` 中最长的回文子串。

**示例 1：**

```
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
```

**示例 2：**

```
输入：s = "cbbd"
输出："bb" 
```

**提示：**

- `1 <= s.length <= 1000`
- `s` 仅由数字和英文字母组成

---

这是一个有故事的题目，2019年的春天，当时面试浦发银行的时候就有这道题目，当年四道算法题，一道都没有做出来，经过那场面试之后，我才知道了有力扣这东西。

---

动态规划（Dynamic Programming，简称 DP）是一种通过将复杂问题分解为更小的子问题，并利用子问题的解来构建原问题解的算法设计方法。它通常用于解决具有**重叠子问题**和**最优子结构**性质的问题。

### 动态规划的核心思想

动态规划的核心思想是通过**记忆化**或**递推**的方式，避免重复计算子问题，从而提高算法效率。它的基本步骤包括：

1. **定义状态（State）**：用一个数组或表格来表示问题的解。
2. **状态转移方程（State Transition Equation）**：找到状态之间的递推关系。
3. **初始化（Initialization）**：确定初始状态的值。
4. **计算顺序（Order of Computation）**：通常是从小问题逐步递推到大问题。
5. **返回结果（Result Extraction）**：从状态表中提取最终解。

### 动态规划的两种实现方式

1. **自顶向下（Top-Down）**：也称为记忆化搜索（Memoization）。通过递归的方式解决问题，同时将已经计算过的子问题结果存储起来，避免重复计算。
2. **自底向上（Bottom-Up）**：也称为递推（Tabulation）。从最小的子问题开始，逐步计算出更大的子问题的解，直到得到最终解。

### 动态规划的两个重要性质

1. **重叠子问题（Overlapping Subproblems）**  
   问题可以分解为多个子问题，且这些子问题会重复出现。例如，斐波那契数列的递归计算中，`F(5)` 会调用 `F(4)` 和 `F(3)`，而 `F(4)` 又会调用 `F(3)` 和 `F(2)`，导致重复计算。

2. **最优子结构（Optimal Substructure）**  
   问题的最优解可以通过子问题的最优解构造出来。例如，最短路径问题中，从起点到终点的最短路径可以通过中间节点的最短路径组合而成。

### 动态规划的常见问题类型

1. **线性问题**  
   - 斐波那契数列：`F(n) = F(n-1) + F(n-2)`
   - 最长递增子序列（LIS）
   - 最大子数组和（Kadane's Algorithm）

2. **区间问题**  
   - 戳气球问题（Burst Balloons）
   - 最长回文子序列

3. **背包问题**  
   - 0-1 背包问题
   - 完全背包问题

4. **序列问题**  
   - 编辑距离（Edit Distance）
   - 最长公共子序列（LCS）

5. **路径问题**  
   - 矩阵路径问题（如最小路径和）
   - 图中的最短路径问题（如 Floyd-Warshall 算法）

6. **划分问题**  
   - 分割等和子集
   - 石子游戏问题

### 动态规划的经典例子

#### 1. 斐波那契数列

**问题描述**：计算第 `n` 个斐波那契数。  
**状态定义**：`dp[i]` 表示第 `i` 个斐波那契数。  
**状态转移方程**：`dp[i] = dp[i-1] + dp[i-2]`  
**初始化**：`dp[0] = 0, dp[1] = 1`  
**代码实现**：

```python
def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
```

#### 2. 0-1 背包问题

**问题描述**：给定 `n` 个物品，每个物品有重量 `w[i]` 和价值 `v[i]`，以及一个容量为 `W` 的背包，求如何选择物品使得总价值最大。  
**状态定义**：`dp[i][j]` 表示前 `i` 个物品在容量为 `j` 的情况下的最大价值。  
**状态转移方程**：

- 如果不选第 `i` 个物品：`dp[i][j] = dp[i-1][j]`
- 如果选第 `i` 个物品：`dp[i][j] = dp[i-1][j-w[i]] + v[i]`
- 综合：`dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])`  
  **初始化**：`dp[0][j] = 0`（没有物品时价值为 0）  
  **代码实现**：

```python
def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            if weights[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][W]
```

### 动态规划的优化

1. **空间优化**：  
   - 如果状态转移只依赖于前一行或前几个状态，可以将二维数组压缩为一维数组。例如，0-1 背包问题可以优化为一维数组。

2. **状态压缩**：  
   - 在某些问题中，可以通过位运算等方式压缩状态空间。

### 动态规划的优缺点

**优点**：

- 通过记忆化或递推避免了重复计算，显著提高效率。
- 能够解决许多复杂的优化问题。

**缺点**：

- 状态空间可能很大，导致时间和空间复杂度较高。
- 需要仔细设计状态和转移方程，问题建模较为复杂。

---

最长回文子序列（Longest Palindromic Subsequence, LPS）的常见动态规划解法通常是**自底向上的**，即通过递推的方式逐步计算出子问题的解，最终得到原问题的解。

### 问题描述

给定一个字符串 `s`，求其最长回文子序列的长度。回文子序列是指一个序列可以正着读和反着读都相同，但不要求是连续的。

---

### 自底向上的动态规划解法

#### 1. **状态定义**

设 `dp[i][j]` 表示字符串 `s` 从第 `i` 个字符到第 `j` 个字符之间的最长回文子序列的长度。

#### 2. **状态转移方程**

- 如果 `s[i] == s[j]`，那么 `dp[i][j] = dp[i+1][j-1] + 2`，因为首尾字符相等，可以将它们加入回文子序列。
- 如果 `s[i] != s[j]`，那么 `dp[i][j] = max(dp[i+1][j], dp[i][j-1])`，即最长回文子序列要么不包含 `s[i]`，要么不包含 `s[j]`。

#### 3. **初始化**

- 当 `i == j` 时，`dp[i][i] = 1`，因为单个字符本身就是一个长度为 1 的回文子序列。
- 当 `i > j` 时，`dp[i][j] = 0`，因为无效区间。

#### 4. **计算顺序**

由于 `dp[i][j]` 的值依赖于 `dp[i+1][j-1]`、`dp[i+1][j]` 和 `dp[i][j-1]`，所以我们需要从区间长度较短的子问题开始计算，逐步扩展到整个字符串。

#### 5. **最终结果**

`dp[0][n-1]` 即为整个字符串的最长回文子序列长度，其中 `n` 是字符串的长度。

---

### 代码实现

以下是自底向上的动态规划实现：

```python
def longestPalindromeSubseq(s):
    n = len(s)
    # 初始化 dp 数组
    dp = [[0] * n for _ in range(n)]
    
    # 单个字符的回文子序列长度为 1
    for i in range(n):
        dp[i][i] = 1
    
    # 从长度为 2 的子问题开始计算，逐步扩展到整个字符串
    for length in range(2, n + 1):  # 子串长度从 2 到 n
        for i in range(n - length + 1):  # 起始位置
            j = i + length - 1  # 终止位置
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    # 返回整个字符串的最长回文子序列长度
    return dp[0][n - 1]
```

---

### 示例

```python
s = "bbbab"
print(longestPalindromeSubseq(s))  # 输出: 4
```

**解释**：最长回文子序列是 `"bbbb"`，长度为 4。

---

### 时间和空间复杂度

- **时间复杂度**：`O(n^2)`，因为我们需要填充一个 `n x n` 的二维数组，每个状态的计算需要常数时间。
- **空间复杂度**：`O(n^2)`，用于存储 `dp` 数组。

#### 空间优化

如果只需要返回最长回文子序列的长度，可以将二维数组压缩为一维数组，因为 `dp[i][j]` 只依赖于当前行和上一行的状态。

---

```java
public class Solution {

public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
```

这里的 `L` 表示**子串的长度**，是动态规划中递推的一个关键变量。通过枚举子串的长度 `L`，我们可以从短的子串开始计算，逐步扩展到更长的子串，最终覆盖整个字符串。这种写法是动态规划中常见的**自底向上递推**方式。

---

### 为什么要用 `L` 表示子串长度？

动态规划的核心是通过已知的子问题解来推导更大的问题解。在这个问题中，`dp[i][j]` 表示从字符串第 `i` 个字符到第 `j` 个字符之间的最长回文子序列长度。为了计算 `dp[i][j]`，我们需要依赖更短的子串的结果，比如 `dp[i+1][j-1]`、`dp[i+1][j]` 和 `dp[i][j-1]`。

因此，递推的顺序必须是从短的子串开始，逐步扩展到更长的子串。`L` 就是用来控制子串的长度的变量。

---

### 代码逻辑解析

```cpp
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
    // 枚举左边界，左边界的上限设置可以宽松一些
    for (int i = 0; i < len; i++) {
        // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
        int j = L + i - 1;
        // 如果右边界越界，就可以退出当前循环
        if (j >= len) {
            break;
        }
        // 状态转移逻辑
        if (s[i] == s[j]) {
            dp[i][j] = dp[i + 1][j - 1] + 2;
        } else {
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
}
```

#### 1. **外层循环：枚举子串长度**

```cpp
for (int L = 2; L <= len; L++) {
```

- `L` 表示子串的长度，从 2 开始，因为长度为 1 的子串已经初始化（`dp[i][i] = 1`）。
- 通过从小到大的子串长度递推，保证在计算 `dp[i][j]` 时，所依赖的状态（如 `dp[i+1][j-1]`）已经被计算过。

---

#### 2. **内层循环：枚举左边界**

```cpp
for (int i = 0; i < len; i++) {
```

- `i` 是子串的左边界。
- 枚举所有可能的左边界 `i`，从 0 开始。

---

#### 3. **确定右边界**

```cpp
int j = L + i - 1;
```

- 通过子串长度 `L` 和左边界 `i`，可以确定右边界 `j`：
  \[
  j - i + 1 = L \implies j = L + i - 1
  \]
- 例如：
  - 如果子串长度 `L = 3`，左边界 `i = 2`，那么右边界 `j = 3 + 2 - 1 = 4`。

---

#### 4. **右边界越界检查**

```cpp
if (j >= len) {
    break;
}
```

- 如果右边界 `j` 超出了字符串的长度 `len`，说明当前左边界 `i` 和子串长度 `L` 不合法，直接退出循环。

---

#### 5. **状态转移**

```cpp
if (s[i] == s[j]) {
    dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
```

- 如果 `s[i] == s[j]`，说明首尾字符可以构成回文，最长回文子序列长度等于去掉首尾后的子串的最长回文子序列长度 `dp[i+1][j-1]` 加上 2。
- 如果 `s[i] != s[j]`，说明首尾字符不能同时出现在回文子序列中，取决于去掉左边界或右边界后的子串的最长回文子序列长度，即 `max(dp[i+1][j], dp[i][j-1])`。

---

### 为什么要用 `L` 控制子串长度？

1. **保证递推顺序正确**  
   动态规划的递推顺序必须从小问题到大问题。如果直接枚举 `i` 和 `j`，可能会导致依赖的状态（如 `dp[i+1][j-1]`）还未被计算，无法完成递推。而通过 `L` 控制子串长度，可以确保在计算长度为 `L` 的子串时，长度为 `L-1` 的子串已经被计算过。

2. **逻辑清晰**  
   使用 `L` 表示子串长度，逻辑上更清晰：先计算长度为 2 的子串，再计算长度为 3 的子串，依次类推，直到整个字符串。

3. **避免重复计算**  
   通过从短子串到长子串的顺序递推，避免了重复计算子问题的解。

---

### 改写为更清晰的版本

如果觉得原代码不够直观，可以稍微调整注释和变量名，使其更易理解：

```cpp
// 动态规划求解最长回文子序列
for (int length = 2; length <= len; length++) {  // 枚举子串长度
    for (int left = 0; left < len; left++) {    // 枚举左边界
        int right = left + length - 1;          // 计算右边界
        if (right >= len) {                     // 如果右边界越界，跳出循环
            break;
        }
        if (s[left] == s[right]) {              // 如果首尾字符相等
            dp[left][right] = dp[left + 1][right - 1] + 2;
        } else {                                // 如果首尾字符不相等
            dp[left][right] = max(dp[left + 1][right], dp[left][right - 1]);
        }
    }
}
```

---

### 总结

- `L` 表示子串的长度，控制递推的顺序，从短子串到长子串逐步计算。
- 这种写法是动态规划中常见的自底向上递推方式，保证了依赖的状态已经被计算。
- 通过 `L` 和 `i` 确定右边界 `j`，可以避免直接枚举所有可能的 `(i, j)`，使得逻辑更加清晰。

2024.11.24日记

作者: zorth
时间: 2024-11-24
分类: 日记
评论