反转一个字符串的算法

向右看齐 2022-07-25 20:27 119阅读 0赞

这个功能在java的JDK中StringBuffer的父类已经实现了，实现代码如下（不相关代码已经省略）：

abstract class AbstractStringBuilder implements Appendable, CharSequence { 
        /** * The value is used for character storage. */
        char[] value;
        /** * The count is the number of characters used. */
        int count;
        /** * Causes this character sequence to be replaced by the reverse of * the sequence. If there are any surrogate pairs included in the * sequence, these are treated as single characters for the * reverse operation. Thus, the order of the high-low surrogates * is never reversed. * (省略部分注释).... * @return a reference to this object. */
        public AbstractStringBuilder reverse() {
            boolean hasSurrogates = false;
            //n为字符串长度
            int n = count - 1;
            //循环交换
            //(n-1) >> 1 位移算法的结果是取到了对数
            for (int j = (n-1) >> 1; j >= 0; j--) {
                //j是最后一个，n-j是第一个
                int k = n - j;
                //进行交换，从中间向两端交换，如果n为奇数，则第一次交换j和k相等。
                char cj = value[j];
                char ck = value[k];
                value[j] = ck;
                value[k] = cj;
                //判断cj和ck是否是合法的字符
                if (Character.isSurrogate(cj) ||
                    Character.isSurrogate(ck)) {
                    hasSurrogates = true;
                }
            }
            //存在Surrogate，如果存在，循环一次将所有Surrogate位置交换回来，否则无法正常显示了。
            if (hasSurrogates) {
                reverseAllValidSurrogatePairs();
            }
            return this;
        }
        /** Outlined helper method for reverse() */
        private void reverseAllValidSurrogatePairs() {
            for (int i = 0; i < count - 1; i++) {
                char c2 = value[i];
                if (Character.isLowSurrogate(c2)) {
                    char c1 = value[i + 1];
                    if (Character.isHighSurrogate(c1)) {
                        value[i++] = c1;
                        value[i] = c2;
                    }
                }
            }
        }
    }
    
    /** * 省略了部分代码 */
    public final class Character implements java.io.Serializable, Comparable<Character> { 
        public static boolean isSurrogate(char ch) {
            return ch >= MIN_SURROGATE && ch < (MAX_SURROGATE + 1);
        }
        //判断字符是否是Surrogate的高位字符
        public static boolean isHighSurrogate(char ch) {
            // Help VM constant-fold; MAX_HIGH_SURROGATE + 1 == MIN_LOW_SURROGATE
            return ch >= MIN_HIGH_SURROGATE && ch < (MAX_HIGH_SURROGATE + 1);
        }
    }

补充说明：需要用2个字符表示一个超大字符集的汉字，这这种表示方式称之为 Surrogate。