Some notes recorded during the learning data structure and algorithms

常见的数据结构(ADT)有, 链表, 栈, 队列, 有限队列和堆, 表(unique elements), 哈希表, 树(无圈的图), 图.

常见的算法有, 排序, 查找, 图, 字符串.

另一种划分

策略, 分治, 贪心, 动规, BFS, DFS, 模拟.

recursion and algorithm analysis

对于分治,有以下公式

对于减治, 有一下公式

一般的, 对于具体代码的复杂度分析, 我们分析最差情况, 对每一层for内的i,j最差能达到n的什么数量级进行分析, 一般对半分是logn, 对于指数等比较大的相比较, 我们先求对数, 在比较.

对于$\sqrt{n}$形式, 引入$n=2^{m}$, 求出m的复杂度后反带回去

回溯的核心就是剪枝, 去掉完全不可能的选择.

常见的回溯题

  • Binary Strings: generating all binary strings
  • Generating k – ary Strings
  • N-Queens Problem
  • The Knapsack Problem
  • Generalized Strings
  • Hamiltonian Cycles [refer to Graphs chapter]
  • Graph Coloring Problem”

矩阵连通量分析, 可以用到bfs

链表

ADT, 抽象数据类型, 用来定义通用的数据和方法, 具体内容具体化的时候才定义. 比如树, 分为二叉树等,

动态规划

  1. 1,2,5,10,50,100元面值，给你一个数值，怎么计算这个数用人民币表示的方法

  2. 一个台阶 100级, 一次上1,2步, 一共多少种方法

都是一个类型的题目, 按照递归去想.

  1. 12个小球里面一个重量不一样的，称3次找出来

二分

  1. This is microsoft”逆序成“microsoft is This”，他还没说完我就把题目说了，这个写的也不难，之前见过，我就按照传统的方法写了，但是他问可不可以直接根据空格逆序输出。
  2. 如何判断一个数是否是2的指数幂

有很多种二进制1的个数那一种，在他的提示下想起来了n&(n-1)==0

减一, 肯定是最低层的1000的1被消去, 编程0111, 然后&一下, 就可以变成0.

  1. 囚徒困境(博弈)

  2. c++和java有什么不同
    java面向对象更强一些, 思考方式肯定有点不一样,

区别

  1. java没有指针,只有引用
  2. 完全面向对象, 而c++是可选的, 相比较java效率就低一些
  3. 主动多态, 同名成员函数上溯到根源向下调用.
  4. 多继承替代接口.

多态, 根据对象不同, 函数操作不同.

重载–julia使用.

圈检测

circle detection

Inline函数

一般用在体积小, 经常调用的函数, 内部有很多调用的话,用inline相当于自动展开, 不用继续调用函数(有时间花销)

指针与引用

引用不会为0, 但是指针在使用的时候一定要先检查是不是指向0. vector可以作为引用传入, 也可以作为指针传入, 指针使用这样(*vec)[ix]

函数内部对象在内存的栈中, new出来的对象在堆中(注意内存泄漏)

C++提供函数重载和默认参数. 模板就是参数化类型.

初始化可以使用构造函数语法

int aa(0)

vector a(length)
vector a(aa, aa+len)
改造函数语法可以用在多初始值的情况下, c++中引入.

const定义常量, 在函数开头使用的话表示在内部不会修改该值, 一般用在指针上?

指针带来弹性, 不需要知道数组的大小.

防止指针为null

if(p && *p != 1024)

取地址&
取内容*

随机数


srand(xx);
rand();//返回一个从0到最大表示范围的整数.%size进行限制

IO流, 相当于构造函数


每一次 >> 都会读取一个内容
ifstream infile(“seq_data.txt”, ios_bas::app,ios_bas:in)

iofile.seekg(0)

if(!infile) 没有打开成功

Java String

http://www.cnblogs.com/yunfang/p/5028532.html#3322812

units test

http://www.cnblogs.com/coder2012/p/5092190.html

验证码

http://www.cnblogs.com/qldhlbs/p/5386679.html#3407416

CMAKE

http://www.cnblogs.com/ph829/p/4759124.html

多线程

http://rnavagamuwa.com/programming/multithreading-with-posix-threads/

tom cat

http://rnavagamuwa.com/open-source/embed-tomcat-in-your-spring-web-app/

strcmp c++

#include 
#include 
#include 
using namespace std;

int _strcmp(const char* s1, const char* s2) {
    assert(s1 != NULL && s2 != NULL);
    while (*s1 != '\0' && *s2 != '\0' && *s1 == *s2) {
        s1++;
        s2++;
    }
    if (*s1 > *s2) {
        return 1;
    }
    else if (*s1 < *s2) {
        return -1;
    }
    else {
        return 0;
    }


}

int main() {
    char* s1 = "123";
    char* s2 = "1234";
    char* s3 = "123";
    char* s4 = "234";
    cout << _strcmp(s1, s2) << endl;
    cout << _strcmp(s2, s1) << endl;
    cout << _strcmp(s3, s1) << endl;
    cout << _strcmp(s4, s2) << endl;
    cout << endl;
    cout << strcmp(s1, s2) << endl;
    cout << strcmp(s2, s1) << endl;
    cout << strcmp(s3, s1) << endl;
    cout << strcmp(s4, s2) << endl;
}

A* algorithms

http://www.skywind.me/maker/qfind_c.htm

关于几个网站部署的问题

1. gsoc MKDOCS

为正常项目添加文档

  1. 直接进入文件mkdocs new docs
  2. 把里面的内容复制出来, 包括config_.yml, docs
  3. git push
  4. 设置rep的网页为gh-pages
  5. mkdocs gh-deploy

之后只需要改了文档mkdocs gh-deploy即可

config_.yml用来存储文档结构, docs里面存放md文件.

2. 设置主页

直接clone别人的项目, 然后修改, (利用jekyll serve部署, 只需要修改config_.yml), 完成后推送到gh-pages 分支上即可

记住../可以用来返回上一层.

memoiry@outlook.com

Hexo公式的问题

之前公式老是出问题, 今天查了下找到是连续两个{出现的问题..这里记录一下

还有一个不显示的问题是符号的问题, 因为hexo 把 作为特殊符号, 所以在使用_的时候最好加个\, 避免出问题

虚函数

利用虚函数就很好地解决了这个问题。可以看到：当把基类的某个成员函数声明为虚函数后，允许在其派生类中对该函数重新定义，赋予它新的功能，并且可以通过指向基类的指针指向同一类族中不同类的对象，从而调用其中的同名函数。由虚函数实现的动态多态性就是：同一类族中不同类的对象，对同一函数调用作出不同的响应。

虚函数的使用方法是：
在基类用virtual声明成员函数为虚函数。
这样就可以在派生类中重新定义此函数，为它赋予新的功能，并能方便地被调用。在类外定义虚函数时，不必再加virtual。
在派生类中重新定义此函数，要求函数名、函数类型、函数参数个数和类型全部与基类的虚函数相同，并根据派生类的需要重新定义函数体。
C++规定，当一个成员函数被声明为虚函数后，其派生类中的同名函数都自动成为虚函数。因此在派生类重新声明该虚函数时，可以加virtual，也可以不加，但习惯上一般在每一层声明该函数时都加virtual，使程序更加清晰。如果在派生类中没有对基类的虚函数重新定义，则派生类简单地继承其直接基类的虚函数。
定义一个指向基类对象的指针变量，并使它指向同一类族中需要调用该函数的对象。
通过该指针变量调用此虚函数，此时调用的就是指针变量指向的对象的同名函数。
通过虚函数与指向基类对象的指针变量的配合使用，就能方便地调用同一类族中不同类的同名函数，只要先用基类指针指向即可。如果指针不断地指向同一类族中不同类的对象，就能不断地调用这些对象中的同名函数。这就如同前面说的，不断地告诉出租车司机要去的目的地，然后司机把你送到你要去的地方。

需要说明；有时在基类中定义的非虚函数会在派生类中被重新定义(如例12.1中的area函数)，如果用基类指针调用该成员函数，则系统会调用对象中基类部分的成员函数；如果用派生类指针调用该成员函数，则系统会调用派生类对象中的成员函数，这并不是多态性行为(使用的是不同类型的指针)，没有用到虚函数的功能。

所以说如果不适用虚函数的话, 继承后基类指针如果指向派生类, 其调用同名同参函数仍然调用的是基类的函数, 而不是派生类的函数.

　　C++的虚函数主要作用是“运行时多态”，父类中提供虚函数的实现，为子类提供默认的函数实现。

　　子类可以重写父类的虚函数实现子类的特殊化。

虚函数与纯虚函数

定义一个函数为虚函数，不代表函数为不被实现的函数。
定义他为虚函数是为了允许用基类的指针来调用子类的这个函数。
定义一个函数为纯虚函数，才代表函数没有被实现。
定义纯虚函数是为了实现一个接口，起到一个规范的作用，规范继承这个类的程序员必须实现这个函数。

bash

!$表示上条命令的文件参数

!!表示条命令全部

mv
echo
less
more

文本控制

grep "Error" *.log
grep -C 1 "Error" *.log

进一步想要分割列

grep "Error" *.log | awk '{print $5}'
egrep "Error:|Strin" *.log

cd - 返回
find

find /some/directory -name "*filename*"