Leetcode代码以及解答（1）

### Leetcode代码以及解答（1） #### 389.FindtheDifference **题目描述：** 给定两个字符串 `s` 和 `t`，其中 `t` 是在 `s` 的基础上添加了一个额外字符后的乱序版本。任务是找出这个额外的字符。 **解题思路：** 1. **哈希表法：** 使用 `unordered_map` 记录 `s` 中的所有字符及其出现次数。 2. 遍历 `t`，逐个与 `unordered_map` 匹配。若 `t` 中某字符未出现在 `unordered_map` 或者出现次数超过 `unordered_map` 中记录的次数，则该字符即为答案。 **优化思路：** 1. **异或法：** 将 `s` 和 `t` 中的所有字符进行异或操作。由于异或具有可逆性，相同字符异或结果为0，因此最终结果即为额外的字符。 #### 292.NimGame **题目描述：** 在 Nim 游戏中，给定一堆石头，两人轮流取走任意数量的石头（至少取1颗），谁取到最后的石头谁赢。当玩家面临一定数量的石头时，判断其是否必败。 **解题思路：** 1. 观察发现，当石头总数为4的倍数时，先手玩家会必败。 2. 根据当前剩余石头数量和先手玩家的先后顺序，可以确定游戏的结果。 #### 258.AddDigits **题目描述：** 给定一个非负整数 `num`，反复将各个数字相加直到结果为一位数。 **解题思路：** 1. 使用 `while` 循环持续将数字各个位相加，直到结果小于10为止。 **优化思路：** 1. **数学方法：** 将问题转化为三种情况： - 如果 `num == 0`，结果为0。 - 如果 `num` 是9的倍数，结果为9。 - 否则，结果为 `num % 9`。 #### 283.MoveZeroes **题目描述：** 给定一个数组 `nums`，将所有的0移动到数组的末尾，并保持非零元素的相对顺序不变。 **解题思路：** 1. 直接删除数组中的0，并统计0的数量，最后在数组末尾添加相应数量的0。 **优化思路：** 1. 使用双指针技术，用非零元素覆盖零元素，最后将数组末尾补0。 #### 100.SameTree **题目描述：** 给定两棵二叉树 `p` 和 `q`，判断它们是否完全相同。 **解题思路：** 1. 需要处理两种特殊情况：两棵树均为空或者仅有一棵树为空。 2. 若两棵树均非空，则比较根节点的值，并递归地比较左右子树。 #### 260.SingleNumberIII **题目描述：** 给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，而其他元素均出现两次。找到这两个只出现一次的元素。 **解题思路：** 1. 先计算出两个唯一元素的异或结果。 2. 找出异或结果中最右侧的1，以此划分两个元素的不同位。 3. 分别根据该位的不同，将数组划分为两部分，并对这两部分分别做异或操作，从而得到两个唯一元素。 #### 122.BestTimetoBuyandSellStockII **题目描述：** 给定一个股票价格数组 `prices`，求在最多买入卖出若干次的情况下，能获得的最大利润。 **解题思路：** 1. 使用贪心算法，每当发现股票价格上升时，立即买入并卖出。 #### 238.ProductofArrayExceptSelf **题目描述：** 给定一个非零整数数组 `nums`，返回一个新的数组 `output`，使得 `output[i]` 等于 `nums` 中除 `nums[i]` 之外其余各元素的乘积。 **解题思路：** 1. 常规思路：计算数组所有元素的乘积，然后分别除以数组中的每个元素。 2. 处理除0情况，区分只有一个0和其他情况。 **优化思路：** 1. 使用两个辅助数组分别记录每个位置左侧所有元素的乘积和右侧所有元素的乘积。 2. 最终结果为左侧乘积与右侧乘积的乘积。 #### 242.ValidAnagram **题目描述：** 给定两个字符串 `s` 和 `t`，判断它们是否为字母异位词。 **解题思路：** 1. 判断两个字符串长度是否相等。 2. 使用哈希表记录每个字符出现的次数，遍历 `s` 和 `t` 更新哈希表。 **优化思路：** 1. 使用固定大小的哈希表（如大小为26的数组）来存储每个字符的计数。 2. 对于 `s`，增加相应字符的计数；对于 `t`，减少相应字符的计数。 3. 如果任何字符的计数小于0，则 `s` 和 `t` 不是字母异位词。 #### 217.ContainsDuplicate **题目描述：** 给定一个整数数组 `nums`，判断数组中是否有重复元素。 **解题思路：** 1. 使用 `set` 来检查数组中是否存在重复元素。 **优化思路：** 1. 排序后直接比较相邻元素是否相等。 2. 统计数组中每个元素的出现次数，如果有元素出现次数大于1，则存在重复。 #### 219.ContainsDuplicateII **题目描述：** 给定一个整数数组 `nums` 和一个正整数 `k`，判断数组中是否存在两个不同的索引 `i` 和 `j` 使得 `nums[i] = nums[j]` 并且 `i` 和 `j` 的差的绝对值不超过 `k`。 **优化思路：** 1. 使用滑动窗口和哈希表结合的方法，在遍历数组的过程中维护一个大小为 `k` 的窗口，并使用哈希表来记录窗口内每个元素的最后一次出现的位置。 #### 168.ExcelSheetColumnTitle **题目描述：** 给定一个整数 `columnNumber`，返回对应的 Excel 表列名称。 **解题思路：** 1. 将整数转换为26进制数，但需要注意的是每个数字代表的是 A-Z 的字母。 2. 通过循环处理，将整数转换为相应的 Excel 表列名称。 #### 171.ExcelSheetColumnNumber **题目描述：** 给定一个列名称，将其转换成对应的 Excel 表列编号。 **解题思路：** 1. 从左到右遍历给定的列名称，将每个字符转换为其对应的值，再根据位置乘以相应的权重。 #### 169.MajorityElement **题目描述：** 给定一个数组 `nums`，其中有一个元素出现次数超过数组长度的一半，找出这个元素。 **解题思路：** 1. 使用哈希表记录每个元素出现的次数。 2. 当某个元素的计数超过数组长度的一半时，返回该元素。 **优化思路：** 1. **排序法：** 对数组进行排序，位于中间位置的元素即为众数。 2. **摩尔投票法：** 初始化候选元素和计数器，遍历数组，若遇到相同的元素则增加计数器，否则减少计数器，直到计数器为0重新选择候选元素。 #### 318.MaximumProductofWordLengths **题目描述：** 给定一个字符串数组 `words`，返回所有互不相同的字符串组成的两个字符串的长度乘积的最大值，其中两个字符串不包含相同的字符。 **优化思路：** 1. 将每个单词转换为比特表示，用二进制表示每个字符的存在情况。 2. 遍历每一对单词，通过比较它们的比特表示来判断是否互不相同，进而计算长度乘积的最大值。 #### 319.BulbSwitcher **题目描述：** 给定 n 个开关控制 n 个灯泡，依次按顺序操作每个开关的倍数对应的灯泡。最终亮着的灯泡有多少？ **解题思路：** 1. 分析灯泡操作次数的性质，发现只有完全平方数的灯泡会被操作偶数次。 2. 因此，只需要计算 n 内有多少个完全平方数即可得出答案。