天津房地产网站建设,免费的行情网站推荐大全,网络营销的推广方式有哪些,百度关键词排名提升工具写在前面#xff1a;坚持才是最难的事情
C代码还是不方便写#xff0c;改用python了#xff0c;TAT 文章目录 1.两数之和49. 字母异位词分组128.最长连续序列 1.两数之和
你好#xff0c;梦开始的地方~ https://leetcode.cn/problems/two-sum/description/?envTypestudy…写在前面坚持才是最难的事情
C代码还是不方便写改用python了TAT 文章目录 1.两数之和49. 字母异位词分组128.最长连续序列 1.两数之和
你好梦开始的地方~ https://leetcode.cn/problems/two-sum/description/?envTypestudy-plan-v2envIdtop-100-liked
直接两个for循环
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int size nums.size();for (int i 0; i size; i ){for (int j i 1; j size; j){if (nums[i] nums[j] target){return {i ,j};}}}return {};}
};时间复杂度O N 2 N^2 N2其中N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次 空间复杂度O (1)。
最容易想到的方法是枚举数组中的每一个数 x寻找数组中是否存在 target - x。方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此我们需要一种更优秀的方法能够快速寻找数组中是否存在目标元素。如果存在我们需要找出它的索引。
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int hashtable;for (int i 0; i nums.size(); i){auto it hashtable.find(target - nums[i]);// 如果找到了就返回if (it ! hashtable.end()){return {it-second, i};}// 都保存这个数的位置hashtable[nums[i]] i;}return {};}
};49. 字母异位词分组 https://leetcode.cn/problems/group-anagrams/description/?envTypestudy-plan-v2envIdtop-100-liked
思路将字符串排序字符串排序后相同的放在一起
由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键。
class Solution {
private:unordered_mapstring, vectorstring hash;vectorvectorstring ans;
public:vectorvectorstring groupAnagrams(vectorstring strs) {for (const auto str : strs){string tmp str;sort(tmp.begin(), tmp.end());hash[tmp].emplace_back(str);}for (const auto one: hash){ans.emplace_back(one.second);}return ans;}
};时间复杂度 : O ( n k log k ) :O(nk\log k) :O(nklogk),其中 n n n 是 s t r s strs strs 中的字符串的数量 k k k 是 s t r s strs strs 中的字符串的的最大长度。需要遍历 n n n 个字符串对于每个字符串需要 O ( k log k ) O(k\log k) O(klogk) 的时间进行排序以及 O ( 1 ) O(1) O(1) 的时间更新哈希表因此总时间复杂度是 O ( n k log k ) O(nk\log k) O(nklogk) 。
空间复杂度 O ( n k ) O(nk) O(nk),其中 n n n 是 s t r s strs strs 中的字符串的数量 k k k 是 s t r s strs strs 中的字符串的的最大长 度。需要用哈希表存储全部字符串。 方法二计数 由于互为字母异位词的两个字符串包含的字母相同因此两个字符串中的相同字母出现的次数一定是相同的故可以将每个字母出现的次数使用字符串表示作为哈希表的键。
由于字符串只包含小写字母因此对于每个字符串可以使用长度为 26 的数组记录每个字母出现的次数。、
还是python写比较方便C太不熟悉了TAT
class Solution(object):def groupAnagrams(self, strs)::type strs: List[str]:rtype: List[List[str]]mp collections.defaultdict(list);for st in strs:# 记录字母出现的次数counts [0] * 26for ch in st:# 字母出现记录1# ord() 函数返回一个字符的Unicode码点因此 ord(ch) 返回字符 ch 的Unicode码点counts[ord(ch) - ord(a)] 1# 两个字符串中的相同字母出现的次数一定是相同的放在一起mp[tuple(counts)].append(st)return list(mp.values())时间复杂度 : O ( n ( k ∣ Σ ∣ ) ) :O(n(k|\Sigma|)) :O(n(k∣Σ∣)),其中 n n n 是 s t r s strs strs 中的字符串的数量 k k k 是 s t r s strs strs 中的字符串的的最大长度Σ 是字符集在本题中字符集为所有小写字母 ∣ Σ ∣ 26 |\Sigma|26 ∣Σ∣26。需要遍历 n n n 个字符串对于每个字符串需要 O ( k ) O(k) O(k) 的时间计算每个字母出现的次数 O ( ∣ Σ ∣ ) O(|\Sigma|) O(∣Σ∣) 的时间生成哈希表的键 以及 O ( 1 ) O(1) O(1) 的时间更新哈希表 因此总时间复杂度是 O ( n ( k ∣ Σ ∣ ) ) O(n(k|\Sigma|)) O(n(k∣Σ∣)) 。
空间复杂度 O ( n ( k ∣ Σ ∣ ) ) O(n(k|\Sigma|)) O(n(k∣Σ∣)),其中 n n n 是 s t r s strs strs 中的字符串的数量 k k k 是 s t r s strs strs 中的字符串的最大 长度Σ 是字符集在本题中字符集为所有小写字母 ∣ Σ ∣ 26 |\Sigma|26 ∣Σ∣26。需要用哈希表存储全部字符串而记录每个字符串中每个字母出现次数的数组需要的空间为 O ( ∣ Σ ∣ ) O(|\Sigma|) O(∣Σ∣), 在渐进意义下小于 O ( n ( k ∣ Σ ∣ ) ) O(n(k|\Sigma|)) O(n(k∣Σ∣)),忽略不计。
128.最长连续序列 https://leetcode.cn/problems/longest-consecutive-sequence/description/?envTypestudy-plan-v2envIdtop-100-liked
我们考虑枚举数组中的每个数 x x x,考虑以其为起点不断尝试匹配 x 1 , x 2 , ⋯ x1,x2,\cdots x1,x2,⋯是否存在假设最长匹配到了 x y xy xy,那么以 x x x 为起点的最长连续序列即为 x , x 1 , x 2 , ⋯ , x y x,x1,x2,\cdots,xy x,x1,x2,⋯,xy, 其长度为 y 1 y1 y1, 我们不断枚举并更新答案即可。
对于匹配的过程暴力的方法是 O ( n ) O(n) O(n) 遍历数组去看是否存在这个数但其实更高效的方法是用一 个哈希表存储数组中的数这样查看一个数是否存在即能优化至 O ( 1 ) O(1) O(1) 的时间复杂度。
仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 O ( n 2 ) O(n^2) O(n2) 。 即外层需要枚举 O ( n ) O(n) O(n) 个数内层需要暴力匹配 O ( n ) O(n) O(n) 次), 无法满足题目的要求。
但仔细分析这个过程我们会发现其中执行了很多不必要的枚举如果已知有一个 x , x 1 , x 2 , ⋯ , x y x,x1,x2,\cdots,xy x,x1,x2,⋯,xy 的连续序列而我们却重新从 x 1 x1 x1 , x 2 x2 x2 或者是 x y xy xy 处开始尝试匹配那么得到的结果肯定不会优于枚举 x x x 为起点的答案因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢 由于我们要枚举的数 x x x一定是在数组中不存在前驱数 x − 1 x- 1 x−1的不然按 照上面的分析我们会从 x − 1 x-1 x−1 开始尝试匹配因此我们每次在哈希表中检查是否存在 x − 1 x-1 x−1 即能判断是否需要跳过了。
class Solution(object):def longestConsecutive(self, nums)::type nums: List[int]:rtype: intlongest_streak 0num_set set(nums)for num in num_set:if num - 1 not in num_set:current_num numcurrent_streak 1while current_num 1 in num_set:current_num 1current_streak 1longest_streak max(longest_streak, current_streak)return longest_streak 时间复杂度 O ( n ) O(n) O(n),其中 n n n 为数组的长度。具体分析已在上面正文中给出。 空间复杂度 O ( n ) O(n) O(n)。哈希表存储数组中所有的数需要 O ( n ) O(n) O(n) 的空间。
在 Python 中使用 in 操作符来判断元素是否存在于 set 中其平均时间复杂度是 O(1)。这是因为 set 是基于哈希表实现的在大多数情况下通过哈希函数将元素映射到哈希表的特定位置可以在常数时间内进行查找操作。当然如果出现哈希冲突时间复杂度可以增高到 O(n)。但是在平均情况下查询元素是否在 set 中仍然是效率很高的操作。
