请教一道面试题

最近面了一个DS职位，被问到一道coding题，因为自己算是刷题小白，正在过lc，刷题还是不到位，面试时和面试结束后一直没太想明白这个问题。没有在leetcode里找到原题，至少类似title的没有找到，当然也有可能是自己刷题量少没找到内容类似的题。题目是：
1. 假设有一块面包，它由若干小块组成，每一块上面有一个或者没有葡萄干。让写一段code来判断能不能把面包切N刀以后，切成的N+1份每份葡萄干总数一样。
比如：面包可以表达为[1, 0, 0, 1, 0, 1, 0]， list的每个元素代表一个小块，1代表有一个葡萄干，0代表没有葡萄干。如果N=2，就是切两刀，切完以后的一种情况是[1, 0], [0, 1, 0], [1, 0]，每一份都有一个葡萄干，所以code应该返回True。

2. 同样的问题，每小块有若干个葡萄干（>=0)， 判断切N刀以能不能实现每份葡萄干总数一样。
比如：面包可以表达为[1, 0, 4, 1, 6, 1, 2]

第一问我想到可以简单的判断sum([1, 0, 0, 1, 0, 1, 0])是不是可以被N+1整除。 但是第二问就有点蒙了，感觉应该思路会和第一问相近，但是不知道卡在哪里。不知道有没有朋友给点意见。多谢！


补充内容 (2021-2-22 11:43):
有的地方可能没说清楚： 整个题其实就是写一个function，argument是面包的构成和想要切成刀N，也就是def cut_bread(bread, N), bread = [1, 0, 0, 1, 0, 1, 0]。

补充内容 (2021-2-22 11:46):
最小单位就是块了，也就是list的每一个element，不能再切了。切面包可以理解成把原来的list给拆分成若干个list

sherryzhang4568 发表于 2021-2-22 11:00
这个是不是一个背包问题。。。

哪这么复杂啊，就是个整除问题。

我想的也是先用sum/(n+1) 算每段的Target sum, 不能整除就直接False、能的话就从第一个数字开始加、加到target sum清零继续加、直到有一段无法到达target sum为止

如果每小块还可以继续切就和第一问一样

如果不能继续切
还是先判断能不能被整除，可以的话得到每段个数
然后在原序列上模拟，看是否是真的能分段
举个例子
序列[3, 0, 4...]
假设整除后得到每段应该是三个
在原序列上模拟就不行，因为4没法往下分了
大概就是这样吧，欢迎指正

这个是不是一个背包问题。。。

没有看懂题。。。给定的这个数组，N是给定的么？如果N给定的话，直接计算出每个区间的target（total/(N+1))，不用管是否为1，直接从前往后走计算当前和，达到target就清零，超过就false就可以了。

不过如果N是不给定的，那这道题就有点意思了。。。想了半天想不出来怎么做，唯一能想到的是，直接将total的所有乘子找出来，对每一个乘子计算出当前target，然后重复以上操作，考虑到一个数的乘子顶多也就几百，复杂度也不会太大
---------
看了下楼主的补充，其实就是个整除问题，参加上面第一行

penggeqiang 发表于 2021-2-22 11:35
哪这么复杂啊，就是个整除问题。

对不起。。。。

sherryzhang4568 发表于 2021-2-22 11:56
对不起。。。。

主要是我忘记背包问题是什么问题了。。。

第二题就是把数组走一遍 一共切N+1份 你能算出来每份的目标是多少，然后走一遍就好了。。

这题延伸一下的话就是 同样的input 切N刀后每份葡萄干数量相同 问你N最大可以取到多少

感谢大家的指点，看来是一个不太难的问题，果然是自己没转过弯，思路卡住了。不过归根结底还是刷题不够，继续努力吧～