Задачки для программистов

[Dimm]

joker99
Убрать его физически тебе придётся для освобождения места. Для этого тебе и надо 2 указателя. Ты относишся к массиву как кругу, по которому бегают 2 указателя. Т.е. такая ситуация:

--4768
   H T

абсолютна законна. Следующая попытка положить в очередь элемент поставит Tail
на нулевой индекс (под первой -). Туда и попадёт новый объект.

[joker99]

Да, ситуация совершенно законна, но в моём способе это бы выглядело так

234768
  H  T

Следующая попытка положить в очередь элемент поставит Tail
на нулевой индекс (под 2). Туда и попадёт новый объект.

[Dimm]

joker99
Во-во и если ты пишешь на С++, то у тебя memory leak.
Иначе тебе придётся удалить объект, как я и сказал:

delete array[head];
array[head] = null;

[Dimm]

2 All

Для тех кто решил задачу с петлёй у связного списка.
Усложняю задачу.
Теперь, после того как один указатель догнал другой, найдите начало петли.
Напоминаю, что указатель на Head очереди у вас сохранён.

[Dimm]

2 All
Так еще одна задачка "на засыпку"

Дано бинарное дерево. Ну, например:

                 5
                /  \
               1    4
              / \     \
             3  7     6

Требуется: распечатать его по уровням

 
5
1 4
3 7 6

Хе-хе, всего-то

[a_ber]

Сообщение от Programmer

2 All

Для тех кто решил задачу с петлёй у связного списка.
Усложняю задачу.
Теперь, после того как один указатель догнал другой, найдите начало петли.
Напоминаю, что указатель на Head очереди у вас сохранён.

Я же написал в начальном посте, что это требуется сделать (причем за линейное время) и естественно О(1) памяти ...

[Dimm]

a_ber

есть ли в нем петля и если есть то где

Да, извини не заметил .
Ладно, раз ты уже спрашивал, даю решение.
1) Ставим один из указателей в начало (head), а второй оставляем указывать на последнюю точку встречи.
2) Пускаем их бежать с одинаковой скоростью.
3) Точка их встречи и будет началом петли.

[joker99]

Сообщение от Programmer

joker99
Во-во и если ты пишешь на С++, то у тебя memory leak.
Иначе тебе придётся удалить объект, как я и сказал:

delete array[head];
array[head] = null;

В твоём оригинальном ответе небыло delete array[head], а было только array[head] = null,значит подразумевался язык с GC, да и вообще было сказано решение не привязанное к языку, а не решение на c++.

[Dimm]

joker99
Ну да, конечно. А теперь представь такую ситуацию.
Мы в языке с GC.
Юзер позвал 10 раз enqueue() и 5 раз dequeue(), получил объекты, поработал с ними и благополучно отпустил. И больше не зовёт очередь. Но эти 5 объектов не будет собраны GC, поскольку ты продолжаешь ссылаться на них.
А теперь представь, что объекты эти занимают каждый много места.
Вота так они и будут болтаться у тебя в памяти как "га*но в проруби".
И всё из-за строки которую ты упрямо отказываешся вставить в свой код споришь уже несколько постов:
array[head] = null;

[joker99]

Согласимся на том что мой вариант был для очереди int, а твой ( после добавления delete array[head]) для объектов

[V@nya]

Вот вам простенькая задачка: дана матрица N*M, заполненная случайным образом 0 и 1. 0-чёрный, а 1-белый цвета. Посчитать число белых "паятен" на чёрном "фоне". Стоящие рядом по вертикали или горизонтали 1 считать за одно пятно (на искосок не считается). Пример:
011100
101101
110001
Здесь 3 "пятна"

[Dimm]

V@nya:
Вот вам простенькая задачка

Действительно, простенькая.

int iSpots = 0, iCounter = 0;
for (int i = 0; i < M; i++, iCounter = 0)
{
   for(int j = 0; j < N; j++)
   {
      if ( matrix[i][j] == 1 )
        iCounter++;
      else 
      {
         if ( iCounter >= 2 )
           iSpots++;
         iCounter = 0;
      }  
   }
}

iSpots - содержит число пятен.

[V@nya]

Programmer, не верно, ты наверно не правильно понял условие, вот ещё пример:
00100
10001
10101
11110
10101
здесь 4 пятна

[Dimm]

V@nya

Больше 2-х единиц как по вертикали так и по горизонтали?

Или одна единица?

[joker99]

Может так:

int iSpots = 0
for (int i = 0; i < M; i++)
{
   for(int j = 0; j < N; j++)
   {
      if ( matrix[i][j] == 1 )
      {
           FillSpot(matrix,i,j)
           iSpots++;
      }
}

void FillSpot(int* matrix,int i,int j)
{
   if (i>= M  || j>= N || matix[j*M+i]  == 0)
       return;
  matix[i][j] = 2;
  FillSpot(matrix,i+1,j);
  FillSpot(matrix,i-1,j);
  FillSpot(matrix,i,j-1);
  FillSpot(matrix,i,j+1);
}

[V@nya]

joker99, почти правильно,но если i=0, то FillSpot(matrix,i-1,j); вылетит с ошибкой т.к. будет присваивать m[-1,j] двойку.
Я функцию FillSpot (kill) делал так:
void kill(int i, int j)
{
m[i][j]=0;
if (i>1)
if (m[i-1][j]==1) kill(i-1,j);
if (i<N)
if (m[i+1][j]==1) kill(i+1,j);
if (j>1)
if (m[i][j-1]==1) kill(i,j-1);
if (j<M)
if (m[i][j+1]==1) kill(i,j+1);
}
Массив был глобальной переменной

[V@nya]

Programmer, едениц может быть сколько угодно.

[Dimm]

Вот вам еще легонькая задачка.
дано:
1 1 1 = 6
2 2 2 = 6
3 3 3 = 6
4 4 4 = 6
5 5 5 = 6
6 6 6 = 6
7 7 7 = 6
8 8 8 = 6
9 9 9 = 6

Требуется: используя ЛЮБЫЕ арифмитические знаки, сделайте выражение верным. Например: 2 + 2 + 2 = 6.
Какие угодно знаки и где угодно. Главное, что-бы выражение было правильным.

взято с аудиогейта Там же и решение. Так что не смотрите заранее.

[V@nya]

3*3-3=6

[V@nya]

6*6/6=6
6+6-6=6