合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104

• intervals[i].length == 2

• 0 <= starti <= endi <= 104

解题思路

排序+栈数据结构

这段代码实现了合并重叠区间的功能，主要思路是：

1. 先排序：按区间起始点升序排列

2. 再合并：使用栈结构处理重叠区间

步骤解析

1. 排序阶段：将所有区间按起始点从小到大排序

2. 重叠判断条件（四种情况）：

(intervals[i][0] <= temp[1] && intervals[i][0] >= temp[0]) || // 情况1：i的起点在temp区间内
(intervals[i][1] <= temp[1] && intervals[i][1] >= temp[0]) || // 情况2：i的终点在temp区间内
(intervals[i][1] >= temp[1] && intervals[i][0] <= temp[0]) || // 情况3：i完全包含temp
(intervals[i][1] <= temp[1] && intervals[i][0] >= temp[0])    // 情况4：temp完全包含i

3. 结果收集处理（利用栈结构）

完整代码:

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        ArrayList<int[]> result = new ArrayList<>();
        Stack<int[]> stack = new Stack<>();
        int length = intervals.length;
        for (int i = 0; i < length; i++) {
            if (stack.isEmpty()) {
                stack.push(intervals[i]);
            } else {
                int[] temp = stack.peek();
                if ((intervals[i][0] <= temp[1] && intervals[i][0] >= temp[0])
                        || (intervals[i][1] <= temp[1] && intervals[i][1] >= temp[0])
                        || (intervals[i][1] >= temp[1] && intervals[i][0] <= temp[0])
                        || (intervals[i][1] <= temp[1] && intervals[i][0] >= temp[0])) {
                    temp[0] = Math.min(temp[0], intervals[i][0]);
                    temp[1] = Math.max(temp[1], intervals[i][1]);
                    stack.pop();
                    stack.push(temp);
                } else {
                    stack.push(intervals[i]);
                }
            }
        }
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result.toArray(new int[result.size()][2]);
    }
}

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000

• text1 和 text2 仅由小写英文字符组成。

解题思路

动态规划

基本思想

通过构建二维状态表，将问题分解为更小的子问题，利用已解决的子问题结果来推导更大问题的解。

分步逻辑

1. 状态定义：

   • dp[i][j] = text1前i个字符和text2前j个字符的最长公共子序列

2. 状态转移：

   • 当前字符匹配：dp[i][j] = dp[i-1][j-1] + 1

   • 当前字符不匹配：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 求解顺序：

   • 双重循环从左到右、从上到下填表

4. 示例演算（text1="abc", text2="ac"）

   	''	a	c
   ''	0	0	0
   a	0	1	1
   b	0	1	1
   c	0	1	2	→ 最终结果2

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();

        int[][] dp = new int[char1.length+1][char2.length+1];
        for (int i = 1; i < char1.length+1; i++) {
            for (int j = 1; j < char2.length+1; j++) {
                if(char1[i-1] == char2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);   
                }
            }
        }
        return dp[char1.length][char2.length];
    }
}