目录

每日算法(二)–字符串

字符串中数字子串的求和

思路: 利用3个变量

// 目前的累加和
int res 
// 当前收集到的数字
int num
// num的正负值
boolean posi

public int numSum(String str) {
        if (str == null) return 0;
        char[] charArr = str.toCharArray();
        int res = 0;
        int num = 0;
        boolean posi = true;
        int cur = 0;
        for (int i = 0; i < charArr.length; i++) {
            cur = charArr[i] - '0';
            // 不属于字母 0 ~ 9
            if (cur < 0 || cur > 9) {
                res += num;
                num = 0;
                // 如果等于-
                if (charArr[i] == '-') {
                    // 前面还有个-号
                    if (i - 1 > -1 && charArr[i - 1] == '-') {
                        posi = !posi;
                        // 否则就直接改为符号
                    } else {
                        posi = false;
                    }
                } else {
                    posi = true;
                }
                // 不属于0 ~ 9
            } else {
                num = num * 10 + (posi ? cur : -cur);
            }
        }
        res += num;
        return res;
    }

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

如果一个字符串st，把字符串str前面任意的部分挪到后面形成的字符串叫作str的旋转词。比如str”12345”，str的旋转词有”12345”、”23451”、”34512”、”45123”和”51234”。 给定两个字符串a和b，请判断a和b是否互为旋转词。

要求: 如果a和b长度不一样，那么a和b必然不互为旋转词，可以直接返回 false。当a和b长度一样，都为N时，要求解法的时间复杂度为O（N）

这里的是要求时间复杂度为O(N) 如果用库函数是不能满足要求的 得使用KMP算法

思路: 让第二个字符串生成一个大串 判断是否存在

	public static 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 Algorithm
	public static int getIndexOf(String s, String m) {
		if (s.length() < m.length()) {
			return -1;
		}
		char[] ss = s.toCharArray();
		char[] ms = m.toCharArray();
		int si = 0;
		int mi = 0;
		int[] next = getNextArray(ms);
		while (si < ss.length && mi < ms.length) {
			if (ss[si] == ms[mi]) {
				si++;
				mi++;
			} else if (next[mi] == -1) {
				si++;
			} else {
				mi = next[mi];
			}
		}
		return mi == ms.length ? si - mi : -1;
	}

	public static int[] getNextArray(char[] ms) {
		if (ms.length == 1) {
			return new int[] { -1 };
		}
		int[] next = new int[ms.length];
		next[0] = -1;
		next[1] = 0;
		int pos = 2;
		int cn = 0;
		while (pos < next.length) {
			if (ms[pos - 1] == ms[cn]) {
				next[pos++] = ++cn;
			} else if (cn > 0) {
				cn = next[cn];
			} else {
				next[pos++] = 0;
			}
		}
		return next;
	}

字符串的统计子串

给定一个字符串str，返回str的统计字符串。例如，” aaabbadddff”的统计字符串为 “a_3_b_2_a_l_d_3_f_2_c_l”

public static String staitisNum(String str) {
        if (str == null || str.length() == 0) return "";
        char cur = 0;
        int sum = 0;
        StringBuffer sb = new StringBuffer();
        char[] chars = str.toCharArray();
        String strs = null;
        for (int i = 0; i < chars.length; i++) {
            if (cur == 0) {
                cur = chars[i];
                sum = 1;
            } else if (chars[i] == cur) {
                sum++;
            } else {
                strs = cur + "_" + sum + "_";
                sb.append(strs);
                cur = chars[i];
                sum = 1;
            }
        }
        sb.append(cur + "_" + sum);
        return sb.toString();
    }
// 时间:O(N) 空间:O(N)