leetcode刷題日記[Array專題]

1.Remove Element

這個一開始自己沒想那麼多，就直接erase删除。

代碼：

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

送出後看到評論，感覺直接用數組偏移來做比較好

代碼：

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

2.Remove Duplicates from Sorted Array

這裡就直接用數組偏移

代碼:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0)return 0;
        int shift_left=0;
        int lastnum=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]==lastnum)
            {
                shift_left++; 
            }
            else if(shift_left>0)
            {
                nums[i-shift_left]=nums[i];
            }
            lastnum=nums[i];
        }
        return nums.size()-shift_left;
        
    }
};
           

3.Remove Duplicates from Sorted Array II

這裡還是用上面偏移辦法做

代碼：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0)return 0;
        int shift=0;
        int lastnum=nums[0],counts=0;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]==lastnum)
            {
                counts++;
                if(counts>1)
                {
                    shift++;
                }
            }
            else
            {
                counts=0;
            }
            nums[i-shift]=nums[i];
            lastnum=nums[i];
        }
        return nums.size()-shift;
    }
};
           

但是又一次看了評論大神的代碼，發現了本質是一樣但是利用了寫代碼技巧

代碼：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int n : nums)
        if (i < 2 || n > nums[i-2])
            nums[i++] = n;
        return i;
    }
};
           

這裡用i做标記，由于數組開頭每2個數字後第3個數字一定大于第一個數字，是以當不大于的時候i就不跟着n進行增加并記錄着這個第3個開始重複的數字，直到大于的時候用大于的數字替換掉當初記着的第3個重複數字，後面就以此類推完成循環。

值得借鑒的是這樣寫法 if(i<2 || 條件) 這裡就可以避免一些i在數組中不能取的情況，發現自己以前笨得都不會這樣來寫。

4.Find the Celebrity

5.Rotate Array

這裡最簡單方法是另開個數組，循環一遍。

另外還有個O(1)方法使用逆序

a1 a2 a3 .... an 先逆序a1 ... an-k，再逆序 an-k+1 ... an，最後再全部逆序一遍就可以了

代碼：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k=k%nums.size();
        int n=nums.size();
        reverse(nums.begin(),nums.end()-k);
        reverse(nums.end()-k,nums.end());
        reverse(nums.begin(),nums.end());
    }
};
           

6.First Missing Positive

這裡利用下标，将每個正數交換到它應該在的對應下标上，最後循環一遍看第一個不對應值的下标然後傳回即可。

代碼：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            while(nums[i]>0 && nums[i]<=nums.size() && nums[nums[i]-1]!=nums[i])
            {
                swap(nums[i],nums[nums[i]-1]);
            }
                
        }
        
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=i+1)
                return i+1;
        }
        return nums.size()+1;
    }
};