321

Re: Цікаві задачі

Ви мали на увазі ось це рішення?

var isPalindrome = function(head) {
    let front=head, flag=true;
    let traverse=(node)=>{
        node.next && traverse(node.next);
        if(node.val!==front.val) flag=false;
        front=front.next
    }
    traverse(head);
    return flag;
};

322

Re: Цікаві задачі

Зацініть ще такий алгоритм.

Нам було б добре розділити той список на дві рівні частини, а потім змінити напрямок зв'язків в одній половині, і пройтися відразу по обом половинам, порівнюючи їхні значення.

Але виникає питання, як нам знайти першу половину списку, якшо ми не знаємо довжини? Можна спершу пройтися по всім ланкам, порахувати їхню кількість, а потім пройтися знову, але лише до половини кількості.

А чи можна це зробити в один прохід? Можна.

let slow = head;
    let fast = head;
    
    //finding middle node
    while(fast !== null && fast.next !== null){
        fast = fast.next.next;
        slow = slow.next;
    }

хіба не це прекольно?

Подякували: leofun011

323

Re: Цікаві задачі

FakiNyan написав:

По часу виходе O(n/2)

Це є O(n).

FakiNyan написав:

Чи можна перевірити, чи дані у однозв'язному списку є паліндромом, при цьому шоб O(n) по часу, і O(1) по використаній пам'яті?

Якщо вузли списку (nodes) мутабельні і якщо є доступ (rw, get/set) до звязків (links, nodeptr), то можна.

324

Re: Цікаві задачі

leofun01 написав:
FakiNyan написав:

По часу виходе O(n/2)

Це є O(n).

FakiNyan написав:

Чи можна перевірити, чи дані у однозв'язному списку є паліндромом, при цьому шоб O(n) по часу, і O(1) по використаній пам'яті?

Якщо вузли списку (nodes) мутабельні і якщо є доступ (rw, get/set) до звязків (links, nodeptr), то можна.

А чог оце є O(n) ? Ми ж виконуємо 1 операцію порівняння відразу для двох елементів списку, а не для кожного окремого елементу.

325

Re: Цікаві задачі

FakiNyan, почитайте щось про велике О. Визначення хоча б.

Подякували: leofun011

326

Re: Цікаві задачі

koala написав:

FakiNyan, почитайте щось про велике О. Визначення хоча б.

Може я вже знаю, але мені треба підтвердження?

327

Re: Цікаві задачі

Натрапив на дуже просте завдання, але хотів запитатись, чи його якось можна зробити без рекурсій і циклів, а шоб формулою.

У нас є якесь додатнє ціле число. Нам треба порахувати кількість операцій, після котрих у нас буде 0.
Якшо число ділиться на два, то ми ділимо його на два, а якшо ні, то віднімаємо від нього 1.

328

Re: Цікаві задачі

FakiNyan написав:

Натрапив на дуже просте завдання, але хотів запитатись, чи його якось можна зробити без рекурсій і циклів, а шоб формулою.

У нас є якесь додатнє ціле число. Нам треба порахувати кількість операцій, після котрих у нас буде 0.
Якшо число ділиться на два, то ми ділимо його на два, а якшо ні, то віднімаємо від нього 1.

Ну тобто (довжина)+(кількість одиниць)-1. Довжину можна логарифмом знайти, а от кількість одиниць... гм...

329

Re: Цікаві задачі

От я теж про логаритм думав

330

Re: Цікаві задачі

схоже, формули без ітерацій немає.

Подякували: leofun01, FakiNyan2

331

Re: Цікаві задачі

FakiNyan написав:

От я теж про логаритм думав

#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    int n = 123;

    printf("%d\n", (n == 0) ? 1 : (int)(1 + log10((double)n)));
    printf("%d\n", (n == 0) ? 1 : (int)(ceil(log10(0.5 + n))));

    return 0;
}

332

Re: Цікаві задачі

Задачка така є.
Нехай у нас є два зв'язаних списки довільної довжини. Кожна ланка списку тримає в собі значення якоїсь циферки від 0 до 9, а сам список являє собою певне число, але воно представлене в зворотньому напрямку, тобто, число 123 буде представлене списком
3 -> 2 -> 1

Нам треба додати два таких числа, і повернути результат у вигляді подібного зв'язного списку, наприклад:

3 -> 2 -> 1
+
1 -> 2 -> 3
=
4 -> 4 -> 4

на leetcode це завдання ніби Medium, але не таке вже й складне.

Прихований текст
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const sumHead = new ListNode();
  let currSumNode = sumHead;
  let rest = 0;
  
  let head1 = l1;
  let head2 = l2;
  
  while (head1 || head2) {

    const val1 = head1?.val ?? 0;
    const val2 = head2?.val ?? 0;
    
    const sum = val1 + val2;
    
    currSumNode.val = (sum + rest) % 10 ;
    rest = Math.floor((sum + rest) / 10);
    
    head1 = head1?.next;
    head2 = head2?.next;
    
    if (head1 || head2) {
      const nextSumNode = new ListNode();
      currSumNode.next = nextSumNode;
      currSumNode = nextSumNode;
    } else {
      break;
    }
  }
  
  if (rest) {
    currSumNode.next = new ListNode(rest);
  }
    
  return sumHead;
};

333 Востаннє редагувалося FakiNyan (20.04.2022 18:21:03)

Re: Цікаві задачі

Уявість собі 2D контейнер з перегородками всередині, його стінки і перегородки є нерівними по висоті. Нам треба знайти такі дві перегородки, між котрими ми зможемо налити найбільше води.
Ось на картинці показується, що між перегородками 2 та 6 ми можемо налити 24 квадратних сантиметри води, це тому що перегородка під номером 2 має висоту 7, а перегородка під нумером 6 має висоту 6, і між цими двома перегородками відстань (6-2)= 4 сантиметри, тому 6*4 = 24 кубічних сантиметра води.

Перегородок може бути тисячі, і їхня висота обирається випадковим чином, як би ви вирішили таке завдання?
https://i.imgur.com/EqgJaYE.png

p.s. на вхід нам дається масив з висотами перегородок

334

Re: Цікаві задачі

1. Шукаємо індекс останнього максимального елементу масиву, та запам’ятовуємо його. (id_end = max ≤ a(i), де i = 0 ... N-1)
2. Шукаємо індекс першого максимального елементу масиву (id_beg = max < a(i), де i = 0 ... id_end коли значення елемента масиву збігається із значенням масиву з попереднім кроком 1.) або id_beg = max < a(i), де i = 0 ... N-2 у найгіршому випадку, коли — значення менше за попередній максимальний елемент, виключаючи індекс останнього максимального елементу із кроку 1.
3. Тоді за цими індексами беремо значення, висоти перегородки. Шукаємо серед них мінімальне значення, якщо такий є (мається на увазі рівність між цими двома максимальними елементами).
4. Відстань між індексами за модулем, множимо на найменший серед максимальних елементів.

Якось так...

335

Re: Цікаві задачі

закодуйте це може, бо зі слів важко зрозуміти, чи воно робе, чи ні

336

Re: Цікаві задачі

lucas-kane написав:

найменший серед максимальних елементів

Це як?

337

Re: Цікаві задачі

koala написав:
lucas-kane написав:

найменший серед максимальних елементів

Це як?

https://i.imgur.com/EqgJaYE.png

338

Re: Цікаві задачі

Ви хотіли сказати "менший серед двох найбільших"? Бо максимальний може бути лише один. Якщо мова не про локальні максимуми.
Усе одно не зовсім розумію вашу ідею. Я б розв'язував так.
1. Обираємо дві крайні перетинки, обчислюємо, скільки там можна води налити.
2. В циклі:
2.1. Беремо нижчу з двох обраних, шукаємо першу вищу за неї (з початку - праворуч, з кінця - ліворуч). Якщо обидві однакові - шукаємо нові замість обох. Якщо немає куди далі шукати - завершуємо цикл.
2.2. Перевіряємо, скільки води тепер можна налити. Якщо більше - запам'ятовуємо.

339

Re: Цікаві задачі

осьо розв'язок, до якого я дійшов трішки згодом, бо відразу я зафігачив повний перебір, штибу бульбашкового сортування, але воно не пропустило по часу, а цей пропустило вже

Прихований текст
function maxArea(height: number[]): number {
  let max = 0;
  let left = 0;
  let right = height.length - 1;
  
  while (left < right) {
    const min = Math.min(height[left], height[right]);
    max = Math.max(max, min * (right - left));
    if (height[left] > height[right]) {
      right--;
    } else {
      left++;
    }
  }
  
  return max;
};

340 Востаннє редагувалося lucas-kane (21.04.2022 02:15:17)

Re: Цікаві задачі

Мав на увазі щось типу цього.
Звести задачу пошуку до максимальних елементів та їх індексів

Прихований текст
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a[] = {2, 3, 7, 1, 2, 5, 6, 4}, t1, t2; // вхідний масив та тимчасові змінні
    size_t n = sizeof a / sizeof *a, // довжина масиву
        id_beg, id_end; // змінні для зберігання індексів

    t1 = t2 = *a;
    id_beg = 0;
    id_end = 0;

    // шукаємо індекси
    for (size_t i = 1; i < n; i++)
    {
        if (t1 < a[i]) // ... першого максимального та ...
            t1 = a[id_beg = i];

        if (t2 <= a[i]) // ... останнього
            t2 = a[id_end = i];
    }

    // Якщо елемент не повторюється, тоді ...
    if (id_beg == id_end)
    {
        size_t id[2];

        // ... шукаємо більший елемент серед тих що лишилось
        t1 = *a;
        for (size_t i = 1; i < id_end; i++)
            if (t1 < a[i])
                t1 = a[ *id = i];

        t1 = *(a + (n - 1));
        for (size_t i = (n - 2); i > id_end; i--)
            if (t1 < a[i])
                t1 = a[*(id + 1) = i];

        id_beg = ((id_end - *id) > (*(id + 1) - id_end))
                     ? *(id)
                     : *(id + 1);
    }

    t1 = (a[id_beg] < a[id_end])
             ? a[id_beg]
             : a[id_end];

    t2 = (id_beg < id_end)
             ? (id_end - id_beg)
             : (id_beg - id_end);

    printf(
        "a[%zu] = %d\n"
        "a[%zu] = %d\n"
        "Area = %d\n",
        id_beg, a[id_beg], id_end, a[id_end], (t1 * t2));

    return 0;
}