Welcome to BeckoninGshy's Bolg

7月 31, 2019

单源最短路径算法

算法流程：

对于图G（V，E）维护一个集合S,存放已经被访问过的顶点（准备期间只有源点s），每次从集合V-S中选择与起点s的距离最小的一个顶点（记为u），访问u并加入集合S，并令u为中介点，更新起点s与所有从u能达到的顶点v之间的最短距离。这样执行n次（n为顶点个数），直到集合S包含所有顶点。

适用范围：有向无负权图

1.优先队列版复杂度O(ElogE)

#define INF 0x3f3f3f3f

struct qnode{
    int v,d;
    qnode(int _v=0,int _d=0):v(_v),d(_d){}
    friend bool operator <(const qnode &r)const{
        return d>r.d;
    }
};

struct Edge{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
 
const int MAXN = 100010;
vector<Edge> E[MAXN];
//是否访问标志
int vis[MAXN];
//到源点的最短距离，准备期间设置为无穷大，表示不可及。
int dis[MAXN]; 
//加边
void add_edge(int u,int v,int w){
    E[u].push_back(Edge(v,w));
}
//初始化(从0开始编号)
void init(int n){
    for(int i=0;i<n;i++){
        E[i].clear();
    }
}

void Dijkstra(int s,int n){
    for(int i=0;i<n;i++)vis[i] = 0;
    for(int i=0;i<n;i++)dis[i] = (i == s ? 0 : INF);
    priority_queue<qnode> q;//声明优先队列：每次从队列中取出的是具有最高优先权的元素。
    //优先队列第一个参数为比较类型，第二个为容器类型，第三个为比较函数。
	//greater实现小顶堆//less 实现大顶堆（默认为大顶堆）
	q.push(qnode(s,dis[s]));//先将源点推进优先队列
	qnode temp;
    while(!q.empty()){//当队列空时所有边已被访问
        temp = q.top();q.pop();
        //当前顶点
        int u = temp.v;
        if(vis[u])continue;
        vis[u] = true;
        //每一条与u相邻的边都要更新
        for(int i=0;i<E[u].size();i++){
            //邻点
            int v = E[u][i].v;
            //权重
            int cost = E[u][i].cost;
            //松弛操作，更新权重时机
            if(!vis[v] && dis[u] + cost < dis[v]){
                dis[v] = dis[u] + cost;
                //把每一个更新的长度加进队列
                q.push(qnode(v,dis[v]));
            }
        }
    }
}

2.邻接矩阵版复杂度O(N^2) 记录路径版

const int MAXN = 10000;
const int INF = 0x3f3f3f3f;
bool vis[MAXN];//访问记录
int pre[MAXN];//父节点
int cost[MAXN][MAXN];//权重矩阵
int lowcost[MAXN];//记录最短路径

//初始化矩阵为无穷。
void Init(int N){
    for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cost[i][j] = INF;
		}
	}
	//如果INF是满十六进制表示。如：const int INF = 0x3f3f3f3f;
	//则可以使用memset(cost,INF,sizeof(cost));
}

//cost:权重矩阵,lowcost:最短路径，n:数据范围,beg:源点
void Dijkstra(int cost[][MAXN],int lowcost[],int n,int beg){
	//初始化各值
	for(int i = 0; i < n; i++){
		lowcost[i] = INF;
		vis[i] = false;
		pre[i] = -1;
	}
	//设置源点
	lowcost[beg] = 0;
	for(int j = 0; j < n; j++){
		int k = -1;
		int Min = INF;
		//找到目前最短路径数组中到源点最短的节点。
		for(int i = 0; i < n; i++){
			if(!vis[i] && lowcost[i] < Min){
				Min = lowcost[i];
				k = i;
			}
		}
		//找不到，说明节点都已经全部访问。
		if(k == -1)break;
		//记录该节点。
		vis[k] = true;
		//松弛操作。更新每条与该节点相连并且还未访问到的节点的路径。
		for(int i = 0; i < n; i++){
			if(!vis[i] && lowcost[k] + cost[k][i] < lowcost[i]){
			    //发现一条更短的路径，更新。
				lowcost[i] = lowcost[k] + cost[k][i];
				//更新父节点。
				pre[i] = k;
			}
		}
	}
}

解题通用思路

做关于Dijkstra算法的题，通常不会只出一个裸的寻找最短路径，而是会给出一个或多个次级标尺。通常不会超出三个维度：

边权
点权
多少条最短路径，或该路径的长度。

通常是多个维度组合起来寻找最优解。

遇到这类问题，可通过将每条最短路径都保存下来，依次进行处理。

vector<int> paths[MAXN];
//在其松弛操作中，将路径保存
for(int j = 0; j < N; j++){
	if(!vis[j] && G[k][j] != INF){
		if(dis[j] > dis[k] + G[k][j]){
			dis[j] = dis[k] + G[k][j];
			paths[j].clear();
			paths[j].push_back(k);
		}else if(dis[j] == dis[k] + G[k][j]){
			paths[j].push_back(k);
		}
	}
}
vector<vector<int> > ans;//用于存放每一个最短路径
vector<int> p;
//计算每条路径，注意，这样的路径是反序并且不包含源点的，如需要，则单独计算。
void makeMinPath(vector<vector<int> > &ans,vector<int> p,int j){
	if(j == 0){
		ans.push_back(p);
		return;
	}
	for(int i = 0; i < paths[j].size(); i++){
		p.push_back(paths[j][i]);
		makeMinPath(ans,p,paths[j][i]);
		p.pop_back();
	}
}

之后就可以根据要求计算每一条路径，并挑出符合问题的解了。

AVL树详解

7月 19, 2019

需求

我们在学习二叉搜索树的时候，发现无论是查找还是插入元素在理想情况下都可以达到O(logN)级别，但是由于插入的顺序，数的结构也会不同，这种理想情况很难保持甚至最坏的情况会退化成链表。导致性能下降。这时就需要一个能实现高度自动平衡的树结构。就出现了平衡树，
今天讲的是平衡树的一种：AVL树。

初识AVL树

AVL树得名与 Adelson-Velsky和 Landis两位发明者的首字母，它是自平衡的二叉搜索树，具有二叉树搜索树的性质（左子树的结点都比当前结点小，右子树都比当前结点大），同时它又是平衡二叉树，能够自适应高度。在AVL树中，任意节点的两个子树的高度差不超过1，这也是将不平衡的子树调整为平衡子树的重要指标。

AVL树的调整策略

AVL是在进行插入节点时，通过检测是否破坏了平衡条件，进而通过进行一定程度的节点旋转来达到整棵树的平衡。

简单情形

我们知道一个树如果只有一个或两个时，树是平衡的。所以问题会出现在第三个节点插入的位置，如果是下图：

则是平衡的。

先来看最简单的不平衡情况：

当把根节点的右节点“提”到根节点的位置，将旧根节点当新的根节点的左子节点。就可达到平衡状态。

具体到树中，可以归结为以下四种情况：

1.左旋

上述是最特殊的只有三个节点的情况，下面我们将它代入一般的二叉树来研究：

对于一个节点，当右子树的高度比左子树高一个高度的时候，此时新进来的节点也需要插入右子树。当然，如果新插入节点以后，右子树还维持原来的高度，那么这颗树就还是平衡的。问题出在当新插入节点后，右子树的高度增加了，这时破坏了平衡树两个子树的高度差不超过一的性质，就需要调整使其达到平衡状态。这时，我们首先考虑比较好处理的情况，也就是插在右子树的右边的情况。

调整的策略：

此时我们需要将当前节点的右子树“提”到当前节点的位置，当前节点“下降”为其右子树的左子树，具体操作过程如图：

调整之后变为：

到此，树变成了平衡的，由于整棵树要往左边旋转，所以左旋的操作就右子树的地位上移，根节点的地位下降。

2.右旋

现在我们有了左旋的经验，很容易推出需要进行右旋操作的时机：

对于一个节点，当左子树的高度原先就比右子树的高度多一时，插入节点又使左子树的高度增加，并且插在了左子树的左边的时候，就需要调整了：

树变为平衡的。

至此，单旋转就学习完毕，下面学习双旋转。

3.右左旋

前面我们学习单旋转时，插入节点都是与其子树同向的位置，这种情况由于倾斜的状况比较明显，所以只要找到中间的位置，将其“提”到“根节点”的位置，就可以达到平衡。而当其中子树失去平衡是由于所处子树往相反的方向插入，导致倾斜的状况不容易看出，所以需要经过两次旋转来达到平衡状态。
如下图：

我们可以观察到，在当前的结点的右子树的倾斜情况与我们刚才介绍到的右旋的情况很相似：

所以将右子树按右旋处理，处理之后变为：

这时我们惊奇的发现它变成了我们前面介绍的左旋前时的情形。这种情况我们已经会处理了：将右子节点“提”上来，把当前“根”节点变为右子节点的左子树，最后就调整到平衡状态了。

4.左右旋

同样地，左右旋也可通过先将左子树左旋，再将当前根节点右旋的调整来达到平衡状态。

先将左子树左旋：

再进行右旋：

达到平衡状态。

到此，二叉树的调整策略就介绍完了，下面上代码：

typedef struct AVLNode* AVLTree;
struct AVLNode{
	int data;
	AVLTree left;
	AVLTree right;
	int height;
	AVLNode(int data):data(data){
		left = NULL;
		right = NULL;
		height = 0;
	}
};

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

int GetHeight(AVLTree t){
	if(!t) return 0;
	return t->height;
}

//右旋 
AVLTree SingleRightRotation(AVLTree A){
	//先记录左子树,将左节点的右子树变为根节点的左子树，再将根节点作为左节点的右子树。 
	AVLTree l = A->left;
	A->left = l->right;
	l->right = A;
	//更新两节点的高度。 
	A->height = Max(GetHeight(A->left),GetHeight(A->right))+1;
	l->height = Max(GetHeight(l->left),A->height) + 1;
	return l; 
}

//左旋 
AVLTree SingleLeftRotation(AVLTree A){
	//先记录右子树,将右节点的左子树变为根节点的右子树，再将根节点作为右节点的左子树。 
	AVLTree r = A->right;
	A->right = r->left;
	r->left = A;
	//更新两节点的高度。 
	A->height = Max(GetHeight(A->left),GetHeight(A->right)) + 1;
	r->height = Max(GetHeight(r->right),A->height) + 1;
	return r;
}

//右左旋 
AVLTree DoubleRightLeftRotation(AVLTree A){
	//将左子树右旋 
	A->right = SingleRightRotation(A->right);
	//再将当前节点左旋 
	return SingleLeftRotation(A);
} 

//左右旋 
AVLTree DoubleLeftRightRotation(AVLTree A){
	//将右子树左旋 
	A->left = SingleLeftRotation(A->left);
	//再将当前节点右旋 
	return SingleRightRotation(A);
} 

AVLTree Insert(AVLTree T, int X){
	if(!T){
		T = new AVLNode(X);
	}else if(X < T->data){
		T->left = Insert(T->left,X);
		if(GetHeight(T->left)- GetHeight(T->right) == 2){
			if(X < T->left->data){ //右旋 
				T = SingleRightRotation(T);
			}else{ //左右旋 
				T = DoubleLeftRightRotation(T);
			}
		}
	}else if(X > T->data){
		T->right = Insert(T->right,X);
		if(GetHeight(T->right)- GetHeight(T->left) == 2){
			if(X > T->right->data){ //左旋 
				T = SingleLeftRotation(T);
			}else{ //右左旋 
				T = DoubleRightLeftRotation(T);
			}
		}
	}
	//更新高度 
	T->height = Max(GetHeight(T->left),GetHeight(T->right))+1;
	return T;
}

106-从中序与后序遍历序列构造二叉树

7月 13, 2019

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历

1	inorder = [9,3,15,20,7]

后序遍历

1	postorder = [9,15,7,20,3]

返回如下的二叉树：

Solution

TreeNode* makeTree(vector<int>& postorder, int& postindex, vector<int>& inorder,int left, int right){
        if(left <= right){
            for(int i = 0; i < inorder.size(); i++){
                if(postorder[postindex] == inorder[i]){

                    TreeNode* root = new TreeNode(postorder[postindex--]);
                    root->right = makeTree(postorder,postindex,inorder,i+1,right);
                    root->left = makeTree(postorder,postindex,inorder,left,i-1);  
                    return root;
                }
            }
        }
        return NULL;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int postindex = postorder.size()-1;
        return makeTree(postorder,postindex,inorder,0,inorder.size()-1);
    }

思路：

根据后序遍历的特点，每棵子树的根节点总是最后遍历到。

所以用一个按引用传递的指针指向后序数组的末尾，用该值在中序数组中查找，并将该值当做当前树的根节点。

该值位置的左边为以该节点为根节点的左子树的范围，位置右边为右子树的范围，然后不断更新这个范围，递归下去即可，注意边界值。

正则表达式全解——正则基础

6月 02, 2019

正则表达式

正则基础

^

表示一行的开始

$

表示一行的结束

[…]

表示其中的字符是选择性（逻辑或）的，要么是a,要么是b,要么是…。

c[a|b]t 可以匹配到cat、cbt
[a-z]、[0-9]、[0-9A-Za-z]是支持的。
[^$] 匹配空行
像 . * + ? 这些词在[]中仅表示字面的意思，利用这一特性，如果想表示原本含义，例如要匹配 . ，可以写为[.]

[^…]

表示匹配不是其中的字符。为上一条的取反

-

连字符，表示一个范围，见上一条。

如果要匹配 - ，请将 - 写在开始位置，如果[-a-z]，匹配-或者是小写字母。

.

表示任意字符（除了换行符），

|

表示或者

(cat|dog) 表示要么cat,要么dog,
注意：这和[…]不同的是，[…]匹配其中的单个字符，(..|…)可以匹配不同的字符组。

?

表示可选项，类似于单选框，匹配零个或一个。

+

表示出现一次或多次。

*

表示匹配零次或多次。

{min,max}

表示匹配之前的子表达式重复min到max次。（闭区间）

{count} 表示匹配count次。

括号与反向引用

([0-9]){2,3}add\1 \1表示第一个括号中的内容再次使用。

转义字符

像 . * + ? 这些词在正则中有特殊的含义，要想使用它原本的含义，使用\来进行转义。

(…)

括号的作用：1.限制多选结构，2.分组，3.捕获文本。

一些特殊的字符

\t 制表符
\n换行符
\r 回车符
\s 任何空白字符(例如空格符、制表符、换行符等)
\S 除\s之外的任何字符(所以用(\s|\S) * )来表示任意字符。
\w 相当于[a-zA-Z0-9] 所以经常用\w+来表示一个单词
\W \w取反，也就是[^a-zA-Z0-9]
\d 相当于[0-9] 也就是数字
\D \d取反，也就是[^0-9]

写在大一期末考试之际

6月 01, 2019

写在大一期末考试之际

最近发生了很多各种各样的事，面对即将到来的期末考试，自己真的很没有底气，因为只有自己知道，对于大部分的课程，学的是如何糟糕。我不看重的课程不说，但数学学科的课程自己也没学到什么，一方面是老师的原因，但最多的是自己的问题，学习的重心绝对的向专业偏移，即使是专业，每天学的都是些业务类的技术，如果是这样，我觉得我可以立即辍学，这也不是我上大学的初衷，一定要向研究的方向转变，把数学基础提上来才是我大学应该做的事，大学时光1/4已经过去了，自己却没有调整到合适的状态，实属不应该。不过，也有些收获，算法竞赛这块是我没有预料到的，同时回想自己大一上学期学算法的时候是我最想要的状态，我不知道自己是不是喜欢，但无暇他顾地专心只搞一件事是我想要的，而通过学习它我可以进入这种状态，后来学长又找我说想打acm，我知道这个的难度，也知道意味着什么，但是我觉得人应该有些梦想，先让我做一年试试。

同时，我的学习方法也有很多的不足，很低效，我觉得得花些时间来调整下，通常都是学的快，忘的更快，再要用的时候，又要重新学（虽然会快很多），这也是我写博客项目的原因，一个是记录，一个是整理。记录是记录时光的流逝，整理是整理学习成果。要好好把博客写好了。慢就是快，就像姜文说的：步子迈大了，容易扯着蛋。我时刻提醒自己，一定不能浮起来，要沉下去。

LeetCode-98-验证二叉搜索树

5月 30, 2019

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

Solution1：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<TreeNode*> v;
        inorder(root,v);
        for(int i = 1; i < v.size(); i++){
            if(v[i-1]->val >= v[i]->val){
                return false;
            }
        }
        return true;
    }
    
    void inorder(TreeNode* node, vector<TreeNode*> &v){
        if(!node) return;
        inorder(node->left,v);
        v.push_back(node);
        inorder(node->right,v);
    }
};

利用二叉搜索树的中序遍历是升序的特性。

将每个元素push进一个vector中，如果vector中元素不是按升序排列，这该树不是二叉搜索树。

Solution2：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root,NULL,NULL);
    }
    //返回该结点是否在指定区间内。
    bool helper(TreeNode *node, TreeNode *min, TreeNode *max){
        if(!node) return true;
        if((min && node->val <= min->val) || (max && node->val >= max->val)) return false;
        //左子节点的值不能比当前结点的值大，右节点的值不能不当前结点小。
        return helper(node->left, min, node) && helper(node->right, node, max);
    }
};

根据题目给的三条性质，所有结点及其下面的所有结点均可以构成二叉搜索树，

所以对于非叶子结点，可以以当前结点为根据，划分区间，区间内的点必须比左端点大，比右端点小。

用一个递归函数来不断更新该区间，判断该结点是否在区间内即可。

LeetCode-922-按奇偶排序数-II

5月 30, 2019

922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

Solution:

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i = 0;
        int len = A.size();
        int j = 1;
        while(1){
            while(i < len && (A[i] & 1) == 0) i+=2;
            while(j < len && (A[j] & 1) != 0) j+=2;
            if(i >= len || j >= len) break;
            std::swap(A[i],A[j]);
            i+=2;
            j+=2;
        }
        return A;
    }
    
};

思路：

设置两个指针。
一个指针只走奇数下标，一个指针只走偶数下标。
当碰到不符合条件（奇数下标的值不是奇数，偶数下标的值不是偶数）就停下并交换两个值，之后接着走，直到指针越界为止。

看评论有人用栈或者另外准备两个数组的，速度比原地交换还快，不知道为什么。实现也比较简单，就不赘述了。

LeetCode-92-反转链-II

5月 30, 2019

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

Solution：

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    int chang_len = n-m+1;//逆置的结点个数。
    struct ListNode* prevHead = NULL;//记录开始逆置结点的前驱。
    struct ListNode* result = head;//用于最后返回。
    while(head && --m){ //到达开始逆置的位置。
        prevHead = head;
        head = head->next;
    }
    
    struct ListNode * modify_list_tail = head;//将该结点之前当前开始逆置的结点。
    struct ListNode * newHead = NULL;//用于逆置结点。
    while(head && chang_len){
        struct ListNode * next = head->next;
        head->next = newHead;
        newHead = head;
        head = next;
        chang_len--;
    }
    //此时head就到了n处，modify_list_tail就到了逆置段的最后一个结点。
    //将modify_list_tail 与 head连接。
    modify_list_tail->next = head;
    
    if(prevHead){ //如果prevHead不为空，说明不是从第一个几点开始逆置的。 m > 1。
        prevHead->next = newHead;
    }else{
        result = newHead; //如果prevHead为空， 则说明是从第一个就开始逆置，直接将逆置后的头结点赋值给res，m=1。
    }
    return result;
}

思路：

解决这个问题主要是要找关键节点。

这个题的关键节点为：

要逆置的结点的前一个结点（prevHead）。
要逆置的第一个结点。（直接用head来探测）。
要逆置的最后一个结点。（此结点为逆置前的第一个结点，逆置后就变为了最后一个结点）
要逆置的最后一个结点的后一个结点。（在用head逆置后，head就到了逆置后的这个结点。）

找到前两个结点。
从m开始，到n，一共需要n-m+1个结点需要逆置。所以要逆置n-m+1次。
将逆置后的尾结点与逆置段后面一个结点相连。
如果结点是从开始逆置，将逆置后的头结点返回。否则，将前面的结点与逆置后的头结点链接返回。

LeetCode-88-合并两个有序数组

5月 30, 2019

88. 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

Solution:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int tail = m + n -1;
        int nums1tail = m-1;
        int nums2tail = n-1;
        while(nums1tail >= 0 && nums2tail >= 0){
            if(nums1[nums1tail] >= nums2[nums2tail]){
                nums1[tail] = nums1[nums1tail--];
            }else{
                nums1[tail] = nums2[nums2tail--];
            }
            tail--;
        }
        while(nums2tail >= 0)
            nums1[tail--] = nums2[nums2tail--];
        while(nums1tail >= 0)
            nums1[tail--] = nums1[nums1tail--];
    }
};

与归并排序的merge代码类似，不过是从数组的末尾往前比较。

LeetCode-78-子集

5月 30, 2019

78. 子集

Solution1：

对于每一项相对每个子集来说，都有放与不放两种选择。

创建一个放元素的递归函数，该函数的作用为将一项放和不放两种选择进行描述。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> item;
        result.push_back(item);
        
        putitem(0, nums, item, result);
        return result;
    }
    //把一项放进result中。
    void putitem(int i, vector<int>& nums,vector<int> item, vector<vector<int> > &result){
        if(i == nums.size()){
            return;
        }
        //每个元素都有放和不放两种选择。
        //放
        item.push_back(nums[i]);
        result.push_back(item);
        putitem(i+1, nums, item, result);
        //不放
        item.pop_back();
        putitem(i+1, nums, item, result);
    }
};

Solution2：

遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集

class Solution {
public:
    vector<vector<int> > subsets(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> item;
        result.push_back(item);
        for(int i =0; i < nums.size(); i++){
            int s = result.size();
            for(int j = 0; j < s;j++){
                result.push_back(result[j]);
                result[j].push_back(nums[i]);
            }
        }
        return result;
    }
};

Solution3（位运算）：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > result;
        //子集一共有2的n次方种，使用位运算来解。
        //每一位代表一个元素。
        //如，100 代表[3]、011代表[2,1]。
        int all_set = 1 << nums.size();//2的n次方种；
        for(int i = 0; i < all_set; i++){
            vector<int> item;
            for(int j = 0; j < nums.size(); j++){
                //如果i的第j位为1，说明，有这一位所代表的元素。
                // （1 << j）第j位为1，其他位为0。
                // i & (1 << j)， i 这个数中，j这一位是不是为1。（i中是否包含这个元素）
                if(i & (1 << j)){
                    item.push_back(nums[j]);
                }
            }
            //将该子集放入集合中。
            result.push_back(item);
            item.clear();
        }
        return result;
    }
};

算法流程：

适用范围：有向无负权图

1.优先队列版 复杂度O(ElogE)

2.邻接矩阵版 复杂度O(N^2) 记录路径版

解题通用思路

需求

初识AVL树

AVL树的调整策略

简单情形

1.左旋

2.右旋

3.右左旋

4.左右旋

根据一棵树的中序遍历与后序遍历构造二叉树。

Solution

思路：

正则表达式

正则基础

^

$

[…]

[^…]

-

.

|

?

+

*

{min,max}

括号与反向引用

转义字符

(…)

一些特殊的字符

写在大一期末考试之际

Solution1：

Solution2：

Solution:

思路：

Solution：

思路：

Solution:

Solution1：

Solution2：

遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集

Solution3（位运算）：

1.优先队列版复杂度O(ElogE)

2.邻接矩阵版复杂度O(N^2) 记录路径版