文章目录
- 😉毛遂自荐
- ✨题目
- 🔥解题思路
- 🌈代码实现
- 💖最后
Code皮皮虾 一个沙雕而又有趣的憨憨少年,和大多数小伙伴们一样喜欢听歌、游戏,当然除此之外还有写作的兴趣,emm…,日子还很长,让我们一起加油努力叭🌈
点我,直达底部有粉丝专享福利!!!
😉毛遂自荐
毛遂自荐一下,给大家推荐一下自己的专栏😁,欢迎小伙伴们收藏关注😊
大厂面试题专栏
Java专栏
爬虫专栏
更多专栏尽在主页,点我😁!!!
✨题目
✨力扣链接
🔥解题思路
题目大概扫一眼就应该明白,就是要返回需要补充粉笔的索引下标
对于此题,主要考虑数组元素总和sum和k
三种情况
sum == k
sum > k
sum < k
1. 对于第一个条件sum == k
好说,直接return 0
即可,因为在这种情况下,需要补充的下标永远为0
2. 对于第二个条件sum > k
也好说,在我们计算sum
的过程中,就可以判断sum 是否大于 k
,如果条件满足,那么直接return 当前索引下标
,因为k不够了,需要补充
3. 对于第三个条件sum < k
,我们肯定不能傻乎乎的😂去一边又一遍遍历数组减少k,最终判断是哪个索引下标
题目给出的数据量是非常大的,如果一遍遍的遍历肯定超时,那么我们可以通过k % sum
来得到剩下的值,举个栗子:
sum = 10,k = 25,如果一遍遍的遍历,那么我们需要先遍历两次得到k = 5后,在进行第三次遍历才可得到需要返回的下标
那么采用取模方法,直接tmp = k % sum,tmp = 25 % 10,tmp = 5,那么我们只需要遍历一次就可得到正确结果,极大的降低了时间复杂度
🌈代码实现
class Solution {
public int chalkReplacer(int[] chalk, int k) {
int sum = 0,len = chalk.length;
//在计算总和的时候,需要判断,sum是否已经大于了k,如果已经大于了k,那么也没必要继续算下去,直接return当前索引下标即可
//因为此时已经需要补充k了
for (int i = 0;i < len;i++) {
sum += chalk[i];
if (sum > k) return i;
}
//如果相等直接返回0
if (sum == k) return 0;
int tmp = k % sum;
//一次遍历
for (int i = 0; i < len; i++) {
tmp -= chalk[i];
//如果tmp == 0,如果下一个索引才是需要补充的索引
//如果tmp < 0,那么当前索引就是需要补充的索引
if (tmp == 0) return i + 1;
else if (tmp < 0) return i;
}
return 0;
}
}
💖最后
我是 Code皮皮虾,一个热爱分享知识的 皮皮虾爱好者,未来的日子里会不断更新出对大家有益的博文,期待大家的关注!!!
创作不易,如果这篇博文对各位有帮助,希望各位小伙伴可以一键三连哦!,感谢支持,我们下次再见~~~
粉丝福利👇🏻👇🏻👇🏻