ZklMao-Space
large picture of the cover

Data Struct01

输出二进制

void DEC_2_binSystem(size_t n, size_t x)
{
	std::vector<int> ans;
	while (n != 1)
	{
		//printf("%d", (n % 2));
		ans.push_back((n % 2));
		n /= 2;
	}
	ans.push_back((n % 2));
	//printf("%d \n", (n % 2));
	std::reverse(ans.begin(), ans.end());
	for (int i : ans)
		std::cout << i;
	std::cout << std::endl;
}

输出x进制

void DEC_2_xSystem(size_t n,size_t x)
{

}

字符统计

括号匹配

线性表

数组、单链表（各种操作插⼊、删除、遍历、排序、查找、创建、销毁、逆序） 、循环链表、双向链表

//单向链表结构体
struct OneWayNode;
struct OneWayNode
{
  int data;
  OneWayNode* next;
};
typedef struct OneWayNode Node_s;

// 双向链表结构体
struct TwoWayNode;
struct TwoWayNode
{
  int data;
  TwoWayNode* pre;
  TwoWayNode* next;
};
typedef struct TwoWayNode Node_d;

反转链表

Tip1: 解法一空间换时间

Tip2: 解法二三指针原地算法.

Node* listRserver(Node *header)
{
	Node* cur; 
	Node* pre;
	Node* t;
	cur = header->next;
	pre = header;
	t = cur->next;
	while (t)
	{

		cur->next = pre;
		pre = cur;
		cur = t;
		t = cur->next;
		if (!t)
		{
			cur->next = pre;
			pre = cur;
			cur = t;
		}
	}
	header->next = NULL;
	return pre;
}

Node* listRserver_v2(Node *header)
{
	Node* cur; 
	Node* pre;
	Node* t;
	cur = header->next;
	pre = header;
	t = cur->next;
	while (cur)
	{

		cur->next = pre;
		pre = cur;
		cur = t;
		if(t)
			t = cur->next;
	}
	header->next = NULL;
	return pre;
}

快慢指针

判断链表是否有环

快慢指针,不停转圈圈,总有一天会相遇.

判断两链表是否有交叉

空间换时间,备忘录法,地址哈希.若有相同点则能查询到.

队列

链队列、循环队列、优先级队列

栈

栈实现 栈应用:递归与非递归的转换

串操作

串基本操作、模式匹配、BF算法(暴力算法-逐一匹配)、KMP算法、最长公共子序列[题目待补充]

回文数:atoi() Tip: printf("%i\n", atoi(" -123junk"));

最大子段和

int getMaxSubSum(const int *arr,int lenght)
{
  int tsum = 0;
  int maxsum = 0;
  for(int i = 0;i < lenght;i++)
  {
      tsum+=arr[i];
      tsum > maxsum ? (maxsum = tsum) : (tsum = 0);
  }
  return maxsum;
}

最长公共前缀

Tip: O(n) 同时匹配.

回文串

Tip.回文串只有两种模式:

"aabaa"--单数回文串

"aabbaa" --双数回文串

验证回文串

// 对半比较
bool isPalindromic(const char* str1)
{
  std::string str = str1;
  int lenght = str.length();
  if(NULL == str1) return false;
  if(1 == lenght) return true;

  // [0 1 0] = 3 --单数回文串
  // [0 1 1 0] = 4 --双数回文串 
  if(lenght%2) // 单数回文串
  {
    int l = 0;
    int r = lenght - 1;
    while(l!=r)
    {
      if(str[l]!=str[r])
        return false;
      l++;
      r--;
    }
  }
  else // 双数回文串
  {
    int l = 0;
    int r = lenght - 1;
    while(r != (lenght/2))
    {
      if(str[l]!=str[r])
        return false;
      l++;
      r--;
    }
  }
  return true;
}

可构造最长回文串长度

Tip:Greed、统计

输入:"abccccdd"

输出:7

解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

现在我们考虑一下可以构成回文串的两种情况：

①字符出现次数为双数的组合[统计重复出现的字符] 2n+2n+2n+... = m(2n)

②字符出现次数为双数的组合+一个只出现一次的字符[统计只出现一次的字符、重复出现的字符] (2n-1)+2n+2n+2n+...

① [aa bb cc] -> abccba [aa bb cc dd] -> dabccbad : lenght = m(2n)

② [aa bb cc e] -> abcecba [aa bb cc dd eee] -> dabceeecbad m(2n)+k

int getMax_Pli_Str_Length(const char* str)
{
  // 统计
  std::map<char, int>kmap;
  for(size_t i = 0;i < strlen(str);i++)
    kmap.insert({str[i],0});

  for(size_t i = 0;i < strlen(str);i++)
    kmap[str[i]]++;
  
  // Greed
  int single = 0;
  int sum = 0;
  for(auto& iter : kmap)
  {
    if(!(iter.second%2))
    	sum+=iter.second;
    else
      single > iter.second ? (single) : (single = iter.second);
//    std::cout<<iter.first<<"-"<<iter.second<<std::endl;
  }
   return (sum+=single); 
}

最长回文子串

Tip1:中心扩散法O(n^2) Greed

// 确定中心 左右扩散 验证是否是回文串
void getMax_Pli_Substr(const char* str)
{
  int lenght = strlen(str);
  if(1 == lenght || NULL == str)
    return;
  //处理单数回文串,插入# 使单数回文串变为双数回文串.
  // zabbal -> z#a#b[#]b#a#l 双数回文子串[length = 11]
  // zabcbal -> z#a#b#[c]#b#a#l 单数回文子串[length = 13]
  // 经过这样处理无论是单数回文子串还是双数回文子串都可用对称处理.
  	std::string tstr;
  	for(size_t i = 0;i < lenght - 1;i++)
  	{
    	tstr+=str[i];
    	tstr+="#";
  	}
  	tstr+=str[lenght-1];
	std::cout<<tstr<<std::endl;

	std::string pilstr;
	std::string res;
	std::string s;
	// 定中心 
	for(int flage = 0; flage < tstr.length()-1;flage++)
	{
		int l,r;
		// 左右扩散 取子串
		l = flage;
		r = flage;
		if(l)l--;
		if(r<tstr.length())r++;	
		for(int i = l;i<=r;i++)
			s+=tstr[i];

		std::cout<<flage<<" "<<s<<std::endl;

		while(true)
		{
			if(isPalindromic(s.c_str()))
			{
				if(s.length()>=pilstr.length())
					pilstr=s;
				if(l)l--;
				if(r<tstr.length())r++;
					s.clear();	
				for(int i = l;i<=r;i++)
					s+=tstr[i];
			}
			else 
				break;
		}
//		std::cout<<flage<<" "<<s<<std::endl;
		s.clear(); 
	}

	std::string t;
	for(int i = 0; i < pilstr.length(); i++)
	{
		t=pilstr[i];
		if(t.compare("#"))
			res+=pilstr[i];
			t.clear();
	}
	std::cout<<res<<std::endl;
}

Tip2:manacher 算法O(n) DP

LCS

BF O(n^3)

DP On(n^2) 打表 滚动数组

解法一 二维表DP

void LCS_V1(const char* str1,const char* str2)
{
  	if(!str1||!str2)
		  return ;

	int length = (strlen(str1)*strlen(str2));

	int *record = new int[length];
	for(int n = 0; n < length;n++)
		record[n] = 0;

	std::string s1, s2;
	if(strlen(str1) > strlen(str2))
	{
		// 去较长的字符串为行 
		s1 = str2; //模式 // target
		s2 = str1; //串  // 被查找的串 source text	}
	else
	{
		s1 = str1;
		s2 = str2;
	}

    for(size_t j = 0; j < s2.length();j++)
    record[j] = (s1[0] == s2[j]);
  	for(size_t i = 1;i < s1.length();i++)
	{
		for(size_t j = 0; j < s2.length();j++)
    	{
    		if(j)
    			record[i*s2.length()+j] = (s1[i] == s2[j])+record[(i-1)*s2.length()+j-1];
    		else
    			record[i*s2.length()+j] = (s1[i] == s2[j]);
    	}
  	}
  
    int rank = 0;
    int t = record[0];
    for(int i = 0;i < length;i++)
  	{
  		t >= record[i] ? :(t = record[i],rank = i);
  	}
  	std::string res;
  	while(t)
  		res+=s1[t--];
  	for(int l = res.length()-1;l>-1;l--)
  	std::cout<<res[l];
  	delete []record;
}

解法二 备忘录DP

void LCS_V2(const char* str1,const char* str2)
{
  	if(!str1||!str2)
		  return ;

	std::string s1, s2,tstr,res;
	if(strlen(str1) > strlen(str2))
	{
		// 去较长的字符串为行 
		s1 = str2; //模式 // target
		s2 = str1; //串  // 被查找的串 source text
	}
	else
	{
		s1 = str1;
		s2 = str2;
	}
	for(int i = 0;i < s1.length();i++)
	{
		for(int j = 0;j < s2.length();j++)
		{
			if(s1[i] == s2[j])
			{
				while(i<s1.length()&&j<s2.length())
				{
					if(s1[i] == s2[j])
					{
						tstr+=s1[i];
						i++;
						j++;
					}
					else
						break;
			
				}
				if(res.length() < tstr.length())
					res=tstr;
				tstr.clear();
			}
		}
	}
	std::cout<<res<<std::endl;
}

解法三 滚动数组DP

// maxlenght(str1,str2) ,str1,str2 二者中最长者为串,另一个则为模式,开辟数组长度为(max(str1.length,str2.length))*2
void LCS_V3(const char* str1,const char* str2)
{
  	if(!str1||!str2)
		return ;

	int length = std::max(strlen(str1),strlen(str2))*2;

	int *record = new int[length];
	for(int n = 0; n < length;n++)
		record[n] = 0;

	std::string s1, s2;
	if(strlen(str1) > strlen(str2))
	{
		s1 = str2; //模式 
		s2 = str1; //串 
	}
	else
	{
		s1 = str1;
		s2 = str2;
	}

	for(size_t j = 0; j < s2.length();j++)
		record[j] = ((s1[0] == s2[j]));


	for(size_t i = 0;i < s1.length();i++)
	{
		for(size_t j = 0; j < s2.length();j++)
		{
      // 滚动 数组
			if(!(i%2))
			{
        //...........递推
			}
			else
			{
        //..........递推
			}
	
		}
		std::cout<<std::endl;
	}

//	for(int n = 0; n < length;n++)
//		std::cout<<record[n]<<" ";
//	std::cout<<std::endl;

	delete []record;
}

####　删除所有子串

二叉树

二叉树基本操作

// 叶子节点结构体
struct Node;
struct Node
{
  const char* data;
  Node* lc;
  Node* rc;
};
typedef struct Node TreeNode;

DLR

// 递归
void DLR(TreeNode* root)
{
  if(root->data)
    printf("%s ",root->data);
  if(root->l)
    DLR(root->l);
  if(root->r)
    DLR(root->r);
}

// 非递归,栈迭代写法
void DLR_iteration(TreeNode* root)
{
	if (!root) return;
	std::stack<TreeNode*> NodeStack;
	NodeStack.push(root);
	TreeNode* t = NULL;
	printf("%s ", NodeStack.top()->data);
	NodeStack.pop();
	// 迭代左子树 进栈顺序 右->左->中 出栈顺序 中->左->右
	if (root->lc)
		NodeStack.push(root->lc);
	while (!NodeStack.empty())
	{
		printf("%s ", NodeStack.top()->data);
		t = NodeStack.top();
		NodeStack.pop();
		if (t->rc)
			NodeStack.push(t->rc);
		if (t->lc)
			NodeStack.push(t->lc);
	}

	// 迭代右子树 进栈顺序 右->左->中 出栈顺序 中->左->右
	if (root->rc)
		NodeStack.push(root->rc);
	while (!NodeStack.empty())
	{
		printf("%s ", NodeStack.top()->data);
		t = NodeStack.top();
		NodeStack.pop();
		if (t->rc)
			NodeStack.push(t->rc);
		if (t->lc)
			NodeStack.push(t->lc);
	}
	std::cout << std::endl;
}

void DLR_iteration_v2(TreeNode* root)
{
	std::vector<const char*> ans;
	if (root == NULL) return ;
	std::stack<TreeNode*> s;
	s.push(root);

	while (!s.empty()) {
		TreeNode* top = s.top();
		s.pop();
		ans.push_back(top->data);
		if (top->rc) s.push(top->rc);
		if (top->lc) s.push(top->lc);
	}

	for (auto i : ans)
		std::cout << i << " ";
}

LDR

void LDR(TreeNode* root)
{ 
  if(root->l)
    LDR(root->l);
  if(root->data)
    printf("%d",root->data);
  if(root->r)
    LDR(root->r);
}

// 非递归 栈迭代写法
void LDR_iteration(TreeNode* root)
{
	if (!root) return;
	std::stack<TreeNode*> NodeStack;

	while (root || !NodeStack.empty())
	{
		// 将左节点全部压到栈中 
		while (root)
		{
			NodeStack.push(root);
			root = root->lc;
		}

// 1 最左 左节点出栈 / 栈顶元素出栈
		printf("%s ", NodeStack.top()->data);
		root = NodeStack.top();
		NodeStack.pop();
// 2 压入第二左节点(最左节点的父节点)的 右节点
// 若无,重复 1,2 步骤
		root = root->rc;
	}
}

void LDR_iteration_v2(TreeNode* root)
{
	if (!root) return;
	std::stack<TreeNode*> NodeStack;
	std::vector<const char*> ans;//存储结果集

	while (root || !NodeStack.empty())
	{
		while (root)//当前节点不能为空
		{
			NodeStack.push(root);//压栈
			root = root->lc;//继续往左走
		}

		//printf("%s ", NodeStack.top()->data);
		ans.push_back(NodeStack.top()->data);
		root = NodeStack.top();//此时左子树已经走到尽头,返回栈顶元素
		NodeStack.pop();//弹栈
		root = root->rc;//往右走一步

	}
	for (auto i : ans)
		std::cout << i << " ";
}

LRD

void LRD(TreeNode* root)
{
  if(root->l)
    LRD(root->l);
  if(root->r)
    LRD(root->r);
  if(root->data)
    printf("%s ",root->data);
}

// 非递归 栈迭代写法
void LRD_iteration(TreeNode* root)
{
	std::vector<const char*> ans;
	if (root == NULL) return;
	std::stack<TreeNode*> s;
	s.push(root);

	while (!s.empty()) {
		TreeNode* top = s.top();
		s.pop();
		ans.push_back(top->data);
		if (top->lc) s.push(top->lc);
		if (top->rc) s.push(top->rc);
	}

	std::reverse(ans.begin(), ans.end());
	for (auto i : ans)
		std::cout << i << " ";
}

二叉树一般BFS

void BFS_Nomal(TreeNode* root)
{
  std::queue<TreeNode*> NodeQueue;
  if(root)
  NodeQueue.push(root);
  while(!NodeQueue.empty())
  {
    printf("%d ",NodeQueue.front()->data);
    if(NodeQueue.front()->l)
      NodeQueue.push(NodeQueue.front()->l);
    if(NodeQueue.front()->r)
      NodeQueue.push(NodeQueue.front()->r);
    NodeQueue.pop();
  }
}

二叉树按层BFS

void BFS_layer(TreeNode* root)
{
  if(!root) returnl;
  std::stack<TreeNode*> PrintStack;
  std::queue<TreeNode*> GetQueue;
  PrintStack.push(root);
  while(!PrintStack.empty())
  {
    int i = 1;
    printf("Layer %d:",i);
    while(PrintStak.empty())
    {
      printf(" %d ",PrintStack.top());
        if(PrintStack.top()->r)
          GetQueue.push(PrintStack.top()->r);
        if(PrintStack.top()->l)
          GetQueue.push(PrintStack.top()->l);
      PrintStack.pop();
    }
    printf("\n");
    while(!GetQueue.empty())
    {
      PrintStack.push(GetQueue.front());
      GetQueue.pop();
    }
  }
}

二叉树按层BFS扩展:
打印树的最右孩子

BST

BST（二叉搜索树）查找思想也是二分思想 O(logn) 不会自动平衡
当插入节点为有序序列时，构建的树上的节点只有左孩子或右孩子，BST 将会退化为单向链表,最大复杂度O(N)。

AVL

AVL (平衡二叉树) 是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。所有节点左右 -1 <= 平衡因子 <=1 平均复杂度O(logn) 旋转次数最多logn次

单旋转(zagzag全右/zigzig全左):从根节点开始到所要插入的结点的父节点,所经父节点都在同一条直线上.即所经父节点都在上一节点的左或右,则只需要进行一次旋转即可复平衡

双旋转:(zagzzig右左/zigzag左右):从根节点开始到所要插入的结点的父节点,所经父节点不在同一条直线上.此情况需要做两次旋转才可复平衡.

R-B tree

(1) 根节点必须为黑色

(2) 外部节点(新增为保证树平衡的节点/使之成为真二叉树)均为黑色

(3) 其余节点: 若为红,则只能有黑孩子 //红之子、之父必黑 -- 控制红黑树深度

(4) 任意外部节点到根: 经过的黑节点数目相等 //黑深度 -- 控制红黑树平衡

提升变换后(映射为4阶B-树/(2,4)树) 每颗红黑树都对应于一棵(2,4)树(B树)

旋转四种情况同AVL--不平衡才旋转:

zagzag zigzig zagzig zig/zag

插入方式描述旋转方式
LL在 a 的左子树根节点的左子树上插入节点而破坏平衡右旋转
RR在 a 的右子树根节点的右子树上插入节点而破坏平衡左旋转
LR在 a 的左子树根节点的右子树上插入节点而破坏平衡先左旋后右旋
RL在 a 的右子树根节点的左子树上插入节点而破坏平衡先右旋后左旋
---

插入操作-双红缺陷 -- 违反//红之子、之父必为黑 规则.

情况1: 父、子双红

将该冲突部分子树中序遍历重新染色 使其在中序序列中恢复RBR这一模式.

情况2 : 叔、父双红

将叔、父节点均染成黑色

双红缺陷非法的原因: 提升变换后,在某个三叉节点中插入红关键码,使得原黑关键码不在居中 //RRB或BRR,出现相邻红色关键码.调整后的效果相当于提升变换后的B-树拓扑结构不变,但在新的四叉节点中,三个关键码的颜色改为RBR.

删除操作-双黑缺陷(提升转换后对应下溢缺陷)

情况1: 兄弟节点至少还有一个红孩子

删除该节点后通过一次zag/zig旋转即可修复.

情况2: 父节点为红色 兄弟节点均为黑色

删除该节点后,将父节点染为黑色,兄弟节点染为红色.

情况3: 父节点、兄弟、当前节点都是黑色

删除该节点后将兄弟节点染为红色.

情况4: 父节点、当前节点均为黑色,当前节点为红色

将父节点与当前节点颜色对换,父节点做一次旋转操作,在经过一轮情况1或2的重染色即可完成修复.

B-Tree[B族搜索树]

B+[扩展]

B-[扩展]

B*[扩展]

替罪羊树

字典树

树构建[扩展]

查找

二分查找

int find_bin(int target,int arr[],int start,int end)
{
	int rankMid = (start+end)/2;
	if(target == arr[rankMid]) return rankMid;
	if(target < arr[rankMid]) find_bin(target,arr,start,rankMid);  
	if(target > arr[rankMid]) find_bin(target,arr,rankMid+1,end);
}

线性查找-lineselectO(kn)[扩展]

索引

hashTable

散列冲突

M = 90001 hash(key) = key % M

1%10 = 11%10 -> 5153.1876 %90001 = 6278.2001%90001

解决办法 将装填因子(装填元素个数/表总容量)降低 或者加长散列表.常规的操作是，当装填因此大于0.7时，就应该进行扩充了.

B-Tree[B族搜索树]

B-tree

平衡的多路搜索树.

在多级存储系统中使用B-树,可针对外部查找,大大减少I/O次数.批量访问,超级节点.

m阶-m路

上限:内部节点各有不超过m-1个结点的关键码 不超过m个分支.
下限:树根分支树:节点数至少为2, 2<=n+1 其余节点分支数n+1 >= m/2上取整

插入会发生上溢[小概率]-分裂 删除会发生下溢[小概率]-借出关键码/合并

B树长高:[再分裂] 发生上溢且上溢情况传播到根节点,这时可将第一次发生上溢的节点取其中位数作为新子树的根节点,连入原B树中.

B+tree

B+相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上.

八大排序[按考察重点排序]

Quick Sort

void QuickSort(int arr[],int L,int R)
{
  int i,j,key;
  i = L;
  j = R;
  key = arr[(L+R)>>1];
  while(i<=j)
  {
    while(arr[i] < key) i++;
    while(arr[j] > key) j--;
    if(i <= j)
    {
      std::swap(arr[i],arr[j]);
      i++;
      j--;
    }
  }
  // 左部分递归
  if(L < j) //防止越界判断
    QuickSort(arr,L,j);
  // 右部分递归
  if(i < R) //防止越界判断
    QuickSort(arr,i,R);
}

Shell Sort

Tip:分割 嵌套调用其他算法.

void ShellSort(std::vector<int>& arr, int low, int high)
{
	int mid = (low + high) >> 1;

	if (low == high) return;

	ShellSort(arr, low, mid);
	ShellSort(arr, mid + 1, high);

	BubleSort(arr, low, high);
}

Merge Sort

void Merge(std::vector<int>& arr,int L,int mid, int R)
{
	//std::cout << "L<"<<L << "> m<"<<mid <<"> R<" << R << ">"<<std::endl;
	std::stack<int>Lstack, Rstack;

	int m = mid;
	int tl = L;
	int tr = R;

	// 左部分入栈 [L - mid] // [小-大]从右往左入栈
	while (L <= mid)
	{
		Lstack.push(arr[mid]);
		mid--;
	}

	// 右部分入栈 (mid - R] // [小-大]从右往左入栈
	m++;
	while (m <= R)
	{
		Rstack.push(arr[R]);
		R--;
	}

	// 左右比较 出栈 归并
	while (true)
	{
		// 左右比较 出栈
		if (!Lstack.empty())
		{
			if (!Rstack.empty())
			{
				if (Lstack.top() < Rstack.top())
				{
					arr[tl] = Lstack.top();
					Lstack.pop();
					tl++;
				}
				else
				{
					arr[tl] = Rstack.top();
					Rstack.pop();
					tl++;
				}
			}
			else
			{
				arr[tl] = Lstack.top();
				Lstack.pop();
				tl++;
			}
		}
		else
		{
			if (!Rstack.empty())
			{
				arr[tl] = Rstack.top();
				Rstack.pop();
				tl++;
			}
		}

		if (Lstack.empty()&&Rstack.empty())
			break;
	}
}

void MergeSort(std::vector<int>& arr, int L, int R)
{
	int mid = ((L + R) >> 1);
	if (L == R) return;

	MergeSort(arr, L, mid);
	MergeSort(arr, mid + 1, R);

	Merge(arr, L, mid, R);
}

Heap Sort

Insert Sort

void InsertSort_v2(std::vector<int>& arr, int low, int high)
{
	for (int i = low; i < high; i++)
	{
		for (int j = i+1;j<=high;j++)
		{
			// 和前面有序序列比较 插入
			int n = i;
			while (n>=low)
			{
				if(arr[n] > arr[j])
					std::swap(arr[n], arr[j]);
				n--;
			}
		}
	}
}

void InsertSort(std::vector<int>& arr, int low, int high)
{
	//6, 1, 3, 9, 2
	// 从第二开始左往右拿牌 并向左比较插入
	for (int i = low+1; i < high + 1; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			int k = i;
			while (k>0)
			{
				if (arr[k] < arr[k-1])
				{
					std::swap(arr[k], arr[k - 1]);
				}
				k--;
			}
		}
	}
}

Select Sort

// 选择最值 往未维护序列的最左或最右末尾元素交换
void SelectSort(std::vector<int>& arr, int low, int high)
{
	for (int i = low; i < high + 1; i++)
	{
		int index = i;
		for (int j = i+1; j < high+1; j++)
		{
			if (arr[j] < arr[index])
			{
				index = j;
			}
		}
		std::swap(arr[i], arr[index]);
	}
}

Buble Sort

void BubleSort(std::vector<int>& arr, int low, int high)
{
	for (int i = low; i < high;i++)
		for (int j = low; j < high; j++)
			if (arr[j] > arr[j+1])
				std::swap(arr[j], arr[j+1]);
}

Bucket Sort

Bitmap Sort

!!!记住 一个字节 = 8 位!!!

Sort algorithem stablitiy

时间复杂度

算法思想

Enum

Recursion

Divide and Conquer

Decrease and Conquer(pruning)

DP(0-1pakge 8-queue Fibonacci[斐波那契] step[台阶问题-爬楼梯] 图DP-走到某处花费最小代价 最短编辑距离 找零钱)

Fibonacci

// 输出 n 内的斐波那契数列
void Fibonacci_DP(int n)
{
	int res[2]{ 0,1 };
	int i = 2;
	while (res[(i % 2)] < n)
	{
		std::cout << res[(i % 2)] << " ";
		res[(i % 2)] = res[0] + res[1];
		i++;
	}
}

Upstairs

有 1 或 2 两种步长 到第n级台阶有多少种走法

Tip: 若只有 1 2 两种 步长 则为 经典斐波那契问题,即 第n级台阶 即为斐波那契数列的第n+4项

// v1 source
void Upstair_DP_Fibonacci(int n)
{
	int res[2]{ 0,1 };
	int i = 2;
	while (i < (n+4))
	{
		std::cout << res[(i % 2)] << " ";
		res[(i % 2)] = res[0] + res[1];
		i++;
	}
}
// v2
void Upstair_DP(int n)
{
	int res[2]{ 1,2 };
	int i = 2;
	while (i < (n+2))
	{
		std::cout << res[(i % 2)] << " ";
		res[(i % 2)] = res[0] + res[1];
		i++;
	}
}

0-1 pakge

Tip:DP 二维表

void Knapsack()
{
	std::vector<int> price{ 3,1,5,6,9 };
	std::vector<int> weight{ 1,4,3,2,2 }; // 1 + 2 -> 3 + 9 = 12
	const int _capacity = 3;
	int table[5][_capacity];

	// 初始化列
	for (int i = 0; i < _capacity; i++)
		if (i+1 >= weight[0]) table[0][i] = price[0];
		else table[0][i] = 0;
	// 初始化行
	for (int i = 1; i < weight.size(); i++)
		if (weight[i] > 1) table[i][0] = table[i - 1][0];
		else table[i][0] = std::max(table[i-1][0], table[i - 1][0]+price[i]);

	// 列
	for (int capacity = 1; capacity < _capacity; capacity++)
	{
		for (int row = 1; row < weight.size(); row++)
		{
			if (weight[row] > capacity) //不拿: 新增加的容量还是放不下这件物品继承上方的最优记录
			{
				table[row][capacity] = table[row - 1][capacity];
			}
			else //拿: 新增加的容量可以放下这件物品 最优解:max(上方的记录,当前容量 - 占用该物品容量 的最优记录 +当前物品)
			{
				table[row][capacity] = std::max(table[row - 1][capacity], table[row - 1][capacity - weight[row]] + price[row]);
			}
		}
	}
	std::cout << table[4][2] << std::endl;
}

完全背包(指定某件物品数量为无限)

Tip:

不拿: 新增加的容量还是放不下这件物品继承上方的最优记录

拿: 新增加的容量可以放下这件物品 最优解:max(上方的记录,当前容量 - 占用该物品容量 的最优记录 +当前物品价值 + 剩余容量装下 指定物品个数*价值[此处需要回头查表计算剩余容量是否能装下 指定的物品,并计算能装几个,装下指定物品的总价])

混合背包

Tip: 思路同上完全背包，最优解:max(上方的记录,当前容量 - 占用该物品容量 的最优记录 +当前物品价值 + 剩余容量装下 剩余容量的最优解 [此处需要回头查表 剩余容量能装下物品价值的最优解])

凑硬币硬币问题(用最少硬币凑出指定数额)

Tip:打表 一维数组 前一个的最优解+1 即为 当前最优解

// Gather together a coin
// 举个例子:
// coins{1,2,3,5}
// 找币记录(所需硬币最少个数)res[]: 0 1 1 1 2 1 2 2 2 3 2
//                下标(待找面额):  0 1 2 3 4 5 6 7 8 9 10
// 前提:n>=coins[i]
// 转移公式 res[n] = min(res[n - res[n - 1]]+1/*待找数额的前一条记录*/,res[n - coins[i]] + 1/*枚举硬币面额小于等于待找数额的找币最优记录并+1: 当前面额 - 硬币面额coins(i) +1*/)
int Conis(std::vector<int>& coins, int amount)
{
	std::vector<int> res{0,1};
	res.resize(amount + 1);
	int n = 2;
	while (n <= amount)
	{
    // 默认取 前一记录+1 为当前最优解
		int min = res[n - res[n - 1]]+1;
		for (int i = 0;i<coins.size();i++)
		{
      // 状态转移 在小于等于待找面额的硬币中找面值最接近的硬币的找币记录的最优解
			if (n>=coins[i])
			{
				min > res[n - coins[i]] + 1 ? (min = res[n - coins[i]] + 1) : min;
			}
		}
    // 最优解 = min(前一记录,在小于等于待找面额的硬币中找面值最接近的硬币的找币记录的最优解)
		res[n] = min;
		n++;
	}
	return res[amount];
}

int main(int argc, char*args[])
{
	std::vector<int> coins{ 1,2,3,5 };
	std::cout << Conis(coins, 10)<<std::endl;
}

8-queue

Tip : O(n^2) 堆栈法. 二维数组遍历 堆栈 棋盘染色 回溯

Traceback (DFS迷宫、DFS最短路、[DFS A-B 所有路径])

Branch and Bound

Greed(最小生成树[prime Kuskal]、Dijkstra最短路径)

概率算法(求PI)

void getPi(int k)
{
  double sum = 1.0;
  int n = 1;
  while(n<=k)
  {
    sum+=pow(-1,k)*(1/((2*k)+1))
  }
  return sum*4.0;
}

site logo

And if we

© 2025 ZklMao-Space