Записки разработчика

Нашел один очень изящный способ решения данной задачи, делюсь.

void removeSpace(char *str) {
char *p1 = str, *p2 = str;
do
while (*p2 == ' ')
p2++;
while (*p1++ = *p2++);
}

Решил начать цикл постов, про алгоритмы и задачам, которые могут попасться на собеседовании. При желании все можно найти на просторах сети, но классно когда все лежит в одном месте. Так вот первая задачка, мне ее кстати задавали при поступлении в СПбАУ РАН на кафедру “математических и информационных технологий” к слову так и не поступил увы. Условие задачи.

Дана строка, удалить все лишние пробелы, под лишними будем иметь ввиду все пробелы в начале и в конце строки и более одного пробела внутри строки. Использовать еще одну строку запрещено. Ниже мое решение.

#include <stdio.h>
#include <string.h>
int main()
{
char* str = new char[128];
int len = sprintf(str,"  Some huge     string with                a lot multiple white spaces!!!   ");
if(len == 0)
return -1;

printf("%s\r\n",str);
bool isStart = true;

char* ptr = str;
int i = 0;
char previos = 'x'; //переменные надо инициализировать, а иначе может быть очень плохо )))
char* endPtr = &str[len - 1];
while(ptr != endPtr)
{
if(*endPtr == ' ')
{
endPtr--;
continue;
}

if(*ptr == ' ' && isStart)
{
*ptr++;
continue;
}

if(*ptr !=' ')
{
isStart = false;
}
if(previos == ' ' && *ptr == ' ')
{
*ptr++;
continue;
}

previos = *ptr;
str[i++] = *ptr++;
}

str[i++] = *endPtr; //тут записываем последний символ
str[i]='\0';
printf("%s\r\n",str);
getchar();
return 0;
}

Не забывайте, что sprintf deprecated здесь используется только для демонстрации примера. Если вы обнаружили не точность в примере, лучший способ решения или, что еще хуже ошибку, отпишите в коменты, что бы распространять знание, а не на оборот.

Понравился алгоритм для решения этой задачи, активно используется стек так что он эффективен на не больших данных, либо на не больших связных поверхностях. Типичным способом решения этой задачи это поиск в глубину. Ниже исходник для выделения однотонных объектов на изображении.

class Program
 {
 static void Main(string[] args)
 {
 if (args.Length < 0)
 {
 Console.WriteLine("[*] Input image path");
 return;
 }
 GLOBAL_DATA.Image2Recog = (Bitmap)Bitmap.FromFile(args[0]);
 GLOBAL_DATA.Width = GLOBAL_DATA.Image2Recog.Width-1;
 GLOBAL_DATA.Height = GLOBAL_DATA.Image2Recog.Height-1;
 SamePixelRecognition obj = new SamePixelRecognition();
 obj.FindSameLinkedPixels();
 Console.WriteLine("There is a {0} linked surface in image",GLOBAL_DATA.Count);
 Console.ReadKey();

 }
 }

class GLOBAL_DATA
 {
 public static Bitmap Image2Recog;
 public static int Count=0;
 public static int Width = 0;
 public static int Height = 0;
 public static Color White = Color.FromArgb(255, 255, 255, 255);
 }

class SamePixelRecognition
 {
 public void FindSameLinkedPixels()
 {
 for(int y = 0;y < GLOBAL_DATA.Height; y++)
 for (int x = 0; x < GLOBAL_DATA.Width; x++)
 {
 if (GLOBAL_DATA.Image2Recog.GetPixel(x, y) != GLOBAL_DATA.White)
 {
 Color tmp = GLOBAL_DATA.Image2Recog.GetPixel(x, y);
 RemovePixel(x, y);
 GLOBAL_DATA.Count++;
 }
 }
 }
 private void RemovePixel(int x, int y)
 {
 int[] wayX = {-1,0,1,0 };
 int[] wayY = {0,-1,0,1 };
 int tX;
 int tY;
 GLOBAL_DATA.Image2Recog.SetPixel(x, y, GLOBAL_DATA.White);

 for (int i = 0; i < wayX.Length; i++)
 {
 tX = wayX[i] + x;
 tY = wayY[i] + y;
 if (tX < 0 || tX > GLOBAL_DATA.Width || tY < 0 || tY > GLOBAL_DATA.Height)
 continue;
 if (GLOBAL_DATA.Image2Recog.GetPixel(tX, tY) != GLOBAL_DATA.White)
 this.RemovePixel(tX, tY);
 }
 }
 }

Используется как видите C#, алгоритм решает задачу, на поиск связанных пикселов т.е. тех, которые расположена рядом друг с другом.

Нужно было реализовать, код вообще -то не сложен, но тем не менее . Поворот матрицы по часовой стрелке.

#include<iostream>
#define n 10
using namespace std;
int matr[n][n];
int main()
{
 for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
 cin>>matr[i][j];

 int tmp;
 for(int i=0;i<n/2;i++)
 {
 for(int j=i;j<n-1-i;j++)
 {
 tmp = matr[i][j];
 matr[i][j] = matr[n-j-1][i];
 matr[n-j-1][i] = matr[n-i-1][n-j-1];
 matr[n-i-1][n-j-1] = matr[j][n-i-1];
 matr[j][n-i-1] = tmp;
 }
 }
}

Поворот против часовой стрелки

#include<iostream>
#define n 10
using namespace std;
int matr[n][n];
int main()
{
 for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
 cin>>matr[i][j];

 int tmp;
 for(int i=0;i<n/2;i++)
 {
 for(int j=i;j<n-1-i;j++)
 {
 tmp = matr[i][j];
 matr[i][j]=matr[j][n-1-i];
 matr[j][n-1-i]     = matr[n-1-i][n-1-j];
 matr[n-1-i][n-1-j] = matr[n-1-j][i];
 matr[n-1-j][i]     = tmp;
 }
 }
}

Достаточно простая задача на нахождение простых чисел, приведу два исходника на Си / С++ для решение такой задачи. Используем знаменитый метод “Решето Эратосфена”.

Код на Си

long nn = 10000;
int mas[nn];

memset(mas, 0, sizeof(mas));

mas[0] = 1;
mas[1] = 1;
for (int i = 2; i < nn; i++)
 if (!mas[i])
 {
 for (int j = i * 2; j < nn; j += i)
 mas[j] = 1;
 }

Continue reading “Нахождение простых чисел” »

Зарегистрировался на CodeChief и сразу попался, простецкая задача на сортировку, но не тут -то было пробовал Quicksort и MergeSort оба выдавали Time Limit Exceeded. Ответ оказался прост, нужно было воспользоваться сортировкой подсчетом. Основная идея создать нулевой массив размерностью в диапазон в водимых чисел и при вводе чисел производить инкрементацию в итоге после получения данных мы уже получаем “отсортированный” массив. Алгоритм отлично работает с положительными числами, для работы с отрицательными или со структурами данных требуется его переделать. Сортировка подсчетом на вики wiki Ниже приведен код

Continue reading “Сортировка подсчетом” »

Есть два множества нужно найти их пересечение, каким образом это сделать за минимальное время. Можно для этих целей использовать STL . В этом случае нам нужно иметь два множества, обязательно отсортированных. Функция нахождения пересечения и сортировки находятся в заголовочном файле <algorithm>. Пример того как это сделать с помощью STL

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
 int first[] = {5,10,15,20,25};
 int second[] = {50,40,30,20,10};
 vector<int> v(10);
 vector<int>::iterator it;

 sort (first,first+5);     //  5 10 15 20 25
 sort (second,second+5);   // 10 20 30 40 50

 it=set_intersection (first, first+5, second, second+5, v.begin());
 cout << "intersection has " << int(it - v.begin()) << " elements.\n";
 return 0;
}

Этот код взят с cplusplus.com. Если же вы пишете на другом ЯП и считаете что нужно знать как все выполняется то смотрим дальше. Весь код приводить не буду, первое что нужно уяснить алгоритм работает на отсортированных множествах иначе, работать не будет, если не нравится сортировать то добро пожаловать в сложность O(N^2)., нам же этого не нужно. Быстро набросанный код для этого. Тут все еще есть стандартная функция сорт, можно было бы и самому реализовать, но хотел что бы листинг был как можно компактнее, тем более что основные алгоритмы для сортировки в блоге приведены тут и тут.

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
int result[10];
sort (first,first+5);
sort (second,second+5);
for(int i=0,k=0;i<sizeof(first);i++)
for(int j=0;j<sizeof(second);j++)
{
if(second[j]>first[i])
break;
if(first[i]==second[j])
{
result[k]=first[i];
k++;
break;
}
}
return 0;
}

Универсальный  алгоритм для сортировки, так же называется qsort или quicksort. был разработан в 1960 году Чарльзом Хоаром. Сортировка в среднем за  O(n*log n), но в худшем случае может деградировать до O(n^2). Данный вид сортировки, является не устойчивым. Ниже код на С++

Continue reading “Быстрая сортировка” »

После некоторого анализа, проведенного Халом Бурчем (Hal Burch). Все задачи на алгоритмы можно разделить на 16 категорий, причем несколько из них покрывают 80% предметной области. Причем наиболее сложной являются комбинаторные задачи. Ниже список:

Continue reading “Заметка об алгоритмах” »

Сортировка слиянием относиться к классу алгоритмов “разделяй и властвуй”. Является устойчивой. Сложность алгоритма O(n*log(n)), требует выделение дополнительной памяти. Алгоритм изобретен Джоном фон Нейманом в 1945г. Ниже приведен код реализации.

Continue reading “Сортировка слиянием” »