Личный технический блог:www.zhenganwen.top

временная сложность

Временная сложность является одним из важных показателей для измерения качества алгоритма. Временная сложность отражает влияние увеличения размера выборки неопределенности на время, необходимое для работы алгоритма, которое напрямую связано с тем, задействуется ли в работе алгоритма размер выборки и сколько раз она задействована, например, при обходе массива, временная сложность равна длине массива n (соответствующая временная сложность равнаO(n)), в то время как метаоперации с данными (такие как сложение, вычитание, умножение, деление и т. д.), логические операции (такие как суждение) и т. д. относятся кпостоянныйОперации во времени (соответствующие временной сложностиO(1)).

При упрощении выражения временной сложности алгоритма следует соблюдать следующие правила:

Для того же размера выборки член младшего порядка может быть опущен, и может быть сохранен только член старшего порядка, напримерO(n^2)+O(n)можно упростить доO(n^2),O(n)+O(1)можно упростить доO(n)
Постоянный коэффициент перед размером выборки можно не указывать, напримерO(2n)можно упростить доO(n),O(8)можно упростить доO(1)
Для различных неопределенных размеров выборки упрощение не может быть выполнено в соответствии с двумя вышеуказанными правилами, и приращение выражения следует анализировать в соответствии с фактическим размером выборки. какO(logm)+O(n^2)нельзя свести кO(n^2)илиO(logm). И это зависит от разрыва между m и n для упрощения.Например, когда m>>n, это можно упростить какO(logm), так как приращение выражения определяется размером выборки.

дополнительная космическая сложность

Дополнительная пространственная сложность алгоритма относится к дополнительному пространству, требуемому операцией алгоритма для входной выборки. Например, при использовании пузырьковой сортировки для сортировки массива в процессе требуется только одна временная переменная.temp, то дополнительная пространственная сложность алгоритма равнаO(1). Другим примером является сортировка слиянием.В процессе сортировки необходимо создать вспомогательный массив того же размера, что и выборочный массив.Хотя после сортировки массив уничтожается, дополнительная сложность алгоритма по объему памятиO(n).

Классические примеры - выводы из одного случая

Найдите числа в B, которые не принадлежат A

Найдите в массиве B числа, не принадлежащие A. Массив A упорядочен, а массив B неупорядочен. Предполагая, что массив A имеет n чисел, а массив B имеет m чисел, напишите алгоритм и проанализируйте временную сложность.

Способ 1: Траверс

Сначала пройдите B, найдите каждое число в B, чтобы найти в A, и распечатайте, если оно найдено. Соответствующий алгоритм выглядит следующим образом:

int A[] = {1, 2, 3, 4, 5};
int B[] = {1, 4, 2, 6, 5, 7};

for (int i = 0; i < 6; ++i) {
  int temp = B[i];
  bool flag = false;
  for (int j = 0; j < 5; ++j) {
    if (A[j] == temp) {
      flag = true;    //找到了
      break;
    }
  }
  if (!flag) {    //没找到
    printf("%d", temp);
  }
}

Нетрудно видеть, что временная сложность приведенного выше алгоритма равнаO(m*n), потому что оба массива просматриваются один раз

Способ 2: Бинарный поиск

Поскольку массив A упорядочен,Чтобы найти элемент в упорядоченной последовательности, вы можете использовать метод деления пополам (также известный как метод деления пополам).. Принцип состоит в том, чтобы сравнить искомый элемент с медианой последовательности.Если он меньше, удалить медиану и последовательность после нее.Если он больше, удалить медиану и ее предыдущую последовательность.Если он равен, он находится. Если она не равна, продолжайте сравнивать ее с оставшейся последовательностью, пока она не будет найдена или оставшаяся последовательность не станет пустой.

Код для решения задачи методом дихотомии выглядит следующим образом:

for (int i = 0; i < 6; ++i) {		//B的长度为6
  int temp = B[i];
  //二分法查找
  int left = 0,right = 5-1;			//A的长度为5
  int mid = (left + right) / 2;
  while (left < right && A[mid] != temp) {
    if (A[mid] > temp) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
    mid = (left + right) / 2;
  }
  if (A[mid] != temp) {
    printf("%d", temp);
  }
}

forциклmВторосортный,whileциклlognраз (если не указано иное, журнал основан на 2), временная сложность этого алгоритма составляетO(mlogn)

Способ 3: Сортировка + Очередь

Третий метод заключается в сортировке массива B, а затем использованииПоследовательное сравнениеспособ узнать, содержит ли массив A элемент массива B. Вводятся два указателя a и b, указывающие на первые элементы массивов A и B соответственно, и сравниваются значения элементов, на которые указывают указатели.a<b, переместите указатель a назад, чтобы найти элемент; когдаa=b, указывая, что элемент существует в A, пропустить поиск элемента и переместить b назад; когдаa>bКогда это означает, что элемент не существует в A, напечатайте элемент и пропустите поиск элемента и переместите b назад. Пока либо a, либо b не достигнет конца массива (если a достигнет конца первым, то ни число после b, ни b не принадлежит A)

Соответствующий код для решения проблемы выглядит следующим образом:

void fun3(int A[],int a_length,int B[],int b_length){
    quickSort(B, 0, b_length - 1);	//使用快速排序法对数组B排序->O(mlogm)
    int* a = A,*b=B;
    while (a <= A + a_length - 1 || b <= B + b_length - 1) {
        if (*a == *b) {
            b++;
            continue;
        }
        if (*a > *b) {
            printf("%d", *b);
            b++;
        } else {
            a++;
        }
    }

    if (a == A + a_length) {	//a先到头
        while (b < B + b_length) {
            printf("%d", *b);
            b++;
        }
    }
}

Код для быстрой сортировки выглядит следующим образом:

#include <stdlib.h>
#include <time.h>

//交换两个int变量的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//产生一个low~high之间的随机数
int randomInRange(int low, int high){
    srand((int) time(0));
    return (rand() % (high - low))+low;
}

//快速排序的核心算法，随机选择一个数，将比该数小的移至数组左边，比该数大的移至
//数组右边，最后返回该数的下标（移动完之后该数的下标可能与移动之前不一样）
int partition(int arr[],int start,int end){
    if (arr == NULL || start < 0 || end <= 0 || start > end) {
        return -1;
    }

    int index = randomInRange(start, end);//随机选择一个数
    swap(arr[index], arr[end]);//将该数暂时放至末尾

    int small = start - 1;
    //遍历前n-1个数与该数比较并以该数为界限将前n-1个数
    //分为两组，small指向小于该数的那一组的最后一个元素
    for (index = start; index < end; index++) {
        if (arr[index] < arr[end]) {
            small++;
            if (small != index) {
                swap(arr[small], arr[index]);
            }
        }
    }

    //最后将该数放至数值较小的那一个组的中间
    ++small;
    swap(arr[small], arr[end]);
    return small;
}

void quickSort(int arr[],int start,int end) {
    if (start == end) {
        return;
    }
    int index = partition(arr, start, end);
    if (index > start) {
        quickSort(arr,start, index - 1);
    }
    if (index < end) {
        quickSort(arr, index + 1, end);
    }
}

Временная сложность этого метода:O(mlogm)(сначала отсортировать B) +O(m+n)(В худшем случае оба указателя a и b достигли конца).

Сравнение трех методов

O(m*n)
O(mlogn)(На основе 2)
O(mlogm)+O(m+n)(На основе 2)

Легко понять, что алгоритм 2 лучше, чем 1, потому что скорость ростаlogn<n. И сравнение между 2 и 3 зависит от разницы между размерами выборки m и n, еслиm>>nТогда лучше 2, и это нетрудно понять: если в массиве B больше элементов, то сортировка B однозначно займет много времени, и этот шаг не является обязательным для решения задачи, поэтому лучше использовать метод дихотомии; наоборот, еслиm<<n, то 3 лучше.

вопрос о голландском флаге

Дан массив arr и число num, поместите число меньше num в левую часть массива, число, равное num, в середину массива, а число больше num в правую часть массива.

Требуется дополнительная пространственная сложность O (1), временная сложность O (N)

Идея: использовать два указателяL,R,будетLПрежде чем указать на первый элемент,RТочки после хвостового элемента. Пройти последовательность с начала, сравнивая текущий пройденный элемент сnumсравните, еслиnum, затем объедините его сLПоменяйте местами правый элемент и повторите следующий элемент, сдвиньте вправоL;как=numЗатем перейдите непосредственно к следующему элементу; если>numзатем совместите его сRПоменяйте местами позицию левого элемента и переоцените элемент текущей позиции с помощьюnumОтношение. Пока пройденный элемент не будет индексированR-1до того как.

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
void partition(int arr[],int startIndex,int endIndex,int num){
    int L = startIndex - 1, R = endIndex + 1, i = startIndex;
    while (i <= R - 1) {
        if (arr[i] < num) {
            swap(arr[i++], arr[++L]);
        } else if (arr[i] > num) {
            swap(arr[i], arr[--R]);
        } else {
            i++;
        }
    }
}

int main(){
    int arr[] = {1,2, 1, 5, 4, 7, 2, 3, 9,1};
    travles(arr, 8);
    partition(arr, 0, 7, 2);
    travles(arr, 8);
    return 0;
}

Lпредставляет собой менееnumправая граница числа,Rпредставляет собой больше, чемnumлевая граница ,partitionПроцесс заключается в пересечении элементов и ростеL、Rдиапазонный процесс. Что здесь сложнее понять, может быть, почемуarr[i]<numпереместить вправоLиarr[i]>numне движется влевоR, потому что для текущего элементаarr[i],еслиarr[i]<numпровестиswap(arr[i],arr[L+1])После этого известно состояние данных текущего индекса (должны бытьarr[i]=arr[L+1]), потому что он проходит от начала доi, покаL+1<=i. но еслиarr[i]>numпровестиswap(arr[i],arr[R-1])Тогда статус данных текущего элемента неясен, потому чтоR-1>=i,arr[R-1]Еще не проехал.

проблема с матричной печатью

Распечатайте матрицу квадратов по кругу

Дана матрица порядка 4 следующим образом:

Результат печати выглядит следующим образом (требуется дополнительная пространственная сложностьO(1)):

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Идеи: Этот тип проблемы должен открыть разум и выяснить общность проблемы на макроуровне, чтобы решить ее. Если ваше мышление ограничено тем, как 1 становится 2, как 4 становится 8, почему за 11 следует 10 и какова связь между ними, то вы в тупике.

Ищем общие черты с макроуровня, на самом деле процесс печати по кругу — это процесс непрерывной печати периферийных элементов по часовой стрелке до тех пор, пока вам дана точка в верхнем левом углу (например,(0,0)) и точку в правом нижнем углу (например,(3,3)), вы сможете распечатать1 2 3 4 8 12 16 15 14 13 9 5; опять вам(1,1)и(2,2), можно распечатать6 7 11 10. Этот процесс печати элементов на квадрате по двум точкам можно извлечь, и вся проблема решена.

Логика печати точки на квадрате матрицы следующая:

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#define FACTORIAL 4

void printSquare(int leftUp[], int rigthDown[],int matrix[][FACTORIAL]){
    int i = leftUp[0], j = leftUp[1];
    while (j < rigthDown[1]) {
        printf("%d ", matrix[i][j++]);
    }
    while (i < rigthDown[0]) {
        printf("%d ", matrix[i++][j]);
    }
    while (j > leftUp[1]) {
        printf("%d ", matrix[i][j--]);
    }
    while (i > leftUp[0]) {
        printf("%d ", matrix[i--][j]);
    }
}

void printMatrixCircled(int matrix[][FACTORIAL]){
    int leftUp[] = {0, 0}, rightDown[] = {FACTORIAL-1,FACTORIAL-1};
    while (leftUp[0] < rightDown[0] && leftUp[1] < rightDown[1]) {
        printSquare(leftUp, rightDown, matrix);
        ++leftUp[0];
        ++leftUp[1];
        --rightDown[0];
        --rightDown[1];
    }
}

int main(){
    int matrix[4][4] = {
            {1,  2,  3,  4},
            {5,  6,  7,  8},
            {9,  10, 11, 12},
            {13, 14, 15, 16}
    };
    printMatrixCircled(matrix);//1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
}

Вращающаяся квадратная матрица

Учитывая квадратную матрицу, отрегулируйте матрицу так, чтобы она выглядела после поворота на 90° по часовой стрелке, требуется дополнительная пространственная сложность.O(1).

Идея: Возьмем в качестве примера картинку выше, сначала выделим точки в четырех углах матрицы1,3,9,7, по часовой стрелке1прибыть3позиция(1->3),3->9,9->7,7->1, так что четыре точки были скорректированы для повернутой матрицы. Затем просто отрегулируйте2,6,8,4положение, метод регулировки такой же. Просто используйте тот же метод для настройки первых n-1 точек первой строки матрицы, первых n-3 точек второй строки матрицы..., тогда настройка матрицы n-го порядка будет легкой.

Это также общий закон наблюдения за изменением данных на макроуровне, чтобы найти общее решение, которое является инвариантным и адаптируемым (данная точка, определить квадрат с этой точкой как угол на матрице, и повернуть квадрат на 90 ° ), вся проблема не будет решена.

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#define FACTORIAL 4

void circleSquare(int leftUp[],int rightDown[],int matrix[][FACTORIAL]){
    int p1[] = {leftUp[0], leftUp[1]};
    int p2[] = {leftUp[0], rightDown[1]};
    int p3[] = {rightDown[0], rightDown[1]};
    int p4[] = {rightDown[0],leftUp[1]};
    while (p1[1] < rightDown[1]) {
        //swap
        int tmp = matrix[p4[0]][p4[1]];
        matrix[p4[0]][p4[1]] = matrix[p3[0]][p3[1]];
        matrix[p3[0]][p3[1]] = matrix[p2[0]][p2[1]];
        matrix[p2[0]][p2[1]] = matrix[p1[0]][p1[1]];
        matrix[p1[0]][p1[1]] = tmp;

        p1[1]++;
        p2[0]++;
        p3[1]--;
        p4[0]--;
    }
}

void circleMatrix(int matrix[][FACTORIAL]){
    int leftUp[] = {0, 0}, rightDown[] = {FACTORIAL - 1, FACTORIAL - 1};
    while (leftUp[0] < rightDown[0] && leftUp[1] < rightDown[1]) {
        circleSquare(leftUp, rightDown, matrix);
        leftUp[0]++;
        leftUp[1]++;
        --rightDown[0];
        --rightDown[1];
    }
}

void printMatrix(int matrix[][FACTORIAL]){
    for (int i = 0; i < FACTORIAL; ++i) {
        for (int j = 0; j < FACTORIAL; ++j) {
            printf("%2d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main(){
    int matrix[FACTORIAL][FACTORIAL] = {
            {1,  2,  3,  4},
            {5,  6,  7,  8},
            {9,  10, 11, 12},
            {13, 14, 15, 16}
    };
    printMatrix(matrix);
    circleMatrix(matrix);
    printMatrix(matrix);
}

зигзагообразная печатная матрица

Результат печати приведенной выше матрицы выглядит следующим образом (требует дополнительной космической сложностиO(1)):

1 2 7 13 8 3 4 9 14 15 10 5 6 11 16 17 12 18

Этот вопрос также должен найти общность с точки зрения макроса: учитывая две точки, можете ли вы напечатать точки на наклонной линии 45 °, образованной двумя точками в заданном направлении печати. Взяв приведенный выше рисунок в качестве примера,(2,0),(0,2)иturnUp=true, который должен распечатать13,8,3. Тогда вся проблема превращается в задачу о направлении двух точек.Вначале обе точки(0,0), то одна точка идет вниз, а другая вправо (например,1->7,1->2); когда точка, идущая вниз, является граничной точкой, идите направо (например,13->14), когда точка справа достигает границы, она идет вниз (например,6->12). Сделайте два шага за раз и напечатайте точки на линии, соединяющей две точки.

//
// Created by zaw on 2018/10/22.
//
#include <stdio.h>

const int rows = 3;
const int cols = 6;

void printLine(int leftDown[],int rightUp[], bool turnUp,int matrix[rows][cols]){
    int i,j;
    if (turnUp) {
        i = leftDown[0], j = leftDown[1];
        while (j <= rightUp[1]) {
            printf("%d ", matrix[i--][j++]);
        }
    } else {
        i = rightUp[0], j = rightUp[1];
        while (i <= leftDown[0]) {
            printf("%d ", matrix[i++][j--]);
        }
    }
}

void zigZagPrintMatrix(int matrix[rows][cols]){
    if (matrix==NULL)
        return;
    int leftDown[] = {0, 0}, rightUp[] = {0, 0};
    bool turnUp = true;
    while (leftDown[1] <= cols - 1) {
        printLine(leftDown, rightUp, turnUp, matrix);
        turnUp = !turnUp;
        if (leftDown[0] < rows - 1) {
            leftDown[0]++;
        } else {
            leftDown[1]++;
        }
        if (rightUp[1] < cols - 1) {
            ++rightUp[1];
        } else {
            ++rightUp[0];
        }
    }
}

int main(){
    int matrix[rows][cols] = {
            {1,  2,  3,  4,  5,  6},
            {7,  8,  9,  10, 11, 12},
            {13, 14, 15, 16, 17, 18}
    };
    zigZagPrintMatrix(matrix);//1 2 7 13 8 3 4 9 14 15 10 5 6 11 16 17 12 18
    return 0;
}

Найдите числа в матрице с отсортированными строками и столбцами

Как показано на рисунке:

Числа в любом столбце или строке упорядочены, реализуйте функцию, чтобы определить, существует ли определенное число в матрице. Требуемая временная сложностьO(M+N), дополнительная пространственная сложность равнаO(1).

Начинайте с точки в правом верхнем углу матрицы и сравнивайте ее с числом, если оно больше числа, значит столбец, в котором находится точка, не имеет номера, и перемещайте точку влево ; если число в этой точке меньше числа, то это означает, что это число не существует в строке, где находится точка, переместите точку вниз. пока не будет найдена точка, равная этому числу. В худшем случае число всего одно и оно находится в левом нижнем углу матрицы, тогда временная сложность равнаO(M-1+N-1)=O(M+N)

//
// Created by zaw on 2018/10/22.
//
#include <stdio.h>
const int rows = 4;
const int cols = 4;

bool findNumInSortedMatrix(int num,int matrix[rows][cols]){
    int i = 0, j = cols - 1;
    while (i <= rows - 1 && j <= cols - 1) {
        if (matrix[i][j] > num) {
            --j;
        } else if (matrix[i][j] < num) {
            ++i;
        } else {
            return true;
        }
    }
    return false;
}

int main(){
    int matrix[rows][cols] = {
            {1, 2, 3, 4},
            {2, 4, 5, 8},
            {3, 6, 7, 9},
            {4, 8, 9, 10}
    };
    if (findNumInSortedMatrix(7, matrix)) {
        printf("find!");
    } else {
        printf("not exist!");
    }
    return 0;
}

проблема острова

В матрице есть только два значения 0 и 1. Каждая позиция может быть связана со своей верхней, нижней, левой и правой позициями.Если есть часть 1, соединенная вместе, эта часть называется островом.Как много островов?

Например матрица:

1	0	1
0	1	0
1	1	1

Есть 3 острова.

Анализ: мы можем обойти каждую позицию в матрице, и если мы встретим 1, мы заразим часть 1, связанную с ней, в 2, и автоматически увеличим количество островов.

public class IslandNum {
	
	public static int getIslandNums(int matrix[][]){
		int res = 0 ;
		for(int i = 0 ; i < matrix.length ; i++){
			for(int j = 0 ; j < matrix[i].length ; j++){
				if(matrix[i][j] == 1){
					res++;
					infect(matrix , i , j);
				}
			}
		}
		return res;
	}

	public static void infect(int matrix[][], int i ,int j){
		if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[i].length || matrix[i][j] != 1){
			return;
		}
		matrix[i][j] = 2;
		infect(matrix , i-1 , j);
		infect(matrix , i+1 , j);
		infect(matrix , i , j-1);
		infect(matrix , i , j+1);
	}

	public static void main(String[] args){
		int matrix[][] = {
			{1,0,0,1,0,1},
			{0,1,1,0,0,0},
			{1,0,0,0,1,1},
			{1,1,1,1,1,1}
		};
		System.out.println(getIslandNums(matrix));
	}
}

Классические структуры и алгоритмы

нить

Алгоритм КМП

Алгоритм KMP вызван проблемой: для строкиstr(длина N) и еще одна строкаmatch(длина М), еслиmatchдаstrподстрока , вернуть ее вstrНижний индекс первой буквы первого вхождения, еслиmatchнетstrПодстрока возвращает-1.

Самый простой способ - положитьstrпройтись с начала и сравнить сmatchПри последовательном сравнении, если встречается несовпадающая буква, обход прекращается и начинается обход сstrВторой символ обхода начинается сmatchСравнивайте последовательно, пока каждый символ не будет пройден с одним и тем жеmatchсовпадение, иначе возврат-1. Легко понять, что временная сложность этого подхода равнаO(N*M).

Алгоритм KMP дает контроль временной сложности решения этой задачи вO(N)решение.

Во-первых, алгоритм должен соответствоватьmatchСоздать сmatchВспомогательные массивы одинаковой длиныhelp[match.length], элемент массива представляетmatchподстрока перед индексомМаксимальная совпадающая длина подстрок префикса и суффикса.префиксная подстрокаПредставляет любое количество последовательных символов в строке, начиная с первого символа строки и не включая конечный символ строки,суффиксная подстрокаЭто означает любое количество последовательных символов в строке, которые заканчиваются концом строки, за исключением первого символа строки. НапримерabcdПодстрока префикса может бытьa,ab,abc, но не может бытьabcd,иabcdСтрока суффикса может бытьd,cd,bcd, но не может бытьabcd. Давайте поговорим об этом сноваhelpмассив, дляchar match[]="abc1abc2"Скажем, естьhelp[7]=3,так какmatch[7]='2',следовательноmatchиндекс в7предыдущая подстрокаabc1abcКогда подстрока префикса и подстрока суффикса совпадают, максимальная длина подстроки префикса равна 3 (то есть и строка префикса, и строка суффикса занимаютabc);match="aaaab",имеютhelp[4]=3(Максимальная совпадающая длина подстроки префикса и подстроки суффикса, когда обеaaaпри получении) соответствующийhelp[3]=2,help[2]=1.

Предположим, когда подстрока должна быть найденаmatchизhelpПосле того, как массив найден (для строкиhelpМетод нахождения массива вводится после введенияKMPАлгоритм будет подробно описан позже). это может быть сделаноKMPАлгоритм решает эту проблему.KMPЛогика (вывод) алгоритма такова, что дляstrизi~(i+k)часть(i,i+kобаstrюридический индекс) иmatchиз0~kчасть(kзаmatchюридические индексы), если таковые имеютсяstr[i]=match[0],str[i+1]=match[1]...str[i+k-1]=match[k-1],ноstr[i+k]!=[k],ТакstrНижний индекс не обязательно должен быть отi+kстатьi+1Повторное сравнение, просто подстрокаstr[0]~str[i+k-1]Символ после наибольшей совпадающей подстроки префиксаcnвоссоединиться сstr[i+k]Сравните в обратном порядке по очереди и повторите эту операцию, если вы встретите несопоставленные символы позже:

При обнаружении несовпадающих символов обычной практикой являетсяstrиндекс обходаsIndexперейти кi+1местоположение иmatchиндекс обходаmIndexперейти к0Затем сравните по очереди, этот подход не использует информацию сравнения предыдущего раунда (отсутствует оптимизация для сравнения следующего раунда). иKMPАлгоритм не такой, при встрече с непарными символамиstr[i+k]иmatch[k]час,strуказатель обходаsIndex=i+kне двигайся,matchПроведите вправо и проведите по указателюmIndexхит подстрокиmatch[0]~match[k-1]Следующий нижний индекс наибольшей совпадающей подстроки префиксаnпозиция. потомsIndexотi+kНачинать,mIndexотnНачните, сравните по очереди в обратном порядке и повторите этот процесс, если вы снова встретите несовпадающее число.

Соответствующий код выглядит следующим образом:

void length(char* str){
  if(str==NULL)
    return -1;
  int len=0;
  while(*(str++)!='\0'){
    len++;
  }
  return len;
}

int getIndexOf(char* str,char* m){
    int slen = length(str) , mlen = length(m);
    if(mlen > slen)
        return -1;
    int help[mlen];
    getHelpArr(str,help);
    int i=0,j=0;	//sIndex,mIndex
    while(i < slen && j < mlen){
        if(str[i] == m[j]){
            i++;
            j++;
        }else if(help[j] != -1){
            j = help[j];    //mIndex -> cn's index
        }else{	//the first char is not match,move the sIndex
            i++;    
        }
    }
    return j == mlen ? i - mlen : -1;
}

Его можно найтиKMPв алгоритмеstrУказатель обхода не отслеживает это действие (только перемещается назад), когда совпадение выполнено.sIndexдвижется меньше, чемN,в противном случаеsIndexПереход к концу строки также завершает цикл, поэтомуwhileВременная сложность соответствующего процесса сопоставления равнаO(N)(if(help[j] != -1){ j = help[j] }будет выполняться только постоянное количество раз, поэтому его можно игнорировать).

Следующее нужно только решить, как решить строкуhelpмассив, проблема решена.helpМассив должен быть решен спереди назад, напрямуюhelp[n]Трудно получить ключ. когда строкаmatchдлинаmlen=1время, оговариваетсяhelp[0]=-1. когдаmlen=2, Удалитьmatch[1]только после этогоmatch[0], максимальная длина совпадающей подстроки равна 0 (поскольку префиксная подстрока не может содержать конечный символ строки, а суффиксная подстрока не может содержать первый символ строки), т. е.help[1]=0. когдаmlen>2час,help[n](n>=2) можно рассчитать:

Как показано выше, если мы знаемhelp[n-1],Такhelp[n]Возможны два случая решения: еслиmatch[cn]=match[n-1], то областью a и областью b (a, b — подстрокиmatch[0~n-2]Максимальная совпадающая подстрока префикса и строка суффикса совпадают, это можно узнатьhelp[n]=help[n-1]+1;еслиmatch[cn]!=match[n-1], затем найдите следующую большую строку в области a, которая может соответствовать подстроке суффикса в области b, то есть самую большую совпадающую строку префикса в области a.c区域,будетmatch[n-1]и последнее положение области c (cn') при сравнении символов, если равно, тоhelp[n]равна длине области c + 1, а длина области c равнаhelp[cn](helpмассив определен как таковой); если он не равен, то он будетcnударилcn'Позиция продолжается иmatch[n-1]сравнивать до тех пор, покаcnбыть пораженным0пока (т.е.help[cn]=-1пока), то в это времяhelp[n]=0.

Соответствующий код выглядит следующим образом:

int* getHelpArr(char* s,int help[]){
    if(s==NULL)
        return NULL;
    int slen = length(s);
    help[0]=-1;
    help[1]=0;
    int index = 2;//help数组从第三个元素开始的元素值需要依次推算
    int cn = 0;		//推算help[2]时，help[1]=0，即s[1]之前的字符组成的串中不存在最大匹配前后子串，那么cn作为最大匹配前缀子串的后一个下标自然就是0了
    while(index < slen){
        if(s[index-1] == s[cn]){	//if match[n-1] == match[cn]
            help[index] = help[index-1] + 1;
            index++;
            cn++;
        }else if(help[cn] == -1){	//cn reach 0
            help[index]=0;
            index++;
            cn++;
        }else{
            cn = help[cn];	//set cn to cn' and continue calculate help[index]
        }
    }
    return help;
}

Тогда это решениеhelpКак рассчитать временную сложность процесса массива? тщательное наблюдение сдержанностьwhileЦикл включает толькоindexиcnИзменения этих двух переменных:

	сначала, если ветвь	вторая если ветвь	Третья ветвь if
index	увеличивать	увеличивать	постоянный
index-cn	постоянный	постоянный	увеличивать

Его можно найтиwhileЦикл выполняется один раз вместоindexувеличениеindex-cnувеличить, иindex < slen,index - cn < slen,Сейчасindexавтоматическое приращениеM(matchдлина строки) раз ,index-cnувеличить не болееMраз, такwhileвыполнить не болееM+Mраз, то есть временная сложностьO(2M)=O(M).

Подводя итог, используйтеKMPВременная сложность решения этой задачиO(M)(решатьmatchизhelpвременная сложность массива) +O(N)(временная сложность сопоставления) =O(N)(так какN > M).

Применение алгоритма KMP

Определить, является ли бинарное дерево поддеревом другого бинарного дерева (то есть структура и состояние данных дерева аналогичны поддереву другого бинарного дерева).

Идея: если сериализованная строка этого дерева является подстрокой сериализованной строки другого дерева, то первая должна быть поддеревом второго.

префиксное дерево (словарное дерево)

Введение в деревья префиксов

Префиксное дерево является эффективным контейнером для хранения строк.Операции, основанные на этой структуре:

insertвставить строку в контейнер
searchЕсли строка существует в контейнере, возвращает количество раз, когда строка входила в контейнер, в противном случае возвращает 0
deleteУменьшить количество раз, когда строка вводится в контейнер на 1
prefixNumberВозвращает количество вхождений строки с префиксом строки во всех операциях вставки.

Идея дизайна: ключевой реализацией этой структуры является хранилище. Деревья префиксов используют символы в качестве единиц хранения и хранят их в ветвях между узлами, а не в узлах, например, при вставке строк.abcПосле этого префиксное дерево выглядит следующим образом:

Каждый раз, когда вы вставляете строку, вы должны начинать с головного узла и проходить символы в строке, чтобы «проложить дорогу», по очереди, как показано на рисунке выше.abc3 способа. Для каждого узла можно заложитьa~z26 различных путей, если после прибытия в определенный узел путь, который ему нужно проложить (в зависимости от того, какой символ он проходит) проложен предыдущим процессом вставки строки, то вы можете перейти непосредственно к этому пути. следующий узел, иначе придется прокладывать дорогу перед переходом к следующему узлу. Если вы снова вставите строкуabdeиbcdПрефиксное дерево будет выглядеть так:

по префиксному деревуsearchиprefixNumberДве операции, нам также нужно записать, сколько раз проходит каждый узел после каждого мощения (across), и сколько раз каждая операция вставки имеет каждый узел в качестве конечного узла (end).

Реализация префиксного дерева

Пример реализации префиксного дерева:

public class TrieTree {

  public static class TrieNode {
    public int across;
    public int end;
    public TrieNode[] paths;

    public TrieNode() {
      super();
      across = 0;
      end = 0;
      paths = new TrieNode[26];
    }
  }

  private TrieNode root;

  public TrieTree() {
    super();
    root = new TrieNode();
  }

  //向树中插入一个字符串
  public void insert(String str) {
    if (str == null || str.length() == 0) {
      return;
    }
    char chs[] = str.toCharArray();
    TrieNode cur = root;
    for (char ch : chs) {
      int index = ch - 'a';
      if (cur.paths[index] == null) {
        cur.paths[index] = new TrieNode();
      }
      cur = cur.paths[index];
      cur.across++;
    }
    cur.end++;
  }

  //查询某个字符串插入的次数
  public int search(String str) {
    if (str == null || str.length() == 0) {
      return 0;
    }
    char chs[] = str.toCharArray();
    TrieNode cur = root;
    for (char ch : chs) {
      int index = ch - 'a';
      if (cur.paths[index] == null) {
        return 0;
      }else{
        cur = cur.paths[index];
      }
    }
    return cur.end;
  }

  //删除一次插入过的某个字符串
  public void delete(String str) {
    if (search(str) > 0) {
      char chs[] = str.toCharArray();
      TrieNode cur = root;
      for (char ch : chs) {
        int index = ch - 'a';
        if (--cur.paths[index].across == 0) {
          cur.paths[index] = null;
          return;
        }
        cur = cur.paths[index];
      }
      cur.end--;
    }
  }

	//查询所有插入的字符串中，以prefix为前缀的有多少个
  public int prefixNumber(String prefix) {
    if (prefix == null || prefix.length() == 0) {
      return 0;
    }
    char chs[] = prefix.toCharArray();
    TrieNode cur = root;
    for (char ch : chs) {
      int index = ch - 'a';
      if (cur.paths[index] == null) {
        return 0;
      }else{
        cur = cur.paths[index];
      }
    }
    return cur.across;
  }

  public static void main(String[] args) {
    TrieTree tree = new TrieTree();
    tree.insert("abc");
    tree.insert("abde");
    tree.insert("bcd");
    System.out.println(tree.search("abc"));	//1
    System.out.println(tree.prefixNumber("ab"));	//2
  }
}

Проблемы, связанные с деревьями префиксов

Один массив arr1 типа string, другой массив arr2 типа string:

Какие символы есть в arr2, которые появляются в arr1? пожалуйста распечатайте
Какие символы в arr2 появляются в качестве префиксов к строке в arr1? пожалуйста распечатайте
Какие символы в arr2 появляются в качестве префиксов к строке в arr1? Пожалуйста, выведите префикс с наибольшим количеством вхождений в arr2.

множество

Пузырьковая сортировка

Суть пузырьковой сортировки заключается в обходе последовательности с самого начала. Возьмем в качестве примера порядок возрастания: сравните первый элемент со вторым элементом, если первый больше второго, поменяйте местами два элемента, а затем сравните второй элемент с третьим элементом, если первый больше второго. последний, затем поменять местами две позиции и так далее, пока предпоследний элемент не будет сравниваться с последним элементом, если первый больше второго, две позиции меняются местами. Такой раунд сравнения переместит самый большой элемент в последовательности в конец последовательности, чтобы упорядочить позицию наибольшего числа, а затем просто повторит описанную выше операцию для оставшихся (n-1) элементов.

void swap(int *a, int *b){
  int temp = *a;
  *a = *b;
  *b = temp;
}

void bubbleSort(int arr[], int length) {
  if(arr==NULL || length<=1){
    return;
  }
  for (int i = length-1; i > 0; i--) {	//只需比较(length-1)轮
    for (int j = 0; j < i; ++j) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }
}

Временная сложность этого алгоритмаn+(n-1)+...+1, которая, очевидно, является арифметической последовательностью, сумма которой вычисляется как (первый элемент + последний элемент) * количество элементов / 2 равно(n+1)n/2, временная сложностьO(n^2)

сортировка выбором

Возьмем в качестве примера сортировку по возрастанию: найдите индекс наименьшего числаminIndex, поменяйте его местами с первым числом и повторите операцию для подпоследовательности (1-n), пока подпоследовательность не будет содержать только один элемент. (То есть выбрать наименьшее число и поставить его на первую позицию, число расставляется, а затем выбрать наименьшее число для остальных чисел и поставить на вторую позицию и так далее)

void selectionSort(int arr[], int length) {
  for (int i = 0; i < length-1; ++i) {    //要进行n-1次选择，选出n-1个数分别放在前n-1个位置上
    if(arr==NULL || length<=1){
      return;
    }
    int minIndex = i;	//记录较小数的下标
    for (int j = i+1; j < length; ++j) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    if (minIndex != i) {
      swap(&arr[minIndex],&arr[i]);
    }
  }
}

Точно так же нетрудно вычислить временную сложность (большой o) этого алгоритма какO(n^2)(n-1+n-2+n-3+…+1)

Сортировка вставками

Процесс сортировки вставками может напоминать игру в покер, когда карту раскрывают и помещают в правильную позицию заказанной карты в руке. Например, у меня в руке карты 7, 8, 9, J, Q, K. В это время открывается 10. Мне нужно сравнить его с K, Q, J, 9, 8 и 7 по очереди. . 9 оказывается больше 9, поэтому оно вставляется после 9. Для неупорядоченной последовательности ее можно рассматривать как стопку карт, которые нужно открыть. Сначала откройте первый элемент. Поскольку перед открытием в руке нет карт, на этот раз нет необходимости сравнивать карты. вышеуказанная вставка требуется каждый раз, когда карты открываются.Во время карточного процесса, когда карта открывается, последовательность удерживания карт в руке соответствует упорядоченной форме последовательности.

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void insertionSort(int arr[], int length){
    if(arr==NULL || length<=1){
        return;
    }
    for (int i = 1; i < length; ++i) {		//第一张牌无需插入，直接入手，后续揭牌需比较然后插入，因此从第二个元素开始遍历（插牌）
      	//将新揭的牌与手上的逐次比较，若小于则交换，否则停止，比较完了还没遇到更小的也停止
        for (int j = i - 1; j >= 0 || arr[j] <= arr[j + 1]; j--) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

Как рассчитать большой о сортировки вставками? Можно обнаружить, что если последовательность упорядочена, то большой o алгоритма равенO(n), потому что последовательность проходится только один раз (наилучший случай на данный момент); если последовательность отсортирована в порядке убывания, то большой o алгоритма равенO(n^2)(Сравните свопы перед каждой вставкой в сумме: 1+2+…+n-1) (наихудший случай). **В общих сценариях приложений эффективность алгоритма рассматривается в соответствии с наихудшим случаем алгоритма, потому что создаваемое вами приложение должно выдерживать наихудший случай. **То есть большой о алгоритмаO(n^2)

Сортировка слиянием

Основная идея сортировки слиянием состоит в том, чтобы сначала упорядочить левую половину последовательности, затем правую половину последовательности и, наконец, сравнить две подпоследовательности (левую и правую половины) с самого начала и заполнить вспомогательную последовательность меньшее число. .

в последовательности{2,1,4,3}Например, процесс сортировки слиянием выглядит примерно так:

Пример кода алгоритма:

void merge(int arr[],int helpArr[], int startIndex, int midIndex,int endIndex) {
    int L = startIndex, R = midIndex + 1, i = startIndex;
    while (L <= midIndex && R <= endIndex) { //只要没有指针没越界就逐次比较
        helpArr[i++] = arr[L] < arr[R] ? arr[L++] : arr[R++];
    }
    while (L != midIndex + 1) {
        helpArr[i++] = arr[L++];
    }
    while (R != endIndex + 1) {
        helpArr[i++] = arr[R++];
    }
    for (i = startIndex; i <= endIndex; i++) {
        arr[i] = helpArr[i];
    }
}

void mergeSort(int arr[],int helpArr[], int startIndex, int endIndex) {
    int midIndex;
    if (startIndex < endIndex) {  //当子序列只含一个元素时，不再进行此子过程
      	//(endIndex+startIndex)/2可能会导致int溢出，下面求中位数的做法更安全
        midIndex = startIndex + ((endIndex - startIndex) >> 1);
        mergeSort(arr, helpArr, startIndex, midIndex);        //对左半部分排序
        mergeSort(arr, helpArr, midIndex + 1, endIndex);      //对右半部分排序
        merge(arr, helpArr, startIndex, midIndex, endIndex);  //使整体有序
    }
}

int main(){
    int arr[] = {9, 1, 3, 4, 7, 6, 5};
    travels(arr, 7);//遍历打印
    int helpArr[7];
    mergeSort(arr, helpArr, 0, 7);
    travels(arr, 7);

    return 0;
}

Ядром этого алгоритма является24、25、26эти три строки. первое26Строка не должна быть сложной для понимания, просто используйте два указателяL、Rплюс вспомогательный массив, чтобы упорядочить две последовательностиВключитьВспомогательный массив. но почему24、25После выполнения строки левая и правая половины массива сортируются отдельно? Это снова связано с основной идеей сортировки слиянием: сначала сделать левую и правую половины последовательности, а затем объединить, чтобы получить весь порядок. следовательно24、25Это рекурсивное выполнение сортировки слиянием левой и правой половин до тех пор, пока рекурсия не завершится, когда левая и правая половины станут одним элементом в определенной рекурсии. Когда последовательность содержит только два элемента, вызовитеmergeSortнайду24、25строка является недопустимой операцией, выполните ее напрямуюmerge. Как показано на рисунке выше, после рекурсивного завершения двух строк левая и правая половины станут упорядоченными.

Когда рекурсивный процесс сложный (не такой простой, как рекурсивные факториалы), мы можем составить список коротких выборок для анализа.

Для такого сложного рекурсивного поведения не думайте о том, чтобы отследить весь процесс рекурсии, просто проанализируйте, что делать на первом шаге (например, первый шаг в этом примере —mergeSortКак показывает функция: сортируй левую половину, сортируй правую половину и, наконец, объединяй, тебе все равно, как ты это отсортируешь, не будь 24, 25 строк.mergeSortвведен) и условие завершения рекурсии (например, ``startIndex>=endIndex` в этом примере, т. е. когда сортируемая последовательность имеет только один элемент).

Временная сложность сортировки слияниемO(nlogn), дополнительная пространственная сложность равнаO(n).

в соответствии сОсновная формула(Эта статьяСоветыупоминается в разделе) в наличииT(n)=2T(n/2)+O(n), смысл первых 2 в том, что подпроцесс (слияние и сортировка подпоследовательности) нужно выполнить дважды, вторые 2 означают, что размер выборки подпроцесса составляет половину (потому что он делится на левая и правая половинки) и, наконец,O(n)Указывает, что операция слияния, выполняемая после того, как левый и правый порядокO(n+n)=O(n)(Сумма количества перемещений указателей L и R равна n, а вспомогательный массив перезаписывает исходный массив до n), что согласуется сT(n)=aT(n/b)+O(n^d), временная сложность алгоритма рассчитывается какO(nlogn)

проблема с маленькой суммой

В массиве числа слева от каждого числа, которые меньше текущего числа, складываются, что называется малой суммой массива. Найдите малую сумму массива. Например:

对于数组[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16

Простой способ — пройтись по массиву один раз, сравнить текущее пройденное число с предыдущим числом и записать число меньше числа. Легко понять, что его временная сложность равнаO(n^2)(0+1+2+...+n-1).

Более оптимальным подходом является использование сортировки слиянием.Включить логику:

Соответствующий код:

int merge(int arr[],int helpArr[], int startIndex, int midIndex,int endIndex) {
    int L = startIndex, R = midIndex + 1, i = startIndex;
    int res=0;
    while (L <= midIndex && R <= endIndex ) { //只要没有指针没越界就逐次比较
        res += arr[L] < arr[R] ? arr[L] * (endIndex - R + 1) : 0;
        helpArr[i++] = arr[L] < arr[R] ? arr[L++] : arr[R++];
    }
    while (L != midIndex + 1) {
        helpArr[i++] = arr[L++];
    }
    while (R != endIndex + 1) {
        helpArr[i++] = arr[R++];
    }
    for (i = startIndex; i <= endIndex; i++) {
        arr[i] = helpArr[i];
    }
    return res;
}

int mergeSort(int arr[],int helpArr[], int startIndex, int endIndex) {
    int midIndex;
    if (startIndex < endIndex) {  //当子序列只含一个元素时，不再进行此子过程
        midIndex = startIndex + ((endIndex - startIndex) >> 1);
        return mergeSort(arr, helpArr, startIndex, midIndex) +        //对左半部分排序
               mergeSort(arr, helpArr, midIndex + 1, endIndex) +     //对右半部分排序
               merge(arr, helpArr, startIndex, midIndex, endIndex);  //使整体有序
    }
    return 0;	//一个元素时不存在小和
}

int main(){
    int arr[] = {1,3,4,2,5};
    int helpArr[5];
    printf("small_sum:%d\n",mergeSort(arr, helpArr, 0, 4)) ;
    return 0;
}

Алгоритм немного изменен на основе сортировки слиянием, а именноmergeдобавлены переменные вresзаписывать каждый разВключитьОперация должна накопить небольшую сумму,mergeSortНебольшие суммы, которые должны быть накоплены, будут включаться каждый раз. Сложность этого подхода такая же, как у сортировки слиянием, которая лучше обхода. Можно понять, что многие сравнения повторяются в процессе нахождения малой суммы каждого числа по очереди, но при использовании сортировки слиянием для нахождения малой суммы используются преимущества отдельных характеристик упорядочения объединенных двух последовательностей, чтобы исключить ненужные сравнения, например134并入25час,2>1прямой запуск2Цифры позади>1, так прямо1*(endIndex-indexOf(2)+1)Вот и все. Это не показывает эффект оптимизации, когда размер выборки мал.Представьте, если размер выборки2^32, то найти малую сумму по первомуO(n^2)Видно, что временная сложностьO(21亿的平方), а сортировка слиянием, чтобы найти небольшую сумму, требует толькоO(21亿*32), достаточно, чтобы увидетьO(n^2)иO(nlogn)плюсы и минусы.

Задача обратной пары

В массиве, если число слева больше числа справа, эти два числа составляют пару в обратном порядке, выведите все пары в обратном порядке.

Идея этой проблемы также может быть решена с помощью сортировки слиянием, которая записывается во время операции слияния.arr[L]>arr[R]ситуация может быть.

быстрая сортировка

Классическая быстрая очередь

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

Первое, что нам нужно рассмотреть, это то, как для заданного числа переместить последовательность, меньшую числа, влево, а большее число вправо.

Идея: использовать вспомогательный указательsmall, представляет собой правую границу меньшего числа (изначально указывает на предыдущую позицию первого элемента), и каждый раз, когда последовательность обхода встречает число меньше этого числа, она будет объединяться с нимarr[small+1]поменять местами и сдвинуть вправоsmall, и, наконец, это число сarr[small+1]Обмен – это цель. Соответствующий алгоритм выглядит следующим образом:

void partition(int arr[], int startIndex, int endIndex){
    int small = startIndex - 1;
    for (int i = startIndex; i < endIndex; ++i) {
        if(arr[i] < arr[endIndex]) {
            if (small + 1 != i) {
                swap(arr[++small], arr[i]);
            } else {
                //如果small、i相邻则不用交换
                small++;
            }
        }
    }
    swap(arr[++small], arr[endIndex]);
}
int main(){
    int arr[] = {1, 2, 3, 4, 6, 7, 8, 5};
    travles(arr, 8);//1 2 3 4 6 7 8 5
    partition(arr, 0, 7);
    travles(arr, 8);//1 2 3 4 5 7 8 6
    return 0;
}

Тогда есть рекурсивная логика быстрой сортировки: да1 2 3 4 6 7 8 5последовательностьpartitionПосле этого удалите предыдущий параметр сравнения5, для остальных подпоследовательностей1234и786Продолжатьpartition, пока подпоследовательность не станет одним элементом:

int partition(int arr[], int startIndex, int endIndex){
    int small = startIndex - 1;
    for (int i = startIndex; i < endIndex; ++i) {
        if(arr[i] < arr[endIndex]) {
            if (small + 1 != i) {
                swap(arr[++small], arr[i]);
            } else {
                //如果small、i相邻则不用交换
                small++;
            }
        }
    }
    swap(arr[++small], arr[endIndex]);
    return small;
}

void quickSort(int arr[], int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return;
    }
    int index = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, index - 1);
    quickSort(arr, index + 1, endIndex);
}
int main(){
    int arr[] = {1, 5, 6, 2, 7, 3, 8, 0};
    travles(arr, 8);	//1 5 6 2 7 3 8 0
    quickSort(arr, 0,7);
    travles(arr, 8);	//0 1 2 3 5 6 7 8
    return 0;
}

Временная сложность классической сортировки связана с состоянием данных, есликаждый разpartitionКогда хвостовой элемент самый большой или самый маленький в последовательности, то при удалении элемента последовательность не разбивается на левую и правую подпоследовательности с таким же размером выборки, как у нас, а упорядочивается только один элемент (то есть удаляемый элемент), так что Тогда временная сложностьO(n-1+n-2+……+1)=O(n^2); но если каждый разpartitionКогда , последовательность делится на две подпоследовательности, левую и правую подпоследовательности с почти одинаковым размером выборки, тогда временная сложность равнаO(nlogn)(решить по формуле Мастера).

Улучшения классической быстрой сортировки, вызванные проблемой голландского флага.

можно найти здесьpartitionпроцесс с голландским флагом в выпускеpartitionочень похоже, может последнийpartitionКак насчет реализации классической быстрой сортировки? Давайте попробуем:

int* partition(int arr[], int startIndex, int endIndex){ ;
    int small = startIndex - 1, great = endIndex + 1, i = startIndex;
    while (i <= great - 1) {
        if (arr[i] < arr[endIndex]) {
            swap(arr[++small], arr[i++]);
        } else if (arr[i] > arr[endIndex]){
            swap(arr[--great], arr[i]);
        } else {
            i++;
        }
    }
    int range[] = {small, great};
    return range;
}

void quickSort(int arr[], int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return;
    }
    int* range = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, range[0]);
    quickSort(arr, range[1], endIndex);
}

int main(){
    int arr[] = {1, 5, 6, 2, 7, 3, 8, 0};
    travles(arr, 8);	//1 5 6 2 7 3 8 0
    quickSort(arr, 0,7);
    travles(arr, 8);	//0 1 2 3 5 6 7 8
    return 0;
}

Сравнивая классическую сортировку и улучшенную классическую сортировку с использованием проблемы голландского флага, нетрудно обнаружить, что последняя послеpartitionможет удалить более одного элемента (равногоarr[endIndex]области), а первый каждый разpartitionУдалить можно только один элемент, и удаление здесь эквивалентно упорядочиванию (сортировке) положения соответствующего элемента. Поэтому последняя лучше классической сортировки, но оптимизация невелика, это только оптимизация за константное время, а реальная эффективность зависит от состояния данных (последний случайO(nlogn), худший случайO(n^2)).

Случайная быстрая сортировка — O(nlogn)

Как упоминалось выше, недостатком Quick Queue является зависимость от данных, поэтому можем ли мы как-то устранить эту зависимость и сделать ее реальной?O(nlogn)Шерстяная ткань?

Фактически, для того, чтобы операция в алгоритме не зависела от ситуации с данными (например, каждый раз в быстрой сортировкеpartitionВозьмите хвостовой элемент в качестве сравнения, которое не избегает условия данных выборки, если хвостовой элемент имеет максимальное или минимальное значение, это становится наихудшим случаем) Часто есть два подхода:

1. Используйте случайные числа

2. Перемешайте образец хэша данных

Случайная быстрая сортировка принимает первое решение, указанное выше, в каждом раунде.partitionСлучайным образом выбирает число в последовательности в качестве числа для сравнения:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//产生[startIndex,endIndex]之间的随机整数
int randomInRange(int startIndex,int endIndex){
    return rand() % (endIndex - startIndex + 1) + startIndex;
}

int* partition(int arr[], int startIndex, int endIndex){ ;
    int small = startIndex - 1, great = endIndex + 1, i = startIndex;
    int randomNum = arr[randomInRange(startIndex, endIndex)];
    while (i <= great - 1) {
        if (arr[i] < randomNum) {
            swap(arr[++small], arr[i++]);
        } else if (arr[i] > randomNum){
            swap(arr[--great], arr[i]);
        } else {
            i++;
        }
    }
    int range[] = {small, great};
    return range;
}

void quickSort(int arr[], int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return;
    }
    int* range = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, range[0]);
    quickSort(arr, range[1], endIndex);
}

void travles(int dataArr[], int length){
    for (int i = 0; i < length; ++i) {
        printf("%d ", dataArr[i]);
    }
    printf("\n");
}

int main(){
    srand(time(NULL));//此后调用rand()时将以调用时的时间为随机数种子
    int arr[] = {9,7,1,3,2,6,8,4,5};
    travles(arr, 9);
    quickSort(arr, 0,8);
    travles(arr, 9);
    return 0;
}

Глядя на код сравнения, мы видим, что случайная быстрая сортировка есть только вpartitionПри случайном выборе числа в нижнем индексе в качестве объекта сравнения устраняется проблема, заключающаяся в том, что хвостовой элемент каждого раунда выбора будет зависеть от условия данных.

Так какова временная сложность случайной быстрой сортировки?

Математически продемонстрировано, так как каждый раундpartitionЧисла, выбранные для сравнения, являются случайными, то есть каждое число в последовательности имеет1/nВыбирается вероятность , затем временная сложность алгоритма является вероятностным событием, а математическая демонстрация алгоритмаМатематическое ожиданиезаO(nlogn). Хотя это математическое ожидание, в практической инженерии временная сложность случайной быстрой сортировки часто рассматривается какO(nlog).

сортировка кучей

что такое куча

Структура кучи представляет собойполное бинарное деревоМетод хранения, который сопоставляется с массивом:

Большие корневые кучи и маленькие корневые кучи

Когда максимальным значением каждого поддерева кучи (включая само дерево) является его узел, она называется большой корневой кучей; наоборот, когда минимальное значение каждого поддерева кучи является ее корневым узлом, она называется небольшая куча корней. Среди них большая корневая куча широко используется и является очень важной структурой данных.

heapInsert и heapify

Две самые важные операции большой корневой кучи:heapInsertиheapify, первая заключается в том, что когда элемент добавляется в большую корневую кучу, он должен сравниваться с его родительским узлом снизу вверх, и если он больше, чем родительский узел, он будет заменен; второй заключается в том, что когда значение узла в куче меняется, оно должно продолжать опускаться вместе с ним.Сравнивается максимальное значение в дочерних узлах, и если оно меньше, чем обмен. Вот соответствующий код:

//index之前的序列符合大根堆排序，将index位置的元素加入堆结构，但不能破坏大根堆的特性
void heapInsert(int arr[],int index){
    while (arr[index] > arr[(index - 1) / 2]) { //当该结点大于父结点时
        swap(arr[index], arr[(index - 1) / 2]);
        index = (index - 1) / 2;    //继续向上比较
    }
}

//数组中下标从0到heapSize符合大根堆排序
//index位置的值发生了变化，重新调整堆结构为大根堆
//heapSize指的是数组中符合大根堆排序的范围而不是数组长度,最大为数组长度，最小为0 
void heapify(int arr[], int heapSize, int index){
    int leftChild = index * 2 + 1;
    while (leftChild < heapSize) {  //当该结点有左孩子时
        int greatOne = leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild] ?
                leftChild + 1 : leftChild;  //只有当右孩子存在且大于左孩子时，最大值是右孩子，否则是左孩子
        greatOne = arr[greatOne] > arr[index] ? greatOne : index;//将父结点与最大孩子结点比较，确定最大值
        if (greatOne == index) {
            //如果最大值是本身，则不用继续向下比较
            break;
        }
        swap(arr[index], arr[greatOne]);

        //next turn下一轮
        index = greatOne;
        leftChild = index * 2 + 1;
    }
}

Соберите большую кучу корней

void buildBigRootHeap(int arr[],int length){
    if (arr == NULL || length <= 1) {
        return;
    }
    for (int i = 0; i < length; ++i) {
        heapInsert(arr, i);
    }
}

Сортировка с помощью heapify

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

Соответствующий код реализован следующим образом:

void heapSort(int arr[],int length){
    if (arr == NULL || length <= 1) {
        return;
    }
  	//先建立大根堆
    for (int i = 0; i < length; ++i) {
        heapInsert(arr, i);
    }
 	  //循环弹出堆顶元素并heapify
    int heapSize = length;
    swap(arr[0], arr[--heapSize]);//相当于弹出堆顶元素
    while (heapSize > 0) {
        heapify(arr, heapSize, 0);
        swap(arr[0], arr[--heapSize]);
    }
}

int main(){
    int arr[] = {9,7,1,3,6,8,4,2,5};
    heapSort(arr, 9);
    travles(arr, 9);
    return 0;
}

Преимущество сортировки кучей заключается в том, что независимо от того, помещается ли элемент в кучуheapInsertИли после укладки одного элементаheapifyНи один из них не выполняет итерацию по всей выборке (O(n)уровневые операции), но обход на уровне дерева (O(logn)работа уровня).

В этом случае в процессе сортировки кучи временная сложность построения кучи равнаO(nlogn), цикл, чтобы извлечь верхний элемент кучи иheapifyВременная сложностьO(nlogn), временная сложность всей сортировки кучи равнаO(nlogn), дополнительная пространственная сложность равнаO(1)

Структура очереди приоритетов (например, в JavaPriorityQueue) — структура кучи.

Устойчивость алгоритмов сортировки

Стабильность алгоритма сортировки относится к тому, сохраняется ли относительный порядок элементов с одинаковым значением в последовательности до и после сортировки. как последовательность271532, в процессе сортировки, если первое вхождение2во втором появлении2, то алгоритм сортировки может гарантировать стабильность. Сначала проанализируем устойчивость упомянутого выше алгоритма сортировки, а потом поговорим о смысле устойчивости.

Пузырьковая сортировка. Стабильность может быть гарантирована, просто поменяйте местами при сравнении двух соседних чисел, только если последнее число больше первого.
сортировка выбором. Стабильность не может быть гарантирована, например, последовательности926532, в первом туреmaxIndexПосле выбора (maxIndex=0), второе появление2(хвостовой элемент) будет сочетаться с9поменяться местами, затем два2Изменился относительный порядок , и повлияет ли этот обмен на стабильность в нашемcodingвремя непредсказуемо.
Сортировка вставками. Стабильность может быть гарантирована.Каждый раз, когда число вставляется в упорядоченную последовательность, оно будет заменено, когда встретится с большим числом, иначе оно не будет заменено. В этом случае элементы с одинаковым значением всегда будут вставляться после предыдущих.
Сортировка слиянием. Стабильность может быть гарантирована после сортировки левой и правой подпоследовательностей.mergeВо время процесса, если размер равен, предпочтительно вставляется число в левой подпоследовательности.
Быстрый ряд. Стабильность не может быть гарантирована, потому чтоpartitionпроцесс будет сравниватьnumмаленький сsmallзаменив правильный номер диапазона, будет больше, чемnumбольшой сgreatлевый номер диапазона меняется местами, иsmall,greatРазделение двух сторон последовательности может легко нарушить относительный порядок элементов одного и того же значения.
сортировка кучей. Стабильность не гарантируется. Двоичное дерево может гарантировать стабильность, если узлы в позиции обмена являются соседними уровнями, но после извлечения верхнего элемента кучи при сортировке кучиheapifyОбмениваются узлы первого слоя и узлы последнего слоя.

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

марка	цена	продажи
Samsung	1603	92
Просо	1603	74
vivo	1604	92

Требуется сначала отсортировать по цене, а затем по продажам. Если стабильность гарантирована, после сортировки должно получиться так:

марка	цена	продажи
Samsung	1603	92
vivo	1604	92
Просо	1603	74

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

использование компараторов

Большинство алгоритмов, упомянутых ранее, относятся к сортировке базовых типов, но объекты, подлежащие сортировке, в реальном проектировании могут быть непредсказуемыми, так как же реализовать общий алгоритм сортировки, чтобы справиться с этим? На самом деле, все предыдущие виды могут быть классифицированы какСортировка на основе сравнения. То есть нам нужно только реализовать компаратор для сравниваемых объектов, а затем алгоритм сортировки сортирует на основе компаратора, так что алгоритм и конкретные объекты, которые нужно отсортировать, не связаны. В дальнейшем перед сортировкой реализовать компаратор на основе сортируемого объекта (что определяет логику того, как сравнивать размеры объектов), а затем кинуть компаратор в алгоритм сортировки, реализуя таким образом повторное использование.

существуетJava(Я узналJavaнаправление), этот компараторComparatorинтерфейс, нам нужно реализоватьcompareопределите логику сравнения размеров для набора сортируемых объектов, а затем передайте этот конструктор при создании упорядоченного контейнера для добавления таких объектов. Обернутый контейнер использует наш компаратор для реорганизации элементов контейнера при их изменении.

import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.PriorityQueue;
import java.util.Comparator;

public class ComparatorTest {
    
    @Data
    @AllArgsConstructor
    static class Student {
        private long id;
        private String name;
        private double score;
    }

    static class IdAscendingComparator implements Comparator<Student> {
        /**
         * 底层排序算法对两个元素比较时会调用这个方法
         * @param o1
         * @param o2
         * @return  若返回正数则认为o1<o2，返回0则认为o1=o2，否则认为o1>o2
         */
        @Override
        public int compare(Student o1, Student o2) {
            return o1.getId() < o2.getId() ? -1 : 1;
        }
    }

    public static void main(String[] args) {
        //大根堆
        PriorityQueue heap = new PriorityQueue(new IdAscendingComparator());
        Student zhangsan = new Student(1000, "zhangsan", 50);
        Student lisi = new Student(999, "lisi", 60);
        Student wangwu = new Student(1001, "wangwu", 50);
        heap.add(zhangsan);
        heap.add(lisi);
        heap.add(wangwu);
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());//弹出并返回堆顶元素
        }
    }
}

иTreeSetи т. д., все передаются в компаратор в конструкции, иначе он будет напрямую основан на значении элемента (JavaЗначением переменной ссылочного типа является адрес, сравнение будет бессмысленным) сравнивать, и я не буду перечислять их здесь по одному.

Дополнение к вопросам сортировки

Сортировка слияниемДополнительная пространственная сложность может бытьO(1), но это сложнее, если интересно, можете поискатьвнутренний кеш сортировки слиянием
быстрая сортировкаСделать для стабильности можно, но сложно, можно поискать01 stable sort(бумага)
Есть вопрос: нечетные числа размещаются в левой части массива, а четные числа размещаются в правой части массива, и исходный относительный порядок между нечетными числами и нечетными числами, а также между четными числами и четными числами равен требуется оставаться без изменений. Этот вопрос точно такой же, как и сортировка слиянием, за исключением того, что сортировка слияниемarr[length-1]илиarr[randomIndex]В качестве стандарта для сравнения, а этот вопрос состоит в том, может ли он делиться на 2 в качестве эталона для сравнения, все такие вопросы называютсяo1 sort, чтобы сделать эту проблему стабильной, это зависит от01 stable sortЭто эссе.

Комплексный алгоритм сортировки в инженерии

Алгоритм сортировки в практической инженерии обычноСортировка слиянием,Сортировка вставками,быстрая сортировкаВместе мы объединяем сильные стороны каждого для решения различных требований сцены:

Когда элемент для сортировки является базовым типом данных, а количество элементов невелико, используйте его напрямую.Сортировка вставками. Потому что, когда размер выборки мал (например, 60),O(NlogN)Преимущество неочевидно или даже меньше, чемO(N^2), пока вO(N^2)Среди алгоритмов сортировка вставками имеет наименьшее количество операций с постоянным временем.
Когда сортируемый элемент является типом данных объекта (включая несколько полей), для обеспечения стабильностиСортировка слиянием.
Когда сортируемые элементы относятся к базовым типам данных, а размер выборки большой,быстрая сортировка.

сортировка ведра

В предыдущем разделе вся сортировка основана на сравнении, то есть положение каждого элемента определяется путем сравнения. Так можно ли добиться сортировки без сравнения? Это включает в себясортировка ведраЭта методика: подготовить несколько ведер, сложить элементы последовательности в соответствующие ведра по определенным правилам и, наконец, высыпать элементы в ведра по очереди по установленным правилам.

Сортировка без сравнения во многом связана с фактическим состоянием данных отсортированных выборок, поэтому на практике она обычно не используется.

сортировка по подсчету

Сортировка подсчетасортировка ведраРеализация методологии, которая подготавливает массив того же размера, что и диапазон данных элементов в последовательности, затем обходит последовательность, индексирует встреченный элемент как индекс массива и увеличивает число в этой позиции на 1. Например, если значение элемента последовательности находится в диапазоне от 0 до 100, разработайте алгоритм для его сортировки Требуемая временная сложностьO(N).

#include <stdio.h>
void countSort(int arr[],int length){
    int bucketArr[101];
    int i;
    for(i = 0 ; i <= 100 ; i++){
        bucketArr[i]=0;	//init buckets
    }
    for(i = 0 ; i < length ; i++){
        bucketArr[arr[i]]++;	//put into buckets
    }
    int count, j=0;
    for(i = 0 ; i <= 100 ; i++) {
        if (bucketArr[i] != 0) { //pour out
            count = bucketArr[i];
            while (count-- > 0) {
                arr[j++] = i;
            }
        }
    }
}

void travels(int arr[], int length){
    for (int i = 0; i < length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(){
    int arr[] = {9, 2, 1, 4, 5, 2, 1, 6, 3, 8, 1, 2};
    travels(arr, 12);//9 2 1 4 5 2 1 6 3 8 1 2
    countSort(arr, 12);
    travels(arr, 12);//1 1 1 2 2 2 3 4 5 6 8 9
    return 0;
}

Если в следующий раз интервьюер спросит вас, существует ли коэффициент сложности мероприятияO(N)Для улучшения алгоритмов сортировки не забывайте считать и сортировать! ! !

дополнительный вопрос

Учитывая массив, найдите максимальное значение двух соседних чисел после сортировки, требуемая временная сложностьO(N), и требует, чтобы сортировка без сравнения не использовалась.

Идея этого вопроса довольно умна: сначала подготовить N+1 ведер для N чисел, затем разделить диапазон значений на N равных частей с минимальным и максимальным значениями в качестве границы, а затем пройти массив, чтобы разделить номер соответствующего класса диапазона. Поместите его в соответствующее ведро, на следующем рисунке в качестве примера используется длина массива 9.

Вот что сложнее понять:
- Вопрос задаетсяЕсли отсортировано, максимальная разница между двумя соседними числами. Алгоритм умело использует пустое ведро (N чисел входит в N+1 ведро, и одно из них должно быть пустым ведром) и превращает задачу в поискдва соседних непустых ведра(которые могут быть разделены несколькими пустыми ведрами) разница между максимальным значением переднего ведра и минимальным значением в заднем ведре, независимо от того, какие числа введены в каждое ведро (Просто запишите максимальное и минимальное значения каждого ведра и есть ли числа)
Соответствующий код выглядит следующим образом:
```
#include <stdio.h>

//根据要入桶的数和最大最小值得到对应桶编号
int getBucketId(int num,int bucketsNum,int min,int max){
    return (num - min) * bucketsNum / (max - min);
}

int max(int a, int b){
    return a > b ? a : b;
}

int min(int a, int b){
    return a < b ? a : b;
}

int getMaxGap(int arr[], int length) {
    if (arr == NULL || length < 2) {
        return -1;
    }
    int maxValue = -999999, minValue = 999999;
    int i;
    //找出最大最小值
    for (i = 0; i < length; ++i) {
        maxValue = max(maxValue, arr[i]);
        minValue = min(minValue, arr[i]);
    }
    //记录每个桶的最大最小值以及是否有数，初始时每个桶都没数
    int maxs[length + 1], mins[length + 1];
    bool hasNum[length + 1];
    for (i = 0; i < length + 1; i++) {	
        hasNum[i] = false;
    }
    //put maxValue into the last bucket
    mins[length] = maxs[length] = maxValue;
    hasNum[length] = true;

    //iterate the arr
    int bid; //bucket id
    for (i = 0; i < length; i++) {
        if (arr[i] != maxValue) {
            bid = getBucketId(arr[i], length + 1, minValue, maxValue);
          	//如果桶里没数，则该数入桶后，最大最小值都是它，否则更新最大最小值
            mins[bid] = !hasNum[bid] ? arr[i] : arr[i] < mins[bid] ? arr[i] : mins[bid];
            maxs[bid] = !hasNum[bid] ? arr[i] : arr[i] > maxs[bid] ? arr[i] : maxs[bid];
            hasNum[bid] = true;
        }
    }

    //find the max gap between two nonEmpty buckets
    int res = 0, j = 0;
    for (i = 0; i < length; ++i) {
        j = i + 1;//the next nonEmtpy bucket id
        while (!hasNum[j]) {//the last bucket must has number
            j++;
        }
        res = max(res, (mins[j] - maxs[i]));
    }

    return res;
}

int main(){
    int arr[] = {13, 41, 67, 26, 55, 99, 2, 82, 39, 100};
    printf("%d", getMaxGap(arr, 9));	//17
    return 0;
}
```

связанный список

Обратные односвязные и двусвязные списки

Для реализации функции обращения односвязного списка и обратного двусвязного списка требуемая временная сложность равнаO(N), дополнительная пространственная сложность равнаO(1)

Сложность этой задачи в том, что после инвертирования очередного указателя узла невозможно найти последующие узлы в узле через следующий указатель. Следовательно, узлы-преемники этого узла необходимо записывать перед каждой инверсией.

#include<stdio.h>
#include<malloc.h>
#define MAX_SIZE 100

struct LinkNode{
	int data;
	LinkNode* next;
};

void init(LinkNode* &head){
	head = (LinkNode*)malloc(sizeof(LinkNode));
	head->next=NULL;
}

void add(int i,LinkNode* head){
	LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
	p->data = i;
	p->next =  head->next;
	head->next = p;
}

void printList(LinkNode* head){
	if(head==NULL)
		return;
	LinkNode* p = head->next;
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

#include<stdio.h>
#include "LinkList.cpp"

void reverseList(LinkNode *head){
	if(head == NULL)
		return;
	LinkNode* cur = head->next;
	LinkNode* pre = NULL;
	LinkNode* next = NULL;
	while(cur != NULL){
		next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}
	//pre -> end node
	head->next = pre;
	return;
}

int main(){
	LinkNode* head;
	init(head);
	add(1,head);
	add(2,head);
	add(3,head);
	add(4,head);
	
	printList(head);
	reverseList(head);
	printList(head);
}

Проверить, является ли связанный список палиндромом

Пожалуйста, реализуйте функцию, чтобы определить, является ли односвязный список палиндромом, например1->3->1возвращениеtrue,1->2->2->1возвращениеtrue,2->3->1возвращениеfalse.

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

Пример кода выглядит следующим образом:

#include<stdio.h>
#include "LinkList.cpp"
#include "SqStack.cpp"

/*
	判断某链表是否是回文结构
	1、首先找到链表的中间结点（若是偶数个结点则是中间位置的左边一个结点）
	2、使用一个栈将中间结点之前的结点压栈，然后从中间结点的后一个结点开始从栈中拿出结点比较 
*/

bool isPalindromeList(LinkNode* head){
	if(head == NULL)
		return false;
		
	LinkNode *slow = head , *fast = head;
	SqStack* stack;
	init(stack);
	
	//fast指针每走两步，slow指针才走一步 
	while(fast->next != NULL && fast->next->next != NULL){
		fast = fast->next->next;	
		slow = slow->next;	
		push(slow,stack);
	}
	
	//链表没有结点或只有一个结点，不是回文结构
	if(isEmpty(stack)) 
		return false;
		
	//判断偶数个结点还是奇数个结点
	if(fast->next != NULL){	//奇数个结点,slow需要再走一步 
		slow = slow->next;
	}
	
	//从slow的后继结点开始遍历链表，将每个结点与栈顶结点比较
	LinkNode* node;
	slow = slow->next;
	while(slow != NULL){
		pop(stack,node);
		//一旦发现有一个结点不同就不是回文结构 
		if(slow->data != node->data)
			return false;
		slow = slow->next;
	} 
	return true;
}

int main(){
	
	LinkNode* head;
	init(head);
	add(2,head);
	add(3,head);
	add(3,head);
	add(2,head);
	printList(head);
	
	if(isPalindromeList(head)){
		printf("是回文链表");
	}else{
		printf("不是回文链表");
	}
	return 0;
}

LinkList.cpp:

#include<stdio.h>
#include<malloc.h>
#define MAX_SIZE 100

struct LinkNode{
	int data;
	LinkNode* next;
};

void init(LinkNode* &head){
	head = (LinkNode*)malloc(sizeof(LinkNode));
	head->next=NULL;
}

void add(int i,LinkNode* head){
	LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
	p->data = i;
	p->next =  head->next;
	head->next = p;
}

void printList(LinkNode* head){
	if(head==NULL)
		return;
	LinkNode* p = head->next;
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

SqStack:

#include<stdio.h>
#include<malloc.h>

struct SqStack{
	LinkNode* data[MAX_SIZE];
	int length;
}; 

void init(SqStack* &stack){
	stack = (SqStack*)malloc(sizeof(SqStack));
	stack->length=0; 
}

bool isEmpty(SqStack* stack){
	if(stack->length > 0)
		return false;
	return true;
}

bool isFull(SqStack* stack){
	if(stack->length == MAX_SIZE)
		return true;
	return false;
}

void push(LinkNode* i,SqStack* stack){
	if(stack==NULL)
		return;
	if(!isFull(stack)){
		stack->data[stack->length++] = i;
	}
}

bool pop(SqStack* stack,LinkNode* &i){
	if(stack==NULL)
		return false;
	if(!isEmpty(stack))
		i = stack->data[--stack->length];
		return true;
}

Расширенный: требует использования временной сложностиO(N), дополнительная пространственная сложность равнаO(1)Решить эту проблему.

Идея: мы можем сначала соединить узлы во второй половине связанного спискаnextУказатель переворачивается, а затем перемещается с двух концов связанного списка в середину и сравнивается один за другим. (Конечно, чтобы не разрушить исходную структуру данных, нам также нужно восстановить указатель связанного списка после того, как мы пришли к выводу)

#include<stdio.h>
#include "LinkList.cpp"
#include "SqStack.cpp"

bool isPalindromeList(LinkNode* head){
    /*第一步、与方法一一样，找到中间结点*/
    if(head == NULL)
        return false;

    LinkNode *n1 = head , *n2 = head;
    while(n2->next != NULL && n2->next->next != NULL){
        n2 = n2->next->next;
        n1 = n1->next;
    }
    //如果没有结点或者只有一个首结点
    if(n2 == head){
        return false;
    }
    //如果是奇数个结点
    if(n2->next != NULL){
        n1 = n1->next;  //n1 -> middle node
    }

    /*第二步、不使用额外空间，在链表自身上做文章：反转链表后半部分结点的next指针*/
    n2 = n1->next;  // n2 -> right part first node
    n1->next = NULL;//middle node->next = NULL
    LinkNode *n3 = NULL;
    while (n2 != NULL) {
        n3 = n2->next;  //记录下一个要反转指针的结点
        n2->next = n1;  //反转指针
        n1 = n2;
        n2 = n3;
    }
    //n1 -> end node
    n3 = n1;  //record end node
    n2 = head->next;
    while (n2 != NULL) {
        if (n2->data != n1->data) {
            return false;
        }
        n2 = n2->next;  //move n2 forward right
        n1 = n1->next;  //move n1 forward left
    }
    //recover the right part nodes
    n2 = n3; //n2 -> end node
    n1 = NULL;
    while (n2 != NULL) {
        n3 = n2->next;
        n2->next = n1;
        n1=n2;
        n2 = n3;
    }

    return true;
}


/*bool isPalindromeList(LinkNode* head){
    if(head == NULL)
        return false;

    LinkNode *slow = head , *fast = head;
    SqStack* stack;
    init(stack);

    //fast指针每走两步，slow指针才走一步
    while(fast->next != NULL && fast->next->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
        push(slow,stack);
    }

    //链表没有结点或只有一个结点，不是回文结构
    if(isEmpty(stack))
        return false;

    //判断偶数个结点还是奇数个结点
    if(fast->next != NULL){	//奇数个结点,slow需要再走一步
        slow = slow->next;
    }

    //从slow的后继结点开始遍历链表，将每个结点与栈顶结点比较
    LinkNode* node;
    slow = slow->next;
    while(slow != NULL){
        pop(stack,node);
        //一旦发现有一个结点不同就不是回文结构
        if(slow->data != node->data)
            return false;
        slow = slow->next;
    }
    return true;
}*/

int main(){

    LinkNode* head;
    init(head);
    add(2,head);
    add(3,head);
    add(3,head);
    add(1,head);
    printList(head);

    if(isPalindromeList(head)){
        printf("yes");
    }else{
        printf("no");
    }
    return 0;
}

Связанный список и проблема голландского флага

Разделите односвязный список в соответствии со значением в виде маленького левого, равного в середине и большого правого

#include<stdio.h>
#include "LinkList.cpp"

/*
	partition一个链表有两种做法。
	1，将链表中的所有结点放入一个数组中，那么就转换成了荷兰国旗问题，但这种做法会使用O(N)的额外空间；
	2，分出逻辑上的small,equal,big三个区域，遍历链表结点将其添加到对应的区域中，最后再将这三个区域连起来。 
	这里只示范第二种做法： 
*/
void partitionList(LinkNode *head,int val){
	if(head == NULL)
		return;
	LinkNode *smH = NULL;	//small area head node
	LinkNode *smT = NULL;	//small area tail node
	LinkNode *midH = NULL;	//equal area head node
	LinkNode *midT = NULL;	//equal area tail node
	LinkNode *bigH = NULL;	//big area head node
	LinkNode *bigT = NULL;	//big area tail node
	LinkNode *cur = head->next;	
	LinkNode *next = NULL;//next node need to be distributed to the three areas
	while(cur != NULL){
		next = cur->next;
		cur->next = NULL;
		if(cur->data > val){
			if(bigH == NULL){
				bigH = bigT = cur;
			}else{
				bigT->next = cur;
				bigT = cur;
			}
		}else if(cur->data == val){
			if(midH == NULL){
				midH = midT = cur;
			}else{
				midT->next = cur;
				midT = cur;
			}
		}else{
			if(smH == NULL){
				smH = smT = cur;
			}else{
				smT->next = cur;
				smT = cur;
			}
		}
		cur = next;
	}
	//reconnect small and equal
	if(smT != NULL){
		smT->next = midH;
		midT = midT == NULL ? midT : smT;
	}
	//reconnect equal and big
	if(bigT != NULL){
		midT->next = bigH;
	}

	head = smH != NULL ? smH : midH != NULL ? midH : bigH;

	return;
} 

int main(){
	LinkNode* head;
	init(head);
	add(5,head);
	add(2,head);
	add(7,head);
	add(9,head);
	add(1,head);
	add(3,head);
	add(5,head);
	printList(head);
	partitionList(head,5);
	printList(head);
}

Скопируйте связанный список, содержащий узлы со случайными указателями

С хеш-таблицей, дополнительное место`O(N)`

Скопируйте все узлы связанного списка вkey,valueза源结点，副本结点способ сохранить в хеш-таблице, а затем установить связь между узлами-репликами (next、randполе указателя)

import java.util.HashMap;
import java.util.Map;

public class CopyLinkListWithRandom {

    public static class Node {
        public Node(int data) {
            this.data = data;
        }

        public Node() {
        }

        int data;
        Node next;
        Node rand;
    }

    public static Node copyLinkListWithRandom(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> copyMap = new HashMap<>();
        while (cur != null) {
            copyMap.put(cur, new Node(cur.data));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            copyMap.get(cur).next = copyMap.get(cur.next);
            copyMap.get(cur).rand = copyMap.get(cur.rand);
            cur = cur.next;
        }
        return copyMap.get(head);
    }

    public static void printListWithRandom(Node head) {
        if (head != null) {
            while (head.next != null) {
                head = head.next;
                System.out.print("node data:" + head.data);
                if (head.rand != null) {
                    System.out.println(",rand data:" + head.rand.data);
                } else {
                    System.out.println(",rand is null");
                }
            }
        }
    }
  
    public static void main(String[] args) {
        Node head = new Node();
        head.next = new Node(1);
        head.next.next = new Node(2);
        head.next.next.next = new Node(3);
        head.next.next.next.next = new Node(4);
        head.next.rand = head.next.next.next.next;
        head.next.next.rand = head.next.next.next;
        printListWithRandom(head);

        System.out.println("==========");

        Node copy = copyLinkListWithRandom(head);
        printListWithRandom(copy);
    }
}

Расширенная операция: дополнительное пространство`O(1)`

После добавления узла-реплики к соответствующему исходному узлу устанавливается поле указателя между узлами-репликами, и, наконец, узел-реплика отделяется от связанного списка.

//extra area O(1)
public static Node copyLinkListWithRandom2(Node head){
  if (head == null) {
    return null;
  }
  Node cur = head;
  //copy every node and append
  while (cur != null) {
    Node copy = new Node(cur.data);
    copy.next = cur.next;
    cur.next = copy;
    cur = cur.next.next;
  }
  //set the rand pointer of every copy node
  Node copyHead = head.next;
  cur = head;
  Node curCopy = copyHead;
  while (curCopy != null) {
    curCopy.rand = cur.rand == null ? null : cur.rand.next;
    cur = curCopy.next;
    curCopy = cur == null ? null : cur.next;
  }
  //split
  cur = head;
  Node next = null;
  while (cur != null) {
    curCopy = cur.next;
    next = cur.next.next;
    curCopy.next = next == null ? null : next.next;
    cur.next = next;
    cur = next;
  }
  return copyHead;
}

Если два односвязных списка с возможными циклами пересекаются, вернуть первый узел пересечения

Согласно определению односвязного списка, каждый узел имеет один и только одинnextуказатель, то если односвязный список имеет цикл, то его структура будет следующей:

Пересечение приведет к тому, что два узла будут указывать на одного и того же преемника, но узел не может иметь двух преемников.

1. Когда пересекающийся узел не находится на кольце, возможны два следующих случая:

2. Когда пересекающийся узел находится на кольце, возможен только один случай:

Подводя итог, если два односвязных списка пересекаются, либо оба не имеют циклов, либо оба имеют циклы.

Еще один момент, который следует отметить в этом вопросе, заключается в том, что если в связанном списке есть кольцо, как получить кольцо (поскольку он не может передатьnextЯвляется ли он пустым, чтобы судить, является ли он хвостовым узлом). Здесь задействовано правило: если быстрый указательfastи медленный указательslowВ то же время, начиная с самого начала,fastсделать два шагаslowСделай шаг, и когда они встретятся,fastУказатель указывает на головной узел, так что оба выполняются по одному шагу за раз и встречаются в узле входа в цикл.

public class FirstIntersectNode {
    public static class Node{
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
        }
    }

    public static Node getLoopNode(Node head) {
        if (head == null) {
            return null;
        }
        Node fast = head;
        Node slow = head;
        do {
            slow = slow.next;
            if (fast.next == null || fast.next.next == null) {
                return null;
            } else {
                fast = fast.next.next;
            }
        } while (fast != slow);
        //fast == slow
        fast = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static Node getFirstIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1);    //两链表的入环结点loop1和loop2
        Node loop2 = getLoopNode(head2);
        //no loop
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        //both loop
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, head2, loop1, loop2);
        }
        //don't intersect
        return null;
    }

    private static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
        Node cur1 = head1;
        Node cur2 = head2;
        //入环结点相同，相交点不在环上
        if (loop1 == loop2) {
            int n = 0;
            while (cur1.next != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2.next != loop1) {
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;           //将cur1指向结点数较多的链表
            cur2 = cur1 == head1 ? head2 : head1;   //将cur2指向另一个链表
            n = Math.abs(n);
            while (n != 0) {                        //将cur1先走两链表结点数差值个结点
                cur1 = cur1.next;
                n--;
            }
            while (cur1 != cur2) {                  //cur1和cur2会在入环结点相遇
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
        //入环结点不同，相交点在环上
        cur1 = loop1.next;
        while (cur1 != loop1) {
            if (cur1 == loop2) {    //链表2的入环结点在链表1的环上，说明相交
                return loop1;   //返回loop1或loop2均可，因为整个环就是两链表的相交部分
            }
            cur1 = cur1.next;
        }
        //在链表1的环上转了一圈也没有找到链表2的入环结点，说明不想交
        return null;
    }

    private static Node noLoop(Node head1, Node head2) {
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }
        if (cur1 != cur2) {     //两链表的尾结点不同，不可能相交
            return null;
        }
        cur1 = n > 0 ? head1 : head2;           //将cur1指向结点数较多的链表
        cur2 = cur1 == head1 ? head2 : head1;   //将cur2指向另一个链表
        n = Math.abs(n);
        while (n != 0) {                        //将cur1先走两链表结点数差值个结点
            cur1 = cur1.next;
            n--;
        }
        while (cur1 != cur2) {                  //cur1和cur2会在入环结点相遇
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    public static void printList(Node head) {
        for (int i = 0; i < 50; i++) {
            System.out.print(head.data+" ");
            head = head.next;
        }
        System.out.println();
    }

}

Три случая проверяются следующим образом:

public static void main(String[] args) {

        //==================== both loop ======================
        //1->2->[3]->4->5->6->7->[3]...
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next.next = head1.next.next;

        //9->8->[6]->7->3->4->5->[6]...
        Node head2 = new Node(9);
        head2.next = new Node(8);
        head2.next.next = head1.next.next.next.next.next;
        head2.next.next.next = head1.next.next.next.next.next.next;
        head2.next.next.next.next = head1.next.next;
        head2.next.next.next.next.next = head1.next.next.next;
        head2.next.next.next.next.next.next = head1.next.next.next.next;
        head2.next.next.next.next.next.next.next = head1.next.next.next.next.next;

        printList(head1);
        printList(head2);
        System.out.println(getFirstIntersectNode(head1, head2).data);
        System.out.println("==================");

        //1->[2]->3->4->5->6->7->8->4...
        Node head3 = new Node(1);
        head3.next = new Node(2);
        head3.next.next = new Node(3);
        head3.next.next.next = new Node(4);
        head3.next.next.next.next = new Node(5);
        head3.next.next.next.next.next = new Node(6);
        head3.next.next.next.next.next.next = new Node(7);
        head3.next.next.next.next.next.next.next = new Node(8);
        head3.next.next.next.next.next.next.next.next = head1.next.next.next;

        //9->0->[2]->3->4->5->6->7->8->4...
        Node head4 = new Node(9);
        head4.next = new Node(0);
        head4.next.next = head3.next;
        head4.next.next.next = head3.next.next;
        head4.next.next.next.next = head3.next.next.next;
        head4.next.next.next.next.next = head3.next.next.next.next;
        head4.next.next.next.next.next.next = head3.next.next.next.next.next;
        head4.next.next.next.next.next.next.next = head3.next.next.next.next.next.next;
        head4.next.next.next.next.next.next.next.next = head3.next.next.next.next.next.next.next;
        head4.next.next.next.next.next.next.next.next.next = head3.next.next.next;

        printList(head3);
        printList(head4);
        System.out.println(getFirstIntersectNode(head3,head4).data);
        System.out.println("==================");

        //============= no loop ==============
        //1->[2]->3->4->5
        Node head5 = new Node(1);
        head5.next = new Node(2);
        head5.next.next = new Node(3);
        head5.next.next.next = new Node(4);
        head5.next.next.next.next = new Node(5);
        //6->[2]->3->4->5
        Node head6 = new Node(6);
        head6.next = head5.next;
        head6.next.next = head5.next.next;
        head6.next.next.next = head5.next.next.next;
        head6.next.next.next.next = head5.next.next.next.next;

        System.out.println(getFirstIntersectNode(head5,head6).data);
    }

стеки и очереди

Реализация стеков и очередей фиксированного размера с использованием структур массивов

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#define MAX_SIZE 1000

struct ArrayStack{
    int data[MAX_SIZE];
    int top;
};

void init(ArrayStack *&stack) {
    stack = (ArrayStack *) malloc(sizeof(ArrayStack));
    stack->top = -1;
}

bool isEmpty(ArrayStack* stack){
    return stack->top == -1 ?;
}

bool isFull(ArrayStack *stack){
    return stack->top == MAX_SIZE - 1 ?;
}

void push(int i, ArrayStack *stack){
    if (!isFull(stack)) {
        stack->data[++stack->top] = i;
    }
}

int pop(ArrayStack* stack){
    if (!isEmpty(stack)) {
        return stack->data[stack->top--];
    }
}

int getTopElement(ArrayStack *stack){
    if (!isEmpty(stack)) {
        return stack->data[stack->top];
    }
}

int main(){

    ArrayStack* stack;
    init(stack);
    push(1, stack);
    push(2, stack);
    push(3, stack);

    printf("%d ", pop(stack));
    printf("%d ", getTopElement(stack));
    printf("%d ", pop(stack));
    printf("%d ", pop(stack));
		//3 2 2 1
    return 0;
}

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#define MAX_SIZE 1000

//数组结构实现的环形队列
struct ArrayCircleQueue{
    int data[MAX_SIZE];
    int front,rear;
};

void init(ArrayCircleQueue *&queue){
    queue = (ArrayCircleQueue *) malloc(sizeof(ArrayCircleQueue));
    queue->front = queue->rear = 0;
}

bool isEmpty(ArrayCircleQueue *queue){
    return queue->front == queue->rear;
}

bool isFull(ArrayCircleQueue *queue){
    return (queue->rear+1)%MAX_SIZE==queue->front;
}

void enQueue(int i, ArrayCircleQueue *queue){
    if (!isFull(queue)) {
        //move the rear and fill it
        queue->data[++queue->rear] = i;
    }
}

int deQueue(ArrayCircleQueue *queue){
    if (!isEmpty(queue)) {
        return queue->data[++queue->front];
    }
}

int main(){
    ArrayCircleQueue* queue;
    init(queue);
    enQueue(1, queue);
    enQueue(2, queue);
    enQueue(3, queue);
    while (!isEmpty(queue)) {
        printf("%d ", deQueue(queue));
    }
}

Получить наименьший элемент в стеке

Реализовать специальный стек, на основе реализации основных функций стека, а затем реализовать операцию возврата наименьшего элемента в стекеgetMin. Требования следующие:

pop,push,getMinВременная сложность операции составляетO(1).
Разработанный тип стека может использовать готовую структуру стека.

Идея: Потому что каждый разpushПосле этого минимальное значение существующих элементов в стеке может измениться, поэтому контейнер требуется связать со стеком (записывать каждый разpushнаименьшее значение в результирующем стеке). Мы можем использовать вспомогательный стек, стек данныхpushпервый элемент, добавьте и егоpushво вспомогательный стек, а затем в стек данных каждый разpushЭлемент сравнивается с верхним элементом вспомогательного стека, и если он маленький, то такжеpushво вспомогательный стек, иначе взять верхний элемент вспомогательного стекаpushво вспомогательный стек. (Стек данных нормальныйpush,popданные, а вспомогательный стекpushкаждый стек данныхpushМинимальное значение в результирующем стеке, но стек данныхpop, вспомогательный стек также нуждается в простомpopПросто синхронизируй)

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#include "ArrayStack.cpp"

int min(int a, int b){
    return a < b ? a : b;
}

struct GetMinStack{
    ArrayStack* dataStack;
    ArrayStack* helpStack;
};

void initGetMinStack(GetMinStack* &stack){
    stack = (GetMinStack *) malloc(sizeof(GetMinStack));
    init(stack->dataStack);
    init(stack->helpStack);
}

void push(int i, GetMinStack *stack) {
    if (!isFull(stack->dataStack)) {
        push(i, stack->dataStack);  //ArrayStack.cpp
        if (!isEmpty(stack->helpStack)) {
            i = min(i, getTopElement(stack->helpStack));
        }
        push(i, stack->helpStack);
    }
}

int pop(GetMinStack* stack){
    if (!isEmpty(stack->dataStack)) {
        pop(stack->helpStack);
        return pop(stack->dataStack);
    }
}

int getMin(GetMinStack *stack){
    if (!isEmpty(stack->dataStack)) {
        return getTopElement(stack->helpStack);
    }
}

int main(){
    GetMinStack *stack;
    initGetMinStack(stack);
    push(6, stack);
    printf("%d ", getMin(stack));//6
    push(3, stack);
    printf("%d ", getMin(stack));//3
    push(1, stack);
    printf("%d ", getMin(stack));//1
  	pop(stack);
    printf("%d ", getMin(stack));//3

    return 0;
}

Реализовать структуру стека, используя только структуру очереди

Идея: просто сосредоточиться напоследний пришел первый вышелДобиться этой функции несложно. Используя очередь данных и вспомогательную очередь, при помещении данных в очередь данных операция использования очереди обычно помещается в очередь данных, но при удалении элементов из очереди необходимо поставить в очередь первые n-1 номеров очереди данных во вспомогательную очередь и очередь данных. Хвостовой элемент очереди всплывает, и, наконец, очередь данных и вспомогательная очередь меняются ролями.

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#include "../queue/ArrayCircleQueue.cpp"

struct DoubleQueueStack{
    ArrayCircleQueue* dataQ;
    ArrayCircleQueue* helpQ;
};

void init(DoubleQueueStack* &stack){
    stack = (DoubleQueueStack *) malloc(sizeof(DoubleQueueStack));
    init(stack->dataQ);
    init(stack->helpQ);
}

void swap(ArrayCircleQueue *&dataQ, ArrayCircleQueue *&helpQ){
    ArrayCircleQueue* temp = dataQ;
    dataQ = helpQ;
    helpQ = temp;
}

void push(int i,DoubleQueueStack* stack){
    if (!isFull(stack->dataQ)) {
        return enQueue(i, stack->dataQ);
    }
}

int pop(DoubleQueueStack* stack){
    if (!isEmpty(stack->dataQ)) {
        int i = deQueue(stack->dataQ);
        while (!isEmpty(stack->dataQ)) {
            enQueue(i, stack->helpQ);
            i = deQueue(stack->dataQ);
        }
        swap(stack->dataQ, stack->helpQ);
        return i;
    }
}

bool isEmpty(DoubleQueueStack* stack){
    return isEmpty(stack->dataQ);
}

int getTopElement(DoubleQueueStack* stack){
    if (!isEmpty(stack->dataQ)) {
        int i = deQueue(stack->dataQ);
        while (!isEmpty(stack->dataQ)) {
            enQueue(i, stack->helpQ);
            i = deQueue(stack->dataQ);
        }
        enQueue(i, stack->helpQ);
        swap(stack->dataQ, stack->helpQ);
        return i;
    }
}

int main(){

    DoubleQueueStack *stack;
    init(stack);
    push(1, stack);
    push(2, stack);
    push(3, stack);
    while (!isEmpty(stack)) {
        printf("%d ", pop(stack));
    }
    push(4, stack);
    printf("%d ", getTopElement(stack));
    
    return 0;
}

Реализовать структуру очереди только со структурой стека

Идея: использовать два стека, один стекPutStackИспользуется для размещения данных, стекGetStackиспользуется для получения данных. При получении данных, еслиPulllStackЕсли он пустой, он должен бытьPutStackсерединавсе элементыодин за разpopи положить вGetStack.

Особо следует отметить этоинвертированные данныевремя:

только тогда, когдаGetStackВы можете упасть только тогда, когда он пуст

инвертированные данныедолжен быть одноразовымPutStackданные в

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#include "../stack/ArrayStack.cpp"

struct DoubleStackQueue{
    ArrayStack* putStack;
    ArrayStack* getStack;
};

void init(DoubleStackQueue *&queue){
    queue = (DoubleStackQueue *) malloc(sizeof(DoubleStackQueue));
    init(queue->putStack);
    init(queue->getStack);
}

bool isEmpty(DoubleStackQueue *queue){
    return isEmpty(queue->getStack) && isEmpty(queue->putStack);
}

void pour(ArrayStack *stack1, ArrayStack *stack2){
    while (!isEmpty(stack1)) {
        push(pop(stack1), stack2);
    }
}

void enQueue(int i, DoubleStackQueue *queue){
    if (!isFull(queue->putStack)) {
        push(i, queue->putStack);
    } else {
        if (isEmpty(queue->getStack)) {
            pour(queue->putStack, queue->getStack);
            push(i, queue->putStack);
        }
    }
}

int deQueue(DoubleStackQueue* queue){
    if (!isEmpty(queue->getStack)) {
        return pop(queue->getStack);
    } else {
        if (!isEmpty(queue->putStack)) {
            pour(queue->putStack, queue->getStack);
            return pop(queue->getStack);
        }
    }
}


int main(){
    DoubleStackQueue *queue;
    init(queue);
    enQueue(1, queue);
    printf("%d\n", deQueue(queue));
    enQueue(2, queue);
    enQueue(3, queue);
    while (!isEmpty(queue)) {
        printf("%d ", deQueue(queue));
    }
    return 0;
}