力扣刷题小记4

博主个人博客网站：文客
这个系列主要记录在力扣刷题的总结和问题
如果你想每天和我一起刷题，可以关注一下我的个人博客网站：文客，我会每天在这里更新技术文章和面试题，也会及时收到大家的评论与留言，欢迎各位大佬来交流！

49. 字母异位词分组

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

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

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

思路：

用哈希表就好啦，很简单的。

题解：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for(String s : strs){
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            if(!map.containsKey(key)){
                map.put(key,new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList(map.values());
    }
}

64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

思路：

刚开始我用搜索做的，然后超时了。最后用动态规划做。

dp数组表示走到（i，j）位置的最小路径和

因为每次只能向左或向下走，所以递归公式就是：dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i][j]

题解：

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < grid.length; i++){
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for(int j = 1; j < grid[0].length; j++){
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }
        for(int i = 1; i < grid.length; i++){
            for(int j = 1; j < grid[0].length; j++){
                dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }
}

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

思路：

快排，划分的思想

题解：

class Solution {
    public void sortColors(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        for(int i = 0; i <= right; i++){
            while(i <= right && nums[i] == 2){
                swap(nums,i,right);
                right--;
            }
            if(nums[i] == 0){
                swap(nums,i,left);
                left++;
            }
        }
    }

    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int i = 0;
        while(i <= right){
            if(nums[i] == 0){
                swap(nums,i,left);
                i++;
                left++;
            } else if(nums[i] == 1){
                i++;
            } else if(nums[i] == 2){
                swap(nums,i,right);
                right--;
            }
        }
    }

    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

博客原文地址

力扣刷题小记4