Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

第一种：3格的滑动窗口

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int str = 0 ,end = 2;
        int tol = 0;
        if (flowerbed.size()==1&&flowerbed[0]==0) {
            tol++;
        }else if(flowerbed[0]==0&&flowerbed[1]==0) {
            flowerbed[0]=1;
            tol++;
        }
        
        while (end<=flowerbed.size()-1) {
            if (!(flowerbed[str]||flowerbed[str+1]||flowerbed[end])) {
                flowerbed[str+1] = 1;
                tol++;
            }
            str++;
            end++;
        }
        if (flowerbed.size()>=3&&flowerbed[flowerbed.size()-1]==0&&flowerbed[flowerbed.size()-2]==0) {
            tol++;
        }
        return tol>=n?1:0;
    }
};

第二种：

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for (int i = 0; i < flowerbed.size(); i++) {
            if (!flowerbed[i] && (i == 0 || !flowerbed[i - 1]) && (i == flowerbed.size() - 1 || !flowerbed[i + 1])) {
                flowerbed[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
};

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

判断数组中是否有重复的元素，并且下标之差不超过k。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i=0; i<nums.size(); i++) {
            if (hash.find(nums[i])!=hash.end()&&i-hash[nums[i]]<=k) {
                return 1;
            }else{
                hash[nums[i]] = i;
            }
        }
        return 0;
    }
};

解决方法：滑动窗口方案

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double r = INT_MIN;
        double sum = 0;
        for (int i = 0; i<nums.size(); i++) {
            if (i<k) {
                sum+=nums[i];
            }else{
                r = max(sum, r);
                sum +=nums[i]-nums[i-k];
            }
        }
        r = max(sum, r);
        return r/double(k);
    }
};

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>>result(numRows);
        for (int i = 0; i<numRows; i++) {
            result[i].resize(i+1);
            result[i][0] = result[i][i] = 1;
        
            for (int j = 1; j<i; j++) {
                result[i][j] = result[i-1][j-1]+result[i-1][j];
            }
        }
        return result;
        
     }
};

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int result = 0;
        for (int i =0; i<nums.size(); i++) {
            if (nums[i]>=target) {
                return i;
            }
        }
        return nums.size();
    }
};

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

第一种解法：分治法

class Solution {
public:
    vector<int> findCrossSubArray(vector<int>& nums, int mid, int low ,int high){
        int sum = 0;
        int leftSum = INT_MIN;
        int maxLeft = 0;
        for (int i = mid; i>=low; i--) {
            sum = sum+nums[i];
            if (sum>leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }
        sum = 0;
        int rightSum = INT_MIN;
        int maxRight = 0;
        for (int j=mid+1; j<=high; j++) {
            sum = sum+nums[j];
            if (sum>rightSum) {
                rightSum = sum;
                maxRight = j;
            }
        }
        
        return {{maxLeft,maxRight,leftSum+rightSum}};
    }

    vector<int> findMaxSubArray(vector<int>& nums,int low ,int high)
    {
        if (low==high) {
            return {{low,high,nums[low]}};
        }else{
            int mid = (low+high)/2;
            vector<int> leftSum = findMaxSubArray(nums, low, mid);
            vector<int> rightSum = findMaxSubArray(nums, mid+1, high);
            vector<int> crossSum = findCrossSubArray(nums, mid, low, high);
            if (leftSum[2]>=rightSum[2]&&leftSum[2]>=crossSum[2]) {
                return leftSum;
            }else if(rightSum[2]>=leftSum[2]&&rightSum[2]>=crossSum[2])
            {
                return rightSum;
            }
            else return crossSum;
        }
    
    }


    int maxSubArray(vector<int>& nums) {
        int len = nums.size()-1;
        vector<int> result = findMaxSubArray(nums, 0, len);
        return result[2];
    }
};

第二种解法：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans=nums[0],i,j,sum=0;
        for(i=0;i<nums.size();i++){
            sum+=nums[i];
            ans=max(sum,ans);
            sum=max(sum,0);
        }
        return ans;
    }
};