顺序表综合操作
顺序表综合操作
线性表(a1,a2,a3…an)中的元素递增有序且按顺序存储与计算机内,
要求设计一个算法完成用最少时间在表中查找数值为x的元素,若找到则将其与后继元素位置相互交换,若找不到则将其插入表中并使表中元素仍然递增有序
1.二分查找递归12345678910111213141516171819202122232425#include "preset.h"//有序顺序表查找(二分查找)递归写法int binSearch(SqList sql, int target, int low, int high) { if (low > high) return -1; int mid = (low + high) / 2; cout << "low : " << low << " high : " << high << " mid : " << mid << endl; if (target == sql.elem[mid]) { return mid; } else if (target < sql.elem[mid]) { high = mid - 1; binSearch(sql, target, low, high); } else { low = mid + 1; binSearch(sql, target, low, high); }}int main() { SqList sql = {{1, 3, 5, 7, 8, 10, 11}, 7}; cout << "current List:" << endl; print(sql); int target; cin >> target; cout << binSearch(sql, target, 0 ...
和大于等于target的最短子数组
和大于等于target的最短子数组
原题链接:https://leetcode.cn/problems/2VG8Kg/
给定一个含有 n 个正整数的数组和一个正整数 target ,
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。
如果不存在符合条件的子数组,返回 0 。
1.静态滑动窗口1遍历滑动窗口大小,每次for循环滑动窗口大小值固定,每次对滑动窗口中的内容进行求和,尝试更新答案,时间超时:
1234567891011121314151617181920class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int flag = 0; int ans = nums.size(); //遍历滑动窗口的大小 for (int len = 1; len <= nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int k = i; k < j; ++k) sum += nums[k]; if (sum >= target && len <= ans) { ans = len; flag = 1; } } } if (!flag) return 0; return ans; }};
2.静态滑动窗口2遍历滑动窗口大小,每次for循环滑动窗口大小值固定,
维护一个sum值 进行加入与减出,每次窗口移动加入与减出 ...
乘积小于K的子数组
乘积小于K的子数组
原题链接:https://leetcode.cn/problems/ZVAVXX/
1.静态滑动窗口
维护一个mul乘积 对乘积进行 * / 操作
当是当滑动窗口的长度len 非常大时, 乘积mul可能会超出数据范围 如果多个 0 ~ 1000 范围的num[i]相乘 可能超出 int 数据范围
这种方法非常容易超出int的数据范围 认定为失败的方法
123456789101112131415161718class Solution {public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { if (k == 0) return 0; int ans = 0; //遍历滑动窗口的长度 for (int len = 1; len <= nums.size(); ++len) { int mul = 1; int flag = 1; for (int i = 0; i < len; ++i) mul *= nums[i]; if (mul < k) ans++; for (int i = 1; i + len <= nums.size(); ++i) { mul /= nums[i - 1]; mul *= nums[i + len - 1]; if (mul < k) ans++; } } return ans; }};
2.动态滑动窗口
从前往后处理所有的nums[i],使用变量i、j代表窗口的左右端点(静态窗口弊端完美解决),使用变量mul记录当前窗口的乘积,
当 mul>=k 时,我们考虑将左端点i右移,同时消除左端点元素 nums[i] 对 mul 的贡献,直到mul>=k不再满足
这样就可以得到每个右端点 nums[i] 的最远左端 ...
排序数组中两个数字之和
排序数组中两个数字之和
原题链接:https://leetcode.cn/problems/kLl5u1/
给定一个已按照 升序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ,所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次。
1.双指针1234567891011121314151617181920class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { vector<int> ans; int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { ans.push_back(low); ans.push_back(high); break; } else if (sum < target) { low++; } else if (sum > target) { high--; } } return ans; }};
时间复杂度:$O(n)$
空间复杂度:$O(1)$
2.二分查找12345678910111213141516171819202122class S ...