6:56 PM
void Main() { var workDir = Path.Combine(Util.MyQueriesFolder, "nunit-work"); var args = new string[] { "-noheader", $"--work={workDir}", }; RunUnitTests(args); } // Define other methods and classes here [Test] [TestCase(new int[] { 0,0,0,0,0 }, 0, new int[] { 1,2,3,4,5 }, 5, new int[] { 1,2,3,4,5 })] // A6 [TestCase(new int[] { 0 }, 0, new int[] {1 }, 1, new int[] { 1 })] // A5 [TestCase(new int[] { 1, 101,0 }, 2, new int[] { }, 0, new int[] {1,101,0})] // A0 [TestCase(new int[] { 101,102,103,0 }, 3, new int[] { 1 }, 1, new int[] {1,101,102,103})] // A1
Достаточно много времени ушло на то, чтобы учесть все сценарии (штук пять тест-кейсов я сам нашлёпал, потом ещё верхних два (А5 и А6) мне сайт подкинул
Я просто глядя на своё решение понимаю, что слишком оно длинное и явно я просто вообще куда-то не в ту степь решал
Это чисто случайно повезло, что в этой стороне тоже есть решение, пусть не оптимальное, но ведь его просто могло бы и не быть
public void Merge(int[] nums1, int m, int[] nums2, int n) { var mPoint = m-1; var nPoint = n-1; for(int i = m+n-1; i>=0; i--) { if(mPoint == -1) nums1[i] = nums2[nPoint--]; else if(nPoint == -1) nums1[i] = nums1[mPoint--]; else if(nums1[mPoint] > nums2[nPoint]) nums1[i] = nums1[mPoint--]; else nums1[i] = nums2[nPoint--]; } }
Понимаю: да, вот это явно хорошее решение. Многократно короче моего - уже плюс, я прямо чувствую, что если начну читать его то сразу подумаю "блиииииииииин, ну ПОЧЕМУ Я не подумал в эту сторону???"
You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don't know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?
Вот почему я эту подсказку смотрел и всё равно не так применил (в общем-то я тоже ведь сравниваю два числа), а кто-то другой понимает так, что получается кратко и изящно?
@tym32167 Они мало того, что сложно подбираемые... они какие-то кривые, нет в них изящности, даже если удалось решить -- вот какая мысль.
@tym32167 пойду гляну и эту книгу... вдруг в ней что-то попадётся такое, что повернёт мне мозги в нужную сторону
7:22 PM
@AK об этом и речь. Вы де не думаете, что за пару дней выучите алгоритмы и будете красиво решать задачи? Вот вы ООП с самого начала использовали со всеми паттернами и практиками? Я, например, поначалу даже не понимал, где хороший код, а где лапша. Хотите преуспеть в решении задач - читать теорию мало, надо решать задачи. Много решать.
Я когда-то был упорный, мне надо было всё решать самому, я не хотел тратить время на теорию, я хотел "вот прям ща сяжу и разнесу задачу", я думал, что я самый умный и гордо не глядел теорию и не смотрел ответы. В итоге вот, поглядите сюда acm.timus.ru/status.aspx?author=123649 - некоторые залачи заняли у меня по 2 года :)
Знаете, когда я решать их массов стал? Когда прошел курс алгоритмов и прочитал кнниги по алгоритмам. Базовые структуры данных мне дали пинка. Я и знать не знал, например, про Union-Find или Trie. А уже вооруженный теорией и спустивгись на землю, дело пошло гораздо быстрей.
Ваша задача же тут- научиться решать. Я смотрел оптимальные решения всех сложных задач. Конечно, хорошо сначала самому решить задачу, а потом поглядеть на лушчее решение. Но если сам не справляешься, не надо зацикливаться - я просто иду, гляжу решение, и пытаюсь понять, как бы я мог до него додуматься
@tym32167 А я вот не знаю, когда я их массово начну решать. Книжки эти я поверхностно листал и раньше. Даст ли буст глубокое чтение? Или буст лежит в наработке? Пока не знаю.
7:34 PM
@AK Открываете книгу - смотрите структуры данных - если вы уже знаете, что это за структура и можете сами её написать, то листайте дальше. С алгоритмом то же - если можете просто сейчас по памяти напистать MergeSort или CountingSort - то вам не надо про него читать. Теория вам дать дожна инструменты, если вы ими уже умеете пользоваться, то нет смысла перечитывать.
@tym32167 Из сортировок я по памяти только сортировку вставками и пузырёк могу минут за 10 набросать, остальное надо смотреть в книги. Тупо не помню даже сам алгоритм. Просто помню "Quick sort - одна из наиболее эффективных, её часто берут в качестве дефолтной реализации сортировок в разных библиотеках" А что там за алгоритм.. его так навскидку не обьяснишь, не вспомнишь.
Ладно, пойду дальше руду добывать... пока выходные и можно чуть больше посидеть над задачами. Есть кстати смысл тут тоже зарегаться acm.timus.ru или лучше пока на leetcode + hackerrank остановиться?
7:44 PM
@AK ну вот на этот уровень я бы и ориентировался. Вы же сказали, что у вас квартал времени - вот рассчитывайте весь квартал решать задачи. Хотя бы по 1-2 в день
+ не зацикливайтесь на легких задачах, если чувствуете себя комфортно с легкими, уменьшайте кол-во легких и увеличивайте кол-во средних
8:33 PM
:56487141 Поглядел на задачу, что вы дали (не подсматривая в ответы) и решил её вот так public class Solution { public void Merge(int[] nums1, int m, int[] nums2, int n) { for (int i = m - 1; i >= 0; i--) nums1[i + n] = nums1[i]; int ind1 = n; int ind2 = 0; int ind = 0; while(ind < m+n) { if (ind1 < (n+m) && ind2 < n) nums1[ind++] = nums1[ind1] <= nums2[ind2] ? nums1[ind1++] : nums2[ind2++]; if (ind1 == (n+m) && ind < m+n) nums1[ind++] = nums2[ind2++]; if (ind2 == n && ind < m+n) nums1[ind++] = nums1[ind1++];
попал в 85% , потом поглядел решение и понял, что да, можно было бы и просто мерджить с конца. Оно было бы и побыстрей чуть чуть. Но асимптотике моего решения такая же, как и лучшего. По пымяти тоже самое. Получается, что мое решение тоже норм подойдет. Просто мне было понятней сдвинуть масив и потом сделать обычный Merge, а лучшее решение будет сделать Merge с конца.
« first day (1953 days earlier) ← previous day next day → last day (1078 days later) »
Transcript for
Dec18
Dec '2019
Dec22
Дискуссии о C#/.NET на русском
Эта комната посвящена обсуждению C#: всё, что не подходит в фо...