108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

把一個排序過的array轉成一個高度平衡二元搜尋樹中。

coding的邏輯

由於是sorted過的array 所以只要將最中間的元素當成root 然後一直不斷的遞迴下去

/**
 * 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:
    
    TreeNode* ArrayToBST(vector<int>& nums, int begin, int end)
    {
        if (begin > end)
        {
            return nullptr;
        }
        
        int mid = (end + begin)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        
        root->left = ArrayToBST(nums, begin, mid - 1);
        root->right = ArrayToBST(nums, mid + 1, end);

        return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        return ArrayToBST(nums, 0, nums.size() - 1);
    }
};

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

我想不用多說了吧
code也很簡單...

   class Solution {  
    public:  
        int maxDepth(TreeNode *root) {  
 
            if(root == NULL)
            {
                return 0;
            }
            
            return 1 + max( maxDepth(root->left), maxDepth(root->right) );  
        }  
    };  

搞定

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3 

簡單來說，判斷是否為對稱樹

程式碼 

class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        
        if (root == NULL) return true;
        
        return isSymc(root->left, root->right);
        
    }
    
    bool isSymc(TreeNode* left, TreeNode* right)
    {
        if (left == nullptr)
        {
            return right == nullptr;
        }
        
        if (right == nullptr)
        {
            return left == nullptr;
        }
        
        if (left->val != right->val)
        {
            return false;
        }
        
        // 檢查是否對稱
        if (!isSymc(left->right, right->left))
        {
            return false;
        }
        
        if (!isSymc(left->left, right->right))
        {
            return false;
        }
            
        return true;
    }
    
};

226. Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

不用多說了，就是反轉二元樹

方法有好幾種。我這邊用最快的方法BFS的作法來做

/**
 * 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:
  
  TreeNode* invertTree(TreeNode* root) {

    if(nullptr == root) return root;

    stack<TreeNode*> myQueue;   // our queue to do BFS
    myQueue.push(root);         // push very first item - root

    while(!myQueue.empty()){    // run until there are nodes in the queue 
        TreeNode *node = myQueue.top();  // get element from queue
        myQueue.pop();                     // remove element from queue

        if(node->left != nullptr){         // add left kid to the queue if it exists
            myQueue.push(node->left);
        }
        if(node->right != nullptr){        // add right kid 
            myQueue.push(node->right);
        }

        // invert left and right pointers      
        swap(node->left, node->right);

    }
    return root;
}       
};

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();
            }
        }        
    }
};