Code – 第160页

LeetCode 145. Binary Tree Postorder Traversal

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

分析：后序遍历，左右根～

/**
 * 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:
    vector<int> result;
    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return result;
    }
    void dfs(TreeNode* root) {
        if(root == NULL) return;
        dfs(root->left);
        dfs(root->right);
        result.push_back(root->val);
    }
};

/**

* 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:

vector<int> result;

vector<int> postorderTraversal(TreeNode* root) {

dfs(root);

return result;

}

void dfs(TreeNode* root) {

if(root == NULL) return;

dfs(root->left);

dfs(root->right);

result.push_back(root->val);

}

};

LeetCode 94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].

分析：中序遍历，先遍历左子树，再输出中间，再遍历右子树～

/**
 * 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:
    vector<int> result;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return result;
    }
    void dfs(TreeNode* root) {
        if(root == NULL) return ;
        dfs(root->left);
        result.push_back(root->val);
        dfs(root->right);
    }
};

/**

* 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:

vector<int> result;

vector<int> inorderTraversal(TreeNode* root) {

dfs(root);

return result;

}

void dfs(TreeNode* root) {

if(root == NULL) return ;

dfs(root->left);

result.push_back(root->val);

dfs(root->right);

}

};

LeetCode 153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

分析：二分搜索法，即使旋转过了也会一半的任何一个元素始终比另一半的任何一个元素大，所以如果nums[mid] < nums[high]，说明最小元素一定在[left, mid]中，所以令high = mid；否则一定在[mid + 1, high]中，令low = mid + 1～～

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        while(low < high) {
            int mid = (low + high) / 2;
            if(nums[mid] < nums[high])
                high = mid;
            else
                low = mid + 1;
        }
        return nums[low];
    }
};

class Solution {

public:

int findMin(vector<int>& nums) {

int low = 0, high = nums.size() - 1;

while(low < high) {

int mid = (low + high) / 2;

if(nums[mid] < nums[high])

high = mid;

else

low = mid + 1;

}

return nums[low];

}

};

LeetCode 167. Two Sum II – Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

分析：每个数遍历找他的后面是否存在与它相加等于target的数，如果存在就放入result数组中～

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result(2);
        for(int i = 0; i < numbers.size(); i++) {
            for(int j = i + 1; j < numbers.size(); j++) {
                if(numbers[i] + numbers[j] == target) {
                    result[0] = i + 1;
                    result[1] = j + 1;
                    break;
                } else if(numbers[i] + numbers[j] > target) {
                    break;
                }
            }
            if(result[0] != 0)
                break;
        }
        return result;
    }
};

class Solution {

public:

vector<int> twoSum(vector<int>& numbers, int target) {

vector<int> result(2);

for(int i = 0; i < numbers.size(); i++) {

for(int j = i + 1; j < numbers.size(); j++) {

if(numbers[i] + numbers[j] == target) {

result[0] = i + 1;

result[1] = j + 1;

break;

} else if(numbers[i] + numbers[j] > target) {

break;

}

if(result[0] != 0)

break;

}

return result;

}

};

LeetCode 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there is not one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

分析：sum为前i个数的和，长度比nums多一个，sum[0] = 0。这样从0开始一直到len，遍历sum计算sum[j]与sum[i]的差大于等于s的时候的j-i长度，把它与minlen比较，如果比minlen小就更新minlen。
一开始minlen的初始化值是len + 1，如果最后minlen的值仍旧为len + 1，说明没有找到这样的minlen满足题意。则直接返回0；否则返回minlen的值～～

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        int minlen = len + 1;
        vector<int> sum(len + 1);
        for(int i = 1; i <= len; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }
        for(int i = 0; i <= len; i++) {
            for(int j = i + 1; j <= len; j++) {
                if(sum[j] - sum[i] >= s) {
                    minlen = min(minlen, j - i);
                    break;
                }
            }
        }
        if(minlen == len + 1)
            return 0;
        return minlen;
    }
};

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) {

int len = nums.size();

int minlen = len + 1;

vector<int> sum(len + 1);

for(int i = 1; i <= len; i++) {

sum[i] = sum[i-1] + nums[i-1];

}

for(int i = 0; i <= len; i++) {

for(int j = i + 1; j <= len; j++) {

if(sum[j] - sum[i] >= s) {

minlen = min(minlen, j - i);

break;

}

if(minlen == len + 1)

return 0;

return minlen;

}

};

LeetCode 216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

分析：一个dfs回溯解决，如果当前k == 0而且 n == 0说明一定达到了k个数，和为n，则将当前path压入result数组中；从start开始一直到9，分别压入path中深度优先搜索。深度优先搜索完了之后记得回溯path中pop出最后一个元素～
因为题目要求结果集合必须是按照集合顺序，也就是从小到大而且没有重复元素，那么就要设立一个start变量，每次for循环的时候从start开始，一开始start为0，每次规定start为i+1，即只能从当前数字的下一个数字开始，这样就能保证结果是递增无重复数字的集合序列～～

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return result;
    }
    
    void dfs(int k, int n, int start) {
        if(k == 0) {
            if(n == 0)
                result.push_back(path);
            return ;
        }
        for(int i = start; i <= 9; i++) {
            path.push_back(i);
            dfs(k - 1, n - i, i + 1);
            path.pop_back();
        }
    }
};

class Solution {

public:

vector<vector<int>> result;

vector<int> path;

vector<vector<int>> combinationSum3(int k, int n) {

dfs(k, n, 1);

return result;

}

void dfs(int k, int n, int start) {

if(k == 0) {

if(n == 0)

result.push_back(path);

return ;

}

for(int i = start; i <= 9; i++) {

path.push_back(i);

dfs(k - 1, n - i, i + 1);

path.pop_back();

}

};