网站整站下载器 全站克隆页面图片视频下载 仿站专用源码工具软件,电子商务网站规划原则,从山海经取公司名三个字,贵阳app制作开发LeetCode 热题 100 文章目录 LeetCode 热题 100多维动态规划87. 中等-不同路径88. 中等-最小路径和89. 中等-最长回文子串90. 中等-最长公共子序列91. 困难-编辑距离 技巧92. 简单-只出现一次的数字93. 简单-多数元素94. 中等-颜色分类95. 中等-下一个排列96. 中等-寻找重复数 …LeetCode 热题 100 文章目录 LeetCode 热题 100多维动态规划87. 中等-不同路径88. 中等-最小路径和89. 中等-最长回文子串90. 中等-最长公共子序列91. 困难-编辑距离 技巧92. 简单-只出现一次的数字93. 简单-多数元素94. 中等-颜色分类95. 中等-下一个排列96. 中等-寻找重复数 本文存储我刷题的笔记。 多维动态规划
87. 中等-不同路径
88. 中等-最小路径和
89. 中等-最长回文子串
90. 中等-最长公共子序列
91. 困难-编辑距离
技巧
92. 简单-只出现一次的数字 我的思路哈希表 思路用哈希集合std::unordered_set遍历所有元素没遇过就存起来遇到了就删除哈希集合对应元素最后哈希集合中剩下的元素就是。时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组长度。只需要对数组遍历一次。空间复杂度 O ( n ) O(n) O(n)最多可能会存储 n / 2 n/2 n/2 个元素。时间24ms(20.69%)内存19.81MB(8.87%)。 class Solution {
public:int singleNumber(std::vectorint nums) {int len nums.size();std::unordered_setint s_num;for(int i0; ilen; i){// 遇到有的就擦除if(s_num.count(nums[i])){s_num.erase(nums[i]); }// 遇到没有的就存起来else{s_num.emplace(nums[i]);}}// 返回只剩下的最后一个元素return *s_num.begin();}
};官方思路一位运算 思路因为只有一个数和其他的都不一样所以将所有数字都进行异或运算最后就只剩下那个单独的数字。时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组长度。只需要对数组遍历一次。空间复杂度 O ( 1 ) O(1) O(1)。时间8ms(98.78%)内存16.89MB(37.16%)。 class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for (auto e: nums) ret ^ e;return ret;}
};93. 简单-多数元素 我的思路哈希表 思路先统计再遍历。时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 nums的长度。我们遍历数组 nums一次又至多遍历一次哈希表最多包含 n − ⌊ n 2 ⌋ n - \lfloor \dfrac{n}{2} \rfloor n−⌊2n⌋ 个键值对。因此总时间复杂度为 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。哈希表最多包含 n − ⌊ n 2 ⌋ n - \lfloor \dfrac{n}{2} \rfloor n−⌊2n⌋ 个键值对所以占用的空间为 O ( n ) O(n) O(n)。时间20ms(45.10%)内存19.69MB(8.36%)。 注由于题目保证会出现多数元素所以也可以将这两个循环放在一起。 class Solution {
public:int majorityElement(std::vectorint nums) {// 使用哈希表统计所有信息// 哈希表键-元素的大小、值-出现的次数std::unordered_mapint,int m_data;for(auto num : nums){m_data[num] 1;}// 找出符合要求的值int target nums.size()/2;for(auto itm_data.begin(); it!m_data.end(); it){if(it-second target){return it-first;}}return -1;}
};官方思路二排序 思路将数组 nums排序那么下标为 ⌊ n 2 ⌋ \lfloor \dfrac{n}{2} \rfloor ⌊2n⌋ 的元素一定是“多数元素”。时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。将数组排序的时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。空间复杂度 O ( log n ) O(\log n) O(logn)。如果使用语言自带的排序算法需要使用 O ( log n ) O(\log n) O(logn) 的栈空间。如果自己编写堆排序则只需要使用 O ( 1 ) O(1) O(1) 的额外空间。时间20ms(45.10%)内存19.66MB(10.82%)。 class Solution {
public:int majorityElement(vectorint nums) {sort(nums.begin(), nums.end());return nums[nums.size() / 2];}
};官方思路三随机化 思路由于“多数元素”过半那么随机挑选一个是“多数元素”的概率很大。于是代码逻辑为随机生成一个下标检查它是否是“多数元素”如果是就返回否则继续随机挑选。时间复杂度理论上最坏情况下的时间复杂度为 O ( ∞ ) O(\infty) O(∞)但实际上期望的时间复杂度为 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。随机方法只需要常数级别的额外空间。时间16ms(75.52%)内存19.63MB(14.46%)。 class Solution {
public:int majorityElement(vectorint nums) {while (true) {int candidate nums[rand() % nums.size()];int count 0;for (int num : nums)if (num candidate)count;if (count nums.size() / 2)return candidate;}return -1;}
};官方思路四分治 思路分治算法递归求解。将数组分成左右两部分分别求出左半部分的众数 a1以及右半部分的众数 a2随后在 a1和 a2中选出正确的众数。最后的的子问题都是长度为 1的数组。时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。推导见原文“方法四分治”。空间复杂度 O ( log n ) O(\log n) O(logn)。尽管分治算法没有直接分配额外的数组空间但在递归的过程中使用了额外的栈空间。算法每次将数组从中间分成两部分所以数组长度变为 1之前需要进行 O ( log n ) O(\log n) O(logn) 次递归即空间复杂度为 O ( log n ) O(\log n) O(logn)。时间28ms(9.03%)内存19.58MB(21.58%)。 class Solution {// 统计目标值在指定范围内的次数int count_in_range(vectorint nums, int target, int lo, int hi) {int count 0;for (int i lo; i hi; i)if (nums[i] target)count;return count;}// 分治算法int majority_element_rec(vectorint nums, int lo, int hi) {// 递归最小的子问题长度为1的数组if (lo hi)return nums[lo];// 统计左右两部分的“多数元素”int mid (lo hi) / 2;int left_majority majority_element_rec(nums, lo, mid);int right_majority majority_element_rec(nums, mid 1, hi);// 检查哪个符合出现次数标准if (count_in_range(nums, left_majority, lo, hi) (hi - lo 1) / 2)return left_majority;if (count_in_range(nums, right_majority, lo, hi) (hi - lo 1) / 2)return right_majority;return -1;}
public:int majorityElement(vectorint nums) {return majority_element_rec(nums, 0, nums.size() - 1);}
};官方思路五Boyer-Moore 投票算法 思路 如果我们把众数记为 111把其他数记为 −1-1−1将它们全部加起来显然和大于 0从结果本身我们可以看出众数比其他数多。于是Boyer-Moore 算法的详细步骤 维护一个候选众数 candidate和它出现的次数 count。初始时 candidate为任意值count为 0遍历数组 nums中的所有元素对于每个元素 x在判断 x之前如果 count的值为 0我们先将 x的值赋予 candidate随后我们判断 x 如果 x与 candidate相等那么计数器 count的值增加 1 如果 x与 candidate不等那么计数器 count的值减少 1。 在遍历完成后candidate即为整个数组的众数。 时间复杂度 O ( n ) O(n) O(n)。Boyer-Moore 算法只对数组进行了一次遍历。空间复杂度 O ( 1 ) O(1) O(1)。Boyer-Moore 算法只需要常数级别的额外空间。时间12ms(93.37%)内存19.70MB(6.31%)。 class Solution {
public:int majorityElement(vectorint nums) {int candidate -1;int count 0;for (int num : nums) {if (num candidate)count;else if (--count 0) {candidate num;count 1;}}return candidate;}
};94. 中等-颜色分类
95. 中等-下一个排列
96. 中等-寻找重复数 我的思路 思路 时间??ms(??%)内存??MB(??%)。 官方思路 思路 时间??ms(??%)内存??MB(??%)。
