###利用康托展开求第K个全排列
-
利用康托编码的思路,假设有 n 个不重复的元素,第 k 个排列是 a1,a2,a3,...,an
-
那么我们把 a1 去掉,那么剩下的排列为 a2,a3,...,an,共计 n−1 个元素,n−1 个元素共有 (n−1)! 个排列
-
于是就可以知道
a1 = k/(n−1)! k2 = k%(n−1)!
###利用康托展开求第K个全排列
利用康托编码的思路,假设有 n 个不重复的元素,第 k 个排列是 a1,a2,a3,...,an
那么我们把 a1 去掉,那么剩下的排列为 a2,a3,...,an,共计 n−1 个元素,n−1 个元素共有 (n−1)! 个排列
于是就可以知道
a1 = k/(n−1)!
k2 = k%(n−1)!
###Merge sort
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void merge(vector<int>& array,int left,int pivot,int right){
int leftLen = pivot - left + 1;
###并查集
假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。 假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。
int uset[10001];
int find(int x){
if (x != uset[x]){
###auto_ptr的实现
#include <iostream>
#include <vector>
using namespace std;
template<class T>
##Heap sort
#include <iostream>
#include <vector>
#include <algorithm>
###Return value optimization
我们知道,在函数内如果需要以value方式返回对象,那么需要生成临时匿名对象,然后以这个临时对象去通过copy构造函数生成新的对象,最后调用析构函数销毁对象
A method(){
...
A temp;
...
return temp;
}
##Struct traits
在《Inside The C++ Object Model》这本书中有一个例子很有趣,就是在struct中放置一个一个元素的char数组,在运行时动态的构造可变长数组,如下:
struct mumble{
/*stuff*/
char pc[1];
};
typedef struct mumble* mumble_ptr;
mumble_ptr resize_mum_t(int size){
###Pointer to pointer
在删除链表的节点的时候,需要考虑是否删除的是头节点的问题,要保存前驱结点的信息,今天看到了一个巧妙地用法,利用二级指针
Code
/*
struct ListNode{
int val;
ListNode* next;
###Reverse list
反转list,使用递归方式
![][1]
如图所示,h为已经经过递归反转过的链表头,在递归之前保存的q指针已经是反转之后的尾指针,修改p指针为新的尾节点,返回h节点
###Code