D&C

思路

回溯
先把candidate排个序，这样可以在中途直接cut掉后面的loop
为了避免重复结果，需要传入一个startIndex，在这之前的都不能作为candidate

代码

class Solution {
public:
    void combSumSub(vector<int>& candidates, int target, vector<vector<int>>& results, vector<int> currPath, int candStartIndex){
        for(int i=candStartIndex; i<candidates.size(); i++){
            if(target - candidates[i] < 0)
                break; //too big
            if(target == candidates[i]){
                currPath.push_back(candidates[i]);
                results.push_back(currPath);
                continue;
            }
            currPath.push_back(candidates[i]);
            combSumSub(candidates, target - candidates[i], results, currPath, i);
            currPath.erase(currPath.end()-1);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        combSumSub(candidates, target, result, vector<int>(), 0);
        return result;
    }
};

注意/思路

• 保存 被乘数*[0…9]的结果备用，然后移位相加即可
• 乘数末尾是0

代码

9ms

class Solution {
public:
    void ReverseStr(string& str){
        int left=0, right = str.size()-1;
        while(left<right){
            char c = str[left];
            str[left] = str[right];
            str[right] = c;
            left++;
            right--;
        }
    }
    void AddResult(string& result, const string& subProduct, const int shift){
        int carry = 0;
        while(result.size() < shift){
            result += "0";
        }
        for(int i=shift; i<subProduct.size() + shift; i++){
            if(i < result.size()){
                int subSum = (result[i]-'0') + (subProduct[i-shift]-'0') + carry;
                if(subSum >= 10){
                    subSum-= 10;
                    carry = 1;
                } else {
                    carry = 0;
                }
                result[i] = subSum + '0';
            } else {
                int subSum = (subProduct[i-shift]-'0') + carry;
                carry = subSum / 10;
                subSum = subSum % 10;
                result = result + (char)(subSum+'0');
            }
        }
        if (carry > 0) {
			result += (char)(carry + '0');
		}
    }
    string getSubProduct(char digit, string op){
        int carry = 0;
        int d = digit-'0';
        for(int i=0; i<op.size(); i++){
            int prod = (op[i]-'0') * d + carry;
            carry = prod / 10;
            prod = prod % 10;
            op[i] = '0' + prod;
        }
        if(carry > 0){
            op = op + (char)(carry+'0');
        }
        return op;
    }
    string multiply(string op1, string op2) {
        string result;
        if(op1.empty() || op2.empty())
            return result;
        if(op1.size() < op2.size()){
            string temp = op1;
            op1 = op2;
            op2 = temp;
        }
        string productSub[10];
        ReverseStr(op1);
        ReverseStr(op2);
        for(int i=0; i<op2.size(); i++){
            char digit = op2[i];
            if(digit == '0')
                continue;
            if(productSub[digit-'0'].empty()){
                productSub[digit-'0'] = getSubProduct(digit, op1);
            }
            AddResult(result, productSub[digit-'0'], i);
        }
        if(result.empty())
            return "0";
        ReverseStr(result);
        return result;
    }
};

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路

记住上一行的输出（结果）节点，每一次从后往前读出下一行，这样第2,4,6次读的时候其实就会翻转成正向了。唯一的问题是左右子节点写入下一行的顺序，按照当前顺序区分一下就行。不是左右左右，就是右左右左，具体看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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == NULL)
            return result;
        vector<TreeNode*>* currRow = new vector<TreeNode*>();
        vector<TreeNode*>* nextRow = new vector<TreeNode*>();
        bool direction = true;  //true: R,L,R,L,...; false:L,R,L,R,...
        currRow->push_back(root);
        while(!currRow->empty()){
            //Output current row
            vector<int> currRowResult;
            for(int i=0; i<currRow->size(); i++){
                currRowResult.push_back( (*currRow)[i]->val );
            }
            result.push_back(currRowResult);
            //
            for(int i=currRow->size()-1; i>=0; i--){
                TreeNode* currNode = (*currRow)[i];
                if(direction){
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                } else {
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                }
            }
            //swap currRow and nextRow
            vector<TreeNode*>* temp = currRow;
            currRow = nextRow;
            nextRow = temp;
            nextRow->clear();
            direction = !direction;
        }
        return result;
    }
};