1040. Moving Stones Until Consecutive II

LeetCode medium оригинал: C# #array #csharp #leetcode #math #medium #sliding-window #sort

LeetCode Static

Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.

Пример:

Input: stones = [7,4,9]

Output: [1,2]

C# решение

сопоставлено/оригинал

using System;
using System.Linq;
public class Solution {
    public int[] NumMovesStonesII(int[] stones) {
        Array.Sort(stones);
        int n = stones.Length;
        
        int maxMoves = stones[n-1] - stones[0] + 1 - n;
        maxMoves -= Math.Min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1);
        int minMoves = int.MaxValue;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                ++j;
            }
            int alreadyInWindow = j - i;
            if (alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = Math.Min(minMoves, 2);
            } else {
                minMoves = Math.Min(minMoves, n - alreadyInWindow);
            }
        }
        return new int[] { minMoves, maxMoves };
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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>& NumMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size();
        
        int maxMoves = stones[n-1] - stones[0] + 1 - n;
        maxMoves -= min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1);
        int minMoves = int.MaxValue;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                ++j;
            }
            int alreadyInWindow = j - i;
            if (alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = min(minMoves, 2);
            } else {
                minMoves = min(minMoves, n - alreadyInWindow);
            }
        }
        return new int[] { minMoves, maxMoves };
    }
}

Java решение

сопоставлено/оригинал

import java.util.Arrays;

public class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        
        int maxMoves = stones[n-1] - stones[0] + 1 - n;
        maxMoves -= Math.min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1);

        int minMoves = Integer.MAX_VALUE;
        int j = 0;

        for (int i = 0; i < n; ++i) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                ++j;
            }
            int alreadyInWindow = j - i;
            if (alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = Math.min(minMoves, 2);
            } else {
                minMoves = Math.min(minMoves, n - alreadyInWindow);
            }
        }

        return new int[] { minMoves, maxMoves };
    }
}

Python решение

сопоставлено/оригинал

def numMovesStonesII(stones):
    stones.sort()
    n = len(stones)
    
    max_moves = stones[-1] - stones[0] + 1 - n
    max_moves -= min(stones[1] - stones[0] - 1, stones[-1] - stones[-2] - 1)

    min_moves = float('inf')
    j = 0

    for i in range(n):
        while j < n and stones[j] - stones[i] + 1 <= n:
            j += 1
        already_in_window = j - i
        if already_in_window == n - 1 and stones[j-1] - stones[i] + 1 == n - 1:
            min_moves = min(min_moves, 2)
        else:
            min_moves = min(min_moves, n - already_in_window)

    return [min_moves, max_moves]

Go решение

сопоставлено/оригинал

import (
    "sort"
)

func numMovesStonesII(stones []int) []int {
    sort.Ints(stones)
    n := len(stones)
    
    maxMoves := stones[n-1] - stones[0] + 1 - n
    maxMoves -= min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1)

    minMoves := int(^uint(0) >> 1) // max int
    j := 0

    for i := 0; i < n; i++ {
        for j < n && stones[j] - stones[i] + 1 <= n {
            j++
        }
        alreadyInWindow := j - i
        if alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1 {
            minMoves = min(minMoves, 2)
        } else {
            minMoves = min(minMoves, n - alreadyInWindow)
        }
    }

    return []int{minMoves, maxMoves}
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

Сортировка:

Сначала отсортируем массив камней.

Максимальное количество ходов:

Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня.

Минимальное количество ходов:

Минимальное количество ходов можно определить следующим образом:

Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни.

Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0.

В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место).

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.