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

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

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 здесь используется только для демонстрации примера. Если вы обнаружили не точность в примере, лучший способ решения или, что еще хуже ошибку, отпишите в коменты, что бы распространять знание, а не на оборот.

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

#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;
}

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

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

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

void SetBit(DWORD& dw, int nBitNumber, int nBitValue)
{
 //dw - целое, в котором задаем бит
 //nBitNumber - номер бита, который задаем (0..31)
 DWORD dwMask = 1 << nBitNumber;// 0000100000....

 //nBitValue (0|1)
 if(nBitValue == 0)
 {//задаем 0
 dwMask = ~dwMask;// 1111011111....
 dw = dw & dwMask; // 0 & x = 0
 }
 else
 {//задаем 1
 dw = dw | dwMask;// 1 | x = 1
 }
}

int GetBit(DWORD dw, int nBitNumber)
{
 //dw - целое в котором узнаем бит
 //nBitNumber - номер бита, который узнаем (0..31)
 DWORD dwMask = 1 << nBitNumber;// 0000100000....
 dw = dwMask & dw;
 if(dw)
 return 1;
 return 0;
}

Взято отсюда

Это классический алгоритм, который знают все от мала до велика, но для полноты картины без него не обойтись.  Сложности алгоритма O(N^2), является  устойчивой сортировкой. Ниже приведен код.

Continue reading “Пузырьковая сортировка” »

Разберем шаблон проектирования Абстрактная фабрика, паттерн относится к группе порождающих паттернов и применяется для создания семейств связанных или не связанных между собой групп объектов, конкретные классы которых не известны. Ниже приведен код на C++/C#.

Continue reading “Шаблон проектирования Абстрактная фабрика (Abstract Factory)” »