數組基礎理論
1.數組的基本特征
1）下標從0開始
2）連續(xù)數組內存空間地址是連續(xù)的
3）數組元素不能刪除累颂，只能覆蓋（也就是說滞详，如果要刪除數組內的一個元素，需要把之后的所有元素依次挪動）
2.C++中的數組實現
C++中數組實現包括vector和array紊馏。
1）vector
vector屬于STL容器料饥，不是數組，其迭代器包括：first朱监、last和end岸啡。
擴容方式包括：固定擴容（空間利用率高但是時間復雜度高）和加倍擴容（空間利用率低但是時間復雜度低）。實際應用通常用空間換時間赫编。
vector的部分函數：
2）array
vector的底層實現是array巡蘸。
704二分查找
思考過程：
分而治之的方法，不斷迭代擂送，直到只剩一個元素悦荒，進行判斷。嘹吨。
但是這好像效率并沒有提高搬味，和遍歷檢測相比，是不是不斷循環(huán)調用耗費的時間更多躺苦？
好了身腻，有這個思路想試試也寫不出來，代碼能力太差了匹厘，看解析去了
看解答：
我忽視了數組是有序排列這個必要條件了嘀趟，這樣就只需要比較和中間值的大小就可以確定是哪個區(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ā)現我的right最開始設置的size炕柔，雖然對后面沒什么影響酌泰，但是要注意最后的標號是size-1
發(fā)現我的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是一直變的欢嘿，倒是也可以衰琐，反而是現在的代碼麻煩了
好的看了答案也糊，沒有把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.注意題目中給定數據是不是有序的
2.注意左右區(qū)間的取值，判斷的范圍
3.注意中值的賦值
27.移除元素
思考過程：
題目中給定的數據是無序的羡宙，用二分法不合適（所以是不是能推斷出二分法僅僅適用于有序數組狸剃？）
查找和刪除移動元素很簡單，用for就可以實現狗热，題目中規(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;
????}
};
解答錯誤，從輸出來看匿刮，應該是邊界出了問題
仔細一看確實僧凰，沒有覆蓋掉，可是最后一個怎么刪除呢僻焚？數組不是不能刪除嗎允悦？
看代碼隨想錄
還是出現了邊界值的問題，沒有考慮覆蓋后的邊界值變化和數組大小的變化
改變后
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)實現兩個for循環(huá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;
????}
};
居然報錯了，看看是哪里和卡哥不一樣
整個思路沒有錯瘾带，居然是判斷正好寫反了Ｊ蟾纭！他的測試用例剛好是四個，兩個相同兩個不同就通過了...
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.感覺雙指針用起來很靈活，適合數組“刪除“類題目谴垫，其他題目做到之后再補充章母。
好啦我要開始大總結啦
今天是刷代碼隨想錄第一天，中間有筆試和各種事情翩剪，沒有具體統(tǒng)計時長乳怎，但是感覺是超了4小時的。
我的代碼實現能力真的太差了Ｇ巴洹蚪缀！中間出了奇奇怪怪的問題，比如賦值沒賦對恕出，沒考慮邊界询枚，判斷條件寫反！多練一練復現浙巫！
啊對還有我的讀題能力emmmm
拿到題不用著急做金蜀，先把題讀明白，思路捋清楚做題更快~
明天見~~
