288 周赛补题

T1
原题传送门

比赛时代码：

class Solution {
public:
    int largestInteger(int num) {
        string a;
        a  = to_string(num);
        
        vector xx, yy;
        
        for(int i = 0; i < a.size(); i ++){
            if(a[i] & 1){
                xx.push_back(a[i]);
            }else{
                yy.push_back(a[i]);
            }
        }
        
        sort(xx.begin(), xx.end(), greater());
        sort(yy.begin(), yy.end(), greater());
        
        string zz;
        int q = 0, p = 0;
        
        for(int j = 0; j < a.size(); j ++){
            if(a[j] & 1){
                zz += xx[q];
                q ++;
            }else{
                zz += yy[p];
                p ++;
            }
        }
        
        int oo;
        istringstream is(zz);
        
        is >> oo;
        
        return oo;
    }
};

写的比较长，但思路清晰，将数组的奇数与偶数分开，排序，再插入回数组中

其中也可以使用优先队列来实现，思路是一样的

第三题要用优先队列，还是对这种数据结构不太熟悉（用的比较少，还是要多些点数据结构的题）

class Solution {
public:
    int largestInteger(int num) {
        priority_queue pq0, pq1;
        string s = to_string(num);
  
        for (auto &ch : s) {
            int val = ch - '0';

            if (val % 2 == 0) {
                pq0.push(val);

            } else {
                pq1.push(val);
            }
        }

        int ans = 0;
       
        for (auto &ch : s) {
            int val = ch - '0';

            if (val % 2 == 0) {
                ans = ans * 10 + pq0.top();
                pq0.pop();
            } else {
                ans = ans * 10 + pq1.top();
                pq1.pop();
            }
        }

        return ans;
    }
};

 还看到可以用冒泡排序的思想做，交换奇偶性一致的数据 

class Solution {
public:
    int largestInteger(int num) {
        string s = to_string(num);
        
        for (int i = 0; i < s.size(); i++) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[j] > s[i] && (s[j] - s[i]) % 2 == 0) {
                    swap(s[i], s[j]);
                }
            }
        }

        return stoi(s);
    }
};

注意 string 转 int 类型，有两种转换方式（以前只知道第二种）

string a;

int b = stoi(a); //完成转换

--------------------------

int x;
string y;

istringstream is(y);

is >> x; //完成转换

T2

原题传送门

这题思路不难，就是一一列举找出答案，但处理真的好麻烦

特别是一些简便 *** 作不熟悉

后来整理了一下，代码就比较清晰了

class Solution {
public:
    string minimizeResult(string tt) {
         int n = tt.size();

         int zhon;
         for(int i = 0; i < tt.size(); i ++){
             if(tt[i] == '+'){
                zhon = i;
             }
         }

         int ans = INT_MAX;
         string xx;

         for(int i = 0; i < zhon; i ++){
             string a = tt.substr(0, i);
             string b = tt.substr(i, zhon - i);

             int aa = (a.size() == 0) ? 1 : stoi(a);
             int bb = stoi(b);

             for(int j = zhon + 1; j < n; j ++){
                 string c = tt.substr(zhon + 1, j - zhon);
                 string d = tt.substr(j + 1, n - j - 1);

                 int cc = stoi(c);
                 int dd = (d.size() == 0) ? 1 : stoi(d);

                 if(aa * (bb + cc) * dd < ans){
                     ans = aa * (bb + cc) * dd;

                     xx = a + '(' + b + '+' + c + ')' + d;
                 }
             }
         }

         return xx;
    }
};

T3

原题传送门 

思路也挺简单的，就是每次让最小的数加一，但实现。

。

比赛时代码：

class Solution {
public:
    int maximumProduct(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        
        int xx = k;
        
        while(xx --){
            nums[0] ++;
            
            sort(nums.begin(), nums.end());
        }
        
        long long count = 1;
        
        for(int i = 0; i < nums.size(); i ++){
            count = (count * nums[i]) % (long long)(1e9 + 7);
        }
        
        return count;
    }
};

毫无疑问，超时了。

没想到用优先队列来处理

class Solution {
public:
    int maximumProduct(vector& nums, int k) {
        priority_queue, greater> aa;

        for(auto x : nums){
            aa.push(x);
        }

        while(k > 0){
            int qp = aa.top();
            aa.pop();
            aa.push(qp + 1);

            k --;
        }

        long long count = 1;
        while(!aa.empty()){
            count = (count * aa.top()) % (long long)(1e9 + 7);

            aa.pop();
        }

        return count;
    }
};

目前的目标就是前三题。