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

台州做网站seo网站制作框架

news 2025/9/17 10:41:13

台州做网站seo,网站制作框架,如何写一份企业网站建设方案,厦门seo推广公司文章目录前言最长公共前缀纵向比较横向比较字符串压缩问题表示数值的字符串总结前言提示：我有时候在想，我是真的不太需要其他人，还是因为跟他们在一起时没法自己，所以才保持距离。我们的交谈就像是平行而毫无交集的自言自语。…

文章目录

前言
最长公共前缀
- 纵向比较
- 横向比较
字符串压缩问题
表示数值的字符串
总结

前言

提示：我有时候在想，我是真的不太需要其他人，还是因为跟他们在一起时没法自己，所以才保持距离。我们的交谈就像是平行而毫无交集的自言自语。我们所分享的可能不过是相互之间的不理解。 --西里尔·佩德罗萨《春分秋分》

我们接着看字符串问题，字符串问题还有很多。

最长公共前缀

参考题目地址：14. 最长公共前缀 - 力扣（LeetCode）

在这里插入图片描述

解答这个问题，首先要就看看公共前缀的分布有什么特点，我们看下下图：

在这里插入图片描述
可以看到，第一种方式，我们可以竖着比较，如左图所示那样，每前进一个位置就比较各个串，看是不是都是相等的，只要在某一轮遇到不相等的，哪么就结束。

第二种方式，我们还可以横着比较，先比较前两个找到公共前缀fix1，然后再和第三个比较找到公共前缀fix2，我们可以确定fix2一定不会比fix1更长，然后在向下比较，直到最后一个fixn，每次得到的fix都不会比前面的长，最后比较完还剩下的就是需要找的前缀了。

看到这里有没有一种似曾相识的感觉，我们在前面合并k个数组或者k个链表不也是类似的思路吗？是的就是这样。

第三种方式，我们可以对第二种做优化，借鉴并归的思想，先两两组找fix，然后找到后在两两并归呢？，当然是可行的，这就是并归的体现。

不过我们先看第一种实现方式，竖着比较，纵向扫描，从前往后遍历所有的字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不同则当前列不再属于公共前缀，当前列之前的部分为最长的公共前缀。

纵向比较

    /*** 纵向比较（最长公共前缀）* @param strs* @return*/public static String longestCommonPrefix1(String[] strs) {// 校验参数if(strs == null || strs.length == 0){return "";}// 获取总串数int count = strs.length;// 获取第一串的长度int len = strs[0].length();// 纵向遍历// 外循环是 第一串的长度for(int i = 0; i < len; 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 ：横向** @param strs* @return*/public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}int count = strs.length;String prefix = strs[0];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 len = Math.min(str1.length(), str2.length());int index = 0;while(index < len && str1.charAt(index) == str2.charAt(index)) {index++;}return str1.substring(0, index);}

字符串压缩问题

参考题目介绍：443. 压缩字符串 - 力扣（LeetCode）

在这里插入图片描述

这道题，如果采用双指针的化，可以吗？显然不行，我们深入分析采用三指针。

这个我们可以使用两个指针分别标志我们在字符串中读和写的位置，还有一个指针left用来标记重复字段的开始位置。read指针不断的向前读取，每次读到指针read移动到某一段连续相同字串的最右侧，我们就在写指针write处一次写入该子串对应的字符和子串长度即可。

当读指针read位于字符串的末尾，或读指针read指向字符不同于下一个字符时，我们就认为读指针read位于某一段连续相同子串的最右侧。该子串对应的字符即为读指针read指向的字符串。我们使用left来记录该字串的最左侧的位置，这样字串长度即为read - left + 1。

这里还有一个问题，就是藏毒可能超过10，因此还要实现将数字转化为字符串写入到原来字符串的功能。这里我们可以采用短除法将字串长度倒叙写入原子符串中，然后再将其反转即可。

    /*** 压缩字符串（三指针）* @param chars* @return*/public static int compress(char[] chars) {// 校验参数if (chars == null || chars.length == 0){return 0;}// 创建指针域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;}// 这里需要反转一下数字（大于10 的情况） 01  10reverse(chars,anchor,write - 1);}// 更新左边界left = read + 1;}}return write;}public static void reverse(char[] chars, int left, int right) {while (left < right){char ch = chars[left];chars[left] = chars[right];chars[right] = ch;left++;right--;}}