LeetCode - 6 - (字符串相乘、下一个更大元素＜ⅠⅡⅢ＞、k个一组翻转链表)

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0") return "0";
        int n = num1.size(), m = num2.size();
        vector<int> tmp(n+m);
        for(int i = n-1; ~i; i--){  //相乘计算
            int x = num1[i]-'0';
            for(int j = m-1; ~j; j--){
                int y = num2[j]-'0';
                tmp[i+j+1] += x*y;
            }
        }
        string ans;
        for(int i = n+m-1; i > 0; i --){ //进位处理
            tmp[i-1] += tmp[i]/10;
            tmp[i] %= 10;
            ans.push_back(tmp[i]+'0');
        }
        if(tmp[0]) ans.push_back(tmp[0]+'0'); //判断前导零
        reverse(ans.begin(), ans.end()); //结果需要翻转
        return ans;
    }
};

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n = nums2.size();
        vector<int> res(n, -1);
        stack<int> st;
        map<int, int> mp;
        for(int i = 0; i < n; i ++){
            mp[nums2[i]] = i;
            while(!st.empty()&&nums2[st.top()]<nums2[i]){
                res[st.top()] = nums2[i];
                st.pop();
            }
            st.push(i);
        }
        vector<int> ans;
        for(int i = 0; i < nums1.size(); i ++){
            ans.push_back(res[mp[nums1[i]]]);
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> st;
        for(int i = 0; i < n*2-1; i ++){
            while(!st.empty()&&nums[st.top()]<nums[i%n]){
                ans[st.top()] = nums[i%n];
                st.pop();
            }
            st.push(i%n);
        }
        return ans;
    }
};

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        if(next_permutation(s.begin(), s.end())&&stoll(s)<=INT_MAX) return stoi(s);
        return -1;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    pair<ListNode*, ListNode*> Reverse(ListNode* bg, ListNode* ed){
        ListNode* pre = ed->next;
        ListNode* p = bg;
        while(pre!=ed){
            ListNode* nex = p->next;
            p->next = pre;
            pre = p;
            p = nex;
        }
        return {ed, bg};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        while(head){
            ListNode* ed = pre;
            for(int i = 0; i < k; i ++){
                ed = ed->next;
                if(!ed) return dummy->next;
            }
            ListNode* nex = ed->next;
            tie(head, ed) = Reverse(head, ed);
            pre->next = head;
            ed->next = nex;
            pre = ed;
            head = ed->next;
        }
        return dummy->next;
    }
};