（栈）leetcode 394-蒲公英云

（栈）leetcode 394

Myth丶恋晨 2021-12-10 02:27 253阅读 0赞

思路：分情况讨论+栈。

class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> ch;
        int num = 0;
        string str = "";
        for(auto c:s){
            if(isdigit(c))
                num = num*10 + (c-'0');
            else if(isalpha(c))
                str += c;
            else if(c=='['){
                ch.push(str);
                nums.push(num);
                str = "";
                num = 0;
            }
            else{
                string tmp = str;
                for(int i=0; i<nums.top()-1; ++i)
                    //本身一次已经在内，故nums.top()-1
                    str += tmp;
                //这里字符相加的顺序不能颠倒
                str = ch.top()+str;
                nums.pop();
                ch.pop();
            }
        }
        return str;
    }
};

思路：递归

/**
 * 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* constructMaximumBinaryTree(vector<int>& nums) {
        int size = nums.size();
        if(size == 0)
            return NULL;
        return MaxTree(nums, 0, size-1);
    }
    TreeNode* MaxTree(vector<int>& nums, int left, int right){
        if(left > right)
            return NULL;
        int max_index = maxIndex(nums, left, right);
        TreeNode* head = new TreeNode(nums[max_index]);
        head->left = MaxTree(nums, left, max_index-1);
        head->right = MaxTree(nums, max_index+1, right);
        return head;
    }
    int maxIndex(vector<int>& nums, int left, int right){
        int index = left, m = nums[left];
        for(int i=left; i<=right; ++i){
            if(nums[i]>m){
                m = nums[i];
                index = i;
            }
        }
        return index;
    }
};