數(shù)組基礎理論
1.數(shù)組的基本特征
1）下標從0開始
2）連續(xù)數(shù)組內(nèi)存空間地址是連續(xù)的
3）數(shù)組元素不能刪除，只能覆蓋（也就是說，如果要刪除數(shù)組內(nèi)的一個元素，需要把之后的所有元素依次挪動）
2.C++中的數(shù)組實現(xiàn)
C++中數(shù)組實現(xiàn)包括vector和array。
1）vector
vector屬于STL容器，不是數(shù)組，其迭代器包括：first、last和end。
擴容方式包括：固定擴容（空間利用率高但是時間復雜度高）和加倍擴容（空間利用率低但是時間復雜度低）。實際應用通常用空間換時間。
vector的部分函數(shù)：
2）array
vector的底層實現(xiàn)是array。
704二分查找
思考過程：
分而治之的方法，不斷迭代，直到只剩一個元素，進行判斷。。
但是這好像效率并沒有提高，和遍歷檢測相比，是不是不斷循環(huán)調(diào)用耗費的時間更多？
好了，有這個思路想試試也寫不出來，代碼能力太差了，看解析去了
看解答：
我忽視了數(shù)組是有序排列這個必要條件了，這樣就只需要比較和中間值的大小就可以確定是哪個區(qū)間了。之前想的思路是遞歸不是二分emmm
試著按照這個思路寫下，我覺得二分的難點主要是邊界值的確定上
自己試寫一版：
class?Solution?{
public:
????int?search(vector<int>&?nums,?int?target)?{
????????int?left?=?0;
????????int?right?=?size(nums);
????????int?mid;
????????while(left?<=?right){
????????????mid?=?(right?-?left)?/?2;
????????????if(target?==?nums[mid])?return?mid;
????????????else?if(target?<?nums[mid]){
????????????????right?=?mid;
????????????}
????????????else?if(target?>?nums[mid]){
????????????????left?=?mid;
????????????}
????????}
????????return?-1;
????}
};
錯誤：超出時間限制
為啥呢？是不是while沒跑出來？
突然發(fā)現(xiàn)我的right最開始設置的size，雖然對后面沒什么影響，但是要注意最后的標號是size-1
發(fā)現(xiàn)我的mid賦值在while里面?。?！這樣mid一直是一樣的達不到二分的效果，肯定跑不出循環(huán)
修改了還是超時
class?Solution?{
public:
????int?search(vector<int>&?nums,?int?target)?{
????????int?left?=?0;
????????int?right?=?nums.size()-1;
????????int?mid?=?(right?-?left)?/?2;;
????????while(left?<=?right){
????????????if(target?==?nums[mid])?return?mid;
????????????else?if(target?<?nums[mid]){
????????????????right?=?mid?-?1;
????????????????mid?=?(right?-?left)?/?2;
????????????}
????????????else?if(target?>?nums[mid]){
????????????????left?=?mid?+?1;
????????????????mid?=?(right?-?left)?/?2;
????????????}
????????}
????????return?-1;
????}
};
思考了一下之前的left和right是一直變的，倒是也可以，反而是現(xiàn)在的代碼麻煩了
好的看了答案，沒有把mid的值設置對
class?Solution?{
public:
????int?search(vector<int>&?nums,?int?target)?{
????????int?left?=?0;
????????int?right?=?nums.size()-1;
????????while(left?<=?right){
????????????int?mid?=?left?+?(right?-?left)?/?2;
????????????if(target?==?nums[mid])?return?mid;
????????????else?if(target?<?nums[mid]){
????????????????right?=?mid?-?1;
????????????}
????????????else?if(target?>?nums[mid]){
????????????????left?=?mid?+?1;
????????????}
????????}
????????return?-1;
????}
};
可以通過
總結：
1.注意題目中給定數(shù)據(jù)是不是有序的
2.注意左右區(qū)間的取值，判斷的范圍
3.注意中值的賦值
27.移除元素
思考過程：
題目中給定的數(shù)據(jù)是無序的，用二分法不合適（所以是不是能推斷出二分法僅僅適用于有序數(shù)組？）
查找和刪除移動元素很簡單，用for就可以實現(xiàn)，題目中規(guī)定了O（1）的額外空間不知道超不超，試試
class?Solution?{
public:
????int?removeElement(vector<int>&?nums,?int?val)?{
????????int?time=0;
????????for(int?i?=?0;i?<?nums.size();?i++){
????????????if?(nums[i]?==?val){
????????????????time?=?time?+?1;
????????????????for(int?j?=?i;?j?<?nums.size()?-?1; j++){
????????????????????nums[j]?=?nums[j?+?1];
????????????????}
????????????}
????????}
????????return?time;
????}
};
解答錯誤，從輸出來看，應該是邊界出了問題
仔細一看確實，沒有覆蓋掉，可是最后一個怎么刪除呢？數(shù)組不是不能刪除嗎？
看代碼隨想錄
還是出現(xiàn)了邊界值的問題，沒有考慮覆蓋后的邊界值變化和數(shù)組大小的變化
改變后
class?Solution?{
public:
????int?removeElement(vector<int>&?nums,?int?val)?{
????????int?time=0;
????????int?size=nums.size();
????????int?i?;
????????for(i?=?0;i?<?size;?i++){
????????????if?(nums[i]?==?val){
????????????????time?=?time?+?1;
????????????????for(int?j?=?i;?j?<?size?-?1;?j++){
????????????????????nums[j]?=?nums[j?+?1];
????????????????}
????????????}
????????}
????????size--;
????????i--;
????????return?time;
????}
};
還是有邊界值的問題，卡哥代碼寫的j-1開始，是不太像這里的問題，但是試試
果然不是這里的問題
是位置的問題，并且我把題目看錯了....
class?Solution?{
public:
????int?removeElement(vector<int>&?nums,?int?val)?{
????????int?time=0;
????????int?size=nums.size();
????????int?i?;
????????for(i?=?0;i?<?size;?i++){
????????????if?(nums[i]?==?val){
????????????????time?=?time?+?1;
????????????????for(int?j?=?i+1;?j?<?size;?j++){
????????????????????nums[j-1]?=?nums[j?];
????????????????}
????????????????size--;
????????????????i--;
????????????}
????????}
????????return?size;
????}
};
暴力居然AC了.....
（啊~~~~剛剛筆試完，感覺前面思考的都忘了）
雙指針沒有學過，直接看代碼隨想錄
雙指針：一個快指針一個慢指針，用一個for循環(huán)實現(xiàn)兩個for循環(huán)的工作；
當快指針檢測到目標值時，只有快指針向前運動，慢指針不動；
當沒有檢測到目標值時，快指針慢指針都向前運動。如果兩個指針指向不同，快指針的值覆蓋慢指針指向的位置。
看了卡哥代碼之后我思考好像復雜了，不需要判斷兩個指針是不是指向不一樣，強制覆蓋就可以。
這道題實際上是用指針的思想，并沒有真正的使用指針，看到雙指針名字的時候差點被勸退~~~
讓我把這個思想復現(xiàn)一下
class?Solution?{
public:
????int?removeElement(vector<int>&?nums,?int?val)?{
????????int?slowIndex?=?0;
????????int?fastIndex?;
????????for(fastIndex?=?0;fastIndex?<?nums.size();?fastIndex++){
????????????if(nums[fastIndex]?==?val){
????????????????nums[slowIndex]?=?nums[fastIndex];
????????????????slowIndex?++;
????????????}
????????}
????????return?slowIndex;
????}
};
居然報錯了，看看是哪里和卡哥不一樣
整個思路沒有錯，居然是判斷正好寫反了?。?/b>他的測試用例剛好是四個，兩個相同兩個不同就通過了...
class?Solution?{
public:
????int?removeElement(vector<int>&?nums,?int?val)?{
????????int?slowIndex?=?0;
????????int?fastIndex?;
????????for(fastIndex?=?0;fastIndex?<?nums.size();?fastIndex++){
????????????if(nums[fastIndex]?!=?val){
????????????????nums[slowIndex]?=?nums[fastIndex];
????????????????slowIndex?++;
????????????}
????????}
????????return?slowIndex;
????}
};
AC啦??！
總結：
1.認真讀題??！
2.注意判斷條件有沒有寫反！
3.雙指針并不是真的使用了兩個指針，是使用指針指向的思想，將兩個for循環(huán)節(jié)省為一個for循環(huán)
4.感覺雙指針用起來很靈活，適合數(shù)組“刪除“類題目，其他題目做到之后再補充。
好啦我要開始大總結啦
今天是刷代碼隨想錄第一天，中間有筆試和各種事情，沒有具體統(tǒng)計時長，但是感覺是超了4小時的。
我的代碼實現(xiàn)能力真的太差了??！中間出了奇奇怪怪的問題，比如賦值沒賦對，沒考慮邊界，判斷條件寫反！多練一練復現(xiàn)！
啊對還有我的讀題能力emmmm
拿到題不用著急做，先把題讀明白，思路捋清楚做題更快~
明天見~~
