Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Code shrimp is a sand carving and funny boy who likes listening to music, playing games and writing as well as most of his friends. The days are still very long, let’s refuel our efforts together 🌈

✨ topic

✨ force link


🔥

Return the index subscript that needs to be supplemented with chalk

For this problem, the main considerationThe sum of the array elements sum and kThree of the following

  1. sum == k
  2. sum > k
  3. sum < k


1. For the first conditionsum == kEasy, directreturn 0Because in this case, the subscript you need to add is always 0


2. For the second conditionsum > kOr rather, before we calculatesumCan be judgedIs sum greater than kIf the conditions are met, then directlyReturn Current index subscriptBecause theK is not enough. It needs to be replenished


3. For the third conditionsum < kWe certainly can’t fool 😂 and go through the sequence again and again decreasing k to determine which index subscript it is

The amount of data they’re giving us is very large, so if iterating over and over again is bound to time out, then we can passk % sumTo get the rest of the value, for example:

Sum = 10,k = 25. If we iterate over and over again, we need to iterate twice to get k = 5, and then iterate the third time to get the index we need to return

Then adopt the modular method, directly TMP = k % sum, TMP = 25% 10, TMP = 5, then we only need to traverse once to get the correct result, greatly reducing the time complexity


🌈 code implementation

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        
        int sum = 0,len = chalk.length;
        
        // If the sum is already greater than k, return the current index subscript
        // Because this is the time to add k
        for (int i = 0; i < len; i++) { sum += chalk[i];if (sum > k) return i;
        }
        // Return 0 if equal
        if (sum == k) return 0;

        int tmp = k % sum;
        // a traversal
        for (int i = 0; i < len; i++) {
            tmp -= chalk[i];
            // if TMP == 0, if the next index is the one that needs to be supplemented
            // if TMP < 0, the current index is the index that needs to be supplemented
            if (tmp == 0) return i + 1;
            else if (tmp < 0) return i;
        }
        return 0; }}Copy the code


🔥 Featured column

Self-introduction, to everyone recommend their column 😁, welcome small partners to collect attention 😊

Force link algorithm problem solving area

The small white to learn Java

MybatisPlus column

App crawler Column

PC side crawler column

Big factory interview question column

💖 finally

I am aCode pipi shrimp, a prawns lover who loves to share knowledge, will update useful blog posts in the future, looking forward to your attention!!

Creation is not easy, if this blog is helpful to you, I hope you can == one key three even oh! Thank you for your support. See you next time

🔥 original text link: ✨【Code prawns 】 once pass 99.90%, train of thought detail solution 【 find the student number that needs to add chalk 】