算法题解（Leetcode 48、49、53、55、56）

￡神魔★判官ぃ 2022-09-12 14:43 9阅读 0赞

### 文章目录 ###

*   *  48. 旋转图像 - 中等 - 9/26
     *  49. 字母异位词分组 - 中等 - 9/27
     *  53. 最大子序和 - 简单 - 9/28
     *  55. 跳跃游戏 - 中等 - 9/29
     *  56. 合并区间 - 中等 - 9/30

## 48. 旋转图像 - 中等 - 9/26 ##

[48. 旋转图像 - 中等 - 9/26][48. _ - _ - 9_26]

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 2]

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

解析：找规律，先按对角线交换，再按对称轴交换即可。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 3]

class Solution { 
        public void rotate(int[][] matrix) { 
            int l_len = matrix.length;
    
            //对角线交换
            for(int i=0; i<l_len; i++){ 
                for(int j=0; j<=i; j++){ 
                    if(i==j) continue; //对角线值，跳过
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
    
            //对称轴交换
            for(int i=0,j=l_len-1; i<l_len/2; i++,j--){ 
                for(int k=0; k<l_len; k++){ 
                    int temp = matrix[k][i];
                    matrix[k][i] = matrix[k][j];
                    matrix[k][j] = temp;
                }
            }  
        
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
时间复杂度：O（n²）。

空间复杂度：O（1）。

也可以先以横向的中轴线为轴，对称的行进行交换，然后再以对角线交换。

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

## 49. 字母异位词分组 - 中等 - 9/27 ##

[49. 字母异位词分组 - 中等 ][49. _ - _]

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
![在这里插入图片描述][4d5f1fa929124c89928d4fd45492d990.png]

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

解析：**排序**

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_12_color_FFFFFF_t_70_g_se_x_16]

形式一：

class Solution { 
        public List<List<String>> groupAnagrams(String[] strs) { 
            //创建HashMap存储
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            //遍历
            for(String str: strs){ 
                //将字符串转为字符数组
                char[] array = str.toCharArray();
                //排序
                Arrays.sort(array);
                //存为键
                String key = new String(array);
                //当Map集合中存在这个key时，就使用这个key值，如果没有就使用默认值defaultValue（第二个参数）
                List<String> list = map.getOrDefault(key, new ArrayList<String>());
                //归类 同类的添加在一起
                list.add(str);
                //加入map中
                map.put(key, list);
            }
            //返回map中所有的values
            return new ArrayList<List<String>>(map.values());
        }
    }

形式二：

public List<List<String>> groupAnagrams(String[] strs) { 
        HashMap<String, List<String>> hash = new HashMap<>();
        for (int i = 0; i < strs.length; i++) { 
            char[] s_arr = strs[i].toCharArray();
            //排序
            Arrays.sort(s_arr);
            //映射到 key
            String key = String.valueOf(s_arr); 
            //添加到对应的类中
            if (hash.containsKey(key)) { 
                hash.get(key).add(strs[i]);
            } else { 
                List<String> temp = new ArrayList<String>();
                temp.add(strs[i]);
                hash.put(key, temp);
            }
    
        }
        return new ArrayList<List<String>>(hash.values()); 
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
时间复杂度：O(nklogk)，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。需要遍历n个字符串，对于每个字符串，需要O（klogk）的时间进行排序以及O（1）的时间更新哈希表，因此总时间复杂度是O（nklogk）。

空间复杂度：O（nk），其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。需要用哈希表存储全部字符串。

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

## 53. 最大子序和 - 简单 - 9/28 ##

[53. 最大子序和 - 简单][53. _ -]

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 8]

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

解析： 动态规划

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
![在这里插入图片描述][ee21f04d164c4a9da6fe5224d5c68ce1.png]

class Solution { 
        public int maxSubArray(int[] nums) { 
            int n = nums.length;
            int dp = nums[0];
            int max = nums[0];
            for(int i=1; i < n; i++){ 
                //取 当前累加后一个数 与 后一个数 的较大值
                dp= Math.max(dp + nums[i],nums[i]);
                //更新最大值
                max = Math.max(max,dp);
            }
            return max;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
时间复杂度：O（n），其中n为nums数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度：O（1）。我们只需要常数空间存放若干变量。

## 55. 跳跃游戏 - 中等 - 9/29 ##

[55. 跳跃游戏 - 中等][55. _ -]

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 11]

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

解析：

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

局部最优推出全局最优，找不出反例，试试贪心！

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 12]

i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。

而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。

如果cover大于等于了终点下标，直接return true就可以了。

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

class Solution { 
        public boolean canJump(int[] nums) { 
            if(nums.length == 1) return true;
            //覆盖范围
            int coverRange = nums[0];
            //在覆盖范围内更新最大的覆盖范围
            for(int i=0; i<=coverRange; i++){ 
                coverRange = Math.max(coverRange, i+nums[i]); //更新最大的覆盖范围
                if(coverRange >= nums.length - 1){  //如果覆盖到最后一个，就返回true
                    return true;
                }
            }
            //没有覆盖到，就返回false
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 13]

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

## 56. 合并区间 - 中等 - 9/30 ##

[56. 合并区间 - 中等][56. _ -]

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 14]

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

解析：

用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

class Solution { 
        public int[][] merge(int[][] intervals) { 
            List<int[]> res = new LinkedList<>(); //存储结果
            //按照数组第一个元素排序
            Arrays.sort(intervals, (o1,o2) -> Integer.compare(o1[0],o2[0]));
            //定义开始
            int start = intervals[0][0];
            //遍历
            for(int i=0; i<intervals.length-1; i++){ 
                //如果当前数组的尾元素 小于 后一个数组的头元素，则直接把当前数组添加进入
                if(intervals[i][1] < intervals[i+1][0]){ 
                    res.add(new int[]{ start,intervals[i][1]});
                    start = intervals[i+1][0]; //更新开始位置为 后一个数组头元素
                } else { 
                    //更新后一个数组的尾元素
                    intervals[i+1][1] = Math.max(intervals[i+1][1],intervals[i][1]);
                }
            }
            res.add(new int[]{ start,intervals[intervals.length-1][1]});
            return res.toArray(new int[res.size()][]);
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 15]

[48. _ - _ - 9_26]: https://leetcode-cn.com/problems/rotate-image/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/36212e0d5af2428cbc116a7bfa81079c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/9ece72b6a2f3471281ae436ebde616df.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/21f967df53b04480a7cbb24cfdb6b8f6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/5d2158042cf04d7497b60611527def37.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/45e126ad67da4e5d880cde5593b85879.png
[49. _ - _]: https://leetcode-cn.com/problems/group-anagrams/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/b02e234f4a144ef8bd11b8484d9afd17.png
[4d5f1fa929124c89928d4fd45492d990.png]: /images/20220828/cbde7a8f94eb4fc0a48ca9f13c149a1a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/77babffaae8d49358760166743d8a8f5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/980b0672862944658a5afdb38cfaed5d.png
[53. _ -]: https://leetcode-cn.com/problems/maximum-subarray/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/cd1194c249eb4379b96787b7716aa4ac.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/9ae273dc3adc417cb5c635d51b4e035e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/d6c7cd75e16d40baa7720299171c41d0.png
[ee21f04d164c4a9da6fe5224d5c68ce1.png]: /images/20220828/a3c65152ae2b400486378bc29c406386.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/356c9645a30b4fb98b1ba91acf9afc19.png
[55. _ -]: https://leetcode-cn.com/problems/jump-game/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/6997250ea8394341a80a7cae0759b5b5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/86432a0a229642918cd8b17136827e97.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/528e7ab6980b46909fe6dd232693a738.png
[56. _ -]: https://leetcode-cn.com/problems/merge-intervals/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/b3cf24f2e59943ea86cd8cf33536583b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/c662d5525bf8441aaf7343cdec5f9427.png