40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
] 

39. Combination Sum的衍生 

邏輯大同小異，只是array中的每個元素,只能使用一次。

解法如下 

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
        vector<vector<int>> answerset;
        vector<int> combination;
        sort(candidates.begin(), candidates.end());
        
        combinationSumDFS(candidates, 0, target -0, combination, answerset);
        
        return answerset;
    }
    
    void combinationSumDFS(const vector<int>& candidates, int start, int target, vector<int> &combination, vector<vector<int>>              
                           &answerset)
    {
        // 小於0代表，再找下去也不可能會有符合的數字了
        if (target < 0)
        {
            return;
        }
        // 這個數字組合剛好符合
        else if (target == 0)
        {
            answerset.push_back(combination);
        }
        else
        {
            for (int i = start; i < candidates.size(); i++)
            {
                //排除掉重複的元素
                if (i > start && candidates[i] == candidates[i - 1]) continue;
                
                combination.push_back(candidates[i]);
                //因為已經加入這個元素了，所以要從下一個元素開始
                combinationSumDFS(candidates, i + 1, target - candidates[i], combination, answerset);
                combination.pop_back();
            }
        }        
    }
};

643. Maximum Average Subarray I

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1. 1 <= k <= n <= 30,000.
2. Elements of the given array will be in the range [-10,000, 10,000].

 這題的思維，要想像一個k大小的sub array 從 0開始一路前進到 vector的盡頭。

class Solution {
public:
double findMaxAverage(vector<int>& nums, int k)
{
    //先算出nums[0]到nums[k]的總和
    int sum = accumulate(nums.begin(), nums.begin() + k, 0), max_number = sum, n = nums.size();
    
    for (int i = k; i < n; i++)
    {
        //每前進一格就比一次大小
        sum += nums[i] - nums[i - k];
        max_number = max(max_number, sum);
    }
    
    return double(max_number) / k;
}
};

39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
] 

要求你從一串array中找出符合某個目標加總的集合

解法的邏輯都是以DFS為主 有點類似Subset的作法，但是不同點在於要符合條件的元素才可以加入

。

不多說，來看code

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> answerset;
        vector<int> combination;
        sort(candidates.begin(), candidates.end());
        
        combinationSumDFS(candidates, 0, target -0, combination, answerset);
        
        return answerset;
    }
    
    void combinationSumDFS(const vector<int>& candidates, int start, int target, vector<int> &combination, vector<vector<int>>              
                           &answerset)
    {
        // 小於0代表，再找下去也不可能會有符合的數字了
        if (target < 0)
        {
            return;
        }
        // 這個數字組合剛好符合
        else if (target == 0)
        {
            answerset.push_back(combination);
        }
        else
        {
            for (int i = start; i < candidates.size(); i++)
            {
                combination.push_back(candidates[i]);
                combinationSumDFS(candidates, i, target - candidates[i], combination, answerset);
                combination.pop_back();
            }
        }        
    }
};

100. Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

題意沒有什麼，就是要你檢查兩棵tree是不是一樣的。

懶得講了 直接貼code一下就了解了...

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        
        if (p == nullptr || q == nullptr)
        {
            return (p == q);
        }
        
        return  (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

35. Search Insert Position

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.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

解法 :
         看到有排序又要你找裡面的東西，二話不說，一定就是binary search的概念
 如果找不到，再將target加入nums中再排序一次後，一樣用binary search。
而C++11有提供了 binary search的演算法，有分lower_bound以及upper_bound

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        
        //利用binary search去找
        auto first = std::lower_bound(nums.begin(), nums.end(), target);
        
        //沒有就加入
        if (first == nums.end())
        {
           //加入後sort
            nums.push_back(target);
            sort(nums.begin(), nums.end());
                        
            //再一次binary search去找
            first = std::lower_bound(nums.begin(), nums.end(), target);

        }
        
        //最後iterator跟begin相減就知道是第幾個了
        return first - nums.begin();
    }
};