7.25 拼多多笔试第三题 无限数字集合求指教

题意:
1、初始集合有一个元素A
2、集合中每个元素X,X+B也属于集合
3、集合中每个元素X,X*C也属于集合
问Q是不是集合的元素?
如下代码,想用dfs解决,结果一直说超出内存限制,猜测是递归结束条件可能没写对,导致一直递归调用,但想不出来到底哪不对,网牛友指教。😣
func main() {
    n := 0 
    fmt.Scan(&n)
    for i:=0; i<n; i++ {
        A, B, C, Q := 0, 0, 0, 0
        fmt.Scan(&A, &B, &C, &Q)
        if dfs(A, B, C, Q) {
            fmt.Println(1)
        } else {
            fmt.Println(0)
        }
    }
}


func dfs(A, B, C, Q int) bool {
    if Q == A {
        return true
    }
    if Q < A {
        return false
    }
    return dfs(A, B, C, Q-B) || dfs(A, B, C, Q/C)
}


#拼多多笔试##学习路径#
全部评论
原因很简单,这道题样例限制你不能用递归去做。当Q很大,B= 1的时候,你一直递归栈会溢出
3 回复 分享
发布于 2021-07-25 22:40
Q/C不对,因为可能出现有余数,比较坑
1 回复 分享
发布于 2021-07-25 22:51
偷了个鸡,把bfs循环次数限定在一个范围内你最后之要循环不超过20000次,就能全A
1 回复 分享
发布于 2021-07-27 19:59
大佬是什么岗位的?我也是这题,不会😂
点赞 回复 分享
发布于 2021-07-25 22:18
相同的想法栈溢出,没想明白哪里不对
点赞 回复 分享
发布于 2021-07-25 22:23
第四题你做出来啦?
点赞 回复 分享
发布于 2021-07-25 22:29
只能用数学的方法。https://www.nowcoder.com/discuss/690443?channel=-1&source_id=discuss_terminal_discuss_history_nctrack&ncTraceId=d11ac88dceba4525a7071dff3edf0525.999.16272650324453535
点赞 回复 分享
发布于 2021-07-26 10:06
可以用递归,你需要判断一下,提前结束递归就行了。 ```java private int fun(int a, int b, int c, int q,  int res){         if(res == 1) return 1;         if(c == 1 ){             if(q%b == a)                 return 1;             else{                 return 0;             }         }         if(q % b == a % b) {             return 1;         }         if(a > q) return 0;         res = fun(a + b,b, c,q,res);         res = fun(a *c,b,c,q,res);         return res;     } ```
点赞 回复 分享
发布于 2021-07-26 16:29
int search(int a, int b, int c, int q){     int index = 0;     if(c == 1){         if((q-a)%b == 0)return 1;         else return 0;     }     while(1){         int num = a*pow(c,index);         // 超过上限,这里可能有问题,过不了再说,miao的         if(num > q || num <= 0){             break;         }         if((q - num)%b==0){             return 1;         }         index++;     }     return 0; }
点赞 回复 分享
发布于 2021-07-27 19:51
递归有很多重复情况的计算(类比费布拉切数的递归情况),我写的是迭代,迭代没有内存超限,反而时间超限了。
点赞 回复 分享
发布于 2021-08-03 10:16

相关推荐

昨天 11:05
门头沟学院 Java
华为海思 通软开发 总包大概在30左右
点赞 评论 收藏
分享
2024-12-07 21:27
重庆邮电大学 Java
疯狂学习a:好看,想要,我是学生能送我么😋
投递大疆等公司10个岗位
点赞 评论 收藏
分享
2024-11-28 22:27
已编辑
西南交通大学 Java
Kensley:交大的学弟,整体挺好的 稍微有点乱可以考虑做减法了 并发和java可以合一起,知识上补充一下Redis集群技术的死角,主从,Sentinel,Cluster。 大计基改成课程就行:《计算机网络》《操作系统原理》《数据结构》《算法》。 最重要的,项目还要再挖掘,要用【问题/场景】驱动开发,效果放在最后一句就行,“基于XXX/集成XXX实现XXX功能,【解决XXX问题】,效果XXX”,比如基于Redis实现商品信息的读缓存,解决了浏览高峰时因高频访问MySQL偶发卡顿的问题,体感性能上升30% 排版相关的:1. 大段文本要做提炼,比如“XXX等有基本的了解”改为“了解XXX”,文本相关都可以喂给GPT看看精简效果;2.黑体粗有点多,长文本和奖项的加粗去掉,奖项的时间不用列;3. 项目和实习的时间挪到后面,保持一致
点赞 评论 收藏
分享
评论
1
3
分享

创作者周榜

更多
牛客网
牛客企业服务