（栈）leetcode 394

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

![1266918-20190711231559977-341210834.png][]

思路：分情况讨论+栈。

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

![1266918-20190715112933407-916952630.png][]

思路：递归

/**
     * 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;
        }
    };

转载于:https://www.cnblogs.com/Bella2017/p/11173459.html

[1266918-20190711231559977-341210834.png]: /images/20211209/fa1c7bee96ea46c790fba5d9df2bf4f8.png
[1266918-20190715112933407-916952630.png]: /images/20211209/1ab3e72607cd49bcb058aa13b54a9d18.png