1. How to solve violence 2. How to optimize

Topic describes

You are given a string s and two integers A and b. Where, the string s has an even length and consists only of the digits 0 through 9.

You can perform one of the following two operations on S multiple times in any order:

Summation: Adds a to all elements of S whose subscripts are odd (subscripts start at 0). As soon as the number goes beyond 9, it goes to 0, and so on. For example, if s = “3456” and a = 5, s becomes “3951” after this operation. Rotation: Rotate S to the right of position B. For example, if s = “3456” and B = 1, s becomes “6345”. Return the smallest lexicographic string you can get by performing the above operation any number of times on S.

If two strings are of the same length, the lexicographical order of string A is less than that of string B can be defined as follows: at the first position where a and B differ, characters in string A appear in the alphabet before their counterparts in string B. For example, “0158 “lexicographic order is smaller than “0190” because the different first position is in the third character, obviously ‘5’ appears before ‘9’.

Example 1:

Input: s = "5525", a = 9, b = 2 Output: "2050" Description: Perform the following operations: Initial state: "5525" Rotation: "2555" Accumulation: "2454" Accumulation: "2353" Rotation: "5323" Accumulation: "5222" Accumulation: "5121" rotation: "2151" Summation: "2050" cannot get strings with lexicographical order less than "2050".Copy the code

Example 2:

Input: s = "74", A = 5, b = 1 Output: "24" Description: Perform the following operations: Initial state: "74" Rotation: "47" Cumulative: "42" Rotation: "24" Cannot obtain the character string whose lexicographically order is less than "24".Copy the code

Example 3:

Input: s = "0011", a = 4, b = 2 Output: "0011" Description: Cannot get a string whose lexicographical order is less than "0011".Copy the code

Example 4:

Input: s = "43987654", a = 7, b = 3Copy the code

Tip:

2 <= S. length <= 100. S. length is even. S consists only of the numbers 0 to 9. 1 <= A <= 9Copy the code

The violence problem solving

The data is small, and violence is entirely answerable

But even if it was violent, and I was confused, violence is not violent

Finally, on reflection, the easy to understand operation is:

There are two operations, one of which can be done at any time, and it doesn’t matter, right

So it’s like traversing the left and right nodes of the tree

The terminating traversal condition is that the situation has already been visited and there is no need to visit again

class Solution { int move=0; int rotate=0; HashSet<String> set; String min=""; public String findLexSmallestString(String s, int a, int b) { set=new HashSet<>(); move=b%s.length(); rotate=a; min=s; Bfs(s); return min; } public void Bfs(String s){if(set.contains(s)){// system.out.println (" accessed, stop accessed "); return; } set.add(s); Min =getMinString(min,s); // Move Bfs(moveToNewStringBuffer(new StringBuffer(s))); Rotate Bfs(rotateToNewString(new StringBuffer(s))); } public String getMinString(String s1,String s2){ if(s1.compareTo(s2)<=0){ return s1; }else { return s2; } } public String moveToNewStringBuffer(StringBuffer sb){ for (int i = 0; i < move; i++) { sb.insert(0,sb.charAt(sb.length()-1)); sb.deleteCharAt(sb.length()-1); } return sb.toString(); } public String rotateToNewString(StringBuffer sb){ for (int i = 1; i < sb.length(); i=i+2) { char c= (char) ((sb.charAt(i)-'0'+rotate)%10+'0'); sb.setCharAt(i,c); } return sb.toString(); }}Copy the code

To optimize the

So if b%2 is equal to 0, then we can only add a to the odd number, right

Let’s call the shift operation m, and the rotation operation r, and the optimal solution must be the combination of m and R, and r everywhere is the addition or subtraction of the odd coordinates M r M m r R M…

In other words, m r r r and r r m get the same result

So we can simply move String S 0 a distance, 1 A distance… All the way to s again

In this process we are choosing 1 R, 2 r… To 10 r’s, because 10 rotations will repeat

If b%2==1, we split the array into parts A and B, and obviously only part B moved when we did r at the beginning

But when we move B, then we do r, part A moves

And a motion doesn’t affect B motion

So the way we can think about it is, now the situation is like this, we move B, we change A to the best case, and we move n to get back to where we are

If you get rid of this whole complicated process, isn’t that the same thing as saying that A can rotate

So now we have the condition that a and B are independent and can be rotated

So we maximize a, and then we maximize B, and that’s the best case

And then we can do m

Here’s another example: R1 represents moving part A, R2 represents moving part B and operation M

r2 r2 r2 m m m r1 r1 m r2 m r1 r1 r1 m m m r2 r2 r2

We’ve moved 8 m’s, 5 R1’s, and 7 R2’s, and we’ve completely covered that, and we’ve optimized unnecessary calculations, for example, we just need to combine the best case of R1 and the best case of R2, and we don’t have to worry about the bad case of R1 and R2

class Solution {
    int move=0;
    int rotate=0;
    public String findLexSmallestString(String s, int a, int b) {
        String min=s;
        String begin=s;
        move=b;
        rotate=a;
        //if(b%2==1)move=1;
        boolean flag=true;
        while (!begin.equals(s)||flag){
            flag=false;
            String rotate=begin;
            if(b%2==1){
                String temp=rotate;
                for (int i = 0; i < 11; i++) {
                    min=getMinString(min,rotate);
                    temp=getMinString(temp,rotate);
                    rotate=rotateToNewString1(new StringBuffer(rotate));
                }
                rotate=temp;
                for (int i = 0; i < 11; i++) {
                    min=getMinString(min,rotate);
                    rotate=rotateToNewString(new StringBuffer(rotate));
                }
            }else {
                for (int i = 0; i < 11; i++) {
                    min=getMinString(min,rotate);
                    rotate=rotateToNewString(new StringBuffer(rotate));
                }
            }
             begin=moveToNewStringBuffer(new StringBuffer(begin));
        }
        return min;

    }
    public String getMinString(String s1,String s2){
        if(s1.compareTo(s2)<=0){
            return s1;
        }else {
            return s2;
        }
    }
    public String moveToNewStringBuffer(StringBuffer sb){
        for (int i = 0; i < move; i++) {
            sb.insert(0,sb.charAt(sb.length()-1));
            sb.deleteCharAt(sb.length()-1);
        }
        return sb.toString();
    }
    public String rotateToNewString(StringBuffer sb){
        for (int i = 1; i < sb.length(); i=i+2) {
            char c= (char) ((sb.charAt(i)-'0'+rotate)%10+'0');
            sb.setCharAt(i,c);
        }
        return sb.toString();
    }
    public String rotateToNewString1(StringBuffer sb){
        for (int i = 0; i < sb.length(); i=i+2) {
            char c= (char) ((sb.charAt(i)-'0'+rotate)%10+'0');
            sb.setCharAt(i,c);
        }
        return sb.toString();
    }

}
Copy the code