denrydu/denrydu.github.io

Denry's Blog

Hi there 👋

课内(NJUPT) 🔭 学习过程 ... [Java-SSM] | 软件项目实训之慢病智慧健康系统 - 2020-05-28 [C++] | 数据结构实验 - 2020-05-28 [C++] | 编译原理实验 - 2020-05-28 [C++] | 操作系统实验 - 2020-05-28 [Java] | Android - 2020-05-28

课外 🔭 I’m currently working on ... [Python] | STITP-语音分离 - 2020-12-28 ✨ I'm preparing myself for ... [Matlab] | 数模 - 2020-05-28 🌱 I’m currently learning ... [Python] | HungyiLi 机器学习 - 2020-05-28 [C++] | PAT题库 - 2020-05-28 [Python\C++] | 计算机视觉 - 2020-05-28 [Python] | 爬虫 - 2020-05-28 [Python-GBDT] | 用户行为挖掘 - 2020-05-28

denrydu.github.io's Issues

CS231N 之 作业环境搭建 (Anaconda install)

CS231N 之 作业环境搭建

Table (目录):

• 1.下载安装Anaconda
• 2.配置虚拟环境
• 3.在虚拟环境中安装依赖
• 4.使用jupyter开始编辑作业

---

1.下载安装Anaconda

• 下载.sh文件 (请选择对应版本进行下载)

  • 清华大学开源软件镜像站下载
  • 官网下载

• 打开terminal,打开下载文件的位置：

cd Downloads/

• 运行 .sh 文件：

bash Anaconda3-5.2.0-Linux-x86_64.sh

• 进入注册信息页面，输入yes
• 确认文件即将安装的位置，按enter
• 进入安装过程
• 安装完成后，收到__加入环境变量__的提示信息

Do you wish the installer to prepend the Anaconda3 install location to PATH in your /home/.../.bashrc ? [yes|no]
输入yes

• 安装完成,出现提示信息

Do you wish to proceed with the installation of Microsoft VSCode? [yes|no]
输入no

• 重启终端，即可使用Anaconda3
• 添加环境变量: 若在终端输入 python，仍然会显示Ubuntu自带的python版本，我们执行：

sudo gedit ~/.bashrc
export PATH="/home/...(待填)/anaconda3/bin:$PATH"

注意：PATH后面需要填写ANACONDA的实际安装位置

• 执行下面命令更新环境变量

source ~/.bashrc

• 这时候可以查看python版本

python --version

---

2.配置虚拟环境

• 运行（在终端中）创建一个叫做cs231n的环境:

conda create -n cs231n python=3.6 anaconda 1

注意：python=3.6 需要根据实际的python版本设置

• 激活并进入环境，请运行 source activate cs231n

source activate cs231n

• 要退出，您只需关闭窗口或运行即可

source deactivate cs231n

请注意，每次要处理作业时，都应该运行 source activate cs231n

---

3.在虚拟环境中安装依赖

• 首先，激活并进入环境，请运行:

source activate cs231n

• 如果缺少库，可以执行下面命令安装（...替换为numpy或者scipy）

conda install ... 

• 查看conda安装了哪些包可以使用以下命令:

conda list

• 如果有requirements.txt,则可以使用如下命令在虚拟环境中pip install:

python -m pip install requirement.txt
> (python -m 以保证安装在虚拟环境中)

---

4.使用jupyter开始编辑作业

jupyter是Anaconda中安装好的一个编译器，你如果在上面安装完Anaconda后执行了conda list 会看到jupyter

• 在终端执行打开jupyter notebook

jupyter notebook

• 然后点击assignment1/knn.ipynb即可开始做第一个作业

Attention: 程序界面是分块的，在每一个块内按shift+enter就会执行相应的块查看输出结果。注意的是：程序需要顺序执行，否则会出现未定义的变量

---

// DenryDu
// 2020-06-20

细说 类/结构体+vector+find()/find_if() 实现自定义查询 C++ STL

写在之前：

众所周知，vector是STL中很好用的一个类，我们可以通过vector实现很多操作，今天就来说一说利用vector如何实现查询操作

---

回顾一下------

》基础数据类型查询：find()

一般的，对于c++内置的基础数据类型，我们可以直接通过 find() 函数（ #include < algorithm >）来进行查询.

函数原型：

返回值：vector迭代器 find(迭代起点,迭代终点,要查询的值(基础数据类型))；

std::vector< VALUE_TYPE >::iterator it = find_if(vec.begin(),vec.end(),VALUE);

函数实例：

	vector<int> intVec;
	intVec.push_back(1);
	intVec.push_back(2);
	intVec.push_back(4);
	intvec.push_back(5);
	vector<int>::iterator it = find( intVec.begin( ), intVec.end( ), 5 ); 
    if ( it != intVec.end( ) )	cout<<"true";
    else   	cout<<"false";

---

回顾完基础数据类型的查找之后，我们进入

》》》》》》正题！！！

---

》类/结构体自定义查询：find_if()

---

在实际的编程过程中，基础数据类型的查询还是少数，更多的情况下我们需要为自己定义的结构体或者类进行排序、查询操作

先不急着看函数原型，来一个情景代入：

为了存储学生的成绩信息，我创建了一个结构体：stuInfo ,里面存放有 学生ID，四科成绩，四科排名等等信息

typedef struct{
	string id;
	int score[4];
	int rank[4]={-1};
}stuInfo;

但现在，数据存好了，但是我希望能够通过 idVec[m] 中存放的几个想要查询成绩的 学生的ID，来为他们查找结构体中各自的成绩和排名信息

---

那么这个时候，find_if() 函数就能派上用场

函数原型：

返回值：vector迭代器 find_if(迭代起点,迭代终点,一元函数)；

std::vector< STRUCT >::iterator it = find_if(vec.begin(),vec.end(),COMP_FUNCTION);

这里的最后一个参数，要求的是unary function，在此即是只有一个参数，并且返回值为bool类型的函数，而且数据类型是vector容器中放入的数据类型，在这里，参数类型即为学生信息结构体：stuInfo

首先我们很容易可以实现的是类似于sort函数那样的，写一个比较函数作为参数填入：

	bool compare(stuInfo si){
		string id="1010134";
		return (si.id.compare(id)==0);
	}
	std::vector<stuInfo>::iterator it = find_if(info.begin(),info.end(),compare);

---

但是！！！这种方式我们明显就只能查找ID为1010134的这位同学的信息，那怎么做到查询别的同学呢？

接下来我们有四种解决方案：

• 全局变量
• 仿函数+构造方法
• 仿函数+绑定器
• 泛型模板函数+绑定器

---

1、全局变量实现：

我们要实现的就是想让搜索更具普遍性，那么将compare()函数里的局部变量变成可以随时修改的全局变量不就好了，只要在每次使用搜索之前更新一下全局变量的值就能实现这样的目的。

	string id；//定义全局变量
	bool compareId(stuInfo si){
		return (si.id.compare(id)==0);
	}
	for(int i=0;i<m;i++){
		id=idVec[i];//更新全局变量的值
		std::vector<stuInfo>::iterator it = find_if(info.begin(),info.end(),compareId);
	}

但是，这样不仅容易出错，而且最关键的是：不优雅！！！！
那么我们再来看看剩下的三种方法

---

2、仿函数+构造函数实现：

我们要实现的无非就是想在第三个参数函数里不只传递一个参数，还要传进另一个参数用以比较，那么仿函数就可以实现这一点，
编写一个新结构体/类，并编写一个仿函数（重载operator()函数），使得其与构造函数一起被调用，就能实现多传递一个参数进行比较的要求。
一般的，我们将需要比较的值作为结构体/类的变量，通过构造函数进行赋值。
然后，编写仿函数传递find_if()函数进行遍历的整个stuInfo对象
最后我们就可以在仿函数里拿到新结构体/类里的变量来和stuInfo对象里的变量进行比较，并返回bool值

仿函数一般长这样：

bool operator()(const ???& obj){
	return ???????;
}

值得注意的是，这里的参数应该是常引用类型

具体实现如下（以结构体为例）：

	typedef struct ifIdMatch{
		string m_id;
		ifIdMatch(string id):m_id(id){}//构造函数
		bool operator()(const stuInfo& si){//仿函数
			return (si.id.compare(m_id)==0);
		}
	}ifIdMatch;
	
	for(int i=0;i<m;i++){//遍历寻找符合idVec中第i个Id的学生信息
		std::vector<stuInfo>::iterator it = find_if(info.begin(),info.end(),ifIdMatch(idVec[i]));
		if(it!=info.end())//存在
			Rank(*it);//进行后续操作，通过*it取得符合要求结构体信息
		else cout<<"N/A";//不存在
	}

---

3、仿函数+绑定器实现：

仿函数也可以放在绑定器里，从绑定器里获取另外一个参数而不是从结构体或者类中获取

这里需要用到一个一元函数结构体类型才能使用绑定器，否则会出错，因为需要指定argument type、result type等类型才能结合bind2nd使用，它的参数列表有三个参数，前两个是入参（argument type），第三个是返回值参数（result type）

当然，这里是一元函数的写法，下面即将要讲的绑定器+泛型模板函数实现里还有一种直接从普通函数变成符合要求的二元函数的方法

（这里只展示次参函数绑定器，其实还有首参、类绑定器）：

	struct compareId: binary_function<stuInfo, string, bool> {
		bool operator()(const stuInfo& si, string id){
			if (si.id.compare(id)==0)	return true;
			else	return false;
		}
	};
	for(int i=0;i<m;i++){//遍历寻找符合idVec中第i个Id的学生信息
		std::vector<stuInfo>::iterator it = find_if(info.begin(),info.end(),bind2nd(compareId(),idVec[i]));
		if(it!=info.end()) ????;//存在,进行后续操作，通过*it取得符合要求结构体信息
		else ?????;//不存在
	}

---

4、泛型模板函数+绑定器实现：

只要涉及到绑定器，就一定要写合乎规范的函数，但我们在这里定义的泛型模板函数并不符合要求，缺少argument type 和result type这两种参数类型的信息，但是，不要怕，很简单的，我们可以同伙ptr_fun()函数实现从普通函数到合规二元函数的转化

然后再用绑定器将二元函数与多余参数绑定变成一元函数即可

	template<typename T> bool compareId(const T* s1 , const T* s2){
		return s1->id.compare(s2->id);
	}
	for(int i=0;i<m;i++){//遍历寻找符合idVec中第i个Id的学生信息
		stuInfo temp;
		strcpy(temp.id,idVec[i]);
		std::vector<stuInfo>::iterator it = find_if(info.begin(),info.end(),bind2nd(ptr_fun(compareId<stuInfo>), &temp));
		if(it!=info.end()) ????;//存在,进行后续操作，通过*it取得符合要求结构体信息
		else ?????;//不存在
	}

PAT 1002 A+B for Polynomials (25分) (finished by 2020-02-16)

PAT 1002 A+B for Polynomials (25分)

This time, you are supposed to find A+B where A and B are two polynomials.

Input Specification:
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:K N​1​​ a​N~~1 N​2​​ a​N~~2​​ ... N​k​​ a​N~~k
​​ where K is the number of nonzero terms in the polynomial, N​i​ and a​N~~​i​​ (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤N​K​​ <⋯<N​2​​ <N​1​​ ≤1000.

Output Specification:

For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 2 1.5 1 2.9 0 3.2

Attention!

• do not output when Coefficient equals ZERO（because coefficient can be negative, so, after operation, the coefficient can be zero)
• NO SPACE at the end of the line
• if K equals ZERO, just output ZERO

There are two ways to implement it as below

1. One is to create a class named polynomial and override it's operation+ function and overlaod outputstream's implementation.

2. The Other is to use the class Map to create int-float pair.

Reference Link about way two

Code1:

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;
class singleUnit {
public:
	int exp;
	double cof;
};
class poly {
private:
	int k;
	int highestExp;
	singleUnit* unitList;
public:
	void setK(int k) {
		this->k = k;
		this->unitList = (singleUnit*)malloc(k * sizeof(singleUnit));
	}
	int getK() {
		return this->k;
	}
	void setHighestExp(int highestExp) {
		this->highestExp = highestExp;
	}
	void setUnitList(singleUnit* unitList) {
		this->unitList = unitList;
	}
	singleUnit* getUnitList() {
		return this->unitList;
	}
	poly() {
	}
	poly(int k) {
		this->k = k;
		this->unitList = (singleUnit*)malloc(k * sizeof(singleUnit));
		for (int i = 0; i < k; i++) {
			scanf("%d", &this->unitList[i].exp);
			scanf("%lf", &this->unitList[i].cof);
		}
		this->highestExp = this->unitList[0].exp;
	}
	friend poly operator+(poly a, poly b) {
		//get highestExp
		int highestExp = a.unitList[0].exp > b.unitList[0].exp ? a.unitList[0].exp : b.unitList[0].exp;
		poly dst;
		//set highestExp
		dst.setHighestExp(highestExp);
		//get K & unitList
		int k = 0;
		singleUnit* unitList = (singleUnit*)malloc((highestExp + 1) * sizeof(singleUnit));
		singleUnit* src1 = a.getUnitList();
		int k1 = a.getK();
		singleUnit* src2 = b.getUnitList();
		int k2 = b.getK();
		for (int i = highestExp; i >= 0; i--) {
			//init the unitList
			unitList[highestExp - i].exp = i;
			unitList[highestExp - i].cof = 0;
			//search src1 to check if it is possible to add on
			for (int j = 0; j < k1; j++) {
				if (src1[j].exp == i) {
					unitList[highestExp - i].cof += src1[j].cof;
					break;
				}
			}
			//search src2 to check if it is possible to add on
			for (int j = 0; j < k2; j++) {
				if (src2[j].exp == i) {
					unitList[highestExp - i].cof += src2[j].cof;
					break;
				}
			}
			//check whether the cof exists and count the K(num of nonzero terms) 
			if (unitList[highestExp - i].cof) {
				k++;
			}
		}
		//create the unitList used to return 
		singleUnit* unitListFinal = (singleUnit*)malloc(k * sizeof(singleUnit));
		//transmit the value from intermediate variable to final variable( to Eliminate blank area)
		int i = 0;
		for (int j = 0; j < highestExp+1; j++) {
			if (unitList[j].cof) {
				unitListFinal[i].exp = unitList[j].exp;
				unitListFinal[i].cof = unitList[j].cof;
				i++;
			}
		}

		//set k & unitList
		dst.setK(k);
		dst.setUnitList(unitListFinal);
		return dst;
	}
	friend ostream& operator<<(ostream& out, poly& p)    //overload the output stream
	{
		out << p.getK();
		out << fixed;
		out << setprecision(1);
		for (int j = 0; j < p.getK(); j++) {
			out << " ";
			out << p.getUnitList()[j].exp;
			out << " ";
			out << p.getUnitList()[j].cof;
		}
		return out;
	}
};

int main() { 
	int k;
	scanf("%d", &k);
	poly a(k);
	scanf("%d", &k);
	poly b(k);
	poly c = a + b;
	cout << c;
	return 0;
}

Code2

With all the details packaged into the class Map and Vector, the code below is easier to read compared to the one above.

#include<iostream>
#include<map>
#include<vector>

using namespace std;

map<int, float> poly;
int main() {
    for (int i = 0; i < 2; ++i)
    {
        int k;
        scanf("%d", &k);
        for (int i = 0; i < k; ++i)
        {
            int exp;
            float cof;
            scanf("%d%f", &exp, &cof);
            poly[exp] += cof;
        }
    }
    vector<pair<int, float> > res;
    for(map<int, float>::reverse_iterator it = poly.rbegin(); it != poly.rend(); it++) {
    	// eliminate the pair whose efficient is zero
        if(it->second != 0) 
            res.push_back(make_pair(it->first, it->second));
    }

    printf("%lu", res.size());
    for (int i = 0; i < res.size(); ++i)
    {
        printf(" %d %.1f", res[i].first, res[i].second);
    }
    return 0;
}

Summary and harvest

(for my current level)

In Code One:

• Set decimal for output stream:

out<<fixed<<setprecision(n);     //(e.g : 2.34345 ---> 2.3)

In Code Two:

• Map&Pair

Quick Look:

map可以当做一个容器（装载具有一定格式的数据）；pair可以理解为元素（放入到容器的的每个个体），pair并没有单独行动的典型用法，正常都是配合map来使用（即把pair这个元素插入到map这个容器里面）。
  pair与map怎样联系起来：
通过map的insert()可以把一个pair对象作为map 的参数，如map1.insert(pair1<id,grade>);

我们知道C++ STL中的map是以key排序的。
那如果我要以value进行排序呢？
方案：将map的key和value以pair的形式装到vector中，对vector进行排序。

• Vector

Quick Look:

vector简介
vector是STL中最常见的容器，它是一种顺序容器，支持随机访问。vector是一块连续分配的内存，从数据安排的角度来讲，和数组极其相似，不同的地方就是：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了；而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。

vector的数据结构
vector数据结构，采用的是连续的线性空间，属于线性存储。他采用3个迭代器_First、_Last、_End来指向分配来的线性空间的不同范围，下面是声明3个迭代器变量的源代码。

Mermaid：如何在Markdown文本中添加流程图，附支持github的方法

Mermaid：流程图 in Markdown

@[toc]

Background

---

我们在写博客或者写项目的README文档的时候，往往都需要画流程图，有的时候用在线编辑器，有的时候用draw.io，有的时候用Visio
但是这些可视化工具再给我们带来直观性的同时，也增加了操作的难度，需要精细地调整组件的大小和样式，
更多的时候，我们不是为了写一份漂亮的报告而画流程图，只是需要便捷地向他人分享自己的idea，在这样的需求下，代码生成流程图显然更适合。

Introduction

---

Mermaid是什么？

Mermaid 是一个用于画流程图、状态图、时序图、甘特图的库，使用 JS 进行本地渲染，广泛集成于许多 Markdown 编辑器中。

之前用过 PlantUML，但是发现这个东西的实现原理是生成 UML 的图片后上传服务端，每次再从服务端读取，因此觉得不够鲁棒，隐私性也不好，因而弃用。

为什么是Mermaid？

Mermaid 作为一个使用 JS 渲染的库，生成的不是一个“图片”，而是一段 HTML 代码，因此安全许多。

Usage

---

Mermaid代码如何撰写

基本格式

    ```mermaid
 	    graph 流程图方向[TB|LR|RL|BT]
 	    流程图内容
    ```

例子在前

    ```mermaid
          graph LR
          start[开始] --> input[输入A,B,C]
          input --> conditionA{A是否大于B}
          conditionA -- YES --> conditionC{A是否大于C}
          conditionA -- NO --> conditionB{B是否大于C}
          conditionC -- YES --> printA[输出A]
          conditionC -- NO --> printC[输出C]
          conditionB -- YES --> printB[输出B]
          conditionB -- NO --> printC[输出C]
          printA --> stop[结束]
          printC --> stop
          printB --> stop
    ```

          graph LR
          start[开始] --> input[输入A,B,C]
          input --> conditionA{A是否大于B}
          conditionA -- YES --> conditionC{A是否大于C}
          conditionA -- NO --> conditionB{B是否大于C}
          conditionC -- YES --> printA[输出A]
          conditionC -- NO --> printC[输出C]
          conditionB -- YES --> printB[输出B]
          conditionB -- NO --> printC[输出C]
          printA --> stop[结束]
          printC --> stop
          printB --> stop

指定流程图方向

写在最前面

	graph [TB|BT|LR|RL|TD]

• 纵向：TB：从上至下；BT：从下至上；TD：从上至下
• 横向：LR：从左至右；RL：从右至左

定义框体

结构：

	id【包围符】【显示文本】【包围符】

示例：

	```mermaid
		graph TD
    	id1[带文本的矩形]
    	id2(带文本的圆角矩形)
    	id3>带文本的不对称的矩形]
    	id4{带文本的菱形}
    	id5((带文本的圆形))
    ```

效果：

graph TD
    id1[带文本的矩形]
    id2(带文本的圆角矩形)
    id3>带文本的不对称的矩形]
    id4{带文本的菱形}
    id5((带文本的圆形))

框体只要定义一遍，之后只需要通过id来指定就行了

定义连接线和子图

连接线结构：

	id1【连接【文本】符】id2

子图结构：

	subgraph 子图名
	子图内容
	end

连接线格式例子（用子图分组）：

	```mermaid
    	graph TB
		subgraph 实线
    	A0[A] --- B0[B] 
    	A1[A] --> B1[B]
    	A2[A] -- 描述 --> B2[B] 
    	end
    	subgraph 虚线
    	A3[A] -.- B3[B] 
   		A4[A] -.-> B4[B] 
   		A5[A] -. 描述 .-> B5[B] 
    	end
    	subgraph 加粗线
    	A6[A] === B6[B]
    	A7[A] ==> B7[B] 
    	A8[A] == 描述 ==> B8[B] 
    	end
	```

效果：

graph TB
	subgraph 实线
    A0[A] --- B0[B] 
    A1[A] --> B1[B]
    A2[A] -- 描述 --> B2[B] 
    end
    subgraph 虚线
    A3[A] -.- B3[B] 
    A4[A] -.-> B4[B] 
    A5[A] -. 描述 .-> B5[B] 
    end
    subgraph 加粗线
    A6[A] === B6[B]
    A7[A] ==> B7[B] 
    A8[A] == 描述 ==> B8[B] 
    end

如何在Github的md文档里支持mermaid？

解决办法：

• 需要插件支持
  Chrome、Firfox、Opera浏览器插件

PAT Day1 1001 A+B Format (20分) (finished by 2020-02-15)

PAT 1001 A+B Format (20分)

Calculate a+b and output the sum in standard format -- that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

Input Specification:

Each input file contains one test case. Each case contains a pair of integers a and b where −10^​6​​ ≤a,b≤10^6​​ . The numbers are separated by a space.

Output Specification:

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

Sample Input:

-1000000 9

Sample Output:

-999,991

Attention:

• how to convert long to string
• how to insert ',' into string
• how to insert ',' when there is a '-' ahead of the num

MyAnswer

#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
int main(){
    long a, b, c;
    cin>>a;
    cin>>b;
    c = a + b;
    //convert long to string
    //way1
    /*ostringstream os;
    os << c;
    istringstream is(os.str());
    string str;
    is >> str;*/
    //way2
    string str = to_string(c)
    size_t len = str.length();
    for(int index =(int) len-3; index > 0; index -= 3)
        if(str[index-1]>='0'&&str[index-1]<='9')
            str.insert(index, ",");
    cout<<str<<endl;
    return 0;
}