织梦怎么建设论坛网站,网站开发需求分析,中小型网站建设机构,2345网址导航 中国最目录 题目#xff1a;最长公共前缀解法1#xff1a;纵向对比-循环内套循环写法复杂度#xff1a;时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法2#xff1a;横向对比-两两对比#xff08;类似合并K个数组、合并K个链表#xff09;复… 目录 题目最长公共前缀解法1纵向对比-循环内套循环写法复杂度时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法2横向对比-两两对比类似合并K个数组、合并K个链表复杂度时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目压缩字符串解法1读写指针 次数统计 顺向思维处理次数输出复杂度时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法2读写起始三指针 逆向思维处理次数输出优化解法1复杂度时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目最长公共前缀
题目链接LeetCode-14. 最长公共前缀
解法1纵向对比-循环内套循环写法
以第一个子字符串为标准遍历其每个字符时内嵌遍历其余子字符串的对应字符是否一致。不一致时则返回当前字符之前的子字符串。
复杂度时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)、空间复杂度 O ( 1 ) O(1) O(1)
时间复杂度其中 n 是字符串平均长度m 是字符串数组的长度。
Go代码
func longestCommonPrefix(strs []string) string {length : len(strs)if length1 {return strs[0]}chlen : len(strs[0])for i:0; ichlen; i {// 用第一个子字符串的字符作为比较ch : strs[0][i]for j, v : range strs {if j 0 {continue}// 子字符串的长度比第一个短 或者 出现比较字符不同if i len(v) || v[i] ! ch {return string(strs[0][:i])}}}return strs[0]
}解法2横向对比-两两对比类似合并K个数组、合并K个链表
先让前两个子字符串对比得到公共前缀再将此公共前缀作和下一个子字符串对比得到公共前缀如此循环到末尾返回最后的公共前缀即可优化遍历过程中如果公共前缀已经是空字符串了则可直接返回空字符串。
相比于解法1的优点将逻辑分解到两个函数中使代码更加模块化和可维护。
复杂度时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)、空间复杂度 O ( 1 ) O(1) O(1)
时间复杂度其中 n 是字符串平均长度m 是字符串数组的长度。
Go代码
func longestCommonPrefix(strs []string) string {length : len(strs)if length 1 {return strs[0]}str : strs[0]for i:1; ilength; i {str getCommonPrefix(str, strs[i])if str {return }}return str
}func getCommonPrefix(str1, str2 string) string {length2 : len(str2)for i, v : range str1 {val : byte(v)if i length2 || val ! str2[i] {return string(str1[:i])}}return str1
}题目压缩字符串
题目链接LeetCode-443. 压缩字符串
解法1读写指针 次数统计 顺向思维处理次数输出 安排读写指针分别指向要写的位置和读的位置两指针首先指向第一个字符 如果是相同时最后一个元素的标记或者 读指针的字符和写指针不同时 统计总次数区分是否 1 大于1区分是否 10 小于10仅追加一个数字大于10不断除10得到可除次数和除10的最后余数 追加最后余数遍历可除次数追加数值0根据可除次数用总次数除了10的可除次数次方得到余数追加余数 如果是相同时最后一个元素的标记到这里直接返回写指针1即可更新对比字符为当前字符追加对比字符总次数还原为1读指针如果是最后一个元素到这里直接返回写指针1即可 相同时总次数 如果是最后一个元素添加标记这里只为加上其相同次数
复杂度时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
func compress(chars []byte) int {length : len(chars)if length 0 || length 1 {return length}left, right : 0, 1 // left写 right读num : 1 //次数统计ch : chars[0]lastone : falsefor lastone || right length {if lastone || chars[right] ! chars[left] {// 追加长度if num 1 {// 要追加多个长度if num 10 {tmpnum : numcount10 : 1// 明确有几个10for tmpnum 10 {tmpnum tmpnum/10if tmpnum 10 {count10}}// 追加大于10的首个数字leftchars[left] byte(tmpnum 0) for i:1; icount10; i {// 补零leftchars[left] 0}// 追加大于等于10时的余数f10 : math.Pow(10, float64(count10))yu : num % int(f10)if yu 0 {leftchars[left] byte(yu 0)}} else { //只追加一个长度leftchars[left] byte(num 0)}}if lastone {return left1}ch chars[right]// 追加新字符leftchars[left] chnum 1right// 如果是最后一个元素if right length {return left1}} else {numrightif right length {lastone true}}}return left1
}解法2读写起始三指针 逆向思维处理次数输出优化解法1
优化点
无需用变量循环时累加统计总次数让一个起始指针指向当前统计字符的首位置当遍历到该字符末尾时尾索引-首索引1总次数。将正向计算追加10时的最后余数、可除10次数、余数改为追加依次除10得到的余数最后反转该段数字区间即可。读指针和下一个不同时处理当前此时包含了最后一个字符的场景。解法1中读指针和写指针不同时处理的逻辑就没法包含最后一个字符需要考虑最后一个字符时是和之前一致还是不同的情况。
复杂度时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
func compress(chars []byte) int {length : len(chars)if length 0 || length 1 {return length}left, right, start : 0, 0, 0for ; right length; right {if right length-1 || chars[right] ! chars[right1] {chars[left] chars[right]leftcount : right-start1site : leftif count 1 {for count 0 {n : count%10chars[left] byte(n 0)leftcount count/10}reverse(chars, site, left-1)}start right1}}return left
}
func reverse(chars []byte, left int, right int) {if left right {return}for left right {chars[left], chars[right] chars[right], chars[left]leftright--}
}
