leetcode May Daily Challenge Week1

概述

第一周的题目，多数考察了HashMap的使用、树的遍历、排序。题目难度不大，不过这些问题是构成后续较难问题的基础，如记忆化搜索，可以变成输出解的路径等。

同时考虑到挑战的难度不会太高，这个系列依旧每周一篇，同时考虑再起一个系列, 来介绍一些专项的内容或经典书籍的课后问题整理。

题目地址

思路分析

First Bad Version

给定一个[1...n]的升序序列，其中某一个数字代表错误的版本号, 尽可能少的调用isBadVersion, 找到最早出现的错误版本号, 并返回

思路1. 依照题目表述, 当某一个版本号为错误版本号后, 后续的版本号也同样是错误的, 那么意味着给定数组想表达的是[good, good, bad, bad, ..., bad]，等价于在数组[0,0,1,1,1]中寻找最早出现的1。直接二分法即可。
该方法时间复杂度为O(logN)

总结.

1) 仅考察二分法。

Jewels and Stones

给定字符串J与字符串S, 其中J中的每个字符代表珠宝, S代表你持有的石头, 若S中的字符在J中出现, 则你持有一个珠宝，问你一共持有多少珠宝

Input: J = "aA", S = "aAAbbbb"
Output: 3

思路1. 朴素的来说, 我们只需要迭代S串, 并在J中寻找s中的每一个字符是否出现过, 即可得出正确的解。那么时间复杂度就是O(M*N), 其中M和N分别为S的长度与J的长度。进一步，我们可以对J进行HashMap处理，这样每次判定则为O(1)。
对于字符串问题, 因为字符共有26个, 因此可以直接开辟一个初始大小为26的数组, 用于对'a'~'z'进行快速判定。
该方法的时间复杂度为O(N)

总结.

1) 基础数据结构HashMap的使用。

Ransom Note

给定两个字符串s1, s2, 判定s1是否可以通过s2构造出来, 构造的含义即s2包含s1的所需的所有字符(每个字符可以使用一次)

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

思路1. 与Jewels and Stones是很相似的, 考虑到构造的含义, 我们只需要对s2中出现的字符进行计数后, 看s1出现的字符是否满足计数, 即char_counter[ch_from_s1] > 0,当且仅当char_counter[ch_from_s1] == 0返回False。
该方法的时间复杂度为O(N)

1) 基础数据结构HashMap的使用。

First Unique Character in a String

给定一个字符串，判断第一个出现一次的字符, 并返回该字符的下标

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

思路1. 考虑出现一次, 即某一个字符, 在整个字符串中出现的次数为一, 并且注意第一个, 也就是序的概念(参考April的练习)。所以, 第一步我们完成对字符的计数, 第二步我们从头向尾遍历，得到第一个counter_cnt[ch_from_str] == 1的字符。
PS: 这里依旧可以通过初识大小为26的数组, 进行快速计数。
该方法的时间复杂度为O(N)

总结.

1) 基础数据结构HashMap的使用。

Majority Element

给定一个数组, 找出其中出现次数多于n/2的元素, 可以理解为寻找众数

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

思路1. 如果数组是有序的那么,直接输出nums[n/2]即可。那么我们可以选择稳定的归并排序作为处理,同时考虑使用自第向上的归并可以减少函数的调用开销。
该方法的时间复杂度为O(NlogN)
思路2. 我们用hash_map对出现的元素进行计数, 即<num, count>格式, 若某一个元素的出现次数>=n/2, 则直接输出。
该方法的时间复杂度为O(N)

总结.

1) 计数是一种很朴素的方法，简单且好用
2) 对于归并中分治与合并思想, 值得仔细推敲，是一种场景的大问题到小问题的通用思路