队列和栈

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

   class Solution { public: void push(int node) { while(!stack2.empty()) { stack1.push(stack2.top()); stack2.pop(); } stack1.push(node); } int pop() { while(!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } int ans = stack2.top(); stack2.pop(); return ans; } private: stack<int> stack1; stack<int> stack2; };

类型转换

• 转换成常量：

  1 2 3 4

  int i; const int &j = i; //非常量转换成const int 的引用 const int *p = &i; //非常量的地址转换成const的地址 int &r = j, *q =p; //错误，不能用const转换为非常量

参数传递

1. 传值调用

• 指针形参：

  1 2 3 4 5

  void reset(int *p) { *ip = 0; // 改变指针ip所指对象的值 ip = 0; // 只改变了ip的局部拷贝，实参未被改变 {

  2.传引用调用
• 如果函数无需改变引用形参的值，最好将其声明为常量引用。
• const形参和实参，当使用实参初始化形参，会忽略掉顶层const：也就是说，当形参有顶层const,传给它常量对象或者非常量对象都是可以的：

  1	void fn(const int i) {/* fn能读取i，但是不能向i写入值*/}

• 尽量使用常量引用如 const i&，而不是普通引用i &,因为我们不能把const对象、字面值、或者需要类型转换的对象传递给普通的引用：

  1 2 3 4 5

  string is_sentence(const string &s) { string::size_type ctr = 0; return find_char(s, '.',ctr) == s.size() - 1 && ctr == 1; }

  其中如果find_char的第一个形参是普通引用string&，程序会失败，因为s是常量引用。

• 迭代器：
  标准容器迭代器的运算符, 其中 -> 运算符把解引用和成员访问两个操作结合在一起：

  1 2 3 4 5

  *iter 返回迭代器iter所指元素的引用 iter->mem 等价于 (*iter).mem ，解引用iter并获取该元素的名为mem的成员 ++iter 令iter指示容器中的下一个元素 --iter 零iter指示容器中的上一个元素 iter1 == iter2 iter1 != iter2 判断两个迭代器是否相等

  • 迭代器的类型：
    const_iterator和常量指针差不多：

    1 2 3 4

    string:: const_iterator it4; //it4只能读字符，不能写字符 const vector<int> cv; auto it2 = cv.begin(); // it2的类型是vector<int>::const_iterator

    • 警告：任何使用迭代器的循环体，不该向迭代器所属的容器添加元素，如push_back等。

• string与vector的迭代器支持更多运算符：

  1 2 3

  auto mid = vi.begin() + vi.size() / 2 if (it < mid) // 迭代器的比较，返回difference_type类型的有符号整型数

• 列表初始化：
  使用列表初始化且初始值存在丢失信息的风险，则编译器报错：

  1 2 3 4

  int unit_sold = {0}; // list initialization long double ld =3.14159; int a{id}, b = {id}; //错误 int c(id), d = ld; // 正确

• 默认初始化：
  定义于任何函数体之外的内置类型变量被初始化为0，定义在函数体内部的内置类型变量不被初始化。

• 声明与定义：
  变量只能定义一次，但能被多次声明；
  关键字extern表示声明变量；
  任何包含了显示初始化的声明即成为定义；
  函数内部初始化一个由extern关键字标记的变量，会报错。

  1 2 3 4 5 6 7

  extern int i; //声明而非定义i int j; //声明并定义j extern double pi = 3.1416; // 定义 ``` * 复合类型：指基于其他类型定义的类型，如引用，指针等。 声明语句的组成：基本数据类型 + 声明符，每一个声明符命名了一个变量并指定该变量为与基本数据类型有关的某种类型。 - 引用类型：引用另一种类型,是已经存在的对象的别名，因此不是对象，所以必须初始化。

  int ival = 1024;
  int &refVal = ival;
  int &refVal2; // 报错

  1 2

  - 指针：

  int ival = 42;
  int p = &ival; // &取地址符，p存放变量ival的地址。
  cout << p ; // *解引用符，得到p所指的对象。

  1	- 空指针：不指向任何对象.

  int p1 = nullptr;
  int p2 = 0;
  int *p3 = NULL; // 需要include

  1 2

  * 指向指针的指针

  int ival = 1024;
  int pi = &ival; // pi是指向int的指针
  int *ppi = π // ppi是指向int指针的指针

  1 2 3

  * 指向指针的引用： 指针是对象，存在对指针的引用，但是引用不是对象，不存在指向引用的指针； 离变量最近的符号对变量的类型有最直接的影响，因此r是一个引用。

  int i = 42;
  int p;
  int &r = p ; //r是一个对指针p的引用

  1 2 3

  ### const `const`限定的变量，其值不能改变，因此必须初始化。 `const`变量初始化另一个对象不会改变这个变量：

  int i = 42;
  const int ci = i;
  int j = ci; //正确；拷贝完成，新的对象和原来的对象就没有关系了；

  1 2 3

  * **默认状态下，const对象仅在文件内有效**，因此，当多个文件都要用这个`const`变量的时候，在每个文件都要定义该`const`变量， 只在一个文件中定义`const`,而在其他文件中声明且使用它的办法：在定义前加`extern`关键字：

  //file.cc 定义并初始化了一个常量
  extern const int bufSize = fcn();
  // file_1.h头文件
  extern const int bufSize; // 与file.cc中定义的bufSize是同一个

  1 2

  * 对常量的引用

  const int ci = 1024;
  const int &r1=ci; //正确
  int &r2 =ci; //错误

  1 2	对`const`的引用可能引用一个并非const的对象：

  int i = 42;
  int &r1 = i;
  const int &r2 =i;
  r1 = 0; //正确
  r2 = 0; //错误

  1

  * 指向常量的指针

  const double pi = 3.1415;
  double ptr = π //错误
  const double cptr = π //正确

斐波那契递归: 由斐波那契数列的递归关系推导出n>2时的状态矩阵，然后利用快速矩阵乘法完成；

知识点：

1. $n^m$次方，等于计算$n^{2^{(10010101..1101)}}$，用$m$的二进制位完成乘法；

2. 幂计算的过程中，有$m\&1$判断$m$的最右一个bit位是否为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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

//1.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int mod=1e9 + 7;
/*fib数列的1、2项为0，其余项为前两项的和；*/
int fib1(int n) //O(2^N)
{
    if(n<=1)
        return 1;
    return fib1(n) + fib1(n-1);   
}

int fib2(int n) //O(N)
{
    if(n==1 || n==2)
        return 1;
    int res=1;
    int pre=1;
    int tmp=0;
    for(int i=3;i<=n;++i)
    {
        tmp = res;
        res = pre + res;
        pre = tmp;
    }
    return res;
}



vector<vector<long>> multiply(vector<vector<long>> mat1,vector<vector<long>> mat2)
{
    vector< vector<long>> res(mat1.size(), vector<long>(mat2[0].size(), 0));
    for(int i=0; i<mat1.size(); i++)
    {
        for(int j=0; j<mat2[0].size(); j++)
        {
            for(int k=0; k < mat1[0].size(); k++)
            {
                //res[i][j] += mat1[i][k]*mat2[k][j]; 
                res[i][j]=(res[i][j]+(mat1[i][k]*mat2[k][j])%mod)%mod;
            }
        }
    }
    return res;
}

vector< vector<long>> matrixPower(vector< vector<long>> base, long p)//O(logN)
/*
base: A state matrix;
p: the power number.
*/
{
    vector<vector<long>> res(base.size(), vector<long>(base.size(),0));
    //Set to a unit matrix
    for(int i=0; i<res.size(); i++)
    {
        res[i][i] = 1;
    }
    for(;p!=0; p>>=1)
    {
        if((p&1)!= 0) //every last bit of p 
            res = multiply(base,res);
        base = multiply(base, base); //update tmp for next multuply res when last bit of p equal to 1
    }
    return res;
}

  
void fib3(long n)
{
    vector<vector<long>> base={{1, 1},{1, 0}};
    vector<vector<long>> ans;
    ans = matrixPower(base, n-2);
    cout<<(ans[0][0]+ans[0][1])% mod<< endl;
}


int main(){
    long n;
    cin >> n;
    if(n<1)
    {
        cout << 0;
        return 0;
    }
    if(n==1 || n==2)
    {
        cout << 1;
        return 0;
    }
    fib3(n);
    return 0;
}

最近邻算法

(1).最初版本的算法是这样：

目标：对一个新输入向量 $\mathbf{x}$ 进行分类:

1. 在训练集中找到最近离$\mathbf x$最近的点$\mathbf x^{\ast}$，因此定义一个度量如欧几里得距离；

2. $\mathbf x^{\ast}$的标签$\mathbf y^{\ast}$就是$\mathbf x$的标签。

前言：函数的增长

• 算法的渐进效率：我们关心当输入规模无限增加时，算法的运行时间如何随着输入规模的变大而增加。例子：输入规模$n$增大，最坏情况运行时间为$\Theta(n\lg n)$的归并排序战胜最坏情况运行时间为$\Theta(n^2)$的插入排序；
• 我们设最坏情况运行时间函数为$T(n)$；
• 算法分析的种类：

   最坏情况（Worst Case）：任意输入规模的最大运行时间。（Usually）
  平均情况（Average Case）：任意输入规模的期待运行时间。（Sometimes）
  最佳情况（Best Case）：通常最佳情况不会出现。（Bogus）
  

主成分分析—两种视角

前言：降维方法：主要有主成分分析（PCA）、线性判别分析（LDA）、等距映射（Isomap）、局部线性嵌入（LLE）、拉普拉斯特征映射（LE）、局部保留投影（LPP）；

最大方差

给定训练集合${x_n},n=1,2,…,N$，样本维度是$D$

目标是：样本数据转换为投影数据，其维度为$M$，同时最大化投影数据的协方差。

前言：拉格朗日对偶性

1. 假设$f(x),c_i(x),h_j(x)$是定义在$\mathbf R^n$ 上的连续可微函数。原始问题定义为满足下列条件的约束不等式：