Интересные задачи для программистов

tommy-gung
На сайте с 22.11.2006
Offline
261
#61

ахахахах

простите

Здесь не могла быть ваша реклама
T7
На сайте с 19.09.2018
Offline
36
#62

Сначала в не ту степь с array_combine. Работает, но не обязательно первое достает c например [1,2,3,3,3,3,3, 6].

Потом дошло. Смысл в значениях в качестве индекса.

https://pastebin.com/NcuYkQbe

Вариант в "лоб" по памяти чуть лучше, но медленней

class Solution {

private $n, $t, $l;
public function twoSum(array $nums, int $target) {
$this->n = $nums;
$this->t = $target;
$this->l = count($nums);
$c = $this->l-1;
for($i=0;$i<$c;$i++){
$r = $this->calc($this->n[$i], $i+1);
if(false!==$r) return [$i,$r];
}
return [];
}

private function calc($val, $k){
for($i=$k;$i<$this->l;$i++){
if( $this->t == $val + $this->n[$i]) return $i;
}
return false;
}
}
Gerga
На сайте с 02.08.2015
Offline
89
#63

такой линейный вариант https://pastebin.com/QJvnxc1A , но пока далековато от лучших решений на пхп..

png 1.png
D
На сайте с 18.12.2015
Offline
142
#64

Gerga, очень странно что способ грубого перебора обогнал 49% всех вариантов)) интересно, что там другие понаписывали тогда) наверное count в цикле.

На пыхе у меня вот так вышло, но один раз поняв алгоритм, дальше становится не интересно



Разработка и поддержка высоконагруженных проектов.
S3
На сайте с 29.03.2012
Offline
222
#65

Я заставил свой алгоритм проходить тесты, но пока удручающе все плохо. Но это все еще перебор, хоть и по хэштаб, Пока не могу врубиться в алгоритм(


Runtime: 5964 ms, faster than 8.52% of Python3 online submissions for Two Sum.
Memory Usage: 16 MB, less than 5.77% of Python3 online submissions for Two Sum.


---------- Добавлено 18.06.2020 в 17:47 ----------

danforth:
http://imgur.com/28teQGyl.png

Это как это за 0 сек? 🤪

T7
На сайте с 19.09.2018
Offline
36
#66
danforth:
На пыхе у меня вот так вышло

Очень похожий результат

timo-71:
Смысл в значениях в качестве индекса.
https://pastebin.com/NcuYkQbe
D
На сайте с 18.12.2015
Offline
142
#67

timo-71, у меня такое же решение итоговое. не думал как соточку выжать?

спойлер:

я сначала подумал что нужно преаллоцировать массив (в Go и Rust я так и делал), но в пыхе этого сделать нельзя (SplFixedArray это таки массив, а не мапа или хеш таблица).

T7
На сайте с 19.09.2018
Offline
36
#68

https://pastebin.com/HgtXG8d2

На питоне с тем же алгоритмом:(

---------- Добавлено 18.06.2020 в 19:06 ----------

danforth:
не думал как соточку выжать?

Что то идей больше нет. :(

VoV@
На сайте с 22.09.2007
Offline
196
#69

Вот на С# https://dotnetfiddle.net/rX0UbZ

Вроде правильно работает :)

Compile: 0.014s

Execute: 0.05s

Memory: 0b

CPU: 0.064s

⭐ Разработка Андроид-приложений (Xamarin C#). ⭐ Разработка ASP.NET (WebForms, MVC, WebAPI, Core). ⭐ Цой жив!

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий