Leetcode - 双指针

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int i=0, j=A.size()-1;
        vector<int> ret(A.size());
        int cur = j;
        while(i<=j){
            int ii = A[i]*A[i], jj = A[j]*A[j];
            if(ii > jj){
               ret[cur--] = ii;
                i++;
            }else {
                ret[cur--]=jj;
                j--;
            }
        }
     
        return ret;
    }
};

class Solution {
public:
    
    void swap(vector<int>& nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
     
    // 对每个为零的元素，从后面找一个最近的非零与之交换
    void moveZeroes(vector<int>& nums) {
        int cnt=0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] == 0){
                int j=i+1;
                while(j<nums.size() && nums[j] == 0) j++;
                if(j<nums.size()) swap(nums, i, j);
            }
        }
    }
};

class Solution {
public:
    
    void swap(vector<int>& nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
     
   	/**
   	设i指向原数组，j指向零在后面的数组
   	i每指到一个非零元素，就赋给j指向
   	妙
   	*/
    void moveZeroes(vector<int>& nums) {
        int i=0, j=0;
        for(; i<nums.size(); i++)
            if(nums[i] != 0)
                nums[j++] = nums[i];
        
        for(; j<nums.size(); j++)
            nums[j] = 0;
    }
};

class Solution {
public:
    /**
    	二分搜索
    */
    int binarySearch(vector<int>& nums, int l, int r, int key){
        int mid;
        while(l < r){
            mid = (l+r) >> 1;
            if(nums[mid] > key) r = mid;
            else if(nums[mid] < key) l = mid+1;
            else return mid;
        }
        return -1;
    }
    vector<int> twoSum(vector<int>& nums, int target) {   
        vector<int> ret;
        for(int i=0; i<=nums.size(); i++){
            int t = binarySearch(nums, 0, nums.size(), target-nums[i]);
            if(t != -1){
                ret.push_back(i+1);
                ret.push_back(t+1);
                break;
            }
        }
        return ret;
    }
};

class Solution {
public:
    
	/**
	双指针
	*/
    vector<int> twoSum(vector<int>& nums, int target) {   
        vector<int> ret;
        int i=0, j=nums.size()-1;
        int t;
        while(i < j){
            t = nums[i] + nums[j];
            if(target == t){
                ret.push_back(i+1);
                ret.push_back(j+1);
                break;
            }
            else if(t > target)
                j--;
            else i++;
        }
        return ret;
    }
};

class Solution {
public:
    
    /**
    双指针
    */
    int removeElement(vector<int>& nums, int val) {
        int i=0, j=0;
        for(; i<nums.size(); i++)
            if(nums[i] != val)
                nums[j++] = nums[i];   
        return j;
    }
};