This is the 14th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

1946. Maximum integer possible after substring mutation

Thought analysis

This problem requires us to replace a number in the string to make the number as large as possible. It’s important to note that it’s just a number, so we’re going back and forth.

Since there is only one change[num], there is only one mutation possible, so this is a very simple greedy algorithm

Find the first one from left to right that is larger than the original value.

1947. Maximum compatibility score and

Thought analysis

It is important to note that the subject restrictions on n more strict 1 < = m, n < = 8, that gives us the opportunity to exhaustion, then two to two two array elements matching how many possible, it is difficult to calculate, might as well put a fixed array, discuss another array has several arrangement (which is a simple array arrangement problem completely, There are many answers to this question, and the previous report is prepared.)

To complete the problem, add a code that calculates the sum of the compatibility scores and a code that returns the sum of the maximum compatibility scores.

The compatibility score is calculated by simply traversing the array to the last digit.

Returns the maximum compatibility score and needs to be combined with the original code:

  for (int i = 0; i < n; i++) {
    if (mark[i] == false) {
        mark[i] = true;
        order.push_back(i);
        ret = max(ret, dfs(order, mark, s, m,n));
        order.pop_back(a); mark[i] =false; }}Copy the code

Note that mark[I] true means that a path (when we think of DFS as a tree, a line from the root to a leaf is called a path) already has an I node. So mark[I] needs to be restored after popback.