從今天開始更新數(shù)據(jù)結(jié)構(gòu)的相關(guān)內(nèi)容。（我更新博文的順序一般是按照我當(dāng)前的學(xué)習(xí)進(jìn)度來安排，學(xué)到什么就更新什么（簡單來說就是我的學(xué)習(xí)筆記），所以不會對一個專欄一下子更新到底，哈哈哈哈哈哈哈！！！😄）

---

本專欄以力扣為落腳點(diǎn)，以實(shí)際題目為依據(jù)來進(jìn)行相應(yīng)知識點(diǎn)的講解和應(yīng)用，希望對你能有所幫助！

廢話不多說，我們直接開始！

---

---

🔥LC 2057 ----值相等的最小索引(簡單)

題目鏈接：https://leetcode.cn/problems/smallest-index-with-equal-value/

題目簡介：

給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums ，返回 nums 中滿足 i mod 10 == nums[i] 的最小下標(biāo) i ；如果不存在這樣的下標(biāo)，返回 -1 。

• x mod y 表示 x 除以 y 的 余數(shù) 。

這道題就很簡單了，按照題目說的條件，直接線性枚舉（可以理解為直接遍歷）一遍，就可找出答案。

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

代碼示例：

class Solution {
public:int smallestEqual(vector<int>& nums) {//獲取數(shù)組長度int n=nums.size();for(int i=0;i<n;i++){if(i%10==nums[i]) return i;}return -1;}
};

可能會有人問，二分查找行不行，答案是不行！因?yàn)閚ums數(shù)組的元素之間并沒有特定的聯(lián)系（是無序的），不適合二分。

既然談到了，那就簡單說說什么是二分吧。

??二分查找（Binary Search）：

是一種在有序數(shù)組中查找目標(biāo)值的算法。它通過將目標(biāo)值與數(shù)組的中間元素進(jìn)行比較，從而確定目標(biāo)值可能存在的位置。

下面是一個簡單的函數(shù)模板：

int firstBadVersion(int *arr,int n) {//定義左右邊界，這里我稱left和right為游標(biāo)，而不是指針！避免混淆
int left=-1,right=n;//定義中點(diǎn)
int mid=0;//進(jìn)行二分
while(right-left>1){//記錄中點(diǎn)
mid=left+(right-left)/2;//滿足條件時：
if(arr[mid]滿足條件){//移動游標(biāo)
right=mid;
}
//不滿足條件時：
else{
left=mid;
}
}
return right;
}

1. 可能有人會問，游標(biāo)為什么要取-1和n，不能取0和n-1嗎？他們的中點(diǎn)不應(yīng)該一樣嗎？

   答：其實(shí)這是為了避免極端情況的發(fā)生，如果左右邊界（即0和n-1）滿足條件時，二分查找會出錯，你可以想想為什么。

2. 換位置時，一定是滿足條件時換right嗎？

   答：不一定，這個得具體情況具體分析！

---

🔥LC 1464 ----數(shù)組中兩元素的最大乘積（簡單）

題目鏈接：https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/?envType=list&envId=7q99qCXM

題目簡介：

給你一個整數(shù)數(shù)組 nums，請你選擇數(shù)組的兩個不同下標(biāo) i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
請你計算并返回該式的最大值。

代碼示例：

class Solution {
public:int maxProduct(vector<int>& nums) {//這里直接調(diào)用sort函數(shù)排序：sort(nums.begin(),nums.end());//獲取數(shù)組長度int len=nums.size();//返回結(jié)果return (nums[len-1]-1)*(nums[len-2]-1);}
};

這里我們用到了sort函數(shù)，sort函數(shù)的時間復(fù)雜度通常為O(n log n)，所以我決定寫一個O(n)的解法出來：

class Solution {
public:int maxProduct(vector<int>& nums) {int n=nums.size();int max=0;//最大值int maxIndex;//最大值索引int sec=0;//次大值int secIndex;//次大值索引int i,j;//尋找最大值和其索引for(i=0;i<n;i++){if(nums[i]>max) {max=nums[i];maxIndex=i;}}//尋找次大值和其索引for(j=0;j<n;j++){if(j!=maxIndex){if(nums[j]>sec) {        sec=nums[j];   secIndex=j;            }}}int maxSum=(max-1)*(sec-1);return maxSum;}
};

既然用到了sort函數(shù)，那就來簡單介紹一下：

??sort函數(shù)：

是一種常見的排序算法，它能夠?qū)⒁粋€數(shù)組或容器中的元素按照指定的排序規(guī)則進(jìn)行排列。

• 在C++語言中，sort函數(shù)在< algorithm >頭文件中。
• 基本形式：sort(first,end,comp)

其中，first和last是表示待排序范圍的迭代器，comp是一個可選的比較函數(shù)，用于指定排序規(guī)則。如果不提供comp參數(shù)，則默認(rèn)按照升序排序。要想降序的話，第三個參數(shù)可以寫成greater<int>()，其中<>里面也可以寫double，long，float等等

• 總的來說：
  升序：sort(first,end,cmp)或者sort(first,end)
  降序：sort(first,end,greater<int>()）

---

🔥LC 485----最大連續(xù) 1 的個數(shù)（簡單）

題目鏈接：https://leetcode.cn/problems/max-consecutive-ones/?envType=list&envId=7q99qCXM

題目簡介：

給定一個二進(jìn)制數(shù)組 nums ， 計算其中最大連續(xù) 1 的個數(shù)。

代碼示例：

class Solution {
public:int findMaxConsecutiveOnes(vector<int>& nums) {int n=nums.size();//最長1的個數(shù)int maxLenOne=0;//計數(shù)器：1出現(xiàn)的個數(shù)int countOne=0;for(int i=0;i<n;i++){if(nums[i]==1) countOne++;//計數(shù)器：遇1自增else{          maxLenOne= (maxLenOne>countOne)?maxLenOne:countOne;//對長度賦值countOne=0;//計數(shù)器歸0}}//邊界值：可能最后一個數(shù)不是0，所以最后一段1的值沒有被比較，在此比較一次，防止遺漏最優(yōu)解maxLenOne= (maxLenOne>countOne)?maxLenOne:countOne;return maxLenOne;}
};

---

🔥LC 27---- 移除元素（簡單）

題目鏈接：https://leetcode.cn/problems/remove-element/?envType=list&envId=7q99qCXM

題目簡介：

給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。

代碼示例：

class Solution {
public:int removeElement(vector<int>& nums, int val) {// int n=0;for(int i=0;i<nums.size();i++){if(nums[i]==val){// n=i;nums.erase(nums.begin()+i);i=i-1;}}return nums.size();}
};

這里就是一個線性枚舉，然后對當(dāng)前值進(jìn)行一個判斷，如果等于目標(biāo)值，就將其刪除，用到了vector:erase()函數(shù)。

??vector中刪除元素的方法總結(jié)：

vector中刪除元素大概有這么幾種方法：

• nums.pop_back(); //刪除最后一個元素
• nums.clear(); //清空nums中的元素
• nums.erase(nums.begin()+i,nums.begin()+j); //刪除nums中從第i+1個元素到第j+1個的所有元素，也就是索引[i,j]。寫成nums.erase(nums.begin()+i)就是直接刪除第i+1個元素（下標(biāo)為i）

---

🔥LC 665----非遞減數(shù)列（中等）

題目鏈接：https://leetcode.cn/problems/non-decreasing-array/?envType=list&envId=7q99qCXM

題目簡介：

給你一個長度為 n 的整數(shù)數(shù)組 nums ，請你判斷在 最多 改變 1 個元素的情況下，該數(shù)組能否變成一個非遞減數(shù)列。
我們是這樣定義一個非遞減數(shù)列的： 對于數(shù)組中任意的 i (0 <= i <= n-2)，總滿足 nums[i] <= nums[i + 1]。

代碼示例：

class Solution {
public:bool checkPossibility(vector<int>& nums) {int n=nums.size();if(n==1 || n==2) return true;int count=0;int count1=0;int count2=0;vector<int>num1(nums);vector<int>num2(nums);for(int i=1;i<n;i++){if(nums[i]<nums[i-1]){                                        nums[i-1]=nums[i];                break; }   }for(int i=1;i<n;i++){if(num1[i]<num1[i-1]){num1[i]=num1[i-1];        break;}    }for(int i=1;i<n;i++){if(num2[i]<num2[i-1]){if(i+1<n){num2[i]=num2[i+1];    break; } else num2[i]=num2[n-2];                         }    }        for(int i=1;i<n;i++){if(num1[i]<num1[i-1]) count1=1;if(nums[i]<nums[i-1]) count=1;if(num2[i]<num2[i-1]) count2=1;if(count==1 && count==1 && count2==1) return false;}  return true;}
};

這道題我用的是枚舉的方法，暫時沒啥更優(yōu)化的方法，以后想到了會進(jìn)行更新！

---