本文共 2263 字，大约阅读时间需要 7 分钟。

问题探讨：leetcode732与剑指offer38的解法

最近，我一直在尝试解决leetcode中的两个问题：leetcode732和剑指offer38。虽然这两个问题看起来有点不同，但它们都让我对算法设计和优化有了更深的理解。

问题一：leetcode732 - 休闲日程安排

这个问题有点难，但我觉得我已经找到了一种有效的解决方法。问题的大意是说，给定一系列活动，每个活动有一个开始时间和结束时间，我们需要找出在同一时间段内最多有多少个活动是重叠的。这个问题其实可以转化为寻找最大值的问题。

我想到可以用一个Treemap来记录活动的开始和结束时间。具体来说，每当有一个活动开始时，我们在Treemap中记录一个+1的值；当活动结束时，记录一个-1的值。通过遍历Treemap的键值对，我们可以计算出在任一时刻的活动数量。这个方法既简洁又高效，完全避免了传统的扫描线方法的复杂性。

问题二：剑指offer38 - 生成所有排列

剑指offer38的问题是要生成一个字符串的所有排列。这个问题看起来简单，但要生成所有可能的排列却需要仔细思考。我选择了深度优先搜索（DFS）的方法来解决这个问题。

我的思路是使用一个栈来记录已经访问过的索引位置。然后，通过递归的方式遍历所有可能的索引位置。为了避免重复访问同一个索引，我在栈中记录访问过的索引。每次选择一个未被访问的索引，将其推入栈中，然后继续递归。当栈的大小等于字符串的长度时，说明已经生成了一种排列，可以将当前的排列字符串添加到结果集中。

这种方法的时间复杂度是O(n!)，虽然对于较大的n来说效率不高，但对于n较小的情况（如n<=10），这种方法是完全可行的。

代码解读：MyCalendarThree类

import java.util.Map;import java.util.TreeMap;import java.util.Set;import java.util.Stack;class MyCalendarThree {    TreeMap
   
     map = new TreeMap<>();    public int book(int start, int end) {        map.put(start, map.getOrDefault(start, 0) + 1);        map.put(end, map.getOrDefault(end, 0) - 1);        int max = 0, temp = 0;        for (Integer i : map.values()) {            temp += i;            if (temp > max) {                max = temp;            }        }        return max;    }}
   

这个类使用Treemap来记录活动的时间范围。每次活动开始时，Treemap中对应的值加1，活动结束时对应的值减1。通过遍历Treemap中的值，可以计算出在任一时刻的活动数量，从而找到最大重叠值。

代码解读：Solution类

class Solution {    Set
   
     set = new HashSet<>();    Stack
    
      stack = new Stack<>();    int n;    public String[] permutation(String s) {        dfs(s);        return set.toArray(new String[0]);    }    private void dfs(String s) {        if (stack.size() == s.length()) {            set.add(idx2Str(stack, s));        } else {            for (int i = 0; i < s.length(); i++) {                if (!stack.contains(i)) {                    stack.push(i);                    dfs(s);                    stack.pop();                }            }        }    }    private String idx2Str(Stack
     
       stack, String s) {        StringBuilder sb = new StringBuilder();        for (Integer idx : stack) {            sb.append(s.charAt(idx));        }        return sb.toString();    }}
     
    
   

这个类通过深度优先搜索生成所有可能的排列。使用栈来记录索引位置，避免重复访问同一个位置。每次递归时，选择一个未被访问的索引，将其推入栈中，然后继续递归。当栈的大小等于字符串的长度时，生成一个排列字符串并添加到结果集中。