记录每天的碎片化产出，文章持续更新。

On March 18

  • for循环的这种用法
1
2
3
4
vector<int> nums = {1, 2, -1, -2, -3, 0};
  for (int c : nums)
    cout << c;
  cout << endl;
  • substr()函数返回字符串的某个区间内元素
    例如str.substr(2,4):从下标为2的元素开始(包括下标为2的元素)往后的四个元素
1
2
3
4
5
6
7
8
9
10
11
string FindQZ(vector<string> &str) {
  int result = 0;
  for (; result < str[0].size(); ++result) {
    char checker = str[0][result];
    for (int i = 1; i < str.size(); ++i) {
      if (checker != str[i][result])
        return str[0].substr(0, result);
    }
  }
  return str[0].substr(0, result);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// CPP program to illustrate substr() 
#include <string.h> 
#include <iostream> 
using namespace std; 
int main() 
{ 
  vector<string> str = {"i", "am", "lijunkui"};
    //区分与vector<char> x={'i','a','m','l'};
  cout << str[2].substr(2, 3) << endl;
  string s = "lijunkui";
  cout << s.substr(1, 2) << endl;
  string a = s.substr(1, 2);
  cout << a << endl;
	return 0; 
} 
>>>	jun
>>>	ij
>>>	ij
  • accumulate()累加求和函数,头文件numeric
1
2
int sum = accumulate(vec.begin() , vec.end() , 42);  
accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。

注意范围是[vec.begin(),vec.end())前开后闭区间

  • reverse()函数
1
reverse(digits.begin(), digits.end());
  • find()函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//容器表示方法
find（a.begin(),a.end(),value）
//数组的表示方法
find（a,a+length,val）
//对于string，通过a.find(val)==string::npos判断
string str = "hello world";
    char ch = 'l';
    if(str.find(ch)!=string::npos){ //查找单个字符
        cout<<str.find(ch)<<endl;
    }
    else
        cout<<"NO"<<endl;
        
        int p = 0;//表示第0个位置开始
while(str.find(ch, p)!=string::npos){
            p = str.find(ch, p);
            cout<<p<<endl;
            p = p + 1;
        }
  • distance()函数返回容器中两个地址之间的距离
1
2
3
4
5
//注意:这里是闭区间
 vector<int> numbers = {0, 0, 3, 4};
 cout << distance(numbers.begin(), numbers.end()) << endl;
 cout << numbers.end() - numbers.begin() << endl;
 输出:4
  • unique(it_1，it_2)函数,表示对容器中[it_1，it_2)范围的元素进行去重(注：区间是前闭后开，即不包含it_2所指的元素),返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。
  • erase(first,last);删除从first到last之间的字符（first和last都是迭代器）
1
2
3
4
5
6
7
8
9
int removeDuplicates(vector<int> &nums) {
  int dup = 0;
  // unique的作用是将容器中相邻元素的重复元素至尾
  vector<int>::iterator it = unique(nums.begin(), nums.end());
  dup = it - nums.begin();
  cout << "it=" << *it << endl;
  nums.erase(it, nums.end()); //删除  从it位置开始到end结束
  return dup;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//这两种方法是针对字符串的
#include <iostream>
#include <string>
using namespace std;

int main ()
{
  string str ("This is an example phrase.");
  string::iterator it;

  // 第(1)种用法
  str.erase (10,8);
  cout << str << endl;        // "This is an phrase."

  // 第(2)种用法
  it=str.begin()+9;
  str.erase (it);
  cout << str << endl;        // "This is a phrase."
}

On March 23

python3 读写Excel

  • 2007版以前的Excel（xls结尾的），需要使用xlrd读，xlwt写。
  • 2007版以后的Excel（xlsx结尾的），需要使用openpyxl来读写。

参考文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Reading an excel file using Python 
import xlrd 
# Give the location of the file 
loc = ("path of file") 
# To open Workbook 
wb = xlrd.open_workbook(loc) 
sheet = wb.sheet_by_index(0) 
# For row 0 and column 0 
sheet.cell_value(0, 0)
# Extracting number of rows 
print(sheet.nrows) 
# Extracting number of columns 
print(sheet.ncols)
#Extract a particular row or value
print(sheet.row_values(1))
print(sheet.col_values(2))
# For row and column
for r in range(sheet.nrows):
    for c in range(sheet.ncols):
        print(sheet.cell_value(r, c))

1.整数与罗马数字的转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include "iostream"
#include "string"
#include "unordered_map"
#include "vector"
using namespace std;
//罗马数字转至整数
int romanToInt(string s) {
  unordered_map<char, int> T = {{'I', 1},   {'V', 5},   {'X', 10},  {'L', 50},
                                {'C', 100}, {'D', 500}, {'M', 1000}};
  int sum = T[s.back()]; //无向图最后一个元素的值
  for (int i = s.length() - 2; i >= 0; --i) {
    if (T[s[i]] < T[s[i + 1]]) //当左边元素的值小于右边元素的值 必然是相减的关系
      sum -= T[s[i]];
    else
      sum += T[s[i]];
  }
  return sum;
  //整数转至罗马数字
  string InttoRoman(int num) {
  string res = "";
  char roman[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
  int value[] = {1000, 500, 100, 50, 10, 5, 1};
  // 7表示最大为4位数,n=+2表示从个位十位百位开始计算
  for (int n = 0; n < 7; n += 2) {
    int x = num / value[n];
    if (x < 4) {
      for (int i = 1; i <= x; ++i)
        res += roman[n];
    } else if (x == 4)
      res = res + roman[n] + roman[n - 1];
    else if (x > 4 && x < 9) {
      res += roman[n - 1];
      for (int i = 6; i <= x; ++i)
        res += roman[n];
    } else if (x == 9)
      res = res + roman[n] + roman[n - 2];
    num %= value[n];
  }
  return res;
}
int main(int argc, char const *argv[]) {
  string test1 = "MCMXCIV";
  cout << romanToInt(test1) << endl;
  int number1 = 1994;
  cout << InttoRoman(number1) << endl;
  return 0;
  • 整数转至罗马数字解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
string InttoRoman2(int num) {
  string res = "";
  vector<int> val{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
  vector<string> str{"M",  "CM", "D",  "CD", "C",  "XC", "L",
                     "XL", "X",  "IX", "V",  "IV", "I"};
  for (int i = 0; i < val.size(); ++i) {
    while (num >= val[i]) { //确定num在哪一个阶段
      num -= val[i];        //向下一个较小阶段逼近
      res += str[i];        //叠加相对应的字符
    }
  }
  return res;
}

此处有问题:vector val向量有什么选择要求?应该怎样选择?为什么要这样选?

2.任务调度器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "algorithm"
#include "iostream"
#include "unordered_map"
#include "vector"
using namespace std;
int leastInterval(vector<char> &tasks, int n) {
  unordered_map<char, int> mp;
  int count = 0;
  for (auto e : tasks) {
    mp[e]++;
    cout << e << " " << mp[e] << endl;
    count = max(count, mp[e]);
  }
  int ans = (count - 1) * (n + 1);
  for (auto e : mp)
    if (e.second == count)
      ans++;
  return max((int)tasks.size(), ans);
}
int main(int argc, char const *argv[]) {
  vector<char> tasks = {'A', 'C', 'A', 'A', 'A', 'B', 'B', 'B', 'C', 'C'};
  cout << leastInterval(tasks, 2) << endl;
  return 0;
}

  1. 三角形最小路径和

    从底至上，堪称完美

    1
    2
    3
    4
    for (int i = triangle.size() - 2; i >= 0; i--)
     for (int j = 0; j < triangle[i].size(); j++)
    triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j+1]);
        return triangle[0][0];

On March 24

贪心算法

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

map

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力。map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的

  1. 头文件
1
#include "iostream"
  1. 构造函数
1
map<TYPE,TYPE> MAPNAME;
1
2
3
map<int,int> one;
map<int,string> twe;
map<string,int> three;

pair

pair是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// C++ program to demonstrate sorting in 
// vector of pair according to 1st element of pair 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
	// Declaring vector of pairs 
	vector< pair <int,int> > vect; 
	// Initializing 1st and 2nd element of 
	// pairs with array values 
	int arr[] = {10, 20, 5, 40 }; 
	int arr1[] = {30, 60, 20, 50}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	// Entering values in vector of pairs 
	for (int i=0; i<n; i++) 
		vect.push_back( make_pair(arr[i],arr1[i]) ); 
	// Using simple sort() function to sort 
	sort(vect.begin(), vect.end()); 
	// Using sort() function to sort by 2nd element of pair 
    sort(vect.begin(), vect.end(), sortbysec);
	// Printing the sorted vector(after using sort()) 
	for (int i=0; i<n; i++) 
	{ 
		// "first" and "second" are used to access 
		// 1st and 2nd element of pair respectively 
		cout << vect[i].first << " "
			<< vect[i].second << endl; 
	} 

	return 0; 
}
  1. 构造函数
1
2
3
pair<int, double> p1;  //使用默认构造函数
pair<int, double> p2(1, 2.4);  //用给定值初始化
pair<int, double> p3(p2);  //拷贝构造函数
  1. make_pair 函数
1
2
pair<int, double> p1;
p1 = make_pair(1, 1.2);

递归

递归算法是一种直接或者间接调用自身函数或者方法的算法。

注意:递归内部采用栈的形式

  1. 案例一:求阶乘

  2. 案例二:汉诺塔问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void Hanoi(int n, char A, char B, char C) {
      if (n == 1)
        cout << " from " << A << " to " << C << ", ";
      else {
        Hanoi(n - 1, A, C, B);
        cout << " from " << A << " to " << C << ", ";
        Hanoi(n - 1, B, A, C);
      }
    }

On March 29

NLTK Natural Language Toolkit

chatbot工作原理

提问处理模块、检索模块、答案抽取模块。

提问处理模块要做三项重要工作：查询关键词生成、答案类型确定、句法和语义分析。

查询关键词生成，就是从你的提问中提取出关键的几个关键词，因为我本身是一个空壳子，需要去网上查找资料才能回答你，而但网上资料那么多，我该查哪些呢？所以你的提问就有用啦，我找几个中心词，再关联出几个扩展词，上网一搜，一大批资料就来啦，当然这些都是原始资料，我后面要继续处理。再说答案类型确定，这项工作是为了确定你的提问属于哪一类的，如果你问的是时间、地点，和你问的是技术方案，那我后面要做的处理是不一样的。最后再说这个句法和语义分析，这是对你问题的深层含义做一个剖析，比如你的问题是：聊天机器人怎么做？那么我要知道你要问的是聊天机器人的研发方法

检索模块跟搜索引擎比较像，就是根据查询关键词所信息检索，返回句子或段落，这部分就是下一步要处理的原料

答案抽取模块可以说是计算量最大的部分了，它要通过分析和推理从检索出的句子或段落里抽取出和提问一致的实体，再根据概率最大对候选答案排序，注意这里是“候选答案”噢，也就是很难给出一个完全正确的结果，很有可能给出多个结果，最后还在再选出一个来

reload()

1
2
3
4
5
6
7
#方法一
import sys
import importlib
importlib.reload(sys)
#方法二
from imp import reload
imp.reload('regTrees')

命名实体识别（英语：Named Entity Recognition，简称NER），又称作专名识别、命名实体，是指识别文本中具有特定意义的实体，主要包括人名、地名、机构名、专有名词等，以及时间、数量、货币、比例数值等文字。指的是可以用专有名词（名称）标识的事物，一个命名实体一般代表唯一一个具体事物个体，包括人名、地名等。

NER属于从非结构化文本中分类和定位命名实体感情的子任务，其过程是从是非结构化文本表达式中产生专有名词标注信息的命名实体表达式，目前NER有两个显著的问题，即识别和分类。例如，“奥巴马是美国总统”的“奥巴马”和“美国”都代表一个具体事物，因此都是命名实体。而“总统”不代表一个具体事物，因此不是命名实体。

pynlpir licence 问题或者有以下报错

1
RuntimeError("NLPIR function 'NLPIR_Init' failed.")

解决办法

1
sudo pynlpir update

pynlpir基本用法

依存句法分析

依存语法 (Dependency Parsing, DP) 通过分析语言单位内成分之间的依存关系揭示其句法结构。 直观来讲，依存句法分析识别句子中的“主谓宾”、“定状补”这些语法成分，并分析各成分之间的关系。

语义依存分析

语义依存分析 (Semantic Dependency Parsing, SDP)，分析句子各个语言单位之间的语义关联，并将语义关联以依存结构呈现。 使用语义依存刻画句子语义，好处在于不需要去抽象词汇本身，而是通过词汇所承受的语义框架来描述该词汇，而论元的数目相对词汇来说数量总是少了很多的。语义依存分析目标是跨越句子表层句法结构的束缚，直接获取深层的语义信息。

参考文档

docker介绍

chatterbot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from chatterbot import ChatBot
chatbot = ChatBot("Ron Obvious")
from chatterbot.trainers import ListTrainer

conversation = [
    "Hello",
    "Hi there!",
    "How are you doing?",
    "I'm doing great.",
    "That is good to hear",
    "Thank you.",
    "You're welcome."
]

chatbot.set_trainer(ListTrainer)
chatbot.train(conversation)

报错信息

1
AttributeError: 'ChatBot' object has no attribute 'set_trainer'

解决办法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from chatterbot.trainers import ListTrainer

conversation = [
    "Hello",
    "Hi there!",
    "How are you doing?",
    "I'm doing great.",
    "That is good to hear",
    "Thank you.",
    "You're welcome."
]

trainer = ListTrainer(chatbot)

trainer.train(conversation)

https://github.com/gunthercox/ChatterBot/issues/1555

报错信息

1
Resource averaged_perceptron_tagger not found.

解决办法

https://github.com/vivekkalyanarangan30/Text-Clustering-API/issues/1

On April 2

vector 初始化

1
2
3
4
5
6
7
8
9
10
vector<int> vec;        //声明一个int型向量
vector<int> vec(5);     //声明一个初始大小为5的int向量
vector<int> vec(10, 1); //声明一个初始大小为10且值都是1的向量
vector<int> vec(tmp);   //声明并用tmp向量初始化vec向量
vector<int> tmp(vec.begin(), vec.begin() + 3);  //用向量vec的第0个到第2个值初始化tmp
int arr[5] = {1, 2, 3, 4, 5};   
vector<int> vec(arr, arr + 5);      //将arr数组的元素用于初始化vec向量
//说明：当然不包括arr[4]元素，末尾指针都是指结束元素的下一个元素，
//这个主要是为了和vec.end()指针统一。
vector<int> vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值

https://www.cnblogs.com/zhonghuasong/p/5975979.html

On April 3

深度优先与广度优先

https://www.cnblogs.com/skywang12345/p/3711483.html

树

定义

树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

特点

  • 每个节点都只有有限个子节点或无子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；
  • 树里面没有环路

术语

  1. 节点的度：一个节点含有的子树的个数称为该节点的度；
  2. 树的度：一棵树中，最大的节点的度称为树的度；
  3. 叶节点或终端节点：度为零的节点；
  4. 非终端节点或分支节点：度不为零的节点；
  5. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
  6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
  7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
  8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
  9. 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
  10. 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
  11. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
  12. 节点的祖先：从根到该节点所经分支上的所有节点；
  13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
  14. 森林：由m（m>=0）棵互不相交的树的集合称为森林；

种类

  • 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
  • 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
    • 二叉树：每个节点最多含有两个子树的树称为二叉树；
      • 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
        • 满二叉树：所有叶节点都在最底层的完全二叉树；
      • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
      • 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；
    • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
    • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

遍历

  • 深度优先遍历

    • 前序遍历(Pre-Order Traversal))

      1
      2
      3
      4
      5
      6
      7
      void pre_order_traversal(TreeNode *root) {
          // Do Something with root
          if (root->lchild != NULL)
              pre_order_traversal(root->lchild);
          if (root->rchild != NULL)
              pre_order_traversal(root->rchild);
      }

  • 中序遍历(In-Order Traversal))

    1
    2
    3
    4
    5
    6
    7
    void in_order_traversal(TreeNode *root) {
        if (root->lchild != NULL)
            in_order_traversal(root->lchild);
        // Do Something with root
        if (root->rchild != NULL)
            in_order_traversal(root->rchild);
    }

  • 后序遍历(Post-Order Traversal))

    1
    2
    3
    4
    5
    6
    void post_order_traversal(TreeNode *root) {
        if (root->lchild != NULL)
            post_order_traversal(root->lchild);
        if (root->rchild != NULL)
            post_order_traversal(root->rchild);
        // Do Something with root

  • 广度优先遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    void Layer_Traver(tree *root) {
        int head = 0, tail = 0;
        tree *p[SIZE] = {NULL};
        tree *tmp;
        if (root != NULL) {
            p[head] = root;
            tail++;
            // Do Something with p[head]
        } else
            return;
        while (head < tail) {
            tmp = p[head];
            // Do Something with p[head]
            if (tmp->left != NULL) { // left
                p[tail] = tmp->left;
                tail++;
            }
            if (tmp->right != NULL) { // right
                p[tail] = tmp->right;
                tail++;
            }
            head++;
        }
        return;
    }

最简单的划分：是深度优先（先访问子节点，再访问父节点，最后是第二个子节点）？还是广度优先（先访问第一个子节点，再访问第二个子节点，最后访问父节点）？ 深度优先可进一步按照根节点相对于左右子节点的访问先后来划分。如果把左节点和右节点的位置固定不动，那么根节点放在左节点的左边，称为前序（pre-order）、根节点放在左节点和右节点的中间，称为中序（in-order）、根节点放在右节点的右边，称为后序（post-order）。对广度优先而言，遍历没有前序中序后序之分：给定一组已排序的子节点，其“广度优先”的遍历只有一种唯一的结果。

性质

  • 二叉树第i层上的结点数目最多为 2{i-1} (i≥1)
  • 深度为k的二叉树至多有2{k}-1个结点(k≥1)
  • 包含n个结点的二叉树的高度至少为log2 (n+1)
  • 对于任意一个编号为n的节点，如果它有子节点，它的左子节点编号为2n,右节点的编号为2n+1

顺序存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//二叉树的先序输入与输出
#include <stdio.h>
void get_tree(char*,int);
void print_tree(char*,int);
int main(){
    char tree[1000];
    get_tree(tree,1);
    print_tree(tree,1);
    return 0;
}
void get_tree(char *tree,int sub){
    char t;
    scanf("%c",&t);
    tree[sub]=t;
    if(t=='#')
        return;
    get_tree(tree,2*sub);
    get_tree(tree,2*sub+1);
}
void print_tree(char *tree,int sub){
    if(tree[sub]=='#')
        return;
    printf("%c",tree[sub]);
    print_tree(tree,2*sub);
    print_tree(tree,2*sub+1);
}

链式存储

https://www.cnblogs.com/chenliyang/p/6553128.html

  1. 节点描述

    1
    2
    3
    4
    5
    typedef struct BiTNode
    {
        TElemType data;
        struct BiTNode *lchild,*rchild; 
    }BiTNode,*BiTree;

  2. 创建链式二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void createBitree(Bitree &T)
    {
        char ch;
        if((ch=getchar())=='#')
            T=NULL;
        else
        {
            T=(Bitnode*)malloc(sizeof(Bitnode));
            T->data=ch;
            createBitree(T->Lchild);
            createBitree(T->Rchild);
        }
    }

  3. 遍历二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /*先序遍历*/
    void preTraverse(Bitree T)
    {
        if(T!=NULL)
        {
            printf("%c",T->data);
            preTraverse(T->Lchild);
            preTraverse(T->Rchild);
           }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /*中序遍历*/
    void  inorder(Bitree T)
    {
        if(T!=NULL)
        { 
            inorder(T->Lchild); 
            printf("%c",T->data);
            inorder(T->Rchild);
        } 
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /*后序遍历*/
    void  postorder(Bitree T)
    {
           
    if(T!=NULL)
    {
    postorder(T->lchild);
    postorder(T->rchild);
    printf("%c",T->data);
          }
    }

  4. 二叉树的深度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int   Depth(Bitree T)
    {//返回深度
        int d,dl,dr;
        if(!T)
            d=0;
        else {
            dl=Depth(T->Lchild);
            dr=Depth(T->Rchild);
            d=1+(dl>dr?dl:dr) ;
        }

        return d;
    }

  5. 二叉树的层序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    queue<Bitree> TreeQueue; //使用队列
        TreeQueue.push(tree);   //先将队头元素加入队列
        Bitree p = tree;    
        while (!TreeQueue.empty())  //循环判断队列是否未空，若不空则
        {
            p = TreeQueue.front();  //获取队列头节点，并出队列
            TreeQueue.pop();        
            printf(" %c ", p->data); //打印队列元素

            if (p->Lchild)     //如果该节点有左节点
            {
                TreeQueue.push(p->Lchild);  //加入队列
            } 
            if (p->Rchild)    //如果该节点有右节点
            {
                TreeQueue.push(p->Rchild); //加入队列
            }
        }

结构体的几种形式

https://blog.csdn.net/mengxiangjia_linxi/article/details/78168461

  1. 先定义结构体类型，再定义结构体类型变量

    1
    2
    3
    4
    5
    6
    7
    struct stu 
    {
         char name[20];   //学生姓名
         char sex;        //性别
         long num;        //学号
         float score[3];  //三科考试成绩
    };
    1
    struct stu student1,student2;//struct stu 此时相当于int , char

  2. 定义结构体类型同时定义结构体类型变量

    1
    2
    3
    4
    5
    6
    struct data
    {
         int day;
         int month;
         int year;
    } time1,time2;
    1
    struct data time3,time4;//struct data 此时相当于int , char

  3. 定义一个结构体类型用typedef

    1
    2
    3
    4
    5
    typedef struct Student
    {
    	char name;
        int a;
    }Stu;
    1
    Stu stu1;//Stu 相当于struct Student , 而不能用 Student stu1 这种形式

On April 12

动态规划

Dynamic programming，简称DP，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题

最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

重叠子问题

在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。

1
2
3
4
5
6
7
8
9
A * "1+1+1+1+1+1+1+1 =？" *
A : "上面等式的值是多少"
B : *计算* "8!"
A *在上面等式的左边写上 "1+" *
A : "此时等式的值为多少"
B : *quickly* "9!"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：

  1. 自顶向下
  2. 自底向上。

斐波拉契数列

假设树结构的根为底

自底向上，预求父问题，前求子问题，从后往前

1
2
3
4
5
6
7
8
9
10
public int fib(int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    return fib( n-1)+fib(n-2);
}
//输入:6
//输出：8

该树结构可以很好的解释递归的执行过程

自顶向下，从子问题推求父问题，从前往后

1
2
3
4
5
6
7
8
9
10
11
12
public static int fib(int n)
{
        if(n<=0)
            return n;
        int []Memo=new int[n+1];
        Memo[0]=0;
        Memo[1]=1;
        for(int i=2;i<=n;i++)
        {
            Memo[i]=Memo[i-1]+Memo[i-2];
        }       
        return Memo[n];

动态规划的三种模型

使用最小花费爬楼梯

区间模型，从前往后

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> res(cost.size()+1,0);//dp数组
        for(int i=2;i<cost.size()+1;i++)
            res[i]=min(res[i-1]+cost[i-1],res[i-2]+cost[i-2]);
        return res.back();
    }
};

三角形最小路径和

区间模型，从后往前

1
2
3
4
for (int i = triangle.size() - 2; i >= 0; i--)
  for (int j = 0; j < triangle[i].size(); j++)
  triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
 return triangle[0][0];

买卖股票的最佳时机I

1
2
3
4
5
6
7
8
9
10
11
12
int maxProfit(vector<int>& prices) {
    vector<int> price;
    for(int i=1;i<prices.size();++i)
        price.push_back(prices[i]-prices[i-1]);
    int profit=0,max_profit=0;
    for(int i=0;i<price.size();++i){
        if(price[i]+profit>0)
            profit+=price[i];
        else profit=0;
        if(profit>max_profit) max_profit=profit;
    }
    return max_profit;

买卖股票的最佳时机II

1
2
3
4
5
6
7
8
9
10
11
    int maxProfit(vector<int>& prices) {
    int maxProfit(vector<int>& prices) {
//贪心算法在已知每天的价格之后便宜时买入贵时卖出,虽然每次赚的少,但是最终一定最多
     int maxPro = 0, tmp = 0;
       for (int i = 1; i < prices.size(); ++i) {
         tmp = prices[i] - prices[i-1];
          if (tmp > 0)
           maxPro += tmp;
        }
        return m
    }

On April 13

.begin()和.end()函数

begin返回首元素的地址，end返回尾元素的下一个地址

1
2
3
4
vector<int> temp={1,2,3,4,5,6,7,8,9};
cout<<"temp.begin():"<<*temp.begin()<<endl;
cout<<"temp.end():"<<*(--temp.end())<<endl; 
cout<<"temp.End():"<<*temp.end()<<endl;//为元素的下一个地址
1
2
3
temp.begin():1
temp.end():9
temp.End():0

On April 14

时间与空间复杂度

时间复杂度

1. 时间频度

一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)

2 时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

T (n) = Ο(f (n)) 表示存在一个常数C，使得在当n趋于正无穷时总有 T (n) ≤ C f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T (n)的上界是C f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。例如，O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ，一般都只用O(n2)表示就可以了。注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

3 求解算法的时间复杂度

  • 找出算法中的基本语句

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

  • 计算基本语句的执行次数的数量级

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。

  • 用大Ο记号表示算法的时间性能
1
2
3
4
5
for (i=1; i<=n; i++)
　　       x++;
　　for (i=1; i<=n; i++)
　     　for (j=1; j<=n; j++)
			x++；

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。

  • 在计算算法时间复杂度时有以下几个简单的程序分析法则

    1. 对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

    2. 对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下”求和法则”

      求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

    3. 对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

    4. 对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下”乘法法则”

      乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1T2=O(f(n)g(n))

    5. 对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

      另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

4.示例说明

  1. O(1)

    1
    Temp=i; i=j; j=temp;

    以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

  2. O(n2)

    交换i和j的内容

    1
    2
    3
    4
    sum=0；                 （1次）
        for(i=1;i<=n;i++)     （n+1次）
           for(j=1;j<=n;j++) （n2次）
            sum++；            （n2次）

    因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n2)；

    1
    2
    3
    4
    5
    6
    for (i=1;i<n;i++)
        { 
            y=y+1;         ①   
            for (j=0;j<=(2*n);j++)    
               x++;         ②      
        }

    语句1的频度是n-1,语句2的频度是(n-1)*(2n+1)=2n2-n-1,f(n)=2n2-n-1+(n-1)=2n2-2；

    又Θ(2n2-2)=n2,该程序的时间复杂度T(n)=O(n2).

    一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

  3. O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    a=0;
        b=1;                      ①
        for (i=1;i<=n;i++) ②
        {  
           s=a+b;　　　　③
           b=a;　　　　　④  
           a=s;　　　　　⑤
        }

    语句1的频度：2,
    语句2的频度： n,
    语句3的频度： n-1,
    语句4的频度：n-1,
    语句5的频度：n-1,

    T(n)=2+n+3(n-1)=4n-1=O(n).

  4. O(log2n)

    1
    2
    3
    i=1;     ①
      while (i<=n)
         i=i*2; ②

    语句1的频度是1,
    设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n
    取最大值f(n)=log2n,
    T(n)=O(log2n )

  5. O(n3) 

    1
    2
    3
    4
    5
    6
    7
    8
    for(i=0;i<n;i++)
        {  
           for(j=0;j<i;j++)  
           {
              for(k=0;k<j;k++)
                 x=x+2;  
           }
        }

空间复杂度

On April 15

abs()

a function returns the absolute value of its parameter.
这是一个函数，返回它的参数（整型）的绝对值，浮点数的绝对值用 fabs 函数，头文件include”cmath”

Python中的 // 与 / 的区别

1
2
3
4
5
6
7
8
9
10
11
12
" / "  表示浮点数除法，返回浮点结果;
" // " 表示整数除法,返回不大于结果的一个最大的整数
>>> print(6.0//4)
1.0
>>> print(6.0//4.0)
1.0
>>> print(6.0/4.0)
1.5
>>> print(6/4)
1.5
>>> print(6//4)
1

On April 16

clang-format

为了实现的代码格式化，可以安装这个插件在code中，之前不知道怎么配置的，在做完系统之后重新安装配置出现了问题。

  1. 首先在插件商店搜索并安装clang-format

  2. 打开设置搜索format，勾选format on save 自动保存

    在你按下Ctrl+S保存的同时实现代码的格式化

  3. 打开终端，这一步很重要

    1
    clang-format -style=llvm -dump-config > .clang-format

  4. 在当前的工作目录产生一个.clang-format的模板文件

    1
    vim .clang-format

  5. 根据自己偏好决定自定义格式化

参考链接

INT_MAX INT_MIN

头文件 climits

On April 24

数组的维度

  1. 一维数组

    1
    2
    3
    4
    a = np.array([1,2,3])
    print(a，a.shape)
    [1 2 3]
    (3,)

  2. 二维数组 （矩阵）

    1
    2
    3
    4
    5
    b = np.array([[1,2,3],[4,5,6]])
    print(b, b.shape)
    [[1 2 3]
     [4 5 6]]
    (2, 3)

  3. 高维数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #3-D
    c= np.array([[[1,2],[3,4],[5,6]],[[1,2],[3,4],[5,6]]])
    print(c, c.shape)
    [[[1 2]
      [3 4]
      [5 6]]
      
     [[1 2]
      [3 4]
      [5 6]]]
    (2, 3, 2)
    #4-D
    d= np.array([[[[1,2],[3,4],[5,6]],[[1,2],[3,4],[5,6]]],
                 [[[1,2],[3,4],[5,6]],[[1,2],[3,4],[5,6]]]])
    print(d, d.shape)

    [[[[1 2]
       [3 4]
       [5 6]]

      [[1 2]
       [3 4]
       [5 6]]]


     [[[1 2]
       [3 4]
       [5 6]]

      [[1 2]
       [3 4]
       [5 6]]]]
    (2, 2, 3, 2)
 上一页

Git