1103. Distribute Candies to People

LeetCode easy original: C# #array #csharp #easy #leetcode #math #two-pointers

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом:

Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку.

Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку.

Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз).

return 数组 (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет.

示例:

Input: candies = 7, num_people = 4

Output: [1,2,3,1]

Explanation:

On the first turn, ans[0] += 1, and the array is [1,0,0,0].

On the second turn, ans[1] += 2, and the array is [1,2,0,0].

On the third turn, ans[2] += 3, and the array is [1,2,3,0].

On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

C# 解法

匹配/原始

public class Solution {
    public int[] DistributeCandies(int candies, int num_people) {
        int n = num_people;
        int p = (int)(Math.Sqrt(2 * candies + 0.25) - 0.5);
        int remaining = candies - (p + 1) * p / 2;
        int rows = p / n;
        int cols = p % n;
        
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n;
            if (i < cols) {
                d[i] += i + 1 + rows * n;
            }
        }
        d[cols] += remaining;
        return d;
    }
}

C++ 解法

自动草稿，提交前请检查

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& DistributeCandies(int candies, int num_people) {
        int n = num_people;
        int p = (int)(Math.Sqrt(2 * candies + 0.25) - 0.5);
        int remaining = candies - (p + 1) * p / 2;
        int rows = p / n;
        int cols = p % n;
        
        vector<int>& d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n;
            if (i < cols) {
                d[i] += i + 1 + rows * n;
            }
        }
        d[cols] += remaining;
        return d;
    }
}

Java 解法

匹配/原始

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int n = num_people;
        int p = (int) (Math.sqrt(2 * candies + 0.25) - 0.5);
        int remaining = candies - (p + 1) * p / 2;
        int rows = p / n;
        int cols = p % n;
        
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n;
            if (i < cols) {
                d[i] += i + 1 + rows * n;
            }
        }
        d[cols] += remaining
        return d;
    }
}

Python 解法

匹配/原始

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        n = num_people
        p = int((2 * candies + 0.25)**0.5 - 0.5)
        remaining = int(candies - (p + 1) * p * 0.5)
        rows, cols = p // n, p % n
        
        d = [0] * n
        for i in range(n):
            d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n
            if i < cols:
                d[i] += i + 1 + rows * n
        d[cols] += remaining
        return d

Go 解法

匹配/原始

import (
    "math"
)

func distributeCandies(candies int, num_people int) []int {
    n := num_people
    p := int(math.Floor(math.Sqrt(2*float64(candies)+0.25) - 0.5))
    remaining := candies - (p+1)*p/2
    rows := p / n
    cols := p % n
    
    d := make([]int, n)
    for i := 0; i < n; i++ {
        d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n
        if i < cols {
            d[i] += i + 1 + rows * n
        }
    }
    d[cols] += remaining
    return d
}

Algorithm

Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты:

p = floor(sqrt(2C+0.25)-0.5)

remainig = C - p(p+1)

Вычислите количество полных циклов и распределите конфеты:

rows = p // n

d[i]= i*rows + n*rows*(rows-1)

Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты:

d[i]+=i+n⋅rows для первых p%n людей

d[p%n]+=remaining

return распределение конфет d

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。