# Small Algorithm

### 快排

``````#include <iostream>

using namespace std;

void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/

while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}

a[first] = a[last];/*将比第一个小的移到低端*/

while(first < last && a[first] <= key)
{
++first;
}

a[last] = a[first];
/*将比第一个大的移到高端*/
}
a[first] = key;/*枢轴记录到位*/
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
``````

### 合并

``````//将有二个有序数列a[first...mid]和a[mid...last]合并
void mergearray(int a[],int first,int mid,int last,int temp[])
{
int i = first,j = mid+1;
int m = mid,n = last;
int k = 0;
while (i<=m && j <= n)
{
if (a[i]<=a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
// printf("%d\n", temp[k]);
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (int i = 0; i < k; ++i)
a[first+i] = temp[i];
}

void mergesort(int a[],int first,int last,int temp[])
{
if (first<last)
{
int mid = (first+last)/2;
mergesort(a,first,mid,temp);
mergesort(a,mid+1,last,temp);
mergearray(a,first,mid,last,temp);
}
}

void MergeSort(int a[],int n)
{
int *p = new int[n];
if (p == NULL) return;
mergesort(a,0,n-1,p);
delete[] p;
}
``````

### 打印菱形

``````void PrintLingxing(int size)
{
for (int x=-size;x<=size;x++)
{
for (int y=-size;y<=size;y++)
{
if (abs(x)+abs(y)<=size)
{
printf("*");
}

else
{
printf(" ");
}
}
printf("\n");
}
}
``````

### 验证ipv4,ipv6

https://blog.csdn.net/jacky_chenjp/article/details/70233212

https://www.cnblogs.com/wzxwhd/p/6030083.html

``````http://www.cnblogs.com/grandyang/p/6185339.html
//输入输出控制类 https://blog.csdn.net/jacky_chenjp/article/details/70233212
istringstream is(IP);
string t = "";
int cnt = 0;
if (IP.find(':') == string::npos) { // Check IPv4
while (getline(is, t, '.')) {
++cnt;
if (cnt > 4 || t.empty() || (t.size() > 1 && t[0] == '0') || t.size() > 3) return "Neither";
for (char c : t) {
if (c < '0' || c > '9') return "Neither";
}
//字符串转int https://www.cnblogs.com/wzxwhd/p/6030083.html
int val = stoi(t);
if (val < 0 || val > 255) return "Neither";
}
return (cnt == 4 && IP.back() != '.') ? "IPv4" : "Neither";
} else { // Check IPv6
while (getline(is, t, ':')) {
++cnt;
if (cnt > 8 || t.empty() || t.size() > 4) return "Neither";
for (char c : t) {
if (!(c >= '0' && c <= '9') && !(c >= 'a' && c <= 'f') && !(c >= 'A' && c <= 'F')) return "Neither";
}
}
return (cnt == 8 && IP.back() != ':') ? "IPv6" : "Neither";
}
}
``````

### 二维数组中的查找

``````#include <stdio.h>
#include <stdbool.h>

bool find(int target, int arr[3][3])
{
int rows = 3;
int cols = 3;
int i = 0,j = cols-1;
while(i < rows && j >= 0)
{
if (arr[i][j] == target)
return true;
else if (arr[i][j] > target)
j --;
else
i ++;
}
return false;
}
``````

### 链表中倒数第k个结点

``````
struct ListNode{
int val;
struct ListNode* next;
ListNode(int x):
val(x),next(NULL){
}
};

class Solution{
public:
if (pListHead == NULL || k == 0)
{
return NULL;
}
for (unsigned int i = 0; i < k-1; i++)
{
if (pFast->next==NULL)
{
return NULL;
}
pFast = pFast->next;
}
while (pFast->next!=NULL)
{
pSlow = pSlow->next;
pFast = pFast->next;
}
return pSlow;
}
};
``````

### 翻转链表

``````class Solution{
public:
ListNode* pre = NULL;
ListNode* pn = NULL;

while (p) {
pn = p->next;
p->next = pre;
pre = p;
p = pn;
}
return pre;
}
};
``````

### 二叉树镜像

``````struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int x):
val(x),left(NULL),right(NULL){};
};

class Solution {
public:
void Mirror(TreeNode* pRoot)
{
if (pRoot == NULL)
return;
TreeNode* tmp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = tmp;
if (pRoot->left)
Mirror(pRoot->left);
if (pRoot->right)
Mirror(pRoot->right);
}
};

//非递归解法
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL) return;
stack<TreeNode*> s;
s.push(pRoot);
while(!s.empty())
{
s.pop();
{
}
}
}
};
``````

### 二叉树遍历

• 前序遍历：根节点->左子树->右子树
• 中序遍历：左子树->根节点->右子树
• 后序遍历：左子树->右子树->根节点
``````#include <vector>
#include <stack>

using namespace std;

struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int x) :
val(x),left(NULL),right(NULL){}
};

//前序递归遍历
vector<int> preVector;
void PreOrder(TreeNode* root)
{
if (root != NULL)
{
preVector.push_back(root->val);
PreOrder(root->left);
PreOrder(root->right);
}
}

//前序非递归遍历
void PreOrder2(TreeNode* root)
{
stack<TreeNode*> s;
TreeNode* p = root;
vector<int> result;
while (p || !s.empty())
{
if (p)
{
result.push_back(p->val);
s.push(p);
p = p->left;
}
else
{
p = s.top();
p = p->right;
s.pop();
}
}
}

//中序递归遍历
vector<int> inResult;
void InOrder(TreeNode* root)
{
if (root != NULL) {
InOrder(root->left);
inResult.push_back(root->val);
InOrder(root->right);
}
}

//中序非递归遍历
void InOrder2(TreeNode* root)
{
stack<TreeNode*> s;
vector<int> result;
TreeNode* p = root;
while (p || !s.empty())
{
if (p)
{
s.push(p);
p = p->left;
}
else
{
p = s.top();
result.push_back(p->val);
s.pop();
p = p->right;
}
}
}

//后序递归遍历
vector<int> postResult;
void PostOrder(TreeNode* root)
{
if (root != NULL)
{
PostOrder(root->left);
PostOrder(root->right);
postResult.push_back(root->val);
}
}

//后序非递归遍历
void PostOrder2(TreeNode* root)
{
stack<TreeNode*> s;
vector<int> result;
TreeNode* p = root;
TreeNode* r =new TreeNode(0);
while (p || !s.empty())
{
//走到最左边
if (p)
{
s.push(p);
p = p->left;
}
else
{
//取栈顶结点
p  = s.top();
//如果右子树存在,且未被输出
if (p->right&&p->right!=r)
{
p = p->right;
s.push(p);
//在走到最左
p = p->left;
}
//否则,访问栈顶结点并弹出
else
{
result.push_back(p->val);
//记录该结点
r = p;
s.pop();
//结点访问完后,重置p指针
p = NULL;
}
}
}
}
``````

### 最小的k个数

``````#include <vector>
#include <set>
using namespace std;
/*
解法1:
运用快排的思想
把数组的元素分成两组,右边比左边的都要大
数据都读到内存,并且修改数组
*/
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int>input,int k)
{
vector<int> res;
int n = input.size();
if (n == 0 || k > n || k <= 0) {
return res;
}
int start = 0,end = n-1;
int mid = partition(input, start, end);
while (mid != k-1)
{
if (mid > k-1)
{
end = mid - 1;
mid = partition(input, start, end);
}
else
{
start = mid + 1;
mid = partition(input, start, end);
}
}
for (int i = 0; i < k; i++) {
res.push_back(input[i]);
}
return res;
}

int partition(vector<int>& input,int start,int end)
{
int key = input[start];
while (start < end)
{
while (start < end && input[end] >= key)
end --;
input[start] = input[end];
while (start < end && input[start] <= key)
start++;
input[end] = input[start];
}
input[start] = key;
return start;
}
};
/*
解法2
用大根堆的思想
这里用multiset(内部红黑树,查找快(Ologn))保存k个元素,greater排序保证首个元素为最大
k个元素之后每个与multiset首个元素比较
适合海量数据,不修改原数组,修改都在multiset中
*/
class Solution2 {
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
int n = input.size();
if (n == 0 || n < k || k <= 0)
return vector<int>();
multiset<int,greater<int>> leastNumbers;
for (int i = 0;i < n;i++)
{
if (i < k)
leastNumbers.insert(input[i]);
else
{
multiset<int,greater<int>> ::const_iterator iter = leastNumbers.begin();
if (*iter > input[i]) {
leastNumbers.erase(iter);
leastNumbers.insert(input[i]);
}
}
}
vector<int> res(leastNumbers.begin(),leastNumbers.end());
return res;
}
};
``````