? LeetCode 热题 HOT 100: 49 && 53

“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

49. 字母异位词分组

一、题目描述：

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

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

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

二、思路分析：
哈希表， Map<String, List> ， 对每个字符串计算 key

• 排序， eat -> aet
• 计数。 eat -> a1e1t1

三、AC 代码：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for(String s : strs){
            char[] c = s.toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            List<String> value = map.getOrDefault(key, new ArrayList<>());
            value.add(s);
            map.put(key, value);
        }

        return new ArrayList<>(map.values());
    }
}
复制代码

53. 最大子数组和

一、题目描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入： nums = [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。
复制代码

二、思路分析：

动态规划

dp[i] 是以 i 结尾子数组的最大和

状态转移： dp[i] = dp[i – 1] > 0 ? dp[i – 1] + nums[i] : nums[i];

状态转移只与前一个位置有关， 因此 dp 数组可以压缩使用一个变量替代

三、AC 代码：

class Solution {
    public int maxSubArray(int[] nums) {

        int dp = nums[0], ans = dp;
        for(int i = 1; i < nums.length; i++){
            dp = dp < 0 ? nums[i] : dp + nums[i];
            ans = Math.max(ans, dp);
        }
        return ans;
    }
}
复制代码