淘宝客建站模板,国外开源商城系统,wordpress编辑器插件ueditor,网站内部链接是怎么做的文章目录 二分查找题目描述题解 移除元素题目描述题解#xff1a;暴力解法题解#xff1a;双指针法 有序数组的平方题目描述题解#xff1a;暴力解法题解#xff1a;双指针法 长度最小的子数组题目描述题解#xff1a;暴力解法题解#xff1a;滑动窗口#xff08;双指针… 文章目录 二分查找题目描述题解 移除元素题目描述题解暴力解法题解双指针法 有序数组的平方题目描述题解暴力解法题解双指针法 长度最小的子数组题目描述题解暴力解法题解滑动窗口双指针 螺旋矩阵II题目描述题解 二分查找
力扣题目链接
题目描述
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
示例
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4 题解
class Solution {
public:int search(vectorint nums, int target) {int low0,high nums.size()-1,mid;while (lowhigh){mid(lowhigh)1;if (nums.at(mid) target)return mid;else if(nums.at(mid)target) high mid-1;else low mid1;}return -1;}
};移除元素
力扣题目链接
题目描述
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums [3,2,2,3], val 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums [0,1,2,2,3,0,4,2], val 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
题解暴力解法
class Solution {
public:int removeElement(vectorint nums, int val) {size_t len nums.size();for (int i 0; i len; i) {if(nums[i] val){for (int j i; j len-1; j) {nums[j] nums[j1];}--i;// 因为下标i以后的数值都向前移动了一位所以i也向前移动一位--len;}}return len;}
};题解双指针法
class Solution {
public:int removeElement(vectorint nums, int val) {int slowIndex{0},fastIndex{0};while (fastIndexnums.size()){if(val!nums[fastIndex])nums[slowIndex] nums[fastIndex];fastIndex;}return slowIndex;}
};有序数组的平方
力扣题目链接
题目描述
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 1
输入nums [-4,-1,0,3,10] 输出[0,1,9,16,100] 解释平方后数组变为 [16,1,0,9,100]排序后数组变为 [0,1,9,16,100] 示例 2
输入nums [-7,-3,2,3,11] 输出[4,9,9,49,121]
题解暴力解法
先平方后排序
class Solution {
public:vectorint sortedSquares(vectorint nums) {for (auto item: nums)item*item;sort(nums.begin(),nums.end());return nums;}
};题解双指针法
分析 数组是有序的那么数组里面的元素平方之后的最大值要么是开头的要么是结尾的依次移动
class Solution {
public:vectorint sortedSquares(vectorint nums) {size_t n nums.size()-1;size_t slowIndex{0},fastIndex{n};vectorintresult(n1,0);while (slowIndexfastIndex) {int s1 nums[slowIndex] * nums[slowIndex],s2 nums[fastIndex] * nums[fastIndex];if (s1 s2){result[n--] s1;slowIndex;}else {result[n--] s2;--fastIndex;}}result[0]nums[slowIndex]*nums[slowIndex];return result;}
};代码简写的版本
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;}
};长度最小的子数组
力扣题目链接
题目描述
给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。
示例
输入s 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 提示
1 target 10^9 1 nums.length 10^5 1 nums[i] 10^5
题解暴力解法
已经超时
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {size_t len nums.size();if (len 0)return 0;int min_o INT_MAX;for (int i 0; i len; i) {int sum{0};for (int j i; j len; j) {sum nums[j];if (sum target){min_o (min_o (j - i 1)) ? min_o : (j - i 1);break;}}}return min_o INT_MAX ? 0 : min_o;}
};题解滑动窗口双指针
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {size_t len nums.size();// beg起始位置 sum总和 result最终的结果int beg{0}, sum{0}, result{INT_MAX};// i是一个中止位置for (int i 0; i len; i) {sum nums[i];// 持续更新起始位置当满足条件的时候起始位置前移while (sum target) {// 选择最小窗口result (result (i - beg 1)) ? result : (i - beg 1);sum - nums[beg];}}return result INT_MAX ? 0 : result;}
};螺旋矩阵II
力扣题目链接
题目描述
给定一个正整数 n生成一个包含 1 到 n^2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
题解
class Solution {
public:vectorvectorint generateMatrix(int n) {vectorvectorintv(n,vectorint(n,0));//offset偏移量 count总数int offset{1},start_x{0},start_y{0},i{0},j{0},count{1};// 循环n/2次 奇数特殊处理一下 偶数直接结束int loop n/2;//循环的次数while(loop--){for (j start_y; j n - offset; j)v[start_x][j] count;for (i start_x ; i n - offset; i)v[i][j] count;for (; j start_y; --j)v[i][j] count;for (; i start_x; --i)v[i][j] count;start_x;start_y;offset;}if (n%2!0)v[n/2][n/2] count;return v;}
};
