sorted array去重只需要O(n) time, O(1) space

26. Remove Duplicates from Sorted Array.cpp

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

int removeDuplicates(vector<int>& nums) {
    int i = !nums.empty();
    for (int n : nums)
        if (n > nums[i-1])
            nums[i++] = n;
    return i;
}

27. Remove Element.cpp

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int cur = -1;
        for (auto n:nums){
            if (n!=val){
                nums[++cur] = n;
            }
        }
        return cur+1;
    }
};

//有一个更好的方法，还没有写出来，明天写出来。

28. Implement strStr().cpp

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        bool flag = false;
        for (int i=0;i<haystack.size();i++){
            if (haystack[i] == needle[0]){
                flag = true;
                for (int j=0;j<needle.size();j++){
                    if (i+needle.size()>haystack.size() || haystack[i+j] != needle[j]){
                        flag = false;
                        break;
                    }
                }
                if (flag) return i;
            }
        }
        return -1;
        
    }
};


//改进1： 判断条件可以变成i<m-n+1

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        bool flag = false;
        for (int i=0;i<haystack.size()-needle.size()+1;i++){
            if (haystack[i] == needle[0]){
                flag = true;
                for (int j=0;j<needle.size();j++){
                    if (haystack[i+j] != needle[j]){
                        flag = false;
                        break;
                    }
                }
                if (flag) return i;
            }
        }
        return -1;
        
    }
};

//改进2：不用flag，而是比较j是不是全部比较完了。
//不用比较第一个，直接开始For循环。
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        bool flag = false;

        for (int i=0;i<int(haystack.size())-int(needle.size())+1;i++){
                int j=0;
                for (;j<needle.size();j++){
                    if (haystack[i+j] != needle[j]){
                        flag = false;
                        break;
                    }
                }
                if (j == needle.size()) return i;
            
        }
        return -1;
        
    }
};