工程建设信息网站,网站建设 swot分析,公司网站备案申请,wordpress 远程调用函数1.移除元素
目标#xff1a;移除数组中的某一个元素
数组的元素在内存地址中是连续的#xff0c;不能单独删除数组中的某个元素#xff0c;只能覆盖。
1.1暴力解法
建立两个for循环#xff0c;当查找到某个元素以后#xff0c;将此元素后面的元素全部往前移动
时间复…1.移除元素
目标移除数组中的某一个元素
数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖。
1.1暴力解法
建立两个for循环当查找到某个元素以后将此元素后面的元素全部往前移动
时间复杂度
1.2双指针法
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
快指针用来遍历全部的数组元素慢指针用来更新数组元素当快指针的元素不是要删除的元素的时候赋值给慢指针
时间复杂度 #include iostream
using namespace std;
#include vector
#include algorithm
class Solution1 {
public:int removeElement(vectorint nums, int val) {int size nums.size();for (int i 0; i size; i) {if (nums[i] val) { for (int j i 1; j size; j) {nums[j - 1] nums[j];}i--; size--; }}return size;}
};class Solution2 {
public:int removeElement(vectorint nums, int val) {int slowIndex 0;for (int fastIndex 0; fastIndex nums.size(); fastIndex) {if (val ! nums[fastIndex]) {nums[slowIndex] nums[fastIndex];}}return slowIndex;}
};int main()
{vectorint array1 { 1 ,2,4,4,5,5,5,6,7,8 };Solution1 solution1;int size1 solution1.removeElement(array1, 5);for (int i 0; i size1; i){cout array1[i] ;}coutendl;vectorint array2 { 1 ,2,4,4,5,5,5,6,7,8 };Solution2 solution2;int size2 solution2.removeElement(array2, 5);for (int i 0; i size2; i){cout array2[i] ;}return 0;
}2.有序数组的平方
要求给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 输入nums [-7,-3,2,3,11] 输出[4,9,9,49,121]2.1暴力解法
每个数平方以后排个序
class Solution {
public:vectorint sortedSquares(vectorint A) {for (int i 0; i A.size(); i) {A[i] * A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
};
2.2双指针法
由于数组是有序的平方以后最大的肯定出现在两端因此令k为最大索引依次往前排列
双指针i从左往右索引j从右往左索引将大的值赋值给nums[k]然后k--
class Solution {
public:vectorint sortedSquares(vectorint A) {int k A.size() - 1;vectorint result(A.size(), 0);for (int i 0, j A.size() - 1; i j;) { // 注意这里要i j因为最后要处理两个元素if (A[i] * A[i] A[j] * A[j]) {result[k--] A[j] * A[j];j--;}else {result[k--] A[i] * A[i];i;}}return result;}
};
3.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。
输入s 7, nums [2,3,1,2,4,3] 输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组
3.1暴力解法
建立两个for循环然后不断的寻找符合条件的子序列
3.2滑动窗口
只使用一个for循环循环的索引是滑动窗口的终止位置。
指针1滑动窗口的终止位置依次往右移动
指针2滑动窗口的起始位置同样也是一直往右移动
class Solution {
public:int minSubArrayLen(int s, vectorint nums) {int result INT32_MAX;int sum 0; // 滑动窗口数值之和int i 0; // 滑动窗口起始位置int subLength 0; // 滑动窗口的长度for (int j 0; j nums.size(); j) {sum nums[j];// 注意这里使用while每次更新 i起始位置并不断比较子序列是否符合条件while (sum s) {subLength (j - i 1); // 取子序列的长度result result subLength ? result : subLength;sum - nums[i]; // 这里体现出滑动窗口的精髓之处不断变更i子序列的起始位置}}// 如果result没有被赋值的话就返回0说明没有符合条件的子序列return result INT32_MAX ? 0 : result;}
}; 滑动窗口本质上也是一种双指针法是在充分理解题目的情况下暴力算法的一种简化 这道题之所以可以使用滑动窗口很重要的一个原因是在移动终止位置的时候初始位置是不可逆的初始位置只可能往后移动而不用每次都从第零个元素开始 所有双指针法都是充分利用题目的一个隐藏的特征来对暴力算法的一种简化
