LeetCode题解——随机刷题(三)

亦凉 2022-12-04 01:18 184阅读 0赞

### 文章目录 ###

*   *  48. 旋转图像
     *   *  解法
     *  49. 字母异位词分组
     *   *  解法
     *  56. 合并区间
     *   *  排序
     *  85. 最大矩形
     *   *  单调栈
     *  96. 不同的二叉搜索树
     *   *  解法
         *   *  推荐阅读

## 48. 旋转图像 ##

[48. 旋转图像][48.]

给定一个 n × n 的二维矩阵表示一个图像。
    
    将图像顺时针旋转 90 度。
    
    说明：
    
    你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
    
    示例 1:
    
    给定 matrix = 
    [
      [1,2,3],
      [4,5,6],
      [7,8,9]
    ],
    
    原地旋转输入矩阵，使其变为:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]
    示例 2:
    
    给定 matrix =
    [
      [ 5, 1, 9,11],
      [ 2, 4, 8,10],
      [13, 3, 6, 7],
      [15,14,12,16]
    ], 
    
    原地旋转输入矩阵，使其变为:
    [
      [15,13, 2, 5],
      [14, 3, 4, 1],
      [12, 6, 8, 9],
      [16, 7,10,11]
    ]

### 解法 ###

class Solution {
        
        public void rotate(int[][] matrix) {
        
            int n = matrix.length;
            // 转置矩阵
            for (int i = 0; i < n; i++) {
        
                for (int j = i; j < n; j++) {
        
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = tmp;
                }
            }
            // 翻转每一行
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n / 2; j++) {
        
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[i][n - j - 1];
                    matrix[i][n - j - 1] = tmp;
                }
            }
        }
    }

## 49. 字母异位词分组 ##

[49. 字母异位词分组][49.]

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: \[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”\]  
输出:  
\[  
\[“ate”,“eat”,“tea”\],  
\[“nat”,“tan”\],  
\[“bat”\]  
\]  
说明：

所有输入均为小写字母。  
不考虑答案输出的顺序。

### 解法 ###

class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            if (strs.length == 0) {
        
                return new ArrayList();
            }
            Map<String, List> ans = new HashMap<String, List>();
            int[] count = new int[26];
            for (String s : strs) {
        
                Arrays.fill(count, 0);
                for (char c : s.toCharArray()) {
        
                    count[c - 'a']++;
                }
                StringBuilder sb = new StringBuilder("");
                for (int i = 0; i < 26; i++) {
        
                    sb.append('#');
                    sb.append(count[i]);
                }
                String key = sb.toString();
                if (!ans.containsKey(key)) {
        
                    ans.put(key, new ArrayList());
                }
                ans.get(key).add(s);
            }
            return new ArrayList(ans.values());
        }
    }

## 56. 合并区间 ##

[56. 合并区间][56.]

给出一个区间的集合，请合并所有重叠的区间。
    
     
    
    示例 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] 可被视为重叠区间。
    注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
    
     
    
    提示：
    
    intervals[i][0] <= intervals[i]

### 排序 ###

![format_png][]

class Solution {
        
        public int[][] merge(int[][] intervals) {
        
            List<int[]> res = new ArrayList<>();
            if (intervals.length == 0 || intervals == null) {
        
                return res.toArray(new int[0][]);
            }
            Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
            int i = 0;
            int len = intervals.length;
            while (i < len) {
        
                int left = intervals[i][0];
                int right = intervals[i][1];
                // 找出重复的
                while (i < len - 1 && intervals[i + 1][0] <= right) {
        
                    i++;
                    right = Math.max(right, intervals[i][1]);
                }
                res.add(new int[]{
        left, right});
                i++;
            }
            return res.toArray(new int[0][]);
        }
    }

## 85. 最大矩形 ##

[85. 最大矩形][85.]

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
    
    示例:
    
    输入:
    [
      ["1","0","1","0","0"],
      ["1","0","1","1","1"],
      ["1","1","1","1","1"],
      ["1","0","0","1","0"]
    ]
    输出: 6

### 单调栈 ###

详解见[leetcode][]，可以对比[leetcode 84][]

class Solution {
        
        public int maximalRectangle(char[][] matrix) {
        
            if (matrix.length == 0) {
        
                return 0;
            }
            int ans = 0;
            int rowLen = matrix.length;
            int columnLen = matrix[0].length;
            int[] dp = new int[columnLen];
            for (int i = 0; i < rowLen; i++) {
        
                for (int j = 0; j < columnLen; j++) {
        
                    dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
                }
                ans = Math.max(ans, maxArea(dp));
            }
            return ans;
        }
        
        private int maxArea(int[] heights) {
        
            Deque<Integer> stack = new LinkedList<>();
            stack.offerFirst(-1);
            int maxarea = 0;
            for (int i = 0; i < heights.length; i++) {
        
                while (stack.peekFirst() != -1 && heights[stack.peekFirst()] >= heights[i]) {
        
                    maxarea = Math.max(maxarea, heights[stack.pollFirst()] * (i - stack.peekFirst() - 1));
                }
                stack.offerFirst(i);
            }
            while (stack.peekFirst() != -1) {
        
                maxarea = Math.max(maxarea, heights[stack.pollFirst()] * (heights.length - stack.peekFirst() - 1));
            }
            return maxarea;
        }
    }

## 96. 不同的二叉搜索树 ##

[96. 不同的二叉搜索树][96.]

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
    
    示例:
    
    输入: 3
    输出: 5
    解释:
    给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

### 解法 ###

详解见[leetcode][leetcode 1]

class Solution {
        
        public int numTrees(int n) {
        
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
        
                for (int j = 1; j <= i; j++) {
        
                    dp[i] += dp[j - 1] * dp[i - j];
                }
            }
            return dp[n];
        }
    }

--------------------

#### 推荐阅读 ####

*  [剑指offer精品题解][offer]
 *  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

**欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。**  
![format_png 1][]

[48.]: https://leetcode-cn.com/problems/rotate-image/
[49.]: https://leetcode-cn.com/problems/group-anagrams/
[56.]: https://leetcode-cn.com/problems/merge-intervals/
[format_png]: /images/20221123/ae1560a229da484ba22a1be40ac0ec38.png
[85.]: https://leetcode-cn.com/problems/maximal-rectangle/
[leetcode]: https://leetcode-cn.com/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode/
[leetcode 84]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
[96.]: https://leetcode-cn.com/problems/unique-binary-search-trees/
[leetcode 1]: https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
[offer]: https://mp.weixin.qq.com/s/R5VKVxOYBr6CcGTIrlLQpw
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png 1]: /images/20221123/2789e844f4e94658b225c705ed0451dc.png