1894. 找到需要补充粉笔的学生编号.md

1894. 找到需要补充粉笔的学生编号

版本1

class Solution {
     public int chalkReplacer(int[] chalk, int k) {
        while (true) {
            for (int i = 0; i < chalk.length; i++) {
                k -= chalk[i];
                if (k < 0) {
                    return i;
                }
            }
        }
    }
}

版本2:

class Solution {
     public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] sum = new long[n];
        sum[0] = chalk[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + chalk[i];
        }
        int remain = (int) (k % sum[n - 1]);
        for (int i = 0; i < n; i++) {
            if (remain < sum[i]) {
                return i;
            }
        }
        return 0;
    }
}

版本3

class Solution {
     public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] sum = new long[n];
        sum[0] = chalk[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + chalk[i];
        }
        int remain = (int) (k % sum[n - 1]);
        int idx = Arrays.binarySearch(sum, remain);
        if (idx >= 0) {
            return idx + 1;
        } else {
            return -(idx + 1);
        }
    }
}

版本4

class Solution {
      public int chalkReplacer(int[] chalk, int k) {
        if (chalk[0] > k) {
            return 0;
        }
        int n = chalk.length;
        for (int i = 1; i < n; i++) {
            chalk[i] = chalk[i - 1] + chalk[i];
            if (chalk[i] > k) {
                return i;
            }
        }
        k = k % chalk[n - 1];
        int idx = Arrays.binarySearch(chalk, k);
        if (idx >= 0) {
            return idx + 1;
        } else {
            return -(idx + 1);
        }
    }
}