当前位置：首页 > news >正文

算法通关村第十二关|黄金挑战|最长公共前缀字符串压缩

news 2025/9/8 16:36:27

1.最长公共前缀

原题：力扣14.

1.从前到后比较每个字符串的同一个位置。

public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}int length = strs[0].length();int count = strs.length;for (int i = 0; i < length; i++) {char c = strs[0].charAt(i);for (int j = 1; j < count; j++) {if (i == strs[j].length() || strs[j].charAt(i) != c) {return strs[0].substring(0, i);}}}return strs[0];
}

2.将完整的字符串进行比较得到公共前缀。然后遍历每个字符串，不断缩小这个公共前缀，遍历结束后得到的就是最长的公共前缀。

public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];int count = strs.length;for (int i = 1; i < count; i++) {prefix = longestCommonPrefix(prefix, strs[i]);if (prefix.length() == 0) {break;}}return prefix;
}public String longestCommonPrefix(String str1, String str2) {int length = Math.min(str1.length(), str2.length());int index = 0;while (index < length && str1.charAt(index) == str2.charAt(index)) {index++;}return str1.substring(0, index);
}

2.字符串压缩问题

原题：力扣443.

public int compress(char[] chars) {int n = chars.length;int write = 0, left = 0;for (int read = 0; read < n; read++) {if (read == n - 1 || chars[read] != chars[read + 1]) {chars[write++] = chars[read];int num = read - left + 1;if (num > 1) {int anchor = write;while (num > 0) {chars[write++] = (char)(num % 10 + '0');num /= 10;}reverse(chars, anchor, write - 1);}left = read + 1;}}return write;
}
public void reverse(char[] chars, int left, int right) {while (left < right) {char temp = chars[left];chars[left] = chars[right];chars[right] = temp;left++;right--;}
}