江苏建设监理协会网站,网站建设siteserver,产品营销推广方案,微信开发有哪些文章目录 前言最长公共前缀纵向比较横向比较 字符串压缩问题表示数值的字符串总结 前言 提示#xff1a;我有时候在想#xff0c;我是真的不太需要其他人#xff0c;还是因为跟他们在一起时没法自己#xff0c;所以才保持距离。我们的交谈就像是平行而毫无交集的自言自语。… 文章目录 前言最长公共前缀纵向比较横向比较 字符串压缩问题表示数值的字符串总结 前言 提示我有时候在想我是真的不太需要其他人还是因为跟他们在一起时没法自己所以才保持距离。我们的交谈就像是平行而毫无交集的自言自语。我们所分享的可能不过是相互之间的不理解。 --西里尔·佩德罗萨《春分秋分》 我们接着看字符串问题字符串问题还有很多。 最长公共前缀
参考题目地址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--;}}表示数值的字符串
参考题目地址LCR 138. 有效数字 - 力扣LeetCode 推荐做一下这个题目不是难就是麻烦。这里留个作业 总结
提示字符串难度冲刺最长前缀处理字符串压缩处理三指针问题解决字符串表示数值问题 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
