这个主要是自己学习mongoDB的一些小的笔记

##mongoDB简介

  • MongoDB是一个面向文档的数据库,而不是关系型数据库(Mysql)与关系型数据库相比,文档型数据块不再有“行”(row)的概念,取而代之的是“文档”(Document)模型,主要是运用一条记录来表现复杂的层次关系

  • 没有固定的类型和大小,可以存储任意的数据类型和大小,包括很大的数据内容

  • MongoDB可以很方便的进行分片,可以采取分布式的部署方式

  • 索引:MongoDB支持通用二级索引,允许多种快速索引

##MongoDB shell简单命令

  • 数据库的查看show dbs

  • 使用数据库use lab

  • 显示集合show collections

  • 显示文档,db.sessions.find()

  • 创建文档

    post = {“title” : “My Blog Post”,”content” : “Here’s my blog post”,”date” : new Date()}
    {

    "title" : "My Blog Post",
    "content" : "Here's my blog post"
    "date" : ISODate("2015-01-29T21:00:00.982Z")
    

    }
    //创建
    db.blog.insert(post)
    //查看
    db.blog.find()
    //查看其中一个
    db.blog.findOne()

  • 更新文档
    修改post变量,增加键”comments”

    post.comments = []
    执行update操作,替换标题为”My Blog Post”的文章
    db.blog.update({titile : “My Blog Post”}, post)
    db.blog.find()
    {

    "_id":
    "titile"
    "content"
    "date"
    "comments" : [ ]
    

    }

  • 删除文档

    db.blog.remove({title : “My Blog Post”})

  • 删除数据库

    drop blog

##nodejs中使用MongoDB

var mongodb = require('./db');

function Report(name, grade, time, Report) {
  this.name = name;
  this.grade = grade;
  this.time = time;
  this.report = Report;
};
module.exports = Report;

Report.prototype.save = function save(callback) {
  // 存入 Mongodb 的report
  var report = this.report;
  var name =this.name;
  var grade=this.grade;
  var time= this.time;
  mongodb.open(function(err, db) {
    if (err) {
      return callback(err);
    }
    // 读取report
    db.collection('report', function(err, collection) {
      if (err) {
        mongodb.close();
        return callback(err);
      }
      // 若存在则更新,若不存在则增加
      collection.update({"name": name, "grade":grade, "time": time}, {$set: {"report" : report}}, {upsert:true}, function(err, report) {
        mongodb.close();
        callback(err, report);
      });
    });
  });
};

Report.get = function get(name, callback) {
  mongodb.open(function(err, db) {
    if (err) {
      return callback(err);
    }
    // 讀取 posts 集合
    db.collection('report', function(err, collection) {
      if (err) {
        mongodb.close();
        return callback(err);
      }
      // 查找 user 屬性爲 username 的文檔,如果 username 是 null 則匹配全部
      var query = {};
      if (name) {
        query.name = name;
      }
      collection.find(query).sort({time: -1}).toArray(function(err, docs) {
        mongodb.close();
        if (err) {
          callback(err, null);
        }
        // 封裝 posts 爲 Post 對象
        var reports = [];
        docs.forEach(function(doc, index) {
          var report = new Report(doc.name, doc.grade, doc.time, doc.report);
          reports.push(report);
        });
        //console.log(reports);
        callback(null, reports);
      });
    });
  });
};

##决策树小结

决策树分类器就像带有终止块的流程图,终止块表示分类结果。
开始处理数据集时,我们首先需要测量集合中数据的不一致性,也就是熵,然后寻找最优方案划分数据集,直到数据集中的 所有数据属于同一分类。
ID3算法可以用于划分标称型数据集。构建决策树时,我们通常采用递 归的方法将数据集转化为决策树。一般我们并不构造新的数据结构,而是使用python语言内嵌的 数据结构字典存储树节点信息。
使用Matplotlib的注解功能,我们可以将存储的树结构转化为容易理解的图形。python语言的pickle模块可用于存储决策树的结构。隐形眼镜的例子表明决策树可能会产生过多的数据集划分, 从而产生过度匹配数据集的问题。我们可以通过裁剪决策树,合并相邻的无法产生大量信息增益 的叶节点,消除过度匹配问题。
还有其他的决策树的构造算法,最流行的是C4.5和CART

##问题描述

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 

该问题即要求计算出excle表格中块对应的数字
每一行有26个,换到下一行即AA,AB,AC,下下行BA,BB,BC
以此类推


#java代码
public class Solution {
public int titleToNumber(String s) {
int result = 0;
for (int i = 0; i < s.length(); result = result * 26 + (s.charAt(i) - ‘A’ + 1), i++);
return result;
}
}


##Tips

该问题比较简单,看一下代码就可以明白

##问题描述

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.


##问题分析

该问题比较简单
即数组合并的问题,其中A数组长度为m+n


##c++代码
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int i = m - 1;
int j;
for(j = n - 1; j>=0; j–){
while((A[i] > B[j]) && i >= 0 ){
A[i + j + 1] = A[i];
i–;
}
A[i + j + 1] = B[j];
}
}

};

##k-近邻算法的一般流程

(1)收集数据:可以使用任何方法。

(2)准备数据:距离计算所需要的数值,最好是结构化的数据格式。

(3)分析数据:可以使用任何方法。

(4)测试算法:计算错误率。

(5)使用算法:首先需要输入样本数据和结构化的输出结果,然后运行女-近邻算法判定输
入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。


##k-近邻算法分类器的构造

对未知类别属性的数据集中的每个点依次执行以下操作:

(1)计算已知类别数据集中的点与当前点之间的距离;

(2)按照距离递增次序排序;

(3)选取与当前点距离最小的走个点;

(4)确定前灸个点所在类别的出现频率;

(5)返回前女个点出现频率最高的类别作为当前点的预测分类。


##分类器的检测

通过大量数据检测分类器构造是否准确


##实例 —— 在约会网站上使用&近邻算法

(1)收集数据:提供文本文件。

(2)准备数据: 使用python解析文本文件。

(3)分析数据:使用Matplotlib化画二维扩散图。

(4)训练算法:此步驟不适用于k-近邻算法

(5)测试算法:使用海伦提供的部分数据作为测试样本。

(6)使用算法:产生简单的命令行程序,然后可以输入一些特征数据以判断对方是否为自己喜欢的类型。


##Tips

1.在机器学习中经常会利用矩阵,线性代数等方面知识,一般需要导入numpy包
from numpy import *

2.在图像识别过程中,一般是将图像分为像素点,用1,0来表示,记录矩阵

##问题描述

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.


##问题分析

该问题即字符串匹配,解决该这类型问题最好使用,队列、堆栈数据结构
堆栈是一个不错的想法

在解决匹配的时候需要用到两个值,考虑hashmap的key-value模式

##java代码

public class Solution {
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        Map<Character,Character> pairs = new HashMap<Character,Character>();
        //key-value
        pairs.put('(',')');
        pairs.put('[',']');
        pairs.put('{','}');
        Stack<Character> stack = new Stack<Character>();
        for(char c:chars){
            //key=c,对应的value是否存在,存在返回true
            if(pairs.containsKey(c)){
                //获取value
                stack.push(pairs.get(c));
            } else{
                if(stack.isEmpty() || c != stack.pop() ){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

##问题描述

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

##问题分析

该问题要求对已经排好的数组进行范围查找,邀请时间复杂度为O(log n)
为了满足该时间复杂度,应用二分查找的方法进行改造

##java代码
public class Solution {
public int[] searchRange(int[] A, int target) {
int low = 0;
int high = A.length - 1;
int[] flag = new int[2];
int flag_low,flag_high;
while(low <= high && low <= A.length - 1 && high <= A.length - 1){
int middle = low + ((high-low)>>1);
if(A[middle] == target){
flag_low = middle;
flag_high = middle;

                while(flag_low>=0 && A[flag_low] == target){
                    flag_low --;
                }
                while(flag_high<= A.length-1 && A[flag_high] == target){
                    flag_high ++;
                }
                flag[0] = flag_low + 1;
                flag[1] = flag_high - 1;
                return flag;
            } else if(A[middle] < target){
                low = middle + 1;
            } else{
                high = middle - 1;
            }
        }
        flag[0] = -1;
        flag[1] = -1;
        return flag;
    }
}

##注意

主要还是注意数组越界,还有二分的思想

##问题描述
>

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

>

But the following is not:

  1
 / \
2   2
 \   \
 3    3

##C++ code

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        TreeNode *left,*right;
        if(root == NULL) return true;
        queue<TreeNode *> q1,q2;
        q1.push(root->left);
        q2.push(root->right);
        while(!q1.empty() && !q2.empty()){
            left = q1.front();
            q1.pop();
            right = q2.front();
            q2.pop();
            if(left == NULL && right == NULL){
                continue;
            }
            if(left == NULL || right == NULL){
                return false;
            }
            q1.push(left->left);
            q1.push(left->right);
            q2.push(right->right);
            q2.push(right->left);
        }
        return true;
    }
}

##问题分析

该问题要利用一个队列存储节点

##问题描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

该问题即要求设计一个栈,并能取回最小值(这个是最重要的)

##Java代码

class MinStack {
    static class Element{
        final int val;
        final int min;
        Element(final int val,final int min){
            this.val = val;
            this.min = min;
        }
    }

    final Stack<Element> stack = new Stack<>();

    public void push(int x) {
        final int min = (stack.empty() ? x : Math.min(stack.peek().min , x) );
        stack.push(new Element(x,min));
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek().val;
    }

    public int getMin() {
        return stack.peek().min;
    }
}

##问题简单分析

利用java内置的stack类,注意把最小值和value又存在另外的一个Element类中

##code

# -*- coding: utf-8 -*-

import urllib2
import re
import thread
import time


#----------- 加载处理糗事百科 -----------
class Spider_Model:

    def __init__(self):
        self.page = 1
        self.pages = []
        self.enable = False

    # 将所有的段子都扣出来,添加到列表中并且返回列表
    def GetPage(self,page):
        myUrl = "http://m.qiushibaike.com/hot/page/" + page
        user_agent = 'Mozilla/4.0 (compatible; MSIE 5.5; Windows NT)'
        headers = { 'User-Agent' : user_agent }
        req = urllib2.Request(myUrl, headers = headers)
        myResponse = urllib2.urlopen(req)
        myPage = myResponse.read()
        #encode的作用是将unicode编码转换成其他编码的字符串
        #decode的作用是将其他编码的字符串转换成unicode编码
        unicodePage = myPage.decode("utf-8")

        # 找出所有class="content"的div标记
        #re.S是任意匹配模式,也就是.可以匹配换行符
        myItems = re.findall('<div.*?class="content".*?title="(.*?)">(.*?)</div>',unicodePage,re.S)
        items = []
        for item in myItems:
            # item 中第一个是div的标题,也就是时间
            # item 中第二个是div的内容,也就是内容
            items.append([item[0].replace("\n",""),item[1].replace("\n","")])
        return items

    # 用于加载新的段子
    def LoadPage(self):
        # 如果用户未输入quit则一直运行
        while self.enable:
            # 如果pages数组中的内容小于2个
            if len(self.pages) < 2:
                try:
                    # 获取新的页面中的段子们
                    myPage = self.GetPage(str(self.page))
                    self.page += 1
                    self.pages.append(myPage)
                except:
                    print '无法链接糗事百科!'
            else:
                time.sleep(1)

    def ShowPage(self,nowPage,page):
        for items in nowPage:
            print u'第%d页' % page , items[0]  , items[1]
            myInput = raw_input()
            if myInput == "quit":
                self.enable = False
                break

    def Start(self):
        self.enable = True
        page = self.page

        print u'正在加载中请稍候......'

        # 新建一个线程在后台加载段子并存储
        thread.start_new_thread(self.LoadPage,())

        #----------- 加载处理糗事百科 -----------
        while self.enable:
            # 如果self的page数组中存有元素
            if self.pages:
                nowPage = self.pages[0]
                del self.pages[0]
                self.ShowPage(nowPage,page)
                page += 1


#----------- 程序的入口处 -----------
print u"""
---------------------------------------
   程序:糗百爬虫
   版本:0.3
   作者:why
   日期:2014-06-03
   语言:Python 2.7
   操作:输入quit退出阅读糗事百科
   功能:按下回车依次浏览今日的糗百热点
---------------------------------------
"""


print u'请按下回车浏览今日的糗百内容:'
raw_input(' ')
myModel = Spider_Model()
myModel.Start()

##code

# -*- coding: utf-8 -*-
#!/usr/bin/python

'''
    name: get_pay_info
    function: 自动获取流量信息
    lib: requests, lxml, tesseract
    parameters:
        BASE_URL---基本的url,在此网址获取用户名,密码和验证码图片
        FORM_URL---登陆的url
        PAY_INFO_URL---获取信息的url
        USERNAME(username)---用户名
        PASSOWORD(passoword)---密码
        checkcode---验证码
'''

import re
import time
import os
import requests
from lxml import html

USERNAME = "*********"
PASSOWORD = "*******"

BASE_URL = "http://zyzfw.xidian.edu.cn:8800/"
FORM_URL = "http://zyzfw.xidian.edu.cn:8800/index.php?action=login"
PAY_INFO_URL = "http://zyzfw.xidian.edu.cn:8800/index.php"

TMP_DIR = os.path.expanduser("~/.xidian/")
IMG_PATH = os.path.join(TMP_DIR, "img.jpg")
TEXT_PATH = os.path.join(TMP_DIR, "result.txt")

'''
    name: make_data_and_cookies
    function: 获取登陆所需的数据和cookies
    return: data,cookies
'''
def make_data_and_cookies():
    """make the post data(including vcode) and get cookies"""

    vcode = ''
    while len(vcode) is not 4:
        r = requests.get(BASE_URL)
        doc = html.document_fromstring(r.text)

        vcode_link = doc.cssselect('form img')[3].get('src')
        img_url = BASE_URL + vcode_link
        img = requests.get(img_url)

        # write to the image file
        with open(IMG_PATH, 'w') as f:
            f.write(img.content)

        # using tesseract to get the vcode img value
        try:
            os.popen('tesseract %s %s' % (IMG_PATH, TEXT_PATH[:-4]))
        except:
            print "open tesseract error"
        with open(TEXT_PATH) as f:
            vcode = f.read().strip('\n')

    data = {
            "username": USERNAME,
            "password": PASSOWORD,
            "checkcode": vcode,
            "ts": "login"
            }
    return data, r.cookies

'''
    name: submit_form
    parameters: data,cookies(其意义与上函数类似)
    function: 模仿form进行登陆
    return: None
'''
def submit_form(data, cookies):
    """submit the login form so you're logined in"""
    form_action_url = FORM_URL
    r = requests.post(form_action_url, data=data, cookies=cookies)

'''
    name: get_info
    parameters: cookies
    function: 获取信息,并打印出来
    return: None
'''
def get_info(cookies):
    """retrieve the data using the cookies"""
    info_url = PAY_INFO_URL
    r = requests.get(info_url, cookies=cookies)
    doc = html.document_fromstring(r.text)
    #items = re.findall('<td class="title td_content">(.*?)</td>',r.text, re.S)
    messageList = doc.cssselect('div table tbody tr td')[41].text_content()
    lMsg = messageList.strip().split("\n")
    for i in lMsg:
        print i.strip()

if __name__ == '__main__':
    if not os.path.exists(TMP_DIR):
        os.mkdir(TMP_DIR)

#循环,直至成功才跳出循环

    while True:
        data, cookies = make_data_and_cookies()
        submit_form(data, cookies)
        time.sleep(1)
        try:
            get_info(cookies)
            break
        except:
            time.sleep(1)

###参考http://github.com/dby

##问题描述

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

click to show clarification.

简单介绍一下,即字符串的反转

##python代码
class Solution:

# @param s, a string
# @return a string
def reverseWords(self, s):
    items = s.strip().split(" ")
    items = items[::-1]
    str = ""
    for i in items:
        if(i != ""):
            str = str + i + " "
    str = str[0:len(str)-1]
    return str

##问题分析
>

本题主要需要注意空格的分割

##nodejs普通传值

doLogin时,如果用户名和密码正确,我们使用redirect方法跳转到的home

res.redirect('/home');

执行exports.home时,我们又用render渲染页面,并把user对象传给home.html页面

res.render('home', { title: 'Home',user: user});

为什么不能在doLogin时,就把user对象赋值给session,每个页面就不再传值了。

session这个问题,其实是涉及到服务器的底层处理方式。

##Java

像Java的web服务器,是多线程调用模型。每用户请求会打开一个线程,每个线程在内容中维护着用户的状态。

##PHP

像PHP的web服务器,是交行CGI的程序处理,CGI是无状态的,所以一般用cookie在客户的浏览器是维护用户的状态。但cookie在客户端维护的信息是不够的,所以CGI应用要模仿用户session,就需要在服务器端生成一个session文件存储起来,让原本无状态的CGI应用,通过中间文件的方式,达到session的效果。

##nodejs

Nodejs的web服务器,也是CGI的程序无状态的,与PHP不同的地方在于,单线程应用,所有请求都是异步响应,通过callback方式返回数据。如果我们想保存session数据,也是需要找到一个存储,通过文件存储,redis,Mongdb都可以。

通过mongodb来保存session,并实现登陆后用户对象传递。

##问题描述

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

比较两个二叉树是否完全相同,包括节点的值和节点的结构

##问题解决

###C++代码

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p == NULL && q == NULL) return true;
        if(p !=NULL && q ==NULL) return false;
        if(p ==NULL && q !=NULL) return false;
        if((p->val != q->val)  ) return false;
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

##问题解析

该问题与Minimum Depth of Binary Tree 问题,等二叉树的问题都是一样的,需要运用递归不断查找

nodejs的安装

1.从http://nodejs.org 中下载Node.js for MAC 安装

2.安装npm,npm是Node.js的套件管理工具(它非常重要,用来添加各种stupff到node机器)

sudo npm update npm -g

安装express

安装express4.x 版本请用

sudo npm install -g express-generator(4.x版本)
(npm install express是4以下的安装方式)

然后创建express工程 nodetest
express ~/Desktop/node/nodetest
cd ~/Desktop/node/nodetest

安装mongodb

1.去http://www.mongodb.org/downloads下载mongoDB包

2.解压缩,在mongod/bin下面有mongo和mongod两个可执行文件,其中mongo类似于mysql的shell,mongod是管理用的客户端

3.创建mongo数据库默认存放位置
sudo mkdir /data/db

4.修改data的可读可写属性(很重要)
sudo chmod -R 777 /data

5.添加快捷方式

vim ~/.bash_profile
alias mongo=”/mongod/bin/mongo”
alias mongod=”/mongod/bin/mongod”

6.启动mongo

mongod --dbpath /var/data/mongo (- -)

mongo - -dbpath=/data/db (dbpath位置可改变)

修改package.json

{
“name”: “nodetest1”,
“version”: “0.0.1”,
“private”: true,
“scripts”: {
“start”: “node ./bin/www”
},
“dependencies”: {
“express”: “~4.9.0”,
“body-parser”: “~1.8.1”,
“cookie-parser”: “~1.3.3”,
“morgan”: “~1.3.0”,
“serve-favicon”: “~2.1.3”,
“debug”: “~2.0.0”,
“jade”: “~1.6.0”,
“ejs”: “1.0.0”,
“node-xlsx”: “0.4.0”,
“mongodb” : “1.4.3”
}
}

安装依赖包

sudo npm install

测试是否成功

node app.js

打开浏览器输入 http://localhost:3000 你将会看到 Express 的欢迎页面