Все фишки в одном месте

-
Даны фишки, пронумерованные от 0 до n. Они находятся в позициях, от 1 до m. Массив chipsпоказывает, что фишка chips[i]находится в позиции i.
Фишки можно переставлять влево или вправо на 1 или 2 шага любое количество раз. Каждая перестановка фишки имеет стоимость:
  • Переместить i-ю фишку влево или вправо на две позиции стоит 0.
  • Переместить i-ю фишку влево или вправо на одну позицию стоит 1.
Изначально на одной позиции могут находиться несколько фишек.
Вернуть минимальную стоимость того, что мы можем переместить все фишки в одну позицию.
Пример 1:
Дано: chips = [1,2,3] - три фишки расставлены на разных местах 1, 2, 3
Результат: 1
Пояснение: Если мы хотим сместить всё в 1-ю позицию, то из позиции 3 мы переходим за нулевую стоимость, а из позиции 2 - за стоимость 1. Аналогично, если мы хотим сместить всё в позицию 3. Если мы хотим сместить всё в позицию 2, то стоимость перемещения из позиции 1 и 3 будет стоить нам по 1, то есть суммарно 2, а это не минимальная стомость, которая равна 1.
Пример 2:
Дано: chips = [2,2,2,3,3]
Результат: 2
Пояснение: Позиция 1 у нас пустая. В позиции 2 у нас 3 фишки. А в позиции 3 - 2 фишки.
Если мы хотим сместить всё в позицию 1, то это будет стоить суммарно 3, потому что из позиции 3 в 1 стоит 0, а в позиции 2 у нас 3 фишки и стоиомсть перемещения каждой = 1, поэтому суммарная стоимость равна 3. Аналогично, если мы хотим всё сместить в позицию 3. Только при этом в позиции 1 у нас нет ничего.
Еслии мы хотим всё сместить в позицию 2, то нужно переместить две фишки из позиции 3, что будет стоить нам 2. И это минимальная стоимость.

Ограничения:
  • 1 <= chips.length <= 100
  • 1 <= chips[i] <= 10^9
Идея решения
Мы помним, что перемещение на 2 позиции не стоит ничего. Поэтому мы можем сместить все нечётные фишки в позицию 1, а все чётные фишки в позицию 2 с нулевой стоимостью.
Затем мы просто объединим две стопочки, перемстив наименьшу поверх наибольшей. Если обе стопочкки одинаковы, то без разницы, куда что двигать. В любом случае минимум между чётной и нечетной стопочкой будет нашим результатом.

Компилируемое решение 

public int minCostToMoveChips(int[] A) {
        int odd = 0, even = 0;
        for(int a : A)
            if(a % 2 == 0)
                ++even; // считаем фишки на нечетных позициях - 
// это будет стопка в позиции 1
            else
                ++odd; // стопка в позиции 2 (на чётных позиция)
        return Math.min(odd,even); // берем минимум
    }

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Разбиение числа на сумму с максимальным произведнием слагаемых

-
Источник: https://leetcode.com/problems/integer-break/ Дано целое число n , нужно представить его в виде суммы k положительных целых чисел , где k >= 2 , и произведение этих чисел максимально. Вернуть максимальное произведение. Пример 1: Дано: n = 2 Результат: 1 Пояснение: 2 = 1 + 1, 1 × 1 = 1. Пример 2: Дано: n = 10 Результат: 36 Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Ограничения: 2 <= n <= 58 Идея решения Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ...   pk. Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2 (pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4. Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5. Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение.  В итоге нам нужно представить n = a 3 + ...
Далее...

Число подмассивов, в которых сумма элементов равна k

-
Дан целочисленный массив и целое число k . Найти количество непрерывных подмассивов таких, что сумма их элементов равна k . Пример 1: Дано: nums = [1,1,1], k = 2 Результат: 2 Условия: Длинна массива находится в диапазоне [1, 20,000]. Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7]. Идея решения Если кумулятивная сумма (пусть s u m [ i ] - это сумма с нулевого до i^{th} i t h индекса ) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах i i и  j j таковы, что sum[i] - sum[j] = k s u m [ i ] − s u m [ j ] = k , значит, сумма элементов между индексами i i   and   j j равна k k . Создадим хэшмап map m a p , чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму . То есть это пары (sum_i, no. of occurences of sum_i) ( s u m i ​ , n o . o f o c c u r e n c e s o f s u m i ​ ) . Каждый раз, когда мы встречаем ...
Далее...

Сложить два числа, которые представлены списком

-
Даны 2 непустых списка, в которых закодированы, соответственно, два неотрицательных чила. Цифры каждого числа хранятся в обратном порядке. В каждоя ячейке списка находится одна цифра. Сложить эти два числа и вернуть их в виде списка. Можно предположить, что заданные числа не начинаются с нуля, за исключением если они и есть 0. Пример: Дано: (2 -> 4 -> 3) + (5 -> 6 -> 4) Резальтат: 7 -> 0 -> 8 Пояснение: 342 + 465 = 807. Идея решения. В начале каждого списка установим указатель, они будут смещаться одновременно складывая числа ячеек: a+b по правилам сложения в столбик. Имплементация. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {     ListNode dummyHead = new ListNode(0); // запоминаем начало результирующего списка     ListNode p = l1, q = l2, curr = dummyHead;     int carry = 0;     while (p != null || q != null) {         int x = (p != null) ? p.v...
Далее...