找到
2
篇与
LeetCode
相关的结果
-
字母异位词分组：Go/Java/Python最优解法详解 字母异位词分组：Go/Java/Python最优解法详解 问题描述 字母异位词（Anagram）是指由相同字母重新排列组合形成的不同单词。本题要求： 给定一个字符串数组 strs，将其中所有字母异位词组合在一起，可以按任意顺序返回结果列表。 leetcode.jpg图片 示例：输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]解题思路 核心思路 字母异位词的特点是字母组成相同但顺序不同。我们可以利用这个特点： 将每个字符串排序，排序后的字符串作为异位词的统一标识 使用哈希表存储：排序后字符串 → 原始字符串列表的映射 最后将哈希表中的所有值收集起来就是结果 复杂度分析 时间复杂度：O(n*klogk)，n是字符串数量，k是字符串最大长度（排序每个字符串的耗时） 空间复杂度：O(nk)，需要存储所有字符串 各语言最优实现 Go实现 import ( "sort" "strings" ) func groupAnagrams(strs []string) [][]string { groups := make(map[string][]string) for _, str := range strs { // 将字符串转为字符数组并排序 s := strings.Split(str, "") sort.Strings(s) sortedStr := strings.Join(s, "") // 将原始字符串加入对应分组 groups[sortedStr] = append(groups[sortedStr], str) } // 收集结果 result := make([][]string, 0, len(groups)) for _, v := range groups { result = append(result, v) } return result }特点： 使用strings.Split和sort.Strings进行字符串排序 make(map[string][]string)创建哈希表 最后需要将map转为slice Java实现 import java.util.*; class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { // 将字符串转为字符数组并排序 char[] chars = str.toCharArray(); Arrays.sort(chars); String sorted = new String(chars); // 如果不存在该key，则新建一个列表 if (!map.containsKey(sorted)) { map.put(sorted, new ArrayList<>()); } map.get(sorted).add(str); } return new ArrayList<>(map.values()); } }特点： 使用Arrays.sort()对字符数组排序 需要处理key不存在的情况 new ArrayList<>(map.values())直接转换结果 Python3实现 from collections import defaultdict def groupAnagrams(strs): groups = defaultdict(list) for s in strs: # 排序字符串作为key key = "".join(sorted(s)) groups[key].append(s) return list(groups.values())特点： 使用defaultdict简化代码 sorted(s)直接返回排序后的字符列表 代码最为简洁 边界情况测试 测试用例说明预期结果[""]空字符串[[""]]["a"]单个字符[["a"]]["eat","tea","tan","ate","nat","bat"]常规情况[["bat"],["nat","tan"],["ate","eat","tea"]]["abc","cba","bac","def","fed"]多个分组[["def","fed"],["abc","cba","bac"]]算法优化思路 计数法优化（避免排序） 我们可以统计每个字符串中各个字母的出现次数，用计数作为key： def groupAnagrams(strs): groups = defaultdict(list) for s in strs: count = [0] * 26 for c in s: count[ord(c) - ord('a')] += 1 groups[tuple(count)].append(s) return list(groups.values())复杂度分析： 时间复杂度：O(n*k)，n是字符串数量，k是字符串最大长度 空间复杂度：O(nk) 这种方法在字符串较长时效率更高。 实际应用场景 单词游戏：如 Scrabble 等字母排列游戏 文本分析：查找相似单词 密码学：分析字母频率模式 数据清洗：识别和合并相似条目 总结 字母异位词分组问题的核心在于： 找到合适的分组标识（排序后的字符串或字母计数） 使用哈希表高效分组 处理各种边界情况 三种语言的实现展示了不同语言的特性： Go：显式类型转换较多，性能优秀 Java：类型系统严格，代码稍显冗长 Python：利用高级数据结构，代码最简洁 建议读者： 先理解排序法的思路 尝试实现计数法优化 比较不同语言的实现差异 扩展思考 如果字符串包含Unicode字符，如何修改算法？ 如何优化内存使用，特别是处理大量长字符串时？ 如何并行化处理这个分组问题？ 希望这篇文章能帮助你彻底掌握字母异位词分组问题！如有任何疑问，欢迎在评论区讨论。
-
两数之和（Two Sum）问题详解：一篇文章彻底掌握「两数之和」Go/Java/Python 最优解法详解 一篇文章彻底掌握「两数之和」：Go/Java/Python 最优解法详解 问题描述 「两数之和」是LeetCode上最经典的算法题之一，题目要求： 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。 leetcode.jpg图片 示例： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]解法思路分析 1. 暴力解法（不推荐） 最直观的方法是双重循环遍历所有可能的组合： def twoSum(nums, target): for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] 时间复杂度：O(n²) 空间复杂度：O(1) 2. 哈希表优化解法（最优解） 利用哈希表存储已经遍历过的数字及其索引，可以将时间复杂度降为O(n)： 各语言最优实现 Go 实现 func twoSum(nums []int, target int) []int { m := make(map[int]int) for i, v := range nums { if k, ok := m[target-v]; ok { return []int{k, i} } m[v] = i } return nil }特点： 使用map[int]int存储值到索引的映射 if k, ok := m[target-v]; ok 是Go特有的map访问方式 清晰简洁，性能优秀 Java 实现 class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] {map.get(complement), i}; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } }特点： 使用HashMap存储数据 需要处理无解情况（抛出异常） 类型系统更严格 Python3 实现 def twoSum(nums, target): hashmap = {} for i, num in enumerate(nums): complement = target - num if complement in hashmap: return [hashmap[complement], i] hashmap[num] = i return None特点： 使用字典存储数据 enumerate获取索引和值 代码最为简洁 算法分析 时间复杂度 三种实现的时间复杂度都是O(n)，因为： 只需要遍历数组一次 哈希表的查找操作是O(1)时间复杂度 空间复杂度 空间复杂度都是O(n)，因为： 最坏情况下需要存储所有元素到哈希表 边界情况测试 测试用例说明预期结果[2,7,11,15], 9常规情况[0,1][3,2,4], 6非顺序解[1,2][3,3], 6相同元素[0,1][1,2,3], 7无解情况nil/null/None[-1,0,1], 0含负数[0,2]实际应用场景 支付系统：查找两笔交易金额之和等于特定值 游戏开发：查找两个物品的组合效果 数据分析：找出满足特定条件的两个数据点 总结 「两数之和」问题虽然简单，但包含了算法设计的核心思想： 从暴力解法入手理解问题 通过空间换时间优化性能 考虑各种边界情况 掌握不同语言的实现特点 三种语言的实现虽然语法不同，但核心算法思想完全一致。建议读者： 先理解算法思路 然后学习自己主要使用语言的实现 最后尝试用其他语言实现以加深理解 扩展思考 如果数组已排序，是否有更优解法？（可以使用双指针法，空间复杂度O(1)） 如果要求返回所有可能的解而不仅是一个，如何修改代码？ 如果数组非常大，如何优化内存使用？ 希望这篇文章能帮助你彻底掌握「两数之和」问题！如果有任何疑问，欢迎在评论区留言讨论。
