Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
Решаю задачу на leetcode, смысл которой в том, чтобы из целочисленного массива вывести все различные списки Integer'ов, состоящих из 3 чисел таких, что их сумма равна 0 и оформить их в виде списка, то есть будет List<List<Integer>> на выходе. Не понимаю, в чем ошибка, когда тамошний компилятор пишет такое.
<code>
class Solution
{
public List<List<Integer>> threeSum(int[] nums)
{
List<Integer> listOfIntegers = new ArrayList<>();
List<List<Integer>> list = new ArrayList<>();
int M = 0;

if(nums.length == 0)
{
return list;
}

for(int i = 0; i < nums.length - 2; i += 2)
{
for(int j = i + 1; j < nums.length - 1; j++)
{
labelK: for(int k = i + 2; k < nums.length; k++)
{
if(nums[i] + nums[j] + nums[k] == 0)
{
listOfIntegers = List.of(nums[i], nums[j], nums[k]);
list.add(listOfIntegers);
M++;
}
else { continue labelK; }
}
}
}

if(M == 1) { return list; }
else
{
for(int l = 0; l < M - 1; l++)
{
labelM: for(int m = l + 1; m < M; m++)
{
if(list.get(m).containsAll(list.get(l)))
{
list.remove(m);
M = M - 1;
}
else { continue labelM; }
}
}
}
return list;
}
}

Wrong Answer
Runtime: 0 ms
Your input
[0,0,0,0]
Output
[[0,0,0],[0,0,0]]
Expected
[[0,0,0]]

</code>
12 июл 20, 08:57    [22165921]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Sergunka
Member

Откуда: Bay Area, CA
Сообщений: 2282
Alexandrietz
Решаю задачу на leetcode, смысл которой в том, чтобы из целочисленного массива вывести все различные списки Integer'ов, состоящих из 3 чисел таких, что их сумма равна 0 и оформить их в виде списка, то есть будет List<List<Integer>> на выходе. Не понимаю, в чем ошибка, когда тамошний компилятор пишет такое.
<code>
class Solution 
{
    public List<List<Integer>> threeSum(int[] nums) 
    {
        List<Integer> listOfIntegers = new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        int M = 0;
        
        if(nums.length == 0)
        {
            return list;
        }
        
        for(int i = 0; i < nums.length - 2; i += 2)
        {
            for(int j = i + 1; j < nums.length - 1; j++)
            {
                labelK: for(int k = i + 2; k < nums.length; k++)
                {
                    if(nums[i] + nums[j] + nums[k] == 0)
                    {
                        listOfIntegers = List.of(nums[i], nums[j], nums[k]);
                        list.add(listOfIntegers);
                        M++;
                    }
                    else { continue labelK; }
                }
            }
        }
        
        if(M == 1) { return list; }
        else
        {
            for(int l = 0; l < M - 1; l++)
            {
                labelM: for(int m = l + 1; m < M; m++)
                {
                    if(list.get(m).containsAll(list.get(l)))
                    {
                        list.remove(m);
                        M = M - 1;
                    }
                    else { continue labelM; }
                }
            }
        }
        return list;
    }
}

Wrong Answer
Runtime: 0 ms
Your input
[0,0,0,0]
Output
[[0,0,0],[0,0,0]]
Expected
[[0,0,0]]

</code>


Вы бы для начала форматировать текст научились, а потом уже за литкод взялись.

На самом деле дайте ссылку на задачу. Там с десяток в решений уже готовых опубликовано.
12 июл 20, 09:58    [22165928]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz, перед тем как кинуться кодить - расскажи словами как ты сам себе понял задачу.

Your input
[0,0,0,0]


Expected
[[0,0,0]]


На вход пришел вектор из 4х элементов. На выходе - вектор векторов.

А если я подам на вход

Input
[2,3,5,7]


Что ты ожидаешь на выходе?

В подобного рода задачах (алгоритмизация, олимпиадные задчи и контестеры)
важен не java код, а важно твоё понимание тест-кейсов и всех-всех алгоритмических исходов решения.

Если у тебя этого понимания нет - то jav-ой заниматься еще рано. Это будет
зря потраченное время.
12 июл 20, 10:21    [22165933]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Немного подправил
class Solution 
{
    public List<List<Integer>> threeSum(int[] nums) 
    {
        List<Integer> listOfIntegers = new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        int M = 0;
        
        if(nums.length == 0)
        {
            return list;
        }
        
        for(int i = 0; i < nums.length - 2; i++)
        {
            for(int j = i + 1; j < nums.length - 1; j++)
            {
                labelK: for(int k = i + 2; k < nums.length; k++)
                {
                    if(nums[i] + nums[j] == -nums[k])
                    {
                        listOfIntegers = List.of(nums[i], nums[j], nums[k]);
                        list.add(listOfIntegers);
                        M++;
                    }
                    else { continue labelK; }
                }
            }
        }
        
        if(M == 1 || M == 0) { return list; }
        else
        {
            for(int l = 0; l < M - 1; l++)
            {
                labelM: for(int m = l + 1; m < M; m++)
                {
                    if(list.get(m).containsAll(list.get(l)))
                    {
                        list.remove(m);
                        M--;
                        m--;
                    }
                    else { continue labelM; }
                }
            }
        }
        return list;
    }
}

Input
[3,0,-2,-1,1,2]
Output
[[3,-2,-1],[0,-2,2],[0,-1,1],[-2,1,1]]
Expected
[[-2,-1,3],[-2,0,2],[-1,0,1]]
12 июл 20, 10:32    [22165936]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Просто что пришло в голову, то и написал
12 июл 20, 10:36    [22165938]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Однако я знаю, что это решение просто отвратительно, так как оно O(N^3).
12 июл 20, 11:01    [22165944]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Я бы сделал простейшую проверку на существование отрицательных. Или знакопеременных чисел в input.

Это инвариант.

И далее ищи генерацию сочетаний 3 из n.

Любой алгоритм. Но он должен быть рекурсивным. Это мое пожелание по качеству самой реализации. Для 3х элементов у ленивого кодера будет соблазн крутить 3 цикла. Поэтому исключим возможность схитрить.
12 июл 20, 11:04    [22165945]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
dakeiras
Member

Откуда:
Сообщений: 549
Alexandrietz
mayton,

Однако я знаю, что это решение просто отвратительно, так как оно O(N^3).

меня тут спросили на интервью про алгоритмическую сложность и О малое.
Я сказал что ту лекцию прогулял в универе.

Надо будет дать им контакты автора, вон он знает что такое О малое О большое.
12 июл 20, 11:04    [22165946]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
dakeiras
Member

Откуда:
Сообщений: 549
это кстати мега бесполезные задачи на перестановки, сортировки и прочее.

В реальной жизни не используются.
12 июл 20, 11:06    [22165948]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
dakeiras,

Ну, знать лучше надо, но вот эти задачи олимпиадные
12 июл 20, 11:46    [22165965]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
dakeiras,

Все эти о-малое, О-большое - символы Ландау и используются в матане.
12 июл 20, 11:49    [22165968]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8775
dakeiras
...на перестановки....
В реальной жизни не используются.

как минимум pokerstars с Вами не согласен )))
12 июл 20, 12:14    [22165978]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Раз тут говорят что эти задачи бесполезны, то изучать это я не буду. Пойду сервлеты изучать.
12 июл 20, 13:57    [22166003]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz
mayton,

Раз тут говорят что эти задачи бесполезны, то изучать это я не буду. Пойду сервлеты изучать.

Что ты кидаешься из одной крайности в другую?

Это плохая черта. Доведи дело до конца, чьорт тебя подбери!
12 июл 20, 14:03    [22166005]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Да я как бы ни думал, будет O(N^3).
12 июл 20, 14:26    [22166013]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
dakeiras
Member

Откуда:
Сообщений: 549
Leonid Kudryavtsev
dakeiras
...на перестановки....
В реальной жизни не используются.

как минимум pokerstars с Вами не согласен )))


Не согласны те в pokerstars (и во многих других фирмах, 90% их), кто пишет требования к соискателям и проводит интервью.
Т.е. те кто выучил это неиспользуемое и отфильтровывает "не таких как они".

А вот если бы бизнес (точнее те за чей счёт карнавал) знал всю эту поднаготную - он бы сильно удивился и расстроился бы.

Alexandrietz
dakeiras,

Все эти о-малое, О-большое - символы Ландау и используются в матане.

Я его в универе прогулял. На самом деле не прогулял, благополучно сдал выучив на 4 (у оч. строгово препода из стекляшки).
И на след. день полностью забыл.

Всё необходимо использовать по мере надобности.
Не нужно использовать то без чего можно обойтись.
12 июл 20, 14:47    [22166027]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
dakeiras
Member

Откуда:
Сообщений: 549
Alexandrietz
mayton,

Раз тут говорят что эти задачи бесполезны, то изучать это я не буду. Пойду сервлеты изучать.


Тяжёлый вопрос на самом деле.

Откуда идти - снизу вверх или сверху вниз.
Я фанат сверху вниз.

Т.е. всегда от общего иду к частному. Сначала изучаю бизнес, архитектуру, Веб.
До алгоритмов так и не дошёл за 15 лет пока, не потребовалось.


Но на интервью требуют их. Мне норм я такие фирмы шлю.
Но тебе может зайдёт.
12 июл 20, 14:50    [22166035]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
dakeiras
Member

Откуда:
Сообщений: 549
насчёт Покера - там кстати может быть математическая специфика.
Как и в трейдинге.
12 июл 20, 14:53    [22166037]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
Alexandrietz
mayton,
Да я как бы ни думал, будет O(N^3).

Если ты не можешь решить задачу сейчас в том виде комплексности как ее предлагает leetcode - отложи ее.

Не всё сразу возможно заглотить. И не все программисты объективно могут пройти экзамен в Google.
Просто кидание из алгоритмизации в сервлеты - это какая-то суета и паника.

Заработай минимум денег. Оплати платные курсы. Оплати ментора.
Я не верю что мужчина совершеннолетнего возраста не может заработать небольшую сумму.

Давай не ленись и не прокрастинируй.
12 июл 20, 15:03    [22166043]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
забыл ник
Member

Откуда:
Сообщений: 3370
Ну вы тут бадягу конечно развели.
У бедолаги просто нету фильтрации на уникальность решения, поэтому у него на выходе два результата, а должен быть один.
автор

Wrong Answer
Runtime: 0 ms
Your input
[0,0,0,0]
Output
[[0,0,0],[0,0,0]]
Expected
[[0,0,0]]

12 июл 20, 15:47    [22166064]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Valentin Kolesnikov
Member

Откуда:
Сообщений: 3312
Такое решение нашёл.

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
 
    ArrayList<List<Integer>> result = new ArrayList<>();
 
    for (int i = 0; i < nums.length; i++) {
        int j = i + 1;
        int k = nums.length - 1;
 
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
 
        while (j < k) {
            if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                k--;
                continue;
            }
 
            if (nums[i] + nums[j] + nums[k] > 0) {
                k--;
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                j++;
            } else {
                ArrayList<Integer> l = new ArrayList<>();
                l.add(nums[i]);
                l.add(nums[j]);
                l.add(nums[k]);
                result.add(l);
                j++;
                k--;
            }
        }
    }
 
    return result;
}


Хорошего вам дня!
12 июл 20, 16:43    [22166074]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
mayton
Member

Откуда: loopback
Сообщений: 47981
На Розетте есть почти под все языки. Осталось только добавить фильтрацию по summ==0

https://rosettacode.org/wiki/Combinations
12 июл 20, 16:50    [22166077]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8775
dakeiras

А вот если бы бизнес (точнее те за чей счёт карнавал) знал всю эту поднаготную - он бы сильно удивился и расстроился бы.

Вы предполагаете, что люди профессионально занимающиеся игровым бизнесом не знаю, что такое "перестановки" и теория вероятности ? )))

Подозреваю, что владельцы бизнеса по данным вопросам подавляющее большинство форумчан уделают. Если и не с теоретически точки зрения, то по крайне мере с практической.
13 июл 20, 12:38    [22166403]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
dakeiras
Member

Откуда:
Сообщений: 549
Leonid Kudryavtsev
dakeiras

А вот если бы бизнес (точнее те за чей счёт карнавал) знал всю эту поднаготную - он бы сильно удивился и расстроился бы.

Вы предполагаете, что люди профессионально занимающиеся игровым бизнесом не знаю, что такое "перестановки" и теория вероятности ? )))

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

блаженная наивность.
13 июл 20, 17:31    [22166711]     Ответить | Цитировать Сообщить модератору
 Re: Не понимаю, в чем ошибка.  [new]
Alexandrietz
Member

Откуда:
Сообщений: 171
mayton,

Что можете сказать о ШАДе Яндекса? Чему обучают? Стоит ли идти?
15 июл 20, 16:56    [22167991]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Java Ответить