刷题记录5---旋转图像+两数之和+字母异位词分组+跳跃游戏+合并区间

前言

所有题目均来自力扣题库中的hot 100，之所以要记录在这里，只是方便后续复习

48.旋转图像

题目：
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 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]]
解题思路：
【找规律】先上下翻转，再对角线翻转，即可达到顺时针旋转90度效果；翻转即交换两个位置的值
代码（python）：

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # 上下翻转 
        for i in range(0, n / 2):
            for j in range(0, n):
                # 即i j 位置 和 n-i-1 j位置交换值
                matrix[i][j], matrix[n - i -1][j] =  matrix[n - i -1][j], matrix[i][j]
        # 对角线翻转 对角线位置是从左上到右下
        for i in range(0, n):
            for j in range(0, i):
                # 即i j 位置和 j i位置交换值
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        return matrix

代码（java）：

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int temp = 0;

        for(int i = 0; i < n/2; i++){
            for(int j = 0; j < n; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i]= temp;
            }
        }

    }
}

知识点：

• python中交换两个值可以用 val1, val2 = val2, val1

原题链接：旋转图像

1.两数之和

题目：
给定一个整数数组 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]
解题思路:
【hash表】遍历给定数组，假设选中每个位置为第一个数后，再遍历数组寻找第二个数的位置即可，但是这种暴力方法的时间复杂度为N方。我们可以优化寻找第二个数的过程，借用hash表结构，也就是python中的dict或java中的HashMap。因为hash结构寻找某一个数的时间复杂度是1，这样总体的时间复杂度即为N。优化后的过程：定义dict，键为nums的值，值为nums的索引；遍历给定数组，对于每个位置值num判断一下target - num是否在dict的键中，如果在则返回该位置的索引和target - num在dict中的值即可 。如果不在则将该位置的值和索引放入dict即可
代码（python）：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_nums = dict()
        for i, num in enumerate(nums):
            if hash_nums.has_key(target - num):
                return [i, hash_nums[target - num]]
            hash_nums[num] = i 

代码（java）：

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

知识点：

• 要在数组中快速寻找某个数，优先考虑hash结构
• python遍历字典的写法，可以用枚举：for i, num in enumerate(dict)
• 对于字典是否包含某个键，python有has_key()方法，java有containsKey()方法

原题连接：两数之和

49.字母异位词分组

题目：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
解题思路：
【Hash表】将字符串分组就要找到其共同点：由相同的字符串组成，只不过顺序不同，那排序后的字符串就是相同的，所以我们可以用排序后的字符串的当作键，字符串组成的列表当作值，定义一个Hash结构，并依次将字符串添加进行就达到了分组效果
代码（python）：

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        results = collections.defaultdict(list)

        for s in strs:
            key = "".join(sorted(s))
            results[key].append(s)
        
        return list(results.values())

代码（java）：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 定义hashmap结构存储结果
        HashMap<String, ArrayList<String>> result = new HashMap<>();
        // 对于每一个字符串
        for (int i = 0; i < strs.length; i ++){
            // 将字符串转为 char数组，用系统方法进行排序后，重新转为字符串
            char[] array = strs[i].toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            // 根据排序后的字符串当作hashmap 的key，将该字符串添加到hashmap中
            ArrayList<String> list = result.getOrDefault(key, new ArrayList<String>());
            list.add(strs[i]);
            result.put(key, list);
        }
        // 最后将hashmap转化链表返回
        return new ArrayList<>(result.values());
    }
}

知识点：

• python中若想定义一个字典，且字典里默认的值都是默认列表，可以用collections.defaultdict(list)写法
• python中对字符串（可迭代对象）排序可以用sorted(str)，其返回值是新的列表；而list.sort()方法是对列表原地排序，无返回值
• python中将列表拼接成字符串可以用"".join(list)写法
• java中对字符串排序可以先用str.toCharArray()方法将字符串转为char数组，然后用Arrays.sort(array)对数组进行原地排序，最后用new String(array)字符串的构造方法重新转成新字符串
• java中hashmap转为ArrayList，可以用 new ArrayList(hashmap.values())；其中hashmap.values()返回map中所有value组成的集合

原题链接：字母异位词分组

55.跳跃游戏

题目：
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
解题思路:
【贪心算法】我们可以计算每个位置能跳的最远距离，如果最远距离大于等于了末尾位置，那就可以到达；所以我们要遍历整个数组，根据每个值能跳的距离和当前位置去更新最远距离；需要注意的是在获取当前位置的最远距离之前要判断一下当前位置是否在当前最远距离内，若不在，则说明到达当前位置，便不能选用当前位置
代码（python）：

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # 定义能跳的最远距离
        max_dis = 0
        n = len(nums)
        # 对于每个位置
        for i in range(0, n):
            # 如果当前位置在能跳的最远距离内  很重要的判断
            if i <= max_dis:
                # 根据当前位置能跳的值更新最远的距离
                max_dis = max(i + nums[i], max_dis)
                # 如果最远距离包含了数组结尾 直接返回True
                if max_dis >= len(nums) - 1:
                    return True
        # 若遍历整个数组最远距离都没达到末尾，则返回False
        return False

代码（java）：

public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

知识点：

• 无

原题连接：跳跃游戏

56.合并区间

题目：
以数组 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] 可被视为重叠区间。
解题思路:
【排序】我们可以将二维数组排序，而排序的方式是按每个数组的第一个元素从小到达排序，这样得到的新二维数组就不会存在后面的数组的头还在前面的头之前了；此时我们判断两个数组是否可以合并，就看第二个数组的头是否小于等于第一个数组的尾，若是则可合并，即更新前一个数组的尾就好了，若不是则将二个数组直接添加到结果集合中
代码（python）：

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """

        intervals.sort(key=lambda x : x[0])

        result = []
        last = 0

        for interval in intervals:
            if len(result) == 0:
                result.append(interval)
            else:
                last = result[-1][-1]
                if interval[0] > last:
                    result.append(interval)
                else:
                    result[-1][-1] = max(last, interval[-1])
        
        return result

代码（java）：

class Solution {
    public int[][] merge(int[][] intervals) {
        // 将二维数组排序，按照每个数组的第一个元素从小到大排序
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] interval1, int[] interval2){
                return interval1[0] - interval2[0];
            }
        });
        // 定义列表存储合并后的数组
        ArrayList<int[]> result = new ArrayList<>();
        // 遍历得到的新二维数组
        for (int i = 0; i < intervals.length; i ++){
            int len = result.size();
            // 如果列表中还没有数组 或者 当前数组的头 大于 列表中前一个数组的尾 ，则说明这两个数组不相交，将当前数组赋值添加到列表中
            if (len == 0  || result.get(len - 1)[1] < intervals[i][0]){
                result.add(new int[]{intervals[i][0], intervals[i][1]});
            // 若当前数组的头小于等于列表中前一个数组的尾，说明这两个数组相交，则更新前一个数组的尾即可，更新为两个数组的尾的较大值
            }else{
                result.get(len - 1)[1] = Math.max(result.get(len - 1)[1], intervals[i][1]);
            }
        }
        // 最后将列表转化为二维数组返回
        return result.toArray(new int[result.size()][2]);
    }
}

知识点：

• python中调用列表排序方法时可以通过传递key值的方式定义比较值：list.sort(key=lambda x : x[0])，其中采用了lambda表达式：x为list中每个元素，而x[0]则代表key是x的第一个元素
• java中调用系统排序方法时可以通过传入比较器的方式定义排序规则，其中比较器是一个具体的Comparator对象，要重写其campare方式进行排序，详情见代码
• java中将列表转化为数组，可以用list.toArray(new in[])方法，其中传入的是用于存储元素的数组

原题连接：合并区间