leetcode 17

17. Letter Combinations of a Phone Number

Medium

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解决方案：

使用递归解决问题：

在这个思路里面， 首先是将一个大问题变成一个数字的小问题，然后在此基础上每次加一个字，将这个数字所代表的代表每个都加在原来形成的字符串的上面
举例：
2 a b c
3 d e f

首先，将其变成一个只含有3的问题
此时ans中只有 d e f
tmp <- ans
ans.push_back(map[digits[0] - '0'][i] + tmp[j]);
ad ae af
bd be bf
cd ce cf
结束

class Solution {
public:
    static const string map[10];
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if (digits.length() > 0) {
            // 先去掉第一位，变成一个规模小1的问题以递归解决
            vector<string> tmp = letterCombinations(digits.substr(1, digits.length() - 1));
            // 处理边界情况
            if (tmp.size() == 0) {
                tmp.push_back("");
            }
            // 在递归计算出的答案前添加上所有第0位可能对应的字母来组成新的答案集
            for (int i = 0; i < map[digits[0] - '0'].length(); i++) {
                for (int j = 0; j < tmp.size(); j++) {
                    ans.push_back(map[digits[0] - '0'][i] + tmp[j]);
                }
            }
        }
        return ans;
    }
    
};
// 对应表

const string Solution::map[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

# 使用深度优先搜索

class Solution {
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.empty()) return {};
        //定义vector存储对应的点
        vector<vector<char>> d(10);
        d[0] = {};
        d[1] = {};
        d[2] = {'a', 'b', 'c'};
        d[3] = {'d', 'e', 'f'};
        d[4] = {'g','h','i'};
        d[5] = {'j','k','l'};
        d[6] = {'m','n','o'};
        d[7] = {'p','q','r','s'};
        d[8] = {'t','u','v'};
        d[9] = {'w', 'x', 'y', 'z'};
        string cur;
        vector<string> ans;
        dfs(digits, d, 0, cur, ans);
        return ans;
     } 
private:
    void dfs(const string& digits, const vector<vector<char>>& d, int l, string& cur, vector<string>& ans)
    {
        if (l == digits.length())
        {
            ans.push_back(cur);
            return ;
        }
        for (const char c: d[digits[l] - '0'])
        {
            cur.push_back(c);
            dfs(digits, d, l+1, cur, ans);
            cur.pop_back();
        }
    }

};

# 使用广度优先搜索
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<vector<char>> d(10);
        d[0] = {' '};
        d[1] = {};
        d[2] = {'a','b','c'};
        d[3] = {'d','e','f'};
        d[4] = {'g','h','i'};
        d[5] = {'j','k','l'};
        d[6] = {'m','n','o'};
        d[7] = {'p','q','r','s'};
        d[8] = {'t','u','v'};
        d[9] = {'w','x','y','z'};
        vector<string> ans{""};
        for (char digit : digits) {
            vector<string> tmp;
            for (const string& s : ans)
               for (char c : d[digit - '0'])
                    tmp.push_back(s + c);
            ans.swap(tmp);
        }
        return ans;
    }

};

leetcode 236

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if (not root) or (root == q) or (root == p):
            return root
        leftNode = self.lowestCommonAncestor(root.left, p, q)
        rightNode = self.lowestCommonAncestor(root.right, p, q)
        if leftNode and rightNode:
            return root
        else:
            return leftNode if leftNode else rightNode

链表翻转

#include <iostream>
using namespace std;

/*
链表翻转。给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，
若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。
*/

struct LinkList
{
int data;
LinkList* next;
LinkList(int i=0){data=i; next=NULL;}
};

void print_list(LinkList* head){
LinkList* p = head;
while(p){
cout<<p->data<<' ';
p = p->next;
}
cout<<endl;
}

LinkList* reverse(LinkList* head, int k){
    if(head == NULL)
    {
        return NULL;
    }
    int i = k;
    LinkList* end = head;
    int length = 1;
    while(--i)
    {
        if(end->next==NULL){
            k = length;
            break;
        }
        else{
            end = end->next;
            length += 1;
        }
    }
    i = k;
    LinkList* save = end->next;
    LinkList* p1 = head;
    LinkList* p2 = head->next;
    while(--i)
    {
        LinkList* temp = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = temp;
    }
    head->next = reverse(save, k);
    return end;
}

int main(){
LinkList* n1 = new LinkList(1);
LinkList* p = n1;
for(int i=2; i<12; i++)
{
LinkList* temp = new LinkList(i);
p->next = temp;
p = p->next;
}
print_list(n1);
    LinkList* a = reverse(n1, 4);
    print_list(a);

}

fasttext初学习

第一步：理解
https://www.leiphone.com/news/201608/y8rhWEglraduqcOC.html

第二步：官方文档
  fasttext库有两个主要的用例：词表征学习（应该是向量表征）和文本分类。

1.词表征学习（word representation learning）
为了获取词向量，

./fasttext skipgram -input data.txt -output model

data.txt是utf-8编码的文件，生成model.bin和model.vec. model.vec是词向量表征，model.bin是包括模型的参数信息和所有的超参数。二进制文件稍后可用于计算词向量或重新开始优化

1.2.为词外特征获取单词向量

类变量、实例变量、局部变量和全局变量

1.类变量
定义：类变量被所有的类实例共享，通常都定义在类声明下面，他被所有的类实例共享

所在位置：类中，函数声明外

什么时候加载：在文件导入到其他文件时加载

如何在函数中调用：在类函数中必须使用ClassName.class_variable = ***来赋值，否则，你创建的只是一个实例变量，举例如下：

class Test(object):
    class_variable = 1
    def func(self):
        Test.class_variable = 2 (正确)
        class_variable = 2(错误，这是一个实例变量)

存在时间：一个到该脚本结束？

python官网的链接：https://www.python-course.eu/python3_class_and_instance_attributes.php

2.实例变量

所在位置：class内，self修饰

3.局部变量：在函数的class内，（不加self）
定义：在一个函数中，一个变量第一次出现，并在=的前面，那么他是一个实例变量

4.全局变量：在模块内，函数和类外面

maven下载加速

在home目录下，修改setting.py脚本如下：

<settings xmlns="http://maven.apache.org/SETTINGS/1.0.0"
      xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
      xsi:schemaLocation="http://maven.apache.org/SETTINGS/1.0.0
                          https://maven.apache.org/xsd/settings-1.0.0.xsd">
      <mirrors>
        <mirror>
            <id>alimaven</id>
            <name>aliyun maven</name>
            <url>http://maven.aliyun.com/nexus/content/groups/public/</url>
            <mirrorOf>central</mirrorOf>
        </mirror>
      </mirrors>
</settings>

xgboost

实用，全面 https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf


dataframe 实现 http://www.cnblogs.com/zhaochunhua/p/6723660.html

解决出现的问题： https://github.com/dmlc/xgboost/issues/2480