
class Solution {
public:
    int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) {
        int len = energy.size();
        int minEnergy = 1, addExper = 0, curExper = initialExperience;
        for(int i = len-1, j = 0; i >= 0; i --, j ++) {
            if(curExper <= experience[j]) {
                addExper += (experience[j]+1 - curExper);
                curExper = experience[j] + 1;
            }
            curExper += experience[j];
            minEnergy += energy[i];
        }
        if(minEnergy <= initialEnergy) return addExper;
        else return minEnergy - initialEnergy + addExper;
    }
};

2. 最大回文数字

给你一个仅由数字（0 - 9）组成的字符串 num 。

请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。

注意：

你无需使用 num 中的所有数字，但你必须使用至少一个数字。
数字可以重新排序。

解题思路：

按照题意构造最大回文整数，一个偶数回文数可以拆分成左右对称的两个字符串，奇数回文数则在左右字符串中间多一个整数。

按照数字序排列可以很容易得到最大回文数。以左边的字符串为例，将数从左至右递减排列即可，中间的整数存在时取最大即可。因此思路是首先统计0-9数字出现的次数，并按照从大到小的方式构建回文串的三个部分。

需要重点注意特殊情况：

无前导零，数字0不能出现在首位

复杂度： $O(n)$

AC代码：


class Solution {
public:
    string largestPalindromic(string num) {
        vector<int> cntN(10,0);
        for(int i = 0; i < num.size(); i ++) 
            cntN[num[i] - '0'] ++;
        string tempStrL = "", tempStrR = "", maxSingle = "";
        for(int i = cntN.size()-1; i >= 0; i --) {
            if(cntN[i] >= 1) {
                int tempN = cntN[i] / 2;
                if(tempStrL == "" && i == 0 && maxSingle == "") return "0";
                else if(tempStrL != "" || i != 0 ) {
                    string t(tempN,'0'+i);
                    tempStrL += t; 
                    tempStrR = t + tempStrR;
                }
                if(cntN[i] % 2 != 0 && maxSingle == "" ) maxSingle += '0' + i;    
            }
        }
        return tempStrL + maxSingle + tempStrR;
    }
};

3. 感染二叉树需要的总时间

给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染将会从值为 start 的节点开始爆发。

每分钟，如果节点满足以下全部条件，就会被感染：

节点此前还没有感染。
节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数。

解题思路：

非常朴素的解题思路，首先思考如何计算节点的被感染时间，最好是转化成二叉树中常见的属性。

当起始点为root时，感染的传播方向只有左右子树，二叉树被感染的时间即该棵树的高度。

而当起始点不在root时，感染的传播方向除了左右子树，还有父节点方向，即不断向上感染父节点的另一子树（即起始点不在的子树），直到传到root

左右子树方向：感染的时间是以起始点作为根节点子树的高度
父节点方向：感染的时间是起始点离父节点的距离+另一子树的高度

感染的时间为两个方向中的最大值即为感染时间

复杂度： $O(nlog(n))$

AC代码：


class Solution {
private:
    vector<TreeNode*> father;
public:
    int amountOfTime(TreeNode* root, int start) {
        father.clear(), father.resize(1e5+10); //初始化
        getFathers(root);
        TreeNode* f = father[start];
        if(f == nullptr) return getMaxDepth(root)-1;
        
        int maxT = 0, cnt = 0, side = 0; // 0 left 1 right
        TreeNode* curNode;
        if(f->left != nullptr && f->left->val == start)
            curNode = f->left;
        if(f->right != nullptr && f->right->val == start)
            curNode = f->right;
        maxT = getMaxDepth(curNode)-1;
 
        while(curNode != nullptr) {
            TreeNode* tempf = father[curNode->val];
            cnt ++;
            if(tempf != nullptr) {
                if(tempf->left == curNode) side = 0;
                else if(tempf->right == curNode) side = 1;
                if(side == 0) maxT = max(cnt + getMaxDepth(tempf->right), maxT);    
                else maxT = max(cnt+getMaxDepth(tempf->left), maxT);
            }
            curNode = tempf;
            if(curNode == nullptr) return maxT;
            tempf = father[tempf->val];
        }
        return maxT;
    }
//获得父节点数组
    void getFathers(TreeNode* root) {
        if(root == nullptr) return;
        if(root->left != nullptr)
            father[root->left->val] = root, getFathers(root->left);
        if(root->right != nullptr) 
            father[root->right->val] = root, getFathers(root->right);
    }
//求节点高度
    int getMaxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return max(getMaxDepth(root->left), getMaxDepth(root->right)) + 1;
    }
};

4. 找出数组的第 K 大和

给你一个整数数组 nums 和一个正整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个最大子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

注意：空子序列的和视作 0 。

解题思路：

对于一个整数数组，最大子序列是所有正数之和。以该队列为始，求第k大子序列和一定是从队列中加入最大负数元素或删除最小正数元素，因此可以将问题简化，把加入负数都转化为删除正数。将元素数组从小到大排列，对于数组的每个元素有两种处理方法：

删除元素nums[i]，保留nums[i-1]
删除元素nums[i]，去掉nums[i-1]。

使用堆思想求解。

复杂度： $O(nlog(n) + klog(k))$

AC代码：


typedef long long LL;
typedef pair<long long, int> PLI; 
class Solution {
public:
    long long kSum(vector<int>& nums, int k) {
        long long sum = 0;
        for(int i = 0; i < nums.size(); i ++) 
            if(nums[i] >= 0) sum += nums[i];
            else nums[i] = -nums[i];
        sort(nums.begin(), nums.end());
        priority_queue<PLI, vector<PLI>, less<PLI>> pq;
        pq.push(sum, 0);
        while(-- k) {
            long long sum = pq.top().first;
            int i = pq.top().second;
            pq.pop();
            if(i < nums.size()) {
                pq.push({sum - nums[i], i + 1});
                if(i != 0) pq.push({sum - nums[i] + nums[i-1], i + 1});
            }
        }
        return pq.top().first;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/510075