科大讯飞笔试求教

求教各位大佬,以下代码还有什么优化空间呢?只能通过20%。

题目大意:

输入两个数(n:字符个数;q:可操作次数)和一个字符串(0和1组成)。操作是把0变成1

求 连续1的个数的平方 的和

例子:

6,1,100101 —— 输出10——对倒数第二位操作变成100111,得到1*1+3*3 = 10

10,2,0010011011 ——输出37 —— 对最后两个0操作变成0010111111,得到1*1+6*6 = 37

package main

import (
    "fmt"
)

func main() {
    var n,q int
    fmt.Scanf("%d %d",&n, &q)
    var str string
    fmt.Scanf("%s",&str)

    strByte := []byte(str)

    
    if q==0{
        fmt.Println(check(strByte)) 
        return
    }

    maxN := 0

    var helper func(int,int)
    helper = func(index, stay int){
        if index == n{
            maxN = max(maxN, check(strByte))
            return 
        }
        if stay > 0{// 还有要做的
            // 找到所有0,依次放入
            for i:=index;i<n;i++{
                if strByte[i]=='0'{
                    strByte[i] = '1'
                    helper(i+1,stay-1)
                    strByte[i] = '0'
                }
            }
        }else{
            helper(n,0)
        }
        // 计算全部的
    }

    helper(0,q)
    fmt.Println(maxN)

}
func check(nums []byte)int{
    total := 0
    index := 0
    for index<len(nums){
        l, r:=0, 0
        for index <len(nums) && nums[index]=='0'{
            index++
        }
        l = index
        for index <len(nums) && nums[index]=='1'{
            index++
        }
        r  = index
        total += (r-l)*(r-l)
    }
    return total
}

func max(a,b int)(int){
    if a>b{
        return a
    }
    return b
}

#科大讯飞##笔试##golang#
全部评论
现在讯飞笔试这么难了?我做那场炒鸡简单轻松全a,感觉你这个比我那回最后一题还难😂
1 回复 分享
发布于 08-30 22:05 黑龙江
我回溯也20%,换滑动窗口A了
1 回复 分享
发布于 08-30 22:21 新加坡
应该是贪心吧,尽可能的要让多出来的1把更多的1串在一起这样平方后加的更多,用滑动窗口来算怎么串1最划算
1 回复 分享
发布于 08-31 04:27 湖北
我回溯做的,也20%,最后没时间再想别的方法了
点赞 回复 分享
发布于 08-30 21:11 湖南
第二题该咋做啊,我时间复杂度是n方超了
点赞 回复 分享
发布于 08-30 21:19 辽宁
n方k好像可以解,枚举每个位置末尾全是1子串的长度。但是应该会超时
点赞 回复 分享
发布于 08-30 23:16 辽宁
第一题咋做
点赞 回复 分享
发布于 08-31 01:19 陕西
前缀和可以100%通过😂刚刚笔试完也是这道题
点赞 回复 分享
发布于 09-11 15:18 天津

相关推荐

牛客339922477号:都不用reverse,直接-1。一行。啥送分题
点赞 评论 收藏
分享
vegetable_more_exercise:1-1.5万,没错啊,最少是1人民币,在区间内
点赞 评论 收藏
分享
2 2 评论
分享
牛客网
牛客企业服务