String

判断两个字符串是否互为变形词

time = n（字符串长度）, space = M（字符种类数）
如果字符种类很多，可以用哈希表代替长度为256的整型数组

public boolean isDeformation(String str1, String str2) {
    if (str1 == null || str2 == null || str1.length() != str2.length()) {
        return false;
    }

    char[] chas1 = str1.toCharArray();
    char[] chas2 = str1.toCharArray();
    int[] map = new int[256];

    for (char ch : chas1) {
        map[ch]++;
    }
    for (char ch : chas2) {
        if (map[ch]-- == 0) {
            return false;
        }
    }
    return true;
}

字符串中数字子串的求和

time = n, space = 1
数组操作一定要注意下标越界问题
本题解法：负号和数字放一组解决

public int numSum(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }

    int minusNum = 0;
    int cur = 0;
    int sum = 0;
    char[] chas = str.toCharArray();

    for (int i = 0; i < chas.length;) {
        while (chas[i] == '-') {
            minusNum++;
            i++;
        }
        while (i < chas.length && Character.isDigit(chas[i])) {
            cur = cur * 10 + chas[i] - 48;
            i++;
        }
        if (cur == 0) {
            i++;
        } else {
            sum += (minusNum & 1) == 0 ? cur : -cur;
        }
        minusNum = 0;
        cur = 0;
    }
    return sum;
}

去掉字符串中连续出现k个0的子串

time = n, space = 1
注意：字符0和数字0不同，数字0在数组转回字符串时不会带入。
字符数组中0值相当于没有赋值的状态

public String removeKZeros(String str, int k) {
    if (str == null || str.length() == 0 || k < 1) {
        return str;
    }

    char[] chas = str.toCharArray();
    int start = -1;
    int count = 0;

    for (int i = 0; i < chas.length; i++) {
        if (chas[i] == '0') {
            count++;
            start = start == -1 ? i : start;
        } else {
            if (count == k) {
                while (count-- != 0) {
                    chas[start++] = 0;
                }
            }
            count = 0;
            start = -1;
        }
    }

    if (count == k) {
        while (count-- != 0) {
            chas[start++] = 0;
        }
    }
    return String.valueOf(chas);
}

判断两个字符串是否互为旋转词

public boolean isRotation(String a, String b) {
    if (a == null || b == null || a.length() != b.length()) {
        return false;
    }
    String b2 = b + b;
    
    // return getIndexOf(b2, a) != -1 KMP算法
    return b2.contains(a);
}

替换字符串中连续出现的指定字符串

先替换为0

public String replace(String str, String from, String to) {
    if (str == null || from == null || to == null) {
        return str;
    }

    char[] chs = str.toCharArray();
    int match = 0;
    // 包含from部分转为0
    for (int i = 0; i < chs.length; i++) {
        match = chs[i] == from.charAt(match) ? match + 1 : 0;
        if (match == from.length()) {
            int j = i;
            while (match > 0) {
                chs[j--] = '0';
                match--;
            }
        }
    }

    // 0转为to
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < chs.length; i++) {
        if (chs[i] == '0') {
            if (i == chs.length - 1 || chs[i + 1] != '0') {
                res.append(to);
            }
        } else {
            res.append(chs[i]);
        }
    }
    return res.toString();
}

字符串的统计字符串

public String getCountString(String str) {
    if (str == null || str.length() == 0) {
        return null;
    }

    char[] chs = str.toCharArray();
    char cur = chs[0];
    int num = 1;
    String res = "";

    for (int i = 1; i < chs.length; i++) {
        if (chs[i] == cur) {
            num++;
        } else {
            res = concat(res, chs, cur, num);
            num = 1;
            cur = chs[i];
        }
    }
    return concat(res, chs, cur, num);
}

public String concat(String res, char[] chs, char cur, int num) {
    return res + cur + '_' + num;
}

判断字符数组中是否所有的字符都只出现过一次

// time = n
public boolean isUniquel(char[] chas) {
    if (chas == null || chas.length < 2) {
        return true;
    }

    boolean[] map = new boolean[256];
    for (int i = 0; i < chas.length; i++) {
        if (map[chas[i]]) {
            return false;
        }
        map[chas[i]] = true;
    }
    return true;
}

字符串的调整与替换

time = n, space = 1

public void replace(char[] chas) {
    if (chas == null || chas.length == 0) {
        return;
    }

    // 字符数
    int charNum = 0;
    // 左半区长度
    int leftLen = 0;
    for (int i = 0; i < chas.length; i++) {
        if (Character.isLetter(chas[i])) {
            charNum++;
            leftLen = i + 1;
        }
    }

    int j = leftLen + (leftLen - charNum) * 2;
    for (int i = leftLen - 1; i >= 0; i--) {
        if (chas[i] == ' ') {
            chas[j--] = '0';
            chas[j--] = '2';
            chas[j--] = '%';
        } else {
            chas[j--] = chas[i];
        }
    }
}

翻转字符串

time = n, space = 1
先全部翻转，再按单词翻转

public void ratateWord(char[] chas) {
    if (chas == null || chas.length == 0) {
        return;
    }

    reverse(chas, 0, chas.length - 1);

    int left = -1;
    int right = -1;

    for (int i = 0; i < chas.length; i++) {
        if (chas[i] != ' ') {
            if (i == 0 || chas[i - 1] == ' ') {
                left = i;
            }
            if (i == chas.length - 1 || chas[i + 1] == ' ') {
                right = i;
            }
        }
        if (left != -1 && right != -1) {
            reverse(chas, left, right);
            left = -1;
            right = -1;
        }
    }
}

public void reverse(char[] chas, int start, int end) {
    char tmp;
    while (start < end) {
        tmp = chas[start];
        chas[start] = chas[end];
        chas[end] = tmp;
        start++;
        end--;
    }
}

括号字符串的有效性

public boolean isValid(String str) {
    if (str == null || str.length() == 0) {
        return false;
    }

    int leftNum = 0;
    int rightNum = 0;
    char[] chas = str.toCharArray();
    int len = chas.length;

    for (int i = 0; i != len; i++) {
        if (chas[i] == '(') {
            leftNum++;
        } else if (chas[i] == ')') {
            rightNum++;
        } else {
            return false;
        }
        if (rightNum > leftNum) {
            return false;
        }
    }
    if (rightNum == leftNum) {
        return true;
    }
    return false;
}

找到被指的新类型字符

// 判断字符是不是数字
Character.isDigit('c');
// 判断字符是不是大写字母
Character.isUpperCase('c');
// 判断字符是不是小写字母
Character.isLowerCase('c');

public String pointNewchar(String s, int k) {
    if (s == null || s.length() == 0 || k < 0 || k >= s.length()) {
        return null;
    }
    
    // k前面连续大写字母的数量
    int upperNum = 0;
    char[] chas = s.toCharArray();

    for (int i = k - 1; i >= 0 ; i--) {
        if (!Character.isUpperCase(chas[i])) {
            break;
        }
        upperNum++;
    }
    
    if ((upperNum & 1) == 1) {
        return s.substring(k - 1, k + 1);
    }
    
    if (Character.isUpperCase(chas[k])) {
        return s.substring(k, k + 2);
    }
    return String.valueOf(chas[k]);
}