当前位置：网站首页>leetcode--数组
leetcode--数组
2022-06-11 16:47:00 【雨幕丶】
目录
1.二分查找
二分法的条件：有序数组、没有重复元素
二分法重点：
①注意区间
左闭右闭区间：[left,right] 可以取到left == right 所以循环写成while(left<=right) right = length - 1
左闭右开区间：[left,right) 不可以取到left == right 所以循环写成while(left<right) right = length
②注意middle取值：为了防止溢出 middle = left + (right - left) / 2，因为left + right 可能会溢出
704 二分查找
第一种写法
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; //target 定义在[left,right]区间内
while(left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] > target )
{
right = middle -1;
}else if(nums[middle] < target){
left = middle + 1;
}else{
return middle;
}
}
return -1;
}
时间复杂度：O(log n)，其中 n 是数组的长度。第二种写法
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle; // target 在左区间，在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，在[middle + 1, right)中
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}35 搜索插入位置
int searchInsert(vector<int> &nums, int target){
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] > target){
right = middle - 1;
}else if(nums[middle] < target){
left = middle + 1;
}else{
return middle;
}
}
return right + 1;
}34 在排序数组中查找元素的第一个和最后一个位置
target 有三种情况：
1.target 在数组的最左边或最右边 返回[-1,-1]
2.target 在数组范围内，但是数组中不存在target 返回[-1,-1]
3.target 在数组范围内，且数组中有target 返回对应的下标
//找左边界 对于[3,3]数组如果找小于等于3的数 返回-1；找大于3的数 返回-2
int getLeftBorder(vector<int> nums, int target){
int left = 0;
int right = nums.size() - 1;
int leftborder = -2;
while(left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] >= target){
right = middle - 1;
leftborder = right;
}else{
left = middle + 1;
}
}
return leftborder;
}
//找右边界 对于[3,3]数组如果找大于3的数（包括3） 返回2；找小于3的数 返回-2
int getRightBorder(vector<int> nums, int target){
int left = 0;
int right = nums.size() - 1;
int rightborder = -2;
while(left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] > target){
right = middle - 1;
}else{
left = middle + 1;
rightborder = left;
}
}
return rightborder;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftborder = getLeftBorder(nums,target);
int rightborder = getRightBorder(nums,target);
//情况一 target在左右边界 只要有一个是-2 意味着在边界
if(leftborder == -2 || rightborder == -2) return {-1,-1};
//情况三
if(rightborder - leftborder > 1) return {leftborder + 1, rightborder - 1};
//情况二
return {-1,-1};
}69 x的平方根
思路：求平方根的时候也可以使用二分查找，left = 0 right = x,只需要判断mid平方和x的关系就能找到x的平方根，这个题要求返回的是整数部分，小数部分舍去
int mySqrt(int x) {
int left = 0,right = x;
while(left <= right){
int middle = left + (right - left)/2;
if( (long)middle * middle <= x){
left = middle + 1;
}else{
right = middle - 1;
}
}
return right;
}
//时间复杂度O(log x)
//空间复杂度O(1)367 有效的完全平方数
思路：和上面的题类似，使用二分查找，在if判断的时候不一样，分为三种情况：mid平方刚好等于num返回true;小于就left = mid + 1;大于right = mid -1
bool isPerfectSquare(int num) {
int left = 0, right = num;
while(left <= right){
int middle = left + (right - left) / 2;
if((long)middle * middle == num){
return true;
}else if((long)middle * middle < num){
left = middle + 1;
}else{
right = middle - 1;
}
}
return false;
}2.双指针
27 移除元素
移除数组中等于val值的元素，空出位置由下一个元素补上。
不能直接删除该val的原因：数组的内存地址是连续的，只能覆盖元素的值。
思路：双指针法，left和right指针开始都指向数组起始位置，如果当right指针指向的值不是要删除的元素，用left指针记录该值，然后left++；如果right指向的是要删除的元素，left指针什么都不执行，right指向下一个值，最后left的索引值就是移除元素数组的长度 （left++）
//27 移除元素
int removeElement(vector<int>& nums, int val) {
int left = 0;
for(int right = 0; right < nums.size(); right++){
if(nums[right] != val){
nums[left] = nums[right];
left++;
//上面两行代码简化成nums[left++] = nums[right];
}
}
return left;
}
时间O(n)
空间O(1)26 移动排序数组中的重复项
思路：首先判断数组大小，如果为0，直接返回0；如果数组长度大于0，从数组索引值1的位置开始使用双指针，判断方法和上一个代码一样
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if(n == 0){
return 0;
}
int left = 1,right = 1;
for(;right < n;right++){
if(nums[right] != nums[right - 1]){
nums[left] = nums[right];
left++;
}
}
return left;
}
O(n)
O(1)283 移动零
void swap(vector<int>& nums,int left,int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
void moveZeroes(vector<int>& nums) {
int left = 0, right = 0;
for(;right < nums.size(); right++){
if(nums[right] != 0){
swap(nums,left,right); //left和right相同交换操作相当于没做，如果不相同说明当前left指向的元素是0
left++;
}
}
}844 比较含退格的字符串
思路：使用双指针法，从后向前遍历字符串，定义snums是字符串s中‘#’的数量，同时也是要删除字符的数量。开始遍历字符串：
- 当遍历到 ‘#’, snums++；
- 当遍历到普通字符，判断要删除字符的数量，当snums大于0，当前字符要删掉，然后snums-1,如果snums 等于0，说明当前字符不需要删掉,此时没有需要删除的字符，退出循环。（注意退出循环的索引值)
举个例子：对于”abc#“，执行到b位置时循环就已经退出了，此时的索引值是1;对于”a#b#“循环会一直执行直到索引值是-1为止；对于'a#bc'，直接退出找#数量的循环，索引值是3
这个题代码看不懂可以举几个例子debug，看看i和j是如何变化的
bool backspaceCompare(string s, string t) {
int snums = 0, tnums = 0;
int i = s.length() -1;
int j = t.length() -1;
while(1){
for(; i >= 0; i--){
if(s[i] == '#') snums++;
else{
if(snums > 0) snums--; //大于0表示当前字符要删除，
else break; //表示当前字符不要删除，退出循环
}
}
for(;j >= 0; j--){
if(t[j] == '#') tnums++;
else{
if(tnums > 0) tnums--; //大于0表示当前字符要删除，
else break; //表示当前字符不要删除，本次循环
}
}
//对于字符串‘a#b#’ i=-1 字符串‘abc#’ j=1
//两次字符都判断完后比较s[i]和t[i]
if(i < 0 || j < 0) break; //当一个字符串已经结束了所有遍历，退出循环
if(s[i] != t[j]) return false;
i--;j--;
}
if(i == -1 && j == -1) return true;
return false;
}
时间复杂度O(n+m)
空间复杂度O(1)除了双指针外可以使用栈解决这个问题
思路：定义一个字符串a作为栈，遍历s字符串，遇到字符将其放到a中，遇到 '#' 则从a中删除一个元素
bool backspaceCompare1(string s, string t) {
string a;//当作栈使用
string b;//当作栈使用
for(int i = 0; i < s.length(); i++){
if(s[i] != '#')
a = a + s[i];
else if(!s.empty())
a.pop_back();
}
for(int i = 0; i < t.length(); i++){
if(t[i] != '#')
b = b + t[i];
else if(!t.empty())
b.pop_back();
}
if( a == b)
return true;
else
return false;
}
时间复杂度O(n+m)
空间复杂度O(n+m)977有序数组的平方
思路：把每个数的平方放到数组中，对这个数组进行排序，时间复杂度是O(n+nlongn) = O(nlogn)，也可以使用双指针法，因为数组中可能由负数，平方的最大值是数组最左边或者最右边的数，因此left指向起始位置，right指向结束位置，将最大的平方值放到新数组的末尾，新数组和原数组长度一样。
vector<int> sortedSquares(vector<int>& nums) {
int k = nums.size() - 1;
vector<int> newnums(nums.size(),0); //每个元素为0
int left = 0, right = nums.size()- 1;
while(left <= right){
if(nums[left] * nums[left] <= nums[right] * nums[right]){
newnums[k] = nums[right] * nums[right];
k--;
right--;
}else { //[left]^2 > [right]^2
newnums[k] = nums[left] * nums[left];
k--;
left++;
}
}
return newnums;
}
时间复杂度O(n)
空间复杂度O(1)3.滑动窗口
209 长度最小的子数组
思路：第一种使用两个for循环遍历，找符合要求的子数组。
int minSubArrayLen(vector<int> nums,int s){
//初始化子数字的最小长度是无穷大 INT_MAX
int length = INT_MAX;
for(int i = 0; i < nums.size(); i++){
int sum = 0;
for(int j = i; j < nums.size(); j++){
sum += nums[j];
if(sum >= s){
length = min(length, j - i + 1);
break;
}
}
}
return length == INT_MAX ? 0 : length;
}思路：暴力法复杂度是O(n^2),也可以使用滑动窗口法，不断调节子序列的起始位置和终止位置。i和j开始都指向0，j往后移动，只要当 当前窗口的值大于s，窗口需要向后移动，也就是i++,此时窗口内元素之和是sum - nums[i].
int minSubArrayLen(int target, vector<int>& nums) {
int length = INT_MAX; //返回子数组的长度
int sum = 0;
int i = 0,j = 0;
while(j < nums.size()){
sum += nums[j];
while(sum >= target){ //当前窗口满足s
length = min(length, j - i + 1);
sum = sum - nums[i];
i++;
}
j++;
}
return length == INT_MAX ? 0 : length;
}904 水果成篮
思路：这个题理解为 含两种元素的最大连续子序列
right向右移动，如果fruits[right]指向的是两种水果的一种，计算当前长度，然后right右移；如果fruits[right]不是两种水果中的一个将left移动到right前一个位置，这里left需要往前找是否有相同的数，条件是left大于等于一（如果left等于0就不需要往前找）同时left-1和left指向的数相同，满足条件left-1继续找，找到最前面的left后计算此时的长度
int totalFruit(vector<int>& fruits) {
int left = 0, right = 0;
int length = 0;
int a = fruits[left], b = fruits[right];
while(right < fruits.size()){
if(fruits[right] == a || fruits[right] == b){ //right指向的满足两种水果中的一种
length = max(length , right - left + 1);
right++;
}else{ //不满足，left = right - 1 同时left也需要往前找是否有相同的
left = right - 1;
a = fruits[left];
while(left >= 1 && fruits[left-1] == a){ //left往前找，如果此时left已经是0就没必要往前，所以left大于1 同时判断left-1 是否和left 指向的数相同
left--; //满足条件再次继续往前找
}
//left已经找到最前面
b = fruits[right];
length = max(length , right - left + 1);
}
}
return length;
}总结:209 长度最小的子数组 和 904 水果成篮 分别是求满足条件的最小子数组和最大子数组。
对于最小数组:L和R指向起始位置，R向右移动，如果窗内元素满足条件，L向右缩小窗口，计算最优结果；如果窗内元素不满足条件，R继续向右扩大。
while ( R < s.size()) { 窗口右端扩展，加进s[R], 更新条件 while(满足条件) { 比较最小长度 窗口左端移除s[L]，更新条件，L++ } R++; }对于最大数组模板：L和R指向起始位置，R向右移动，如果窗内元素满足条件,R向右移动扩大窗口，更新结果；如果窗口内元素不满足条件，L向右缩小窗口。
while ( R < s.size()) { 窗口右端扩展，加进s[R], 更新条件 while(不满足条件) { 窗口左端移除s[L]，更新条件，然后L++ } 比较最大长度 R++; }
对于子串问题也可以使用滑动窗口问题，有大佬总结过子串问题的模板
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
//need记录的是t字符出现次数，window记录当前窗口字符出现次数
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
//valid 表示窗口内满足need 条件的字符个数，如果valid = need.size 说明当前窗口完全覆盖了t字符串
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
// 判断左侧窗口是否要收缩
while (window needs shrink) {
//如果是求最小子串，在这里更新最终结果
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
//如果是求最大子串，在这里更新最终结果
}
return
}两处... 是更新窗口数据的地方，使用模板需要注意四个问题：
1.移动right扩大窗口时需要更新哪些数据？
2.什么时候开始缩小窗口（移动left）?
3.移动left时哪些数据需要更新?
4.需要的结果在扩大窗口还是缩小窗口时更新？ 对于求最小类问题，在缩小窗口更新最终结果
76 最小覆盖子串 相当于求满足条件的最小子串
思路：①当字符进入窗口时，增加window计数器；②当valid = need.size时缩小窗口；③字符移除窗口减少window计数器；④缩小窗口时更新最终结果
string minWindow(string s, string t) {
unordered_map<char,int>need, window; //need是t字符出现次数
for(char a : t)
need[a]++;
int left = 0, right = 0;
int valid = 0; //valid 表示窗口内满足need 条件的字符个数，如果valid = need.size 说明当前窗口完全覆盖了t字符串，然后缩小敞口
//记录最小字符串的起始索引和长度
int start = 0, len = INT_MAX;
while(right < s.length()){
char a = s[right]; //a是进入窗口的字符
right++;
//窗口内更新数据
if(need.count(a)){ //count 容器内key返回1，否则返回0
window[a]++;
if(window[a] == need[a]) //对于同一个字符两个容器记录的次数相同
valid++;
}
//窗口收缩
while(valid == need.size()){
//更新最终结果
if(right - left < len){
start = left;
len = right - left;
}
//判断是否有字符需要移除
char b = s[left];
left++;
//更新窗口数据
if(need.count(b)){
if(window[b] == need[b]) //某一字符出现次数相同
valid--; //退出缩小窗口
window[b]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start,len);
}3 最长无重复子串 相当于求满足条件的最大子串
int lengthOfLongestSubstring2(string s) {
unordered_map<char,int>window;
int left = 0, right = 0;
int length = 0;
while(right < s.length()){
char ref = s[right];
right++;
//更新窗口数据
window[ref]++;
//收缩窗口
while(window[ref] > 1){
char cur = s[left];
left++;
//更新窗口
window[cur]--;
}
//更新最终结果
length = max(length,right - left);
}
return length;
}4.螺旋矩阵
54 螺旋矩阵
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size();
int n =matrix[0].size();
vector<int>ans;
int up = 0, down = m - 1, left = 0, right = n - 1;
while(1){
//上边界开始 从左向右遍历，遍历完上边界下移，如果上边界移动比下边界还要大，退出循环
for(int i = left; i <= right; i++) ans.push_back(matrix[up][i]);
if(++up > down) break;
//右边界，从上往下遍历，遍历完右边界左移
for(int i = up; i <= down; i++) ans.push_back(matrix[i][right]);
if(--right < left) break;
//下边界，从右往左遍历，遍历完下边界上移
for(int i = right; i >= left; i--) ans.push_back(matrix[down][i]);
if(--down < up) break;
//左边界，从下往上遍历,遍历完左边界右移
for(int i = down; i >= up; i--) ans.push_back(matrix[i][left]);
if(++left > right) break;
}
return ans;
}59 螺旋矩阵Ⅱ
vector<vector<int>> generateMatrix(int n) {
int up = 0, down = n - 1, left = 0, right = n - 1;
int num = 1;
vector<vector<int>> ans(n,vector<int>(n));
while(1){
//上边界开始 从左向右遍历，遍历完上边界下移，如果上边界移动比下边界还要大，退出循环
for(int i = left; i <= right; i++) ans[up][i] = num++;
if(++up > down) break;
//右边界，从上往下遍历，遍历完右边界左移
for(int i = up; i <= down; i++) ans[i][right] = num++;
if(--right < left) break;
//下边界，从右往左遍历，遍历完下边界上移
for(int i = right; i >= left; i--) ans[down][i] = num++;
if(--down < up) break;
//左边界，从下往上遍历,遍历完左边界右移
for(int i = down; i >= up; i--) ans[i][left] = num++;
if(++left > right ) break;
}
return ans;
}边栏推荐
- solr（一）solr的安装及权限控制
- tornado环境搭建及基本框架搭建——熟悉的hello world
- The micro service failed to connect to the cloud sentinel console and the link blank problem occurred after the connection was successful (resolved)
- VLAN partition and routing between VLANs
- Text driven for creating and editing images (with source code)
- Student website template brown cake dessert website design - brown cake dessert shop (4 pages) gourmet dessert website production final assignment finished product_ Fresh fruit web design final assign
- leetcode463. Perimeter of the island (simple)
- Classic reading of multi task learning: MMOE model
- RSP: An Empirical Study of remote sensing pre training
- [Clickhouse column] create a new library, user and role
猜你喜欢
2022年安全员-B证国家题库及模拟考试
一套ThinkPHP微信小程序商城源码带后台管理
基于udp端口猜测的内网穿透
数据库全量SQL分析与审计系统性能优化之旅
![[Clickhouse column] create a new library, user and role](/img/e5/d11493a37e25b7dde6cc43b3828749.png)
[Clickhouse column] create a new library, user and role
A set of ThinkPHP wechat applet mall source code with background management
2022 R1 quick opening pressure vessel operation test question bank and simulation test
R1 Quick Open Pressure Vessel Operation test Library and Simulation Test in 2022
C语言各数据类型的内存映像
2022年R1快开门式压力容器操作考试题库及模拟考试
随机推荐
Analysis report on sales status and supply and demand prospects of phosphoric acid fuel cell industry in the world and China 2022-2028 Edition
ASP.NET教育OA系统源码 教育行业OA系统源码带文档
Why does chip design also need "Craftsmanship"?
多任务学习经典品读：MMoE模型篇
Rdkit installation
美团获得小样本学习榜单FewCLUE第一！Prompt Learning+自训练实战
GemBox.Bundle 43.0 Crack
solr（二）solr添加core以及依赖包路径
2022 R1 quick opening pressure vessel operation test question bank and simulation test
Redis --- 学习 NoSQL 五大类型
【opencvsharp】斑点检测 条码解码 图像操作 图像旋转/翻转/缩放 透视变换 图像显示控件 demo笔记
药物评价指标
Katalon Studio Enterprise
[ISITDTU 2019]EasyPHP
2022年危险化学品经营单位主要负责人考试模拟100题及模拟考试
Difference between select into from and insert into select
关联关系
The micro service failed to connect to the cloud sentinel console and the link blank problem occurred after the connection was successful (resolved)
Pytest test framework Basics
微信小程序时间戳转化时间格式+时间相减