当前位置：首页 > news >正文

代码随想录day1数组/字符串总结

news 来源：原创 2024/9/19 9:11:32

二分法
- 按左闭右闭的区间处理
- 适合已经完成排序的，找target数——减少暴力遍历

元素移动类题目

两种方法：

1、双指针

移动规则不同：

移动条件不同\fast一次跳两步，slow一次一步

适合解决元素移动/排序/查找

链表中找环

fast在后面遍历每一个数，slow在需要插入位置

只有在需要插入的时候，fast赋值到slow，且slow向前移动

格式：for（fast遍历每个元素）

if（需要插入）fast->slow；slow++

27. 移除元素

力扣题目链接(opens new window)

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

int removeElement(int* nums, int numsSize, int val) {int k=0;for (int i=0;i<numsSize;i++){if(nums[i]!=val){nums[k]=nums[i];k++;}}return k;
}

977.有序数组的平方

力扣题目链接(opens new window)

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

分析：因为最大值肯定在最左\最右侧，可以通过双指针+创建新的数组空间得到答案

2、直接遍历

关键：注意遍历方向，减少移动的次数——优先从后往前遍历

eg：从前往后遍历，一个需要删除，那么后面的都需要移动

3、向左右移动k个元素

reverse三次

子串类题目

1、滑动窗口（其实是一种双指针）

是对暴力循环子串开头和结尾的优化

按照某个条件——不断的调节子序列的起始位置和终止位置——得出我们要想的结果

通常模式：

for 对于正在考虑的元素i

如果不符合条件了，就出队前元素直至符合条件

实际上任何条件都可以进队

每次符合条件，都构成一个输出

**涉及到子串的字母构成，会用到哈希表

209.长度最小的子数组

力扣题目链接(opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

int minSubArrayLen(int target, int* nums, int numsSize) {int l=0,r=0,sum=nums[0];int ansmin=INT_MAX;if(sum>=target) return 1;while(r+1<numsSize){r++;sum+=nums[r];if(sum>=target){ansmin = fmin(ansmin,r-l+1);}while(sum - nums[l]>=target){sum-=nums[l];l++;ansmin=fmin(ansmin,r-l+1);}}if(ansmin==INT_MAX) return 0;return ansmin;
}