2

如何实现给定字符串 A 生成字符串 B 的函数 increment(string)，其中：

  1. B > A（使用 Java 的 compareTo 逻辑）
  2. 存在 NO C 其中 B > C > A

给定字符串 A 产生字符串 B 的减量（字符串）也是如此，其中：

  1. B < A（使用 Java 的 compareTo 逻辑）
  2. 存在 NO C 其中 B < C < A

编辑

正如评论中所指出的，如果没有一些限制，这个问题是不可能回答的。限制是您不能在字符串中追加/删除新字符，除非它是为了处理流量不足/溢出。

4

4 回答 4

5

增量很简单：B = A + "\u0000".

减量是不可能的；"Y"例如，小于 的最大字符串是"X\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF\uFFFF..."。

于 2012-10-10T20:43:34.280 回答
1

我认为您可以将增量写为：

    str = str.substring(0, str.length()-1)+((char)(str.charAt(str.length()-1)+1));

并递减为：

    str = str.substring(0, str.length()-1)+((char)(str.charAt(str.length()-1)-1));

这里一定要处理边界条件，即在递增期间，如果您的字符串最高，而在递减期间，您的字符串是最小的。

于 2012-10-10T20:48:26.273 回答
1

试试这个：（编辑修复了一些错误，编辑2：测试工作，但比较失败）

import static org.junit.Assert.*;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
class Ids {
    Ids(char min,char max) {
        this.min=min;
        this.max=max;
        n=max-min+1;
    }
    String inc(String s) {
        if(print)
            System.out.println("inc "+s);
        String t="";
        char c=s.charAt(s.length()-1);
        char o=c==max?min:(char)(c+1);
        boolean carry=o==min;
        t+=o;
        for(int i=s.length()-2;i>=0;i--) {
            c=s.charAt(i);
            if(carry) {
                o=c==max?min:(char)(c+1);
                carry=o==min;
            } else o=c;
            t+=o;
        }
        if(carry)
            t+=min;
        t=reverse(t);
        if(print)
            System.out.println("inc returns "+t);
        int compare=s.compareTo(t);
        if(compare!=-1)
            System.out.println("compare fails: "+s+"<>"+t+" returns "+compare);
        return t;
    }
    private static String reverse(String t) {
        String t2="";
        for(int i=0;i<t.length();i++)
            t2+=t.charAt(t.length()-1-i);
        return t2;
    }
    String dec(String s) {
        if(print)
            System.out.println("dec "+s);
        String t="";
        char c=s.charAt(s.length()-1);
        if(c==min&&s.length()==1)
            return null;
        char o=c==min?max:(char)(c-1);
        boolean borrow=o==max;
        t+=o;
        if(print)
            System.out.println("last character, t="+t);
        for(int i=s.length()-2;i>=0;i--) {
            c=s.charAt(i);
            if(print)
                System.out.println("in loop, c="+c);
            if(borrow) {
                if(c==min) {
                    o=max;
                    borrow=true;
                } else {
                    o=--c;
                    borrow=false;
                }
                // o=c==min?max:(char)(c-1);
                // borrow=o==max;
            } else o=c;
            if(print)
                System.out.println("in loop, adding: "+o);
            t+=o;
            if(print)
                System.out.println("in loop, t="+t);
        }
        if(borrow)
            t=t.substring(0,t.length()-1);
        t=reverse(t);
        if(print)
            System.out.println("dec returns "+t);
        int compare=s.compareTo(t);
        if(compare!=1)
            System.out.println("compare fails: "+s+"<>"+t+" returns "+compare);
        return t;
    }
    void run(String s) {
        String i=inc(s);
        String d=dec(s);
        System.out.println(d+"<"+s+"<"+i);
    }
    void run() {
        print();
        run("b");
        run("c");
        run("y");
        run("z");
    }
    public static void main(String[] args) {
        new Ids('a','z').run();
    }
    void print() {
        System.out.println("min="+min+", max="+max+",range="+n);
    }
    static boolean print;
    final char min,max;
    final int n;
}
public class So12827926TestCase {
    @Before public void setUp() throws Exception {
        Ids.print=false;
    }
    @After public void tearDown() throws Exception {
        Ids.print=false;
    }
    @Test public void testIncDecOnOneCharacter() {
        for(char c=ids.min;c<ids.max;c++) {
            String original=""+(char)(c);
            String expected=""+(char)(c+1);
            String actual=ids.inc(""+(char)c);
            assertEquals(expected,actual);
            String duplicate=ids.dec(expected);
            assertEquals(original,duplicate);
        }
    }
    @Test public void testDecIncOnOneCharacter() {
        for(char c=(char)(ids.min+1);c<=ids.max;c++) {
            String original=""+(char)(c);
            String expected=""+(char)(c-1);
            String actual=ids.dec(""+(char)c);
            assertEquals(expected,actual);
            String duplicate=ids.inc(expected);
            assertEquals(original,duplicate);
        }
    }
    @Test public void testIncDecEdgeCaseOnOneCharacter() {
        String original=""+ids.max;
        String expected=""+ids.min+ids.min;
        String actual=ids.inc(original);
        assertEquals(expected,actual);
        String duplicate=ids.dec(expected);
        assertEquals(original,duplicate);
    }
    @Test public void testIncEdgeCaseOnTwoCharacters() {
        String original=""+ids.min+ids.min;
        String expected=""+ids.min+(char)(ids.min+1);
        String actual=ids.inc(original);
        assertEquals(expected,actual);
    }
    @Test public void testDecIncEdgeCaseOnOneCharacter() {
        String original=""+ids.min;
        String expected=null;
        String actual=ids.dec(original);
        assertEquals(expected,actual);
        if(expected!=null) {
            String duplicate=ids.inc(expected);
            assertEquals(original,duplicate);
        }
    }
    @Test public void testIncDecEdgeCaseOnTwoCharacters() {
        String original=""+ids.min+ids.max;
        String expected=""+(char)(ids.min+1)+ids.min;
        String actual=ids.inc(original);
        assertEquals(expected,actual);
        String duplicate=ids.dec(expected);
        assertEquals(original,duplicate);
    }
    @Test public void testDecIncEdgeCaseOnTwoCharacters() {
        String original=""+ids.max+ids.min;
        String expected=""+(char)(ids.max-1)+ids.max;
        String actual=ids.dec(original);
        assertEquals(expected,actual);
        String duplicate=ids.inc(expected);
        assertEquals(original,duplicate);
    }
    @Test public void testIncDecEdgeCaseOnThreeCharacters() {
        String original=""+ids.min+ids.max+ids.max;
        String expected=""+(char)(ids.min+1)+ids.min+ids.min;
        String actual=ids.inc(original);
        assertEquals(expected,actual);
        String duplicate=ids.dec(expected);
        assertEquals(original,duplicate);
    }
    @Test public void testDecIncEdgeCaseOnThreeCharacters() {
        String original=""+ids.max+ids.min+ids.min;
        String expected=""+(char)(ids.max-1)+ids.max+ids.max;
        String actual=ids.dec(original);
        assertEquals(expected,actual);
        String duplicate=ids.inc(expected);
        assertEquals(original,duplicate);
    }
    @Test public void testDecIntForSomeEdgeCases() {
        Ids ids=new Ids('a','z'); 
        for(int i=0;i<originals.length;i++) {
            String original=originals[i];
            String expected=expecteds[i];
            String actual=ids.dec(original);
            assertEquals(expected,actual);
            String duplicate=ids.inc(expected);
            assertEquals(original,duplicate);
        }
    }
    @Test public void testIncDecForSomeEdgeCases() {
        Ids ids=new Ids('a','z'); 
        for(int i=0;i<originals.length;i++) {
            String original=expecteds[i];
            String expected=originals[i];
            String actual=ids.inc(original);
            assertEquals(expected,actual);
            String duplicate=ids.dec(expected);
            assertEquals(original,duplicate);
        }
    }
    @Test public void testInc() {
        Ids ids=new Ids('a','z'); 
        String start=""+ids.min,s=start;
        for(int i=0;i<ids.n-1;i++) 
            s=ids.inc(s);
        assertEquals(""+ids.max,s);
    }
    @Test public void testDec() {
        Ids ids=new Ids('a','z'); 
        String start=""+ids.max,s=start;
        for(int i=0;i<ids.n-1;i++) 
            s=ids.dec(s);
        assertEquals(""+ids.min,s);
    }
    Ids ids=new Ids('a','b');
    // swap these, they will make more sense that way.
    static final String[] originals=new String[]{"baa","caa","daa","xaa","yaa","zaa"};
    static final String[] expecteds=new String[]{"azz","bzz","czz","wzz","xzz","yzz"};
}
于 2012-10-10T23:36:24.787 回答
0

正如你对数字所做的那样。例如，取一个数字ABCD。D通过增加 可以找到下一个数字1。但如果这导致D成为0，你必须增加C。等等。将字符串视为数字，其中每个数字实际上是一个 16 位值。减少的方法相同。如何做到这一点的技术部分掌握在您手中。

于 2012-10-10T20:47:31.220 回答