LeetCode 11月第1周题目汇总

前言

最近一个多月发现以【每天一题】系列的形式来更新题目并不太合适，一是没有足够多合适的题目来更新，二是单独拿出来一个题来讲不太系统，应该把多个相似的题目放在一起讲，这样才能够达到举一反三的效果，所以决定停止【每天一题】系列，改为【每周小结】，然后每个月再进行一次月总结，接下来言归正传。

11月第1周共有20道题目，所有源码以及对应的解题思路均匀开源到 GitHub，公众号内回复 “LeetCode” 获取，具体分类如下。

映射

该类题目常用数据结构为：map, unordered_map, set 或 使用数组进行 hash 映射。

• 0242_valid_anagram
• 0290_word_pattern
• 0299_bulls_and_cows
  以上三题都是字符或字符串之间的双映射关系是否成立，根据情况使用map、unordered_map 或 使用数组也可以
• 0349_intersection_of_two_arrays
• 0350_intersection_of_two_arrays_ii
  以上两题是求解两个数组的交集，第一个题目只需要找出有几种不同的即可，不关心数量；第二个题目需要找出具体多少个相同字符，重复的也算进去
• 0383_ransom_note
  这一个题目是查询一个字符串中是否含有不少于另一个字符串字符数量

深度优先搜索

• 0257_binary_tree_paths

脑筋急转弯

这个题目比较有意思，刚开始想了很多种做法，但是感觉太复杂了，应该会超时，想想算了，看看官方题解，结果竟然就一句搞定了，我就***了，看完解析后，只能说，服了，感兴趣的可以看看官方的解法，这里就不赘述了。

• 0292_nim_game

数学

这类题目都是可以使用数学方法解决的题目，并不是太多的考察数据结构。

• 0258_add_digits
• 0263_ugly_number
• 0268_missing_number
  该题目有多种解法，第一种是根据递增数组求解，然后计算差值就可得到确实的数是哪一个；第二种是官方给出的一种，通过异或运算得出，方法很有意思；两种方法复杂度相同
• 0303_range_sum_query_immutable
  这个题目就是预先计算积分即可，了解图像处理的都知道图像积分这个概念，只不过这里是一维数组，而图像是二维的(不考虑颜色通道时)，所以很简单
• 0326_power_of_three
• 0342_power_of_four
  这两个题目是判断给定数是否是某个数的幂，最简单的方法就是暴力分解，一种做法是将给定数转化成对应数的进制，即3进制或4进制，转换后的数如果是它的幂，那么一定只含有一个 1，所以判断一下就行了；另一种方法就是如果先找出最大的幂是多少，如果给定数也是，那么最大幂一定可以整除这个数，复杂度为O(1)

二分法

二分法就没什么好说的了，就那些操作，左右各一个，中间数大了右边的往左移动，中间数小了左边的往右移动，直到结束即可。

• 0278_first_bad_version
• 0367_valid_perfect_square
• 0374_guess_number_higher_or_lower

反转数组

反转数组就是使用双指针了，第一个题目直接进行即可，第二个题目只反转元音字母，所以指针移动时不再是++或--操作，而是以元音字母为单位移动，也没什么复杂的。

• 0344_reverse_string
• 0345_reverse_vowels_of_a_string

位运算

根据计算机原理，使用二进制的异或和与运算实现加法，其中异或表示加法，与运算表示进位。

• 0371_sum_of_two_integers