D&C – Page 11 – 懒惰是人类进步的原动力

LeetCode 29. Divide Two Integers

Post author By idailylife
Post date 2016年9月7日
No Comments on LeetCode 29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

思路

边界条件：比如被除数、除数是0，另外结果的正负号要注意。
除法可以用减法实现，不过如果干减的话会很费时间，所以要想想怎么加速。
容易知道，一个数左移一位相当于乘以2。我们可以一次次把除数乘以2试探一下，到底最多能减掉 2^n*除数 多少次，这就相当于做了2^n次除法。由于试探的时候一次次做了乘方，所以试探的次数是log级别的，比原来一个个减要快多了。

代码

class Solution {
public:
	int divide(int dividend, int divisor) {
		if (dividend == 0)
			return 0;
		if (divisor == 0)
			return INT_MAX;
		bool posResult = true;
		if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor >0))
			posResult = false;
		long long lDividend = dividend;
		if (lDividend < 0)
			lDividend = ~(lDividend-1);
		long long lDivisor = divisor;
		if (lDivisor < 0)
			lDivisor = ~(lDivisor-1);
		long long currDivisor = lDivisor;
		long long accRate = 1;
		long long result = 0;
		while (lDividend >= lDivisor) {
			while ((currDivisor << 1) < lDividend) {
				currDivisor <<= 1;
				accRate <<= 1;
			}
			while (currDivisor > lDividend) {
				currDivisor >>= 1;
				accRate >>= 1;
			}
			lDividend -= currDivisor;
			result += accRate;
		}
		if (posResult) {
			if (result > INT_MAX) {
				return INT_MAX;
			}
			else {
				return (int)result;
			}
		}
		else {
			result = -result;
			if (result < INT_MIN)
				return INT_MIN;
			else
				return (int)result;
		}
	}
};

不学无术

LeetCode 103. Binary Tree Zigzag Level Order Traversal

Post author By idailylife
Post date 2016年9月7日
No Comments on LeetCode 103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路

记住上一行的输出（结果）节点，每一次从后往前读出下一行，这样第2,4,6次读的时候其实就会翻转成正向了。唯一的问题是左右子节点写入下一行的顺序，按照当前顺序区分一下就行。不是左右左右，就是右左右左，具体看code吧。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == NULL)
            return result;
        vector<TreeNode*>* currRow = new vector<TreeNode*>();
        vector<TreeNode*>* nextRow = new vector<TreeNode*>();
        bool direction = true;  //true: R,L,R,L,...; false:L,R,L,R,...
        currRow->push_back(root);
        while(!currRow->empty()){
            //Output current row
            vector<int> currRowResult;
            for(int i=0; i<currRow->size(); i++){
                currRowResult.push_back( (*currRow)[i]->val );
            }
            result.push_back(currRowResult);
            //
            for(int i=currRow->size()-1; i>=0; i--){
                TreeNode* currNode = (*currRow)[i];
                if(direction){
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                } else {
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                }
            }
            //swap currRow and nextRow
            vector<TreeNode*>* temp = currRow;
            currRow = nextRow;
            nextRow = temp;
            nextRow->clear();
            direction = !direction;
        }
        return result;
    }
};

Tags LeetCode OJ, 二叉树

木有技术

LeetCode 173. Binary Search Tree Iterator

Post author By idailylife
Post date 2016年9月5日
No Comments on LeetCode 173. Binary Search Tree Iterator

思路

画一个简单的BST，然后可以看出有三种情况

如果当前节点有右孩子，那就在右子树里找到值最小的那个，显然是右子树里最左下侧的那个节点
如果当前节点没有右孩子，由于左子树的值肯定都比当前节点的值小，左右要找父节点
- 如果找到某个父节点的值比当前节点值大，那这个父节点就是下一节点
- 否则，当前节点就是最后一个节点

因此，需要一个栈结构记录当前节点的父亲们（有点像调用栈）。
测试例：NULL根节点，只有一个节点，只有单侧树

代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> callStack;
    TreeNode* currNode;
    TreeNode* rootNode;
public:
    BSTIterator(TreeNode *root) {
        currNode = NULL;
        rootNode = root;
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(currNode == NULL){
            currNode = rootNode;
            while(currNode!=NULL && currNode->left != NULL){
                callStack.push(currNode);
                currNode = currNode->left;
            }
            return currNode!=NULL;
        }
        if(currNode->right != NULL){
            //left-most node in right sub-tree
            callStack.push(currNode);
            currNode = currNode->right;
            while(currNode->left != NULL){
                callStack.push(currNode);
                currNode = currNode->left;
            }
            return true;
        } else {
            //look for first parent whos val is > currNode->val. If not available, return false
            int currVal = currNode->val;
            while(!callStack.empty()){
                TreeNode* parent = callStack.top();
                callStack.pop();
                if(parent->val > currVal){
                    currNode = parent;
                    return true;
                }
            }
            currNode = NULL;
            return false;
        }
    }
    /** @return the next smallest number */
    int next() {
        if(currNode != NULL)
            return currNode->val;
        return INT_MIN;
    }
};
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Tags BST, LeetCode OJ, 二叉树, 数据结构

不学无术

LeetCode 50. Pow(x, n)

边界检查：0，INT_MAX, INT_MIN

class Solution {
private:
    map<int, double> memory;
public:
    double myPow(double x, int n) {
        if(n == 0)
            return 1.0;
        if(n == 1)
            return x;
        if(n == -1)
            return 1/x;
        if(memory.count(n)>0)
            return memory[n];
        double result = myPow(x, n/2) * myPow(x, n/2);
        if(n%2 != 0){
            result *= (n<0)? 1/x : x;
        }
        memory[n] = result;
        return result;
    }
};

Tags LeetCode OJ

不学无术

LeetCode 134. Gas Station

Post author By idailylife
Post date 2016年9月1日
No Comments on LeetCode 134. Gas Station

思路

O(n^2)做法：直接嵌套循环，暴力试就行
O(n)做法：类似贪心的思路。主要还是看gas[i]-cost[i]，如果减出来是正的，那么可以为后面的路段留下点资源，如果减出来是负的话，那么最好的做法是在之前积累最多的资源来解决这个debt. 那什么时候有可能积累到最多资源呢？只能将这个有欠债的站点作为最后一站，所以将该站点的下一站作为起始试试。

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalLoss = 0;
        int tank = 0;
        int max_i = 0;
        for(int i=0; i<gas.size(); i++){
            tank += gas[i] - cost[i];
            if(tank < 0){   //Owe!
                max_i = i+1; //next possible start
                totalLoss += tank;  //add in the debt
                tank = 0;
            }
        }
        if(totalLoss + tank < 0)    //if the debt cannot be paid
            return -1;
        return max_i;
    }
};

Tags LeetCode OJ

不学无术

LeetCode 7. Reverse Integer

Post author By idailylife
Post date 2016年9月1日
No Comments on LeetCode 7. Reverse Integer

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

思路

检测溢出要在溢出之前，因为溢出的结果是undefined的。
比如要判断加法溢出，想当然的就是 A + B > INT_MAX，但是这是不对的，A + B指不定加出什么东西来，应当是 A > INT_MAX – B.

代码

class Solution {
public:
    bool safeMultiply10(int& result){
        //Multiply result by 10 if not overflow
        //Return false if it overflows
        if(result > 0){
            if(result > INT_MAX / 10)
                return false;
        } else if(result < 0) {
            if(result < INT_MIN / 10)
                return false;
        }
        result *= 10;
        return true;
    }
    bool safePlus(int& result, int r){
        //Return false if it overflows
        if(result > 0){
            if(result > INT_MAX - r)
                return false;
        } else if (result < 0) {
            if(result < INT_MIN - r)
                return false;
        }
        result += r;
        return true;
    }
    int reverse(int x) {
        int result = 0;
        //bool negFlag = x<0;
        while(x != 0){
            int r = x % 10;
            if(!safeMultiply10(result))
                return 0;
            if(!safePlus(result, r))
                return 0; //overflow
            x /= 10;
        }
        return result;
    }
};

木有技术

LeetCode 102. Binary Tree Level Order Traversal

Post author By idailylife
Post date 2016年8月30日
No Comments on LeetCode 102. Binary Tree Level Order Traversal

练手水题，直接贴代码。快转正面试了，虚啊，鬼晓得BOSS会问点什么。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if(root == NULL)
            return results;
        queue<TreeNode*>* currQueue = new queue<TreeNode*>();
        queue<TreeNode*>* candidateQueue = new queue<TreeNode*>();
        currQueue->push(root);
        vector<int> levelResult;
        while(!currQueue->empty()){
            TreeNode* currNode = currQueue->front();
            currQueue->pop();
            levelResult.push_back(currNode->val);
            if(currNode->left != NULL)
                candidateQueue->push(currNode->left);
            if(currNode->right != NULL)
                candidateQueue->push(currNode->right);
            if(currQueue->empty()){
                //swap curr and candidte
                results.push_back(levelResult);
                levelResult.clear();
                queue<TreeNode*>* temp = currQueue;
                currQueue = candidateQueue;
                candidateQueue = temp;
            }
        }
        return results;
    }
};

Tags BST, 二叉树

生活琐碎

斑马斑马

听了之后总有一股忧伤，这两天这个调调总是在脑海里若隐若现
宋冬野的歌还是耐听的

斑马，斑马你不要睡着啦
再给我看看你受伤的尾巴
我不想去触碰你伤口的疤
我只想掀起你的头发
斑马，斑马你回到了你的家
可我浪费着我寒冷的年华
你的城市没有一扇门为我打开啊
我终究还要回到路上
斑马，斑马，你来自南方的红色啊
是否也是个动人的故事啊
你隔壁的戏子如果不能留下
谁会和你睡到天亮
斑马，斑马你还记得我吗
我是只会歌唱的傻瓜
斑马，斑马你睡吧睡吧
我会背上吉他离开北方
斑马，斑马你还记得我吗
我是强说着忧愁的孩子啊
斑马，斑马你睡吧睡吧
我把你的青草带回故乡
斑马，斑马你不要睡着啦
我只是个匆忙的旅人啊
斑马，斑马你睡吧睡吧
我要卖掉我的房子
浪迹天涯

Tags 音乐

不学无术

除法的效率

估计应该都知道算除法的效率比算+-*低好多，那么到底低多少呢？简单写了一个程序测试看看。
注意：avg0函数可能会碰到溢出的情况，这种方法尽量不要用。

avg0: 统一加起来，再做除法；
avg1: 加的时候就做除法；
avg2: 加的时候乘以预先算好的，分母的倒数；

void printDuration(clock_t start, clock_t end){
    cout << "Time elapsed: " << (end - start)/(float)CLOCKS_PER_SEC << " seconds." << endl;
}
double avg0(int* ary, int N, long again){
    cout << "avg0: ";
    clock_t start = clock();
    double sum;
    while(again > 0){
        sum = 0;
        for(int i=0; i<N; i++)
            sum += ary[i];
        sum /= (double)N;
        again --;
    }
    clock_t end = clock();
    printDuration(start, end);
    return sum;
}
double avg1(int* ary, int N, long again){
    cout << "avg1: ";
    clock_t start = clock();
    double sum = 0;
    while(again > 0){
        for(int i=0; i<N; i++)
            sum += ary[i]/(double)N;
        again--;
    }
    clock_t end = clock();
    printDuration(start, end);
    return sum;
}
double avg2(int* ary, int N, long again){
    cout << "avg2: ";
    clock_t start = clock();
    double sum = 0;
    while(again > 0){
        double denominator = 1 / (double)N;
        for(int i=0; i<N; i++)
            sum += ary[i] * denominator;
        again--;
    }
    clock_t end = clock();
    printDuration(start, end);
    return sum;
}
int main() {
    int N;
    long again;
    cin >> N >> again; //num of numbers to be generated
    srand(time(NULL));
    int* ary = new int[N];
    for(int i=0; i<N; i++)
        ary[i] = rand();
    double r0 = avg0(ary, N, again);
    double r1 = avg1(ary, N, again);
    double r2 = avg2(ary, N, again);
    return 0;
}

结果：

50000 50000
avg0: Time elapsed: 7.49197 seconds.
avg1: Time elapsed: 16.7689 seconds.
avg2: Time elapsed: 7.51349 seconds.
Process finished with exit code 0

比一倍还多的时间！可怕！

不学无术

用于Sentence Embedding的DSSM与LSTM：管中窥豹

Post author By idailylife
Post date 2016年8月26日
No Comments on 用于Sentence Embedding的DSSM与LSTM：管中窥豹

前置废话：感觉实习这两个月真是顶得上实验室半年，想想对不起我的导师，跟现在相比之前天天像是在打酱油啊。

DSSM一撇

DSSM了解的不是很多，但是这两篇文章有几处是类似的，隐隐地感觉后面这篇是借鉴前面的写出来的。
文章中DSSM的最终目标是实现一个神经网络模型，使得给定输入文档(片段)可以输出一个对应的向量，而通过向量之间的余弦相似度可以判断两个Query-Document的相似性[latex]R(Q,D)=cosine(y_Q,y_D)[/latex]，然后拿这个就能做搜索排序了。

Word-Hashing

DSSM中用到了一个奇淫巧术，就是所谓的Word Hashing方法。我们知道，要将文字拿来处理，首先要表示成向量的形式（数值化），最普通的方法是做One-Hot Vector, 即每个单词对应一个feature值，出现就是1，没出现就是0. 但是单词表实在是太大了，这篇论文用到了一个叫Letter-N-Gram的技术，即将一个单词强行分成几个n-gram. 例如单词Hello做Letter-3-Gram，就会变成#HE, HEL, ELL, LLO, LO# 这样的表示方法（其中#代表开头或结尾）。由于处理的Query/Doc对中特殊字符会在数据预处理阶段被过滤，因此抛开单词大小写，a-z0-9#一共就26+10+1=37个字符，37*37*37=50653种可能性，相比词典来说小多了！
这个办法初看不是很靠谱，但是实验结果却是不错的。

正例/反例

训练神经网络需要给正例以及反例。不出意外地，这里用的是用户的click stream，即用户的点击数据。假设[latex]D[/latex]表示对于一个查询Q的所有候选文档，那么[latex]D^+[/latex]表示用户点击的文档作为正例，[latex]D^-[/latex]表示没有点击的作为负例。再根据上面提到的相似度[latex]R(Q,D)[/latex]，可以做出一个softmax的后验概率：

[latex]P(D|Q)=\frac{exp(\gamma R(Q,D))}{\sum_{D’ \in D}exp(\gamma R(Q,D’))}[/latex]

通俗易懂，对吧。

神经网络结构

想要实战的，可以看看CNTK里面有一个类似的例子：网络定义文件在这里，不过这个文件里面已经是Word Hashing过之后的了，而且参数设置和论文里的不大一样。
上面Figure1可以根据每一列来看。输入的最底层是Query/Doc的高纬度的词向量(Term Vector)，然后进入了Word Hashing阶段把高维词向量弄成了L3G之类的向量，维度大概在30k~50k之间，然后加了两个隐藏层后输出了最终的128维向量y。这个向量y在训练结束之后就是传说中的词向量了。然后两个词向量之间可以算出相似度，最终给出一个softmax算的后验概率[latex]P(D_i|Q)[/latex]。
训练整一坨神经网络要给一个优化目标，文中定义了一个loss function:

[latex]L(\Lambda)=-log\prod_{(Q,D^+)}P(D^+|Q)[/latex]

其中[latex]\Lambda[/latex]表示训练神经网络时的一堆参数。然后使用梯度下降之类的方法，把梯度一层层往回传就能调整参数了。

RNN与LSTM

RNN/LSTM具体是怎么工作的?要详细理解可以看这篇文章，讲得很透彻。这里只提到论文中的一些实现。

RNN

RNN的结构特点是下一个平行节点状态的信息是基于之前节点的。如上图，在本文的环境中，底下的x0,x1,x2,…可以看做一个个单词的输入，这一长串的节点连在一起就变成了一个句子。上面做DSSM时，一整句（段）话的词都拿来一起做Word Hashing，结果就是词汇之间的信息从一开始就会被忽略掉，如果换成了RNN，虽然最后拿到的还是个句子的向量，但是理论上训练出的模型会更加准确一些。中间层是Word Hashing之后的层，用的应该是和DSSM一样的Hashing方法。在最右侧(最后一个词)的激活输出就是Embedding好的句子，一个句子向量:)
但是RNN的引入会引出“梯度爆炸”或“梯度消失”的问题。数学原理不多说，考虑这个句子:I grew up in France… I speak fluent French. 假设我的任务是要训练一个RNN，根据之前的所有单词信息“猜”最后一个词汇French。在这句话中，显然最适合用来参考的是句子开头的那个词France，但是中间还隔了一大堆的“没卵用”词。在根据标签判断loss函数做梯度下降的时候，梯度一层层往回传，但由于中间隔的比较远，等轮到France这个词的时候已经几乎没有影响了。

LSTM-DSSM

LSTM处于什么位置呢？我把两个文章的对比图放在这边，基本上就能看出来了。左图里面用橙色圈出的结构，他的作用和右侧黑色虚线框里的东西是一样的，只是LSTM结构取代了原本比较“单纯”的多层网络的地位。所以这个论文的方法似乎可以叫做LSTM-DSSM.
所以对于怎么做学习，这个新文章的方法也是与它的前身很类似的：根据用户点击的Query-Doc来确定正例及反例(右图中的[latex]D^+[/latex]与[latex]D^-[/latex])，求一个最大似然，它等同于最小化下面这个公式中的参数[latex]\Lambda[/latex]。

[latex]L(\Lambda)=-log\prod_{(Q,D^+)}P(D^+|Q)=\sum_{r=1}^{n}l_r(\Lambda)[/latex]

其中，r对应第r条Query, j是这条Query对应的一条Document。
多说一句，这个Query-Doc的匹配过程有点像做Translation Model，只不过Translation Model有Encoding和Decoding两步，而这里只有Encoding的过程。

LSTM结构

简单来说，LSTM是一种RNN结构，里面通过一些Gate来实现“要不要记住/考虑XXX”的选择。LSTM根据需要有不同的具体实现，下图是论文中用到的结构：

这个结构分成了几个关键部位：Input Gate, Output Gate 和 Forget Gate. 可以看到这些Gate的实现是Sigmoid输出的(图中[latex]\sigma(.)[/latex])，所以值都在0-1之间；然后和前面的h(.)去做一个pointwise multiple(X)，实现了“门”的功能。

Input Gate决定了在这个LSTM结构中哪些值是要更新的，即是否要把当前的输入信息加入到隐藏层的状态；
Output Gate决定了是否把当前这个LSTM的输出传到下一层去;
Forget Gate决定了是否要保留当前一个节点的历史状态c(t-1)，可以看到图中有一个圈状的结构

Tags DSSM, LSTM, RNN, 机器学习

思路

代码

思路

代码

思路

代码

思路

代码

思路

代码

相关文献

DSSM一撇

Word-Hashing

正例/反例

神经网络结构

RNN与LSTM

RNN

LSTM-DSSM

LSTM结构