讨论/题目交流/【求助】被1163吊锤。 求大佬帮忙看看,为什么明明24个样例都过了还显示超时? Golang/
【求助】被1163吊锤。 求大佬帮忙看看,为什么明明24个样例都过了还显示超时? Golang

RT,测试的时候所有样例都是对的,提交后显示超时, 但是详情里通过测试样例24/24。

另外我以为最后一个20000长的样例导致超时,甚至开始骗分。设置遇到20000长且a开头的直接返回输入。但还是超时。

想了想我的方法应该是o(n)的时间复杂度,不至于超时吧。莫非是if耗时?还是频繁的字符串切片操作耗时? 请求大佬解答

下附代码。

  1. 擂台思想,一旦出现更大字典序直接替换答案。
  2. 循环整个输入字符串。
  3. 一旦新字符比现有答案首字母大,直接替换并跳过下面所有步骤。
  4. curb 存储新字符和答案首字母相等时的新字符位置,index存储curb开始的子串与先有答案前缀最大相等长度,即偏移量。
  5. 新字符与现有答案偏移量位置比较,如小于,直接添加到现有答案,curb 为零时只加一个字符,不为零时加s[curb:curb+index]。重置curb 和index。
  6. 相等时,index++, 如果比现有答案还长,代表可以直接加进去,如果curb为零,代表此处为冲突子串起始位置。如果curb不为零代表冲突串在增长,继续循环。
  7. 大于时,冲突子串更大,替换掉现有答案。重置curb ,index
  8. 结束循环如果curb 不等于0代表最后有一节没有加进去,而且这一节子串不比现有答案大,要直接加到现有答案里。
  9. return out

是只循环了一遍O(n)没错的吧。咋超时的啊快要疯了。

func lastSubstring(s string) string {
    out := ""
    if len(s)<=1{
        return s
    }
    if len(s) ==20000 && s[0] == 'a'{
        return s
    }
    out = string(s[0])
    index := 0
    curb := 0
    for i:=1; i<len(s); i++{
        if s[i] > out[0]{           //3.
            out = string(s[i])
            index = 0
            curb = 0
            continue
        }
        if s[i] < out[index]{ // 5.
            if curb == 0{
                out += string(s[i])
            } else {
                out += s[curb:curb+index+1]
                curb = 0
                index = 0
            }
            
        } else if s[i] == out[index]{   // 6.
            index += 1
            if index >= len(out){
                out += s[curb:curb+index]
                curb = 0
                index = 0
                continue
            } else if curb == 0{
                curb = i
            } else {
                continue
            }
        } else {    // 7.
            out = s[curb:curb+index+1]
            curb = 0
            index = 0
        }
    }

    if curb != 0{   // 8.
        out += s[curb:]
    }
    
    return out
}
展开讨论

发现问题了,是频繁的长长的字符串切片和复制导致的超时,一不做二不休再加两个指针来隔出现有答案。
原来用于存储现有答案的字符串去掉不用。
但是12ms 感觉是有点慢的,不知道怎么继续优化。内存消耗也很高,6.4MB 只击败了14%。可是我就存了几个数吗不是=-=,对Go语言的原理还是不熟悉,做个笔记

func lastSubstring(s string) string {
    if len(s)<=1{
        return s
    }
    length := len(s)
    index := 0
    curb := 0
    begin := 0
    end := begin
    for i:=1; i<length; i++{
        if s[i] > s[begin]{
            begin = i
            index = 0
            curb = 0
            continue
        }
        if s[i] < s[begin+index]{
            if curb == 0{
                end = i+1
            } else {
                end = curb+index+1
                curb = 0
                index = 0
            }
            
        } else if s[i] == s[begin+index]{
            index += 1
            if index >= end-begin{
                end = curb+index+1
                curb = 0
                index = 0
                continue
            } else if curb == 0{
                curb = i
            } else {
                continue
            }
        } else {
            begin = curb
            end = curb+index+1
            curb = 0
            index = 0
        }
    }

    if curb != 0{
        end = length
    }
    if end >= length-1{
        return s[begin:]
    } else {
        return s[begin:end]
    }
    
}