代码之家  ›  专栏  ›  技术社区  ›  BUY

一个字符一个字符地交换两个子字符串

  •  2
  • BUY  · 技术社区  · 7 年前

    我有一个字符串,例如:

    "AAA UUU"
    

    我想收到:

    "UUU AAA" 在最后打印每个步骤,同时得到这个解决方案。

    但我只能一次改变一个字符,例如,如果我有

    AA UU 起初我只能拥有

    A AUU
    AAU U
    

    在另一个时间,因为我只能改变一个字符的地方与一个空间。

    如果我有

    AAA UUU 
    

    下一步我可以

    A AAUUU AAAUU U 所以第二个离开空间的炭也可以改变。

    我知道这个问题有点复杂,但这个问题很难解释。如果你能指导我解决一些问题,或者给我一些关于如何解决这个问题的建议,我将不胜感激(我对任何算法都持开放态度)。

    你可以通过下面的代码来改变字母的位置并获得所需的结果,但是我想通过改变字符与空间来实现它,但它不这样做:

    // The Solution of Problem 2 begins
    File file2 = new File(args[1]);
    Scanner reader2 = new Scanner(file2); // The Scanner that is going to read file2.
    ArrayList<String> solution2List = new ArrayList<String>();
    try {  
        while(reader2.hasNext()) {
            solution2List.add(reader2.nextLine());
        }
    
        for(int i = 0; i < solution2List.size(); i++) {
    
            if(i == 0) {
                System.out.println("\nThe 1st String:");
           }
           else if(i == 1) {
                System.out.println("\nThe 2nd String:");
           }
           else {
                System.out.println("\nThe " + (i+1) + "th String:");
           }
    
           System.out.println("The Original Form = " + solution2List.get(i));
           stringCharPlaceChanger(solution2List.get(i));
    
        } 
    }
    finally {
        if(reader2 != null)
            reader2.close();
    }
    
    public static void stringCharPlaceChanger(String stringToChange) {
        int indexOfSpace = stringToChange.indexOf(" ");
        char[] charArrayForProcessing = stringToChange.toCharArray();
        int changeAfterSpace = 0;
        char[] charAfterSpace = stringToChange.substring(indexOfSpace+1, stringToChange.length()).toCharArray();
        System.out.print("CHARSAFTERSPACE = ");
        System.out.println(charAfterSpace);
        int charAfterSpaceCount = charAfterSpace.length;
    
        // Sliding The Chars Before Space After Space.
        while(charArrayForProcessing[0] != ' ') {
            charArrayForProcessing[indexOfSpace] = charArrayForProcessing[indexOfSpace-1];
            charArrayForProcessing[indexOfSpace-1] = ' ';
            indexOfSpace--;
            changeAfterSpace++; // Incrementing When a Char Gets Past Right to the Space.
            System.out.println(charArrayForProcessing);
        }
    
        int changeAfterSpaceToBeIncremented = changeAfterSpace; // Initially.
        int indexCountHolder = 0;
        for(int i = 0; i < charAfterSpaceCount; i++) {
            changeAfterSpaceToBeIncremented++;
            int changeCounterBack = changeAfterSpaceToBeIncremented;
    
            while(changeCounterBack != indexCountHolder) {
                char temporaryCharHolder = charArrayForProcessing[changeCounterBack];
                charArrayForProcessing[changeCounterBack] = charArrayForProcessing[changeCounterBack-1];
                charArrayForProcessing[changeCounterBack-1] = temporaryCharHolder;
                changeCounterBack--;
                System.out.println(charArrayForProcessing);
            }
            indexCountHolder++;
        }
    

    左边的空间只能是一样的炭,右边的空间只能是另一个相同的炭。

    可能的输入:

    • “AAA BB”

    • “uuuuu cccccccccccc”

    • “A”

    • “购买力平价”

    产出将是:

    • “BB-AAA”

    • “cccccccccccccccccc uuuuu”

    • “B A”

    • “购买力平价”

    只有与空间相邻的字符和它们附近的其他1个字符可以用空间来改变它们的位置。

    3 回复  |  直到 7 年前
        1
  •  1
  •   Loris Securo    7 年前

    我的算法是:

    while there are chars to move from right to the far left:
     a. move a char from right to the far left
     b. reset position to next char to move
    

    a 我使用这个基本算法:

     1. a_b
     2. ab_
     3. _ba
     4. b_a
     5. check if we are in situation 2 and repeat from there
    

    b 我只是把空间从左移到右。

    这是我的实现:

    public class StringCharPlaceChanger {
    
        public static void main(String[] args) {
    
            String input = "AAA BB";
            System.out.println("Input: " + input);
            System.out.println();
    
            String result = stringCharPlaceChanger(input);
    
            System.out.println();
            System.out.println("Output: " + result);
    
        }
    
        public static String stringCharPlaceChanger(String stringToChange) {
    
            // input can not be null
            if (stringToChange == null) {
                System.out.println("Error: string can not be null");
                return null;
            }
    
            // index of space
            int x = stringToChange.indexOf(" ");
    
            // a space is required
            if (x == -1) {
                System.out.println("Error: no space found");
                return null;
            }
    
            // input converted in array
            char[] c = stringToChange.toCharArray();
    
            // number of chars on the left
            int numberOfLeft = x;
    
            // number of chars on the right
            int numberOfRight = c.length - x - 1;
    
            // length of the input
            int l = c.length;
    
            boolean first = true;
    
            // print of the original input
            System.out.println(stringToChange);
    
            while (numberOfRight > 0) {
    
                // after the first cycle
                if (!first) {
                    // reset the position of the space near the next number to move 
                    x = goTo(c, x, l - numberOfRight - 1);
                }
                else {
                    first = false;
                }
    
                // move a char from right to left
                // basic algorithm:
                // a_b
                // ab_
                // _ba
                // b_a
    
                // a_b -> ab_
                x = swap(c, x, x + 1);
                for (int left = numberOfLeft; left > 0; left--) {
                    // ab_ -> _ba
                    x = swap(c, x, x - 2);
                    // _ba -> b_a
                    x = swap(c, x, x + 1);
                }
    
                numberOfRight--;
    
            }
    
            return new String(c);
        }
    
        // swap 2 chars
        private static int swap(char[] c, int i, int j) {
            char temp = c[i];
            c[i] = c[j];
            c[j] = temp;
            System.out.println(c);
            return j;
        }
    
        // go from left to right swapping chars
        private static int goTo(char[] c, int i, int j) {
            while (i < j) {
                if (i == j - 1) {
                    i = swap(c, i, i + 1);
                }
                else {
                    i = swap(c, i, i + 2);
                }
            }
            return j;
        }
    
    }
    
        2
  •  2
  •   Anonymous    7 年前

    我对算法的想法是:

    1. 验证字符串是否满足:
      • 它只有一个空间
      • 在空格的左边只有一个字符值(重复)
      • 右边有一个值(重复)
      • 如果需要,还要验证左右值是否不同
    2. 重复以上步骤,直到得到结果:

       If the space is in the spot where it should be in the end
           swap it with some character that is in the wrong place
       else
           swap it with a character that should be where the
                  space is and is not in its correct place
      

    感谢qwertyman指出后者总是可能的:如果空间不在它的最终位置,那么其他字符应该在空间所在的位置,因为它不在,所以至少有一个字符的副本在它不应该在的位置。

    您可能需要编写一个单元测试。对于每个测试用例,您应该验证

    1. 得到正确的结果
    2. 每一步都用另一个char交换空间,并保留剩余的char。

    对于实际的代码,您还可以进行单元测试,以确定验证步骤捕获了所有可能的输入错误。在你的情况下,这是否有价值,你自己判断。我很想这么做。

        3
  •  1
  •   Leo Aso    7 年前

    这是我的实现。基本上,它从两端向内工作,根据需要用空格交换一个或两个结束字符。

    import java.io.*;
    import java.util.*;
    
    public class SpaceReverse {
        public static void main(String[] args) {
            String[] tests = {
                "aa bb", "aa bbb", "aa bbbb", "aaa bb", "aaaa bb",
                " ", "Hello world", " Hello", "Hello ", " Hello "
            };
            for (String s : tests) {
                new SpaceReverse(s, System.out).run();
                System.out.println();
            }
        }
    
        private final StringBuilder sb;
        private final PrintStream ps;
    
        // new SpaceReverse("a b").run() just 
        // returns the result without printing anything while
        // new SpaceReverse("a b", System.out).run() prints each step
    
        public SpaceReverse(String s) {
            this(s, null);
        }
    
        public SpaceReverse(String s, PrintStream output) {
            if (!s.contains(" ")) {
                throw new IllegalArgumentException("no space in " + s);
            }
            sb = new StringBuilder(s);
            ps = output;
        }
    
        private void swap(int i1, int i2) {
            char c1 = sb.charAt(i1);
            char c2 = sb.charAt(i2);
            sb.setCharAt(i1, c2);
            sb.setCharAt(i2, c1);
    
            if (ps != null) ps.println(sb);
        }
    
        public String run() {
            if (ps != null) ps.println(sb);
    
            int lower = 0;
            int upper = sb.length() - 1;
            int space = sb.indexOf(" ");
            int newSpace = sb.length() - space - 1;
    
            while (true) {
                if (lower >= upper) {
                    break;
                } else if (space == lower) {
                    swap(lower, upper);
                    space = upper;
                    lower++;
                } else if (space == upper) {
                    swap(lower, upper);
                    space = lower;
                    upper--;
                } else {
                    swap(space, lower);
                    swap(lower, upper);
                    swap(upper, space);
                    lower++;
                    upper--;
                }
            }
    
            // if the space is not in the right place
            // one of these loops will move it there
            while (space < newSpace) {
                swap(space, space + 1);
                space++; 
            }
            while (space > newSpace) {
                swap(space, space - 1);
                space--;
            }
    
            return sb.toString();
        }
    }