数据结构
数据结构是计算机内部数据的组织形式和存储方法，常用的数据结构有线性结构、数结构、图结构。
线性结构
线性结构主要包括：顺序表、链表、栈、队列等基本形式。其中顺序表和链表是从存储形式上(或物理结构上)区分的，而栈和队列是从逻辑功能上区分的。也就是说，顺序表和链表是线性数据结构的基础，队列和栈是基于顺序表和链表的，它们由顺序表或链表构成。
栈的实现
#ifndef STACK_HPP#define STACK_HPP#include <iostream>using namespace std;template <class T>class Stack {public: Stack(); Stack(int capacity); ~Stack(); bool IsEmpty(); bool IsFull(); void ClearStack(); int Length(); bool Push(const T &element); bool Pop(T &ele); void StackTraverse(); private: T *m_stack; int m_top; int m_capacity; };template <typename T>Stack<T>::Stack() { cout << "构造函数" << endl;}template <typename T>Stack<T>::Stack(int capacity) { this->m_capacity = capacity; this->m_top = 0; this->m_stack = new T[this->m_capacity];}template <typename T>Stack<T>::~Stack() { if (this->m_stack != NULL) { delete[] this->m_stack; this->m_stack = NULL; }}template <typename T>bool Stack<T>::IsEmpty() { return this->m_top == 0 ? true : false;}template <typename T>bool Stack<T>::IsFull() { return this->m_top == this->m_capacity ? true : false;}template <typename T>void Stack<T>::ClearStack() { this->m_top = 0;}template <typename T>int Stack<T>::Length() { return this->m_top;}template <typename T>bool Stack<T>::Push(const T &element) { if (IsFull()) { return false; } else { this->m_stack[this->m_top++] = element; return true; }}template <typename T>bool Stack<T>::Pop(T &ele) { if (!IsEmpty()) { this->m_top--; ele = this->m_stack[this->m_top]; return true; } else { return false; }}template <typename T>void Stack<T>::StackTraverse() { if (!IsEmpty()) { for (int i = m_top - 1; i >= 0; --i) { cout << this->m_stack[i] << ' '; } cout << endl; } else { cout << "栈为空" << endl; }}#endif
队列的实现
#ifndef MYQUEUE_HPP#define MYQUEUE_HPP#include <iostream>using namespace std;template <typename T>struct QueueNode { T data; QueueNode *next; QueueNode () { this->next = NULL; }};template <class T>class MyQueue {public: MyQueue() { this->count = 0; this->head = new QueueNode <T>(); this->tail = new QueueNode <T>(); this->tail = this->head; } ~MyQueue() { if (this->head != NULL) { cout << "释放head" << endl; delete[] this->head; this->head = NULL; } if (this->tail != NULL) { cout << "释放tail" << endl; delete[] this->tail; this->tail = NULL; } } int size() { return this->count; } bool IsEmpty() { if (size() == 0) { return true; } else { return false; } } void InQueue(T val) { QueueNode <T> *temp = new QueueNode<T>(); temp->data = val; this->tail->next = temp; this->tail = temp; this->count++; } QueueNode<T>* OutQueue() { if (this->count == 0) { cout << "队列为空" << endl; return NULL; } QueueNode <T> *temp = this->head->next; if (temp) { this->head->next = temp->next; temp->next = NULL; this->count--; } return temp; } void QueueTraverse() { if (this->count == 0) { cout << "队列为空" << endl; return; } QueueNode <T> *temp = head->next; while (temp) { cout << temp->data << ' '; temp = temp->next; } cout << endl; } void Remove() { this->head->next = NULL; this->tail = this->head; this->count = 0; }private: int count; QueueNode <T> *head; QueueNode <T> *tail;};#endif
链表反转
使用两个节点pre和next，先用next保存当前节点的next指针，然后将当前节点next指针指向上一个节点pre，接下来将当前节点赋值给pre，next赋值给当前节点进行下一循环，直到当前节点为NULL。
struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {}};ListNode* ReverseList(ListNode *pHead) { if(pHead == NULL) return NULL; ListNode *pre = NULL; ListNode *next = NULL; while (pHead != NULL) { next = pHead->next; pHead->next = pre; pre = pHead; pHead = next; } return pre;}
寻找第k大
int Partition(vector<int> &arr, int start, int end) { if (start == end) return start; int left = start, right = end, key = arr[start]; while (left < right) { while (left < right && arr[right] <= key) right--; arr[left] = arr[right]; while (left < right && arr[left] >= key) left++; arr[right] = arr[left]; } arr[left] = key; return left;}int findKth(vector<int> a, int n, int K) { int low = 0; int high = n - 1; int mid; while (low <= high) { mid = Partition(a, low, high); if (K < mid + 1) { high = mid - 1; } else if (K > mid + 1) { low = mid + 1; } else { return a[mid]; } } return -1;}
括号序列
给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列，括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。
bool isValid(string s) { if (s.size() & 1 != 0) return false; stack<char> temp; for (int i = 0; i < s.size(); ++i) { if (s[i] == '(' || s[i] == '{' || s[i] == '[') temp.push(s[i]); else { if (temp.empty()) return false; switch (s[i]) { case '}': if (temp.top() == '{') temp.pop(); break; case ']': if (temp.top() == '[') temp.pop(); break; case ')': if (temp.top() == '(') temp.pop(); break; default: return false; } } } if (!temp.empty()) return false; return true;}
链表中的节点每k有一组翻转
题目描述
将给出的链表中的节点每$k$个一组翻转，返回翻转后的链表如果链表中的节点数不是$k$的倍数，将最后剩下的节点保持原样你不能更改节点中的值，只能更改节点本身。要求空间复杂度$O(1)$。例如：给定的链表是$1→2→3→4→5$
对于 $k = 2$, 你应该返回 $2→1→4→3→5$对于 $k = 3$, 你应该返回 $3→2→1→4→5$
ListNode* reverseKGroup(ListNode* head, int k) { if (head == NULL) return NULL; ListNode *temp = head; int len = 0; while (temp != NULL) { temp = temp->next; ++len; } temp = head; if (len < k) return head; ListNode *pre = NULL; ListNode *next = NULL; for (int i = 0; i < k; ++i) { next = head->next; head->next = pre; pre = head; head = next; } temp->next = reverseKGroup(head, k); return pre; }
判断链表中是否有环
链表和快慢指针
bool hasCycle(ListNode *head) { ListNode *low, *quick; low = quick = head; while (quick->next->next != NULL && quick->next != NULL) { low = low->next; quick = quick->next->next; if (low == quick) return true; } return false;}
链表中环的入口
ListNode *detectCycle(ListNode *head) { if (head == NULL) return 0; ListNode *slow = head; ListNode *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } if (fast == NULL || fast->next == NULL) return NULL; fast = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow;}
合并有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *head = new ListNode(-1); ListNode *temp = head; while (l1 != NULL || l2 != NULL) { if (l1 == NULL) { temp->next = l2; break; } if (l2 == NULL) { temp->next = l1; break; } if (l1->val < l2->val) { temp->next = l1; l1 = l1->next; } else { temp->next = l2; l2 = l2->next; } temp = temp->next; } return head;}
删除链表的倒数第N个节点
ListNode* removeNthFromEnd(ListNode* head, int n) { if (head == NULL) return NULL; ListNode *dummy = new ListNode(0); dummy->next = head; head = dummy; ListNode *slow = head; ListNode *fast = head; for (int i = 0; i < n; ++i) { fast = fast->next; } while (fast->next != NULL) { slow = slow->next; fast = fast->next; } ListNode *temp = slow->next; slow->next = slow->next->next; delete temp; return dummy->next;}
两个链表相加生成相加链表
ListNode* addInList(ListNode* head1, ListNode* head2) { stack<ListNode *> s1; stack<ListNode *> s2; while (head1) { s1.push(head1); head1 = head1->next; } while (head2) { s2.push(head2); head2 = head2->next; } int flag = 0; while (!s1.empty() || !s2.empty()) { int sum = flag; if (!s1.empty()) { sum += s1.top()->val; head1 = s1.top(); s1.pop(); } if (!s2.empty()) { sum += s2.top()->val; if (s2.size() > s1.size()) head1 = s2.top(); s2.pop(); } if (sum < 10) { head1->val = sum; flag = 0; } else { head1->val = sum % 10; flag = sum / 10; } } if (flag > 0) { ListNode *head = new ListNode(flag); head->next = head1; return head; } return head1;}
树结构
数据之间存在“一对多”的关系构成了树结构。
图结构
图结构中数据元素之间存在着“多对多”的关系。
算法
查找和排序
顺序查找
int search(Student *stu, int n, int key) { for (int i = 0; i < n; ++i) { if (stu[i].id == key) return i; } return -1;}
折半查找
int bin_search(int *key, int n, int k) { int low = 0, high = n - 1, mid; while (low <= high) { mid = (low + high) / 2; if (key[mid] == k) return mid; if (k > key[mid]) low = mid + 1; else high = mid - 1; } return -1;}
请实现有重复数字的有序数组的二分查找。输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
int bin_search(int n, int v, vector<int>& a) { int left = 0; int right = n - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (a[mid] >= v) { if (mid == 0 || a[mid-1] < v) return mid + 1; else right = mid - 1; } else left = mid + 1; } return n + 1;}
直接插入排序
void insertSort(int arr[], int n) { for (int i = 1; i < n; ++i) { int temp = arr[i]; int j = i - 1; while (j >= 0 && temp < arr[j]) { arr[j+1] = arr[j]; j--; } arr[j+1] = temp; }}
选择排序
void selectSort(int arr[], int n) { for (int i = 0; i < n; ++i) { int min = i, temp; for (int j = i; j < n; ++j) { if (arr[j] < arr[min]) min = j; } if (min != i) { temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } }}
冒泡排序
void BubbleSort(int arr[], int n) { bool flag = true; for (int i = 0; i < n && flag; ++i) { flag = false; for (int j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { flag = true; int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }}
希尔排序
void shellSort(int arr[], int n) { int i, j, gap = n; bool flag = true; int temp; while(gap > 1) { gap = gap / 2; do { flag = false; for (i = 0; i < n - gap; ++i) { j = i + gap; if (arr[i] > arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; flag = true; } } } while(flag); }}
快速排序
void swap(int &a, int &b) { int temp = a; a = b; b = temp;}void quick(int arr[], int start, int end) { if (start >= end) return; int left = start, right = end, key = arr[start]; while (left < right) { while(left < right && arr[right] >= key) right--; while(left < right && arr[left] <= key) left++; swap(arr[left], arr[right]); } swap(arr[start], arr[left]); quick(arr, start, left - 1); quick(arr, left + 1, end);}void quickSort(int arr[], int n) { quick(arr, 0, n - 1);}
循环实现
int Partition(int *arr, int start, int end) { if (start == end) return start; int left = start, right = end, key = arr[start]; while (left < right) { while (left < right && arr[right] >= key) right--; arr[left] = arr[right]; while (left < right && arr[left] <= key) left++; arr[right] = arr[left]; } arr[left] = key; return left;}void quickSort2(int arr[], int n) { stack<int> st; st.push(0); st.push(n-1); while (!st.empty()) { int right = st.top(); st.pop(); int left = st.top(); st.pop(); int mid = Partition(arr, left, right); if (mid - 1 > left) { st.push(left); st.push(mid - 1); } if (mid + 1 < right) { st.push(mid + 1); st.push(right); } }}
堆排序
void adjust(int arr[], int i, int len) { int temp = arr[i]; for (int k = 2 * i + 1; k < len; k = k * 2 + 1) { if (k + 1 < len && arr[k] < arr[k + 1]) k++; if (arr[k] > temp) { arr[i] = arr[k]; i = k; } else { break; } } arr[i] = temp;}void headSort(int arr[], int n) { int i, temp; for (i = n / 2; i >= 0; --i) { adjust(arr, i, n); } for (int j = n - 1; j > 0; --j) { swap(arr[0], arr[j]); adjust(arr, 0, j); }}
回溯
四皇后问题
在一个4×4的国际象棋棋盘上，一次一个地摆放4枚皇后棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。
解决策略：
初始化一个4x4的数组Q，Q[i][j]=1表示该点有皇后，无皇后的点置为0。遍历每一行，使用isCorrect判断当前点是否可以放置皇后，可以放置后使用递归将皇后数量+1确定四个皇后之后将上个确定的皇后置为0进行回溯，继续执行循环。
int isCorrect(int i, int j, int (*QueenArray)[4]) { int s, t; for (s = i, t = 0; t < 4; ++t) if (QueenArray[s][t] == 1 && t != j) return 0; for (s = 0, t = j; s < 4; ++s) if (QueenArray[s][t] == 1 && s != i) return 0; for (s = i - 1, t = j - 1; s >= 0 && t >= 0; s--, t--) if (QueenArray[s][t] == 1) return 0; for (s = i - 1, t = j + 1; s >= 0 && t < 4; s--, t++) if (QueenArray[s][t] == 1) return 0; for (s = i + 1, t = j - 1; s < 4 && t >= 0; s++, t--) if (QueenArray[s][t] == 1) return 0; for (s = i + 1, t = j + 1; s < 4 && t < 4; s++, t++) if (QueenArray[s][t] == 1) return 0; return 1;}
void Queen(int queenNum, int (*QueenArray)[4]) { int i, k; if (queenNum == 4) { for (i = 0; i < 4; i++) { for (k = 0; k < 4; k++) cout << QueenArray[i][k] << ' '; cout << endl; } cout << endl; count++; return; } for (i = 0; i < 4; i++) { if (isCorrect(i, queenNum, QueenArray)) { QueenArray[i][queenNum] = 1; Queen(queenNum+1, QueenArray); QueenArray[i][queenNum] = 0; } }}
动态规划
上台阶问题
有一楼梯共m级，若每次只能跨上一级或二级，要走上第m级，共有多少走法
int UpStairs(int n) { if (n < 0) return -1; if (n == 1) return 1; if (n == 2) return 2; return UpStairs(n - 1) + UpStairs(n - 2);}
int UpStairs(int n) { if (n < 0) return -1; if (n == 1) return 1; if (n == 2) return 2; int *dp = new int[n+1]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) dp[i] = dp[i-1] + dp[i-2] return dp[n];}
编辑距离
已知两个字符串word1和word2，求从word1转化成word2最少需要几步。其中，每一步只能进行以下三个操作之一：
插入一个字符删除一个字符替换一个字符
解决策略：
使用一个二维数组dp记录需要的操作数dp[i][j]表示word1转化为word2需要的最小操作数，有两种状态，word1[i]==word2[j]和word1[i]!=word2[j]，
word1[i] == word2[j]，则dp[i][j] = dp[i-1][j-1]，word1[i] !=wrod2[j]，有三条路径：
比如，”xyz” => “efg” 的最小编辑距离等于 “xy” => “efg” 的最小编辑距离 + 1(因为允许插入操作，插入一个 “z”)，抽象的描述便是 d[m][n] === d[m-1][n] + 1。比如，”xyz” => “efg” 的最小编辑距离等于 “xyzg” => “efg” 的最小编辑距离 + 1，且因为最后一个字符都是 “g”，根据第一个判断条件，可以再等于 “xyz” => “ef” 的最小编辑距离 + 1，因此，得到结论：”xyz” => “efg” 的最小编辑距离等于 “xyz” => “ef” 的最小编辑距离 + 1，抽象的描述便是：d[m][n] === d[m][n-1] + 1。比如，”xyz” => “efg” 的最小编辑距离等于 “xyg” => “efg” 的最小编辑距离 + 1(因为允许替换操作，可以把 “g” 换成 “z”)，再等于 “xy” => “ef” 的编辑距离 + 1(根据第一个判断条件)，抽象的描述便是： d[m][n] === d[m-1][n-1] + 1。上述三种情况都有可能出现，因此，取其中的最小值便是整体上的最小编辑距离。
int miniDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); int **dp = new int*[n1+1]; for (int i = 0; i <= n1; ++i) dp[i] = new int[n2+1](); for (int i = 0; i < n1; ++i) dp[i+1][0] = dp[i][0] + 1; for (int i = 0; i < n2; ++i) dp[0][i+1] = dp[0][i] + 1; for (int i = 1; i <= n1; ++i) { for (int j = 1; j <= n2; ++j) if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1; } for (int i = 0; i < n1; ++i) delete[] dp[i]; delete[] dp; return dp[n1][n2];}
贪心
