字符串字符判重算法
package string; public class UniqueCharacter { public static void main(String[] args) { System.out.println(isUniqueCharacter("apple".toCharArray())); System.out.println(isUniqueCharacter("abc%^".toCharArray())); System.out.println(isUniqueSmallAlphabetChars("defghjkl".toCharArray())); System.out.println(isUniqueSmallAlphabetChars("#$killer".toCharArray())); } public static boolean isUniqueCharacter(char[] str) { if (str.length > 256) return false; //为每次字符，保留一个标记 boolean[] charSet = new boolean[256]; for (int i = 0; i < str.length; i++) { byte index = (byte) str[i]; if (charSet[index]) { return false; } charSet[index] = true; } return true; } public static boolean isUniqueSmallAlphabetChars(char[] str) { if (str.length > 26) { return false; } // 使用位操作以改进空间占用 int checker = 0; for (int i = 0; i < str.length; i++) { int index = str[i] - 'a'; if (index < 0 || index > 26 || (checker & (1 << index)) > 0) { return false; } checker |= (1 << index); } return true; }}字符串反转算法
package string;public class ReverseString { public static void main(String[] args) { String text1 = "ABC1DEF"; String text2 = "ABC1DEFG"; char[] t1 = text1.toCharArray(); char[] t2 = text2.toCharArray(); reversePartOfString(t1, 1, t1.length - 2); reversePartOfString(t2, 1, t2.length - 2); String s1 = new String(t1); String s2 = new String(t2); System.out.println(s1); System.out.println(s2); String text3 = "ABC1DEF"; String text4 = "ABC1DEFG"; char[] t3 = text3.toCharArray(); char[] t4 = text4.toCharArray(); reverseArrayByXor(t3); reverseArrayByXor(t4); String s3 = new String(t3); String s4 = new String(t4); System.out.println(s3); System.out.println(s4); } public static void reversePartOfString(char[] str, int begin, int length) { char temp; for (int i = begin, j = begin + length - 1; i < j; i++, j--) { temp = str[i]; str[i] = str[j]; str[j] = temp; } } public static void reversePartOfStringWithWhile(char[] str, int begin, int length) { char temp; int i = begin; int j = begin + length - 1; while (i < j) { temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } } public static void reverseArray(char[] str) { char temp; for (int i = 0, j = str.length - 1; i < j; i++, j--) { temp = str[i]; str[i] = str[j]; str[j] = temp; } } public static void reverseArrayByXor(char[] str) { for (int i = 0, j = str.length - 1; i < j; i++, j--) { str[i] ^= str[j]; str[j] ^= str[i]; str[i] ^= str[j]; } }}左旋字符串
package string;public class LeftRotateString { public static void main(String[] args) { String s1 = "abcdefg"; String s2 = "abcdefgh"; char[] a1 = s1.toCharArray(); char[] a2 = s2.toCharArray(); leftRotateString(a1, 2); leftRotateStringByGcd(a2, 2); String str1 = new String(a1); String str2 = new String(a2); System.out.println(str1); System.out.println(str2); } public static void leftRotateString(char[] str, int m) { reverseString(str, 0, m - 1); reverseString(str, m, str.length - 1); reverseString(str, 0, str.length - 1); } private static void reverseString(char[] str, int begin, int end) { char temp; int i = begin; int j = end; while (i < j) { temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } } private static int gcd(int m, int n) { int k = m % n; if (k == 0) { return n; } else { return gcd(n, k); } } public static void leftRotateStringByGcd(char[] str, int m) { int n = str.length; int g = gcd(n, m); int e = n / g; char temp; for (int i = 0; i < g; i++) { temp = str[i]; int j = 0; for (; j < e - 1; j++) { str[(i + j * m) % n] = str[(i + (j + 1) * m) % n]; } str[(i + j * m) % n] = temp; } }}右旋字符串
package string;public class RightRotateString { public static void main(String[] args) { String s1 = "abcdefg"; String s2 = "abcdefgh"; char[] t1 = s1.toCharArray(); char[] t2 = s2.toCharArray(); rightRotateString(t1, 2); rightRotateString(t2, 2); String str1 = new String(t1); String str2 = new String(t2); System.out.println(str1); System.out.println(str2); } public static void rightRotateString(char[] str, int m) { reverseString(str, 0, str.length - m - 1); reverseString(str, str.length - m, str.length - 1); reverseString(str, 0, str.length - 1); } private static void reverseString(char[] str, int begin, int end) { char temp; int i = begin; int j = end; while (i < j) { temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } }}字符串旋转匹配算法
package string;public class RotateMatch { public static void main(String[] args) { String s1 = "apple"; String s2 = "elppa"; String s3 = "elppp"; System.out.println(checkRotate(s1, s2)); System.out.println(checkRotate(s1, s3)); } public static boolean checkRotate(String s1, String s2) { if (s1.length() != s2.length()) return false; for (int i = 0, j = s2.length() - 1; i < s2.length(); i++, j--) { if (s1.charAt(i) != s2.charAt(j)) { return false; } } return true; }}字符串包含算法
package string;public class ContainString { public static void main(String[] args) { String s1 = "abcdefg"; String s2 = "adg"; String s3 = "kgl"; System.out.println(isContainsAllChars(s1.toCharArray(), s2.toCharArray())); System.out.println(isContainsAllChars(s1.toCharArray(), s3.toCharArray())); } public static boolean isContainsAllChars(char[] s1, char[] s2) { int hash = 0; for (int i = 0; i < s1.length; i++) { hash |= (1 << (s1[i] - 'A')); } for (int i = 0; i < s2.length; i++) { if ((hash & (1 << (s2[i] - 'A'))) == 0) { return false; } } return true; }}字符串原地替换算法
package string;public class ReplaceString { public static void main(String[] args) { char[] s1 = new char[100]; for (int i = 0; i < 9; i += 3) { s1[i] = 'a'; s1[i + 1] = 'b'; s1[i + 2] = 'c'; } System.out.println(new String(s1)); replaceAllChars(s1, 9, 'b', "&^%".toCharArray()); System.out.println(new String(s1)); } public static void replaceAllChars(char[] s1, int s1Length, int p, char[] s2) { int count = 0; for (int i = 0; i < s1Length; i++) { if (s1[i] == p) { count++; } } int newLength = s1Length + s2.length * count; //从后向前进行替换，避免数据丢失 for (int i = s1Length - 1; i >= 0; i--) { if (s1[i] == p) { for (int j = 0; j < s2.length; j++) { s1[newLength - s2.length + j] = s2[j]; } newLength = newLength - s2.length; } else { s1[newLength - 1] = s1[i]; newLength = newLength - 1; } } }}字符串压缩算法
package string; public class CompressString { public static void main(String[] args) { String s1 = "aabccccaaa"; System.out.println(s1); char[] s2 = compress(s1.toCharArray()); System.out.println(new String(s2)); String s3 = "aabccdeeaa"; System.out.println(s3); char[] s4 = compress(s3.toCharArray()); System.out.println(new String(s4)); } public static char[] compress(char[] s) { //如果压缩后比原来还长，则不必压缩 int size = countCompression(s); if (size > s.length) { return s; } //根据压缩后的长度创建数组 char[] compressed = new char[size]; int index = 0; char last = s[0]; int count = 1; for (int i = 0; i < s.length; i++) { if (s[i] == last) { count++; } else { index = appendChar(compressed, last, index, count); last = s[i]; count = 1; } } index = appendChar(compressed, last, index, count); return compressed; } public static int appendChar(char[] array, char c, int index, int count) { //首先追加字符 array[index] = c; index++; char[] countString = Integer.toString(count).toCharArray(); //追加字符个数 for (int i = 0; i < countString.length; i++) { array[index] = countString[i]; index++; } return index; } private static int countCompression(char[] str) { if (str == null || str.length == 0) { return 0; } int size = 0; int count = 1; int last = str[0]; for (int i = 0; i < str.length; i++) { if (str[i] == last) { count++; } else { size += 1 + Integer.toString(count).length(); last = str[i]; count = 1; } } size += 1 + Integer.toString(count).length(); return size; }}变位词检测算法
package string;public class Permutation { public static void main(String[] args) { System.out.println(isPermutation("hello".toCharArray(), "ehollu".toCharArray())); System.out.println(isPermutation("hello".toCharArray(), "eholu".toCharArray())); System.out.println(isPermutation("hello".toCharArray(), "eholl".toCharArray())); } public static boolean isPermutation(char[] s1, char[] s2) { if (s1.length != s2.length) { return false; } int[] letters = new int[256]; for (int i = 0; i < s1.length; i++) { letters[s1[i]]++; } for (int i = 0; i < s1.length; i++) { letters[s2[i]]--; if (letters[s2[i]] < 0) { return false; } } return true; }}字符串删除算法
package string;public class DeleteString { public static void main(String[] args) { String s1 = "cdacbcdefabcdef"; String s2 = "ab"; String s3 = deleteString(s1, s2); System.out.println(s3); } public static String deleteString(String s1, String s2) { char[] a1 = s1.toCharArray(); char[] a2 = s2.toCharArray(); boolean[] table = new boolean[256]; for (int i = 0; i < s2.length(); i++) { table[a2[i]] = true; } int faster = 0; int slower = 0; for (int i = 0; i < s1.length(); i++) { if (!table[a1[i]]) { a1[slower] = a1[faster]; faster++; slower++; } else { faster++; } } return new String(a1, 0, slower); }}字符串转整数算法
package string; public class StringToInteger { public static void main(String[] args) { System.out.println(StringToInt32("12345")); System.out.println(StringToInt32("-12345")); System.out.println(StringToInt32("2147483647")); System.out.println(StringToInt32("-2147483647")); System.out.println(StringToInt32("21474836470")); System.out.println(StringToInt32("-21474836470")); } public static int StringToInt32(String str) { if (str.length() > Integer.toString(Integer.MAX_VALUE).length()) { throw new IllegalArgumentException("字符串长度超出了整数的存储范围"); } for (int i = 0; i < str.length(); i++) { if (!Character.isDigit(str.charAt(i)) && str.charAt(i) != '-') { throw new IllegalArgumentException("字符串包含非数字字符，无法转换成整数"); } } if (str.length() == 0) { return 0; } char[] s = str.toCharArray(); int value = 0; int i = 0; //检查是整数还是负数 int sign = 1; if (s[0] == '+' || s[0] == '-') { if (s[0] == '-') sign = -1; i++; } while (i < s.length) { int c = s[i] - '0'; if (sign > 0 && (value > Integer.MAX_VALUE / 10 || (value == Integer.MAX_VALUE / 10 && c >= Integer.MAX_VALUE % 10))) { value = Integer.MAX_VALUE; break; } else if (sign < 0 && (value > -(Integer.MIN_VALUE / 10) || (value == -(Integer.MIN_VALUE / 10) && c >= -(Integer.MIN_VALUE % 10)))) { value = Integer.MIN_VALUE; break; } value = value * 10 + c; i++; } return sign > 0 ? value : value == Integer.MIN_VALUE ? value : -value; }}字符串全排列算法
package string; public class AllPermutation { public static void main(String[] args) { //要求首次输入有序，否则需要排序 calculateAllPermutations("abc".toCharArray()); } public static void calculateAllPermutations(char[] s) { System.out.println(new String(s)); int i, j; // 找到排列中最右一个升序的首位位置 i for (i = s.length - 2; (i >= 0) && (s[i] >= s[i + 1]); --i) ; //已经找到所有的排列 if (i < 0) return; // 找到排列中第 i 位右边最后一个比 s[i] 大的位置 j for (j = s.length - 1; (j > i) && (s[j] <= s[i]); --j) ; //交换s[i],s[j] swap(s, i, j); // 将第 i + 1 位到最后的部分反转 reverse(s, i + 1, s.length - 1); calculateAllPermutations(s); } //交换数组中两个位置的元素 private static void swap(char[] s, int i, int j) { char temp = s[i]; s[i] = s[j]; s[j] = temp; } //反转数组 private static void reverse(char[] s, int start, int end) { char temp; int i = start; int j = end; while (i < j) { temp = s[i]; s[i] = s[j]; s[j] = temp; i++; j--; } }}字符串字典序组合算法
package string; public class DictionaryString { public static void main(String[] args) { //要求字符是不同的，否则需要去重 //要求输入是有序的，否则需要排序 calculateRepeatablePermutations("abc".toCharArray(), new char[3], 0); } public static void calculateRepeatablePermutations(char[] s, char[] permutation, int p) { //如果只剩下一个字符 if (p == s.length) { System.out.println(new String(permutation)); } else { for (int i = 0; i < s.length; i++) { permutation[p] = s[i]; calculateRepeatablePermutations(s, permutation, p + 1); } } }}字符串的（括号）生成算法
package string;import java.util.ArrayList;import java.util.List;public class ParenString { public static void main(String[] args) { List<String> parenList = generateParens(3); for (String s : parenList) { System.out.println(s); } } public static List<String> generateParens(int count) { char[] str = new char[count * 2]; List<String> list = new ArrayList<>(); addParen(list, count, count, str, 0); return list; } public static void addParen(List<String> list, int leftRem, int rightRem, char[] str, int count) { //无效状态 if (leftRem < 0 || rightRem < leftRem) { return; } if (leftRem == 0 && rightRem == 0) { String s = new String(str); list.add(s); } else { //还有左括号可用 if (leftRem > 0) { str[count] = '('; addParen(list, leftRem - 1, rightRem, str, count + 1); } //还有右括号可用 if (rightRem > leftRem) { str[count] = ')'; addParen(list, leftRem, rightRem - 1, str, count + 1); } } }}
