个人简历网站模板下载,网站建设维护与管理实训总结,本地网站模板修改,广告设计公司的进项有哪些文章目录 专题一#xff1a;双指针1. 移动零2. 复写零3. 快乐数4. 盛最多水的容器5. 有效三角形的个数6. 查找总价格为目标值的两个商品7. 三数之和8. 四数之和 专题二#xff1a;滑动窗口1. 长度最小的子数组2. 无重复字符的最长字串3. 最大连续1的个数 III4. 将 x 减到 0 的… 文章目录 专题一双指针1. 移动零2. 复写零3. 快乐数4. 盛最多水的容器5. 有效三角形的个数6. 查找总价格为目标值的两个商品7. 三数之和8. 四数之和 专题二滑动窗口1. 长度最小的子数组2. 无重复字符的最长字串3. 最大连续1的个数 III4. 将 x 减到 0 的最小操作数 专题一双指针 1. 移动零 题目解析
算法原理
代码编写
// 写法一
class Solution
{
public:void moveZeroes(vectorint nums) {// 1、下标初始化int dest -1, cur 0;// 2、数组划分while(cur nums.size()){if(nums[cur]) swap(nums[dest], nums[cur]);else cur;}}
};// 写法二
class Solution
{
public:void moveZeroes(vectorint nums) {for(int dest -1, cur 0; cur nums.size(); cur)if(nums[cur]) // 处理 非0 元素swap(nums[dest], nums[cur]);}
};/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/2. 复写零 算法原理
代码编写
class Solution
{
public:void duplicateZeros(vectorint nums) {// 1、初始化int dest -1, cur 0, n nums.size();// 2、找到最后一个复写的数while(true){if(nums[cur]) dest 1;else dest 2;if(dest n - 1) break;cur;}cout nums[cur] endl;// 1.5、预处理 - 让 dest 的下标有效if(dest n){if(nums[cur]) --cur, --dest;else {nums[n - 1] 0;dest - 2;cur - 1;}}// 2、双指针从后往前进行复写操作while(cur 0){if(nums[cur]) nums[dest--] nums[cur--];else{nums[dest--] 0;nums[dest--] 0;cur--;} }}
};
/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/3. 快乐数 算法原理
代码编写
class Solution
{
private:// 计算每个位置上的数字的平方和inline static int BitSum(int num){int ret 0;while(num){int t num % 10;ret t * t;num / 10;}return ret;}public:bool isHappy(int n) {int slow n, fast BitSum(n);while(slow ! fast){slow BitSum(slow);fast BitSum(BitSum(fast));}return slow 1;}
};4. 盛最多水的容器 算法原理
代码编写
class Solution
{
public:int maxArea(vectorint height) {int left 0, right height.size() - 1;int ret INT_MIN;while(left ! right){// 容积 长度 * 高度int v (right - left) * min(height[left], height[right]);ret max(ret, v);// 移动指针 - 谁小移动谁height[left] height[right] ? left : --right;}return ret;}
};
/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/5. 有效三角形的个数 算法原理
代码编写
class Solution
{
public:int triangleNumber(vectorint nums) {// 1、优化sort(nums.begin(), nums.end());// 2、利用双指针解决问题int ret 0, n nums.size();for(int i n - 1; i 2; --i){int left 0, right i - 1;while(left right){// 当 abc a下标属于 [left, right-1]时都能和 b、c 构成三角形// 当 abc b下标属于[left-1, right]时都不能和 a、c 构成三角形if(nums[left] nums[right] nums[i]){ret right - left;--right;}else left;}}// 返回值return ret;}
};/*
- 时间复杂度O(n^2)
- 空间复杂度O(1)
*/6. 查找总价格为目标值的两个商品 算法原理
代码编写
class Solution
{
public:vectorint twoSum(vectorint price, int target) {// 1、数据初始化int left 0, right price.size() - 1;// 2、利用双指针解决问题while(left right){int sum price[left] price[right];if(sum target) left;else if(sum target) --right;else return {price[left], price[right]};}// 题目没有明确说明没有结果的话会怎么样那么该题的测试用例应该都是有结果的// 为了照顾编译器要求一定要返回一个结果所以我们最后返回一个空数组即可return {};}
};
/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/7. 三数之和 算法原理
代码编写
class Solution
{
public:vectorvectorint threeSum(vectorint nums) {// 1、初始化int n nums.size();vectorvectorint ret;// 2、排序sort(nums.begin(), nums.end());// 3、依次固定一个数for(int i 0; i n - 2;){// 4、双指针算法找到两数之和等于 aim 的元素int left i 1, right n - 1, aim -nums[i];while(left right){int sum nums[left] nums[right];if(sum aim) left;else if(sum aim) --right;else {ret.push_back( {nums[i], nums[left], nums[right]} );left, --right; // 保证 left、right 选择的元素不漏// 对 left、right 已经选择过的元素去重while(left right nums[left] nums[left - 1]) left;while(left right nums[right] nums[right 1]) --right;}}// 保证 i 选择的元素不漏i; // 对 i 已经选择过的元素去重while(i n - 2 nums[i] nums[i - 1]) i;}// 5、返回最终结果return ret;}
};
/*
- 时间复杂度O(n^2)
- 空间复杂度O(1)
*/8. 四数之和 算法原理
代码编写
class Solution
{
public:vectorvectorint fourSum(vectorint nums, int target) {// 1、初始化int n nums.size();vector vectorint ret;// 2、排序sort(nums.begin(), nums.end());// 3、依次固定一个数然后使用“三数之和”解决问题for(int i 0; i n - 3;) {// 4、再依次固定一个数然后使用“双指针”解决问题for(int j i 1; j n - 2;) {int left j 1, right n - 1;double aim (double)target - nums[i] - nums[j];// 5、双指针算法找到两数之和等于 aim 的元素while(left right){double sum nums[left] nums[right];if(sum aim) left;else if(sum aim) --right;else{ret.push_back( {nums[i], nums[j], nums[left], nums[right]} );left, --right; // 保证 left、right 选择的元素不漏// 对 left、right 已经选择过的元素去重while(left right nums[left] nums[left - 1]) left;while(left right nums[right] nums[right 1]) --right;}}// 保证 j 选择的元素不漏j;// 对 j 已经选择过的元素去重while(j n - 2 nums[j] nums[j - 1]) j;}// 保证 i 选择的元素不漏i;// 对 i 已经选择过的元素去重while(i n - 3 nums[i] nums[i - 1]) i;}// 6、返回最终结果return ret;}
};
/*
- 时间复杂度O(n^3)
- 空间复杂度O(1)
*/专题二滑动窗口 1. 长度最小的子数组 算法原理
代码编写
class Solution
{
public:int minSubArrayLen(int target, vectorint nums) {// 1、初始化int n nums.size();int minLength INT_MAX;// 2、使用滑动窗口解决问题for(int left 0, right 0, sum nums[0]; right n;){if(sum target) {minLength min(minLength, right - left 1);sum - nums[left];}else {if(right n)sum nums[right];}}// 3、返回值return minLength INT_MAX ? 0 : minLength;}
};
/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/2. 无重复字符的最长字串 算法原理
代码编写
class Solution
{
public:int lengthOfLongestSubstring(string s) {// 1、初始化int n s.size();vectorint count(256);int left 0, right 0, ret 0;// 2、滑动窗口int length 0; //用来记录窗口长度while(right n){if(!count[s[right]]) //进窗口{count[s[right]];length;right;ret max(ret, length); //更新结果}else //出窗口{--count[s[left]];--length;left;}}// 3、返回值return ret;}
};
/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/3. 最大连续1的个数 III 算法原理
代码编写
class Solution
{
public:int longestOnes(vectorint nums, int k) {// 1、初始化int n nums.size();int ret INT_MIN;// 2、滑动窗口int left 0, right 0;int length 0; // 当前子数组中最长连续 1 的长度int zero 0; // 当前子数组中 0 出现的次数while(right n){if(nums[right] ! 0) // nums[right] 非 0此时 right 一定入窗口{ret max(ret, length);right;}else{if(zero 1 k) {ret max(ret, length);zero;right;}else{if(nums[left] 0) --zero;--length;}}}// 3、返回值return ret;}
};
/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/4. 将 x 减到 0 的最小操作数 题目解析 算法原理 代码编写
class Solution
{
public:int minOperations(vectorint nums, int x) {// 1、初始化int sum 0;for(const auto e : nums) sum e;int target sum - x;// 2、细节处理(数组中所有元素都大于0所以 target 小于 0 是不存在的)if(target 0) return -1;// 3、滑动窗口int ret -1;for(int left 0, right 0, tmp 0; right nums.size();){// 进窗口tmp nums[right];// 出窗口while(tmp target) tmp - nums[left];// 更新结果if(tmp target) ret max(ret, right - left);}// 4、返回结果return ret -1 ? ret : nums.size() - ret;}
};
/*
- 时间复杂度O(n)
- 空间复杂度O(1)
*/
