找工作总结

今天决定签哪家了,至此,找工作全部结束,所以把过程总结一下。

面过的公司包括:

1. 笔试之后无下文的:
有道 — 内推也要笔试,估计笔得不怎么样,确实我基础题做得不行。
雅虎 — 笔试时特别奇葩,我本来内推的是 research engineer职位,结果笔试时傻眼,大题完全没法编。果断把试卷右上角的职位改成SDE(软件开发工程师), 后来竟然接到面试通知了,可是后来面试日期要延后,我也不等了。

2. 等不起的:
hulu — 因为听朋友说这家公司的bar比google高,所以我才考虑去试试的(看有多难)。经历一次电面,3次现场面,后来加了一面,最后终面。因为不是数据挖掘和机器学习背景,我想投研发被HR劝说可能不合适,然后我投的开发。据说开发是要做产品线上的东西,和做网站有关,具体做啥我也不太清楚。我是上周二面完的,由于这周三就要给微软答复,所以催了hulu尽快给结果。HR很nice,看起来还是挺认真负责的,但是很抱歉我每次满怀期待地接电话,得到的通知都是“还不能做出决定,要再等等”。今天仍然如此,我觉得这是soft reject,和HR说那就算了,我得签微软。听说很多人都被pending了,直接收到拒信的应该也有,那我就不是特别清楚了。待遇方面,听说是开发比research要低。基本没有户口。然后应该普通offer也没有给非常高,绝对不像梁斌在weibo里说的那么夸张。P.S. 特别牛的人也许可以拿到那个数。

google — 10月份电面过1次,现场面了2次,因为现场面那天给我安排的是9:00第一场,9:45第二场,然后我那天手机出毛病,闹钟没 响,直接睡过,风风火火地赶上第二场。又在中午补上了第一面。遇到的都是google 美国的面试官,一个老外,一个中国人,一个考算法题,一个考设计题。我好像答得都不怎么样,程序写得也一般,聊得还可以(那有个什么用呢)。不过竟然还给我安排3,4面了,我还挺感动的,虽然前2面反馈不咋的吧。面试日期本来是上周,可是有突然状况,推迟了,我估计这两天就会发信过去说我已经决定签哪了,不去面了。说多了都是泪,因为J1 2-year rules,我只能申请国内职位。google北京这里一堆人排着,轮到我的机会渺茫,几乎是0吧。google的HR很nice,非常认真负责。

JP MORGAN — 投的QUANT职位,就是凑个热闹,听说global pay,不过其实也没有那么吓人。10月份电面过一次,问了我常微题,C++面向对象的题,感觉就是有那么几个方向,你会什么他问什么。我觉得他们对于写程序的考察,侧重点和IT大牛公司不一样,貌似不会问算法题,某人的解释是,他们更希望你代码写得规范,而不是注重创造性。认识也有其他人电面了,都是还没有接到面试通知,估计是会等电面全部结束后集中onsite interview。我个人感觉那个面试官GG对我印象应该不错,不过就算过了电面,我应该也是说我不会去onsite interview了吧。

3. 有口头offer的
华为 — 博士特招项目,8月底就面完了。就面了2次,也没问太技术的问题,就是聊了聊之前的一些经历和一些想法。怎么说呢,觉得华为给我留下的印象不错,感觉还是一个很不错的公司。面试官大概都是40左右的leader,态度都非常谦逊,他们说特别希望招到清华北大中科院的最优秀的学生,以前给不了这些人理想的待遇,现在他们博士特招项目的待遇和发展都非常优厚。(待遇确实很不错了,和本科硕士不是一个level。)给我分到的是做数据库方向,我对这个方向没有任何背景,也不太想做这个方向。重申一次,华为是个好公司,比起很多国内互联网公司的虚假繁荣,它毕竟是个认认真真干实事的公司,你有时觉得他做事口号喊得有点大,但是能够做到就是很强的。

阿里 — 准确地说,是阿里妈妈搜索广告。我比较曲折,先是暑假和我BF去提前批,面了2轮后,面了ZWS大牛老师,终面评价不好,不过终面不挂人。(后来听说,终面过的人就有资格参加阿里星面试了。)然后就是发实习offer了,但是我实习有地方去了,所以就这样了。之后,校招的时候,我们又被当实习生转正,面了终面,当时也有HR在场,面试感觉还比较愉快。面完回家路上,被HR叫回去补了个交叉面,是阿里云的一个人面我的,我当时抽风了最后问他的问题让氛围好尴尬,好在他没往心里去。最后拿到A类口头offer,不过我对于package不是很满意,但是他们觉得这个价格不低了,而且要我看以后的薪资涨幅。我觉得他们说得很有道理,去阿里还是很有前途的,但是第一年package实在远低于我预期。

微软 — 实习生转正,也拖到现在才有正式offer的眉目。实习的时候,是好朋友内推的,当时错过大规模招暑期实习生的时间,所以我和head count斗争了很久。期间我还找了Intel 工程院。最后在大家的共同努力以及STC老大的special approval下,才拿到那个来之不易的实习生名额。我实习期间真的算很拼了,因为想转正,并且知道今年STC招人少很多,而且大部分在苏州。后来我mentor力挺我,给了我很多鼓励和支持,真是太感激她了。好人有好报,前不久她终于升职了,而且连升了2级。实习生转正的面试我被安排在9月下旬2面,10月中旬三四面,给我三,四面的都是principle manager。都是面算法题,程序题以及问项目,没有谈人生和理想。四面的时候,我遇到的面试官很tough,感觉不是很友好,一开始还不是很适应,不过脸皮厚的人总是能够战胜自尊,最后我们聊得还可以。反正当时我面完后我和我mentor都觉得我可能完蛋了,我还难过了几天,结果发现竟然还面试通过了。我突然开始觉得第四面面试官好有爱啊,在他严冬的外表下有颗盛夏的心(我太恶心了有木有)。微软给博士入职的level比硕士要多一级,package符合我预期,IT公司里面应该只比google的博士起薪少那么一点点吧,我还比较满意。

4. 没有面试但要感谢的公司
豌豆荚 — 我2012年去实习的公司,如今规模是我去时的3-4倍。一家非常有爱,有品味的公司,所有显摆自己公司零食,午餐,甜点的公司,我还没有见过一个比得上这家的,甚至我认为都超过google的奢侈程度了。我今年找实习和工作没有那么顺的时候,他们是我最坚强的后盾,我很爱我的小伙伴们,一直想的就是如果微软没有转正的话,我最有可能就是回豌豆荚。(不是因为觉得微软比豌豆荚好,而是别的原因,也就不啥都说那么清楚了)

渣打 — 我和BF还有来神之前参加过一个渣打的比赛,成绩还不错,然后就接到他们一个senior manager的电话,意思是让我考虑一下他们的职位。好吧,其实我写渣打不是很合适,应该是渣打科营,实在拎不清他们的组织结构。无论他有些关于行业的观点我是否同意,我都还是很感谢他能在周末抽出自己宝贵的休息时间给我电话和我聊聊。但是我比较想在北京,不想去天津塘沽,所以没有考虑那里。

最后,还要加上个内推后无下文的:网易游戏数据挖掘研究员,真是一点消息都木有啊,不过听说研发都给信了,估计今年是我投这个方向提前招到合适的人了。

说了那么多,其实仔细想想,面了也没几家公司。找工作是特别辛苦的过程,希望现在还没有拿到offer的XDJM们继续加油,会有大offer在后面等着你们。

Dora总是在鼓励我,有时候特别不喜欢听他说我这没问题,那也行,因为做不成的时候感觉更难受。之后也许还有四处求职的日子,这种不安定感总是时刻伴随着自己,有时候想着如果在一个稳当的环境下搞科研或者教书挺好的,但真那样又会受不了。作为一个矛盾综合体,也只能走一步看一步了,未来完全out of control.

发表在 互联网产品类 | 一条评论

Notes 1: Active Learning

1. supervised learning/semi-supervised learning/active learning
supervised learning:利用一组已知样本调整分类器的参数,使其达到所要求的性能的过程,所给样本包含分类信息,常见的supervised learning方法有:决策树,神经网络等;
semi-supervised VS. active learning:
相同: to get good performance without demanding too many labeled samples
不同:semi-supervised 使用unlabeled data
active learning选择需要被labeled的sample,是主动的学习者

2. 按照对未标注数据的选择策略,可以把当前的主动学习算法分成很多类,本文列举其中两类:
(1) 基于评委(committee-based)
(2) 基于置信度的方法(certainty-based)

基于评委的方法的流程:
(1) 对于n个未标注样本构成的样本组B中每个样本e,使用先前从标注数据集中训练出的k个模型对其进行标注,得到k个分类结果{L1, L2, …., Lk},通过他们,对每个e测量出最有争议的标注结果De
(2) 选出m个De最大的未标注数据,交给标注人员标注
(3) 将刚被标注的样本又加入原模型再重新train,又可以得到m个De最大的未标注数据,如此反复,直到达到需要的数据量

基于置信度的流程:
(1) 从先前标注的样本中训练出一个模型
(2) 对N个未标注样本组中每个样本用模型对其进行标注,评估模型标注的置信度
(3) m个置信度低的样本交给标注人员标注
(4) 加入新样本train,重复上述过程直到达到所需数据量

发表在 边学边记 | 留下评论

priority_queue的用法

通过解决leetcode的一个问题:Merge K Sorted Lists 来使用priority_queue,熟悉了这个数据结构的函数用法。
它建立大顶堆的时间复杂度是O(KlogK),然后每次更新堆顶元素复杂度是O(logK),所以整个合并的时间复杂度是: O(N*NlogK),其中N表示一个链表的平均长度.

代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

 struct data{
     int value;
     int index;
 };

 struct compare{
     bool operator()(data a, data b) {
         if (a.value < b.value) return false;
         else if (a.value == b.value) {
             if (a.index <= b.index) return false;
         }
         return true;
     }
 };

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        vector<ListNode *> tmpList = lists;
        priority_queue<data, vector<data>, compare> datas;
        ListNode *head = NULL;
        ListNode *res;
        int i;
        data tmp;
        for (i = 0; i < lists.size(); i++) {
            if (!tmpList[i]) continue;
            tmp.value = tmpList[i]->val;
            tmp.index = i;
            datas.push(tmp);
        }

        while (!datas.empty()) {
            data minV = datas.top();
            if (!head) {
                head = tmpList[minV.index];
                res = head;
            }else{
                res -> next = tmpList[minV.index];
                res = res->next;
            }
            datas.pop();
            tmpList[minV.index] = tmpList[minV.index]->next;
            if (tmpList[minV.index]) {
                tmp.value = tmpList[minV.index]->val;
                tmp.index = minV.index;
                datas.push(tmp);
            }
        }
        return head;
    }
};
发表在 边学边记 | 留下评论

Longest Palindromic Substring

Useful Links:

http://my.oschina.net/pathenon/blog/63575

http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Solution I: O(N^N) time complexity and O(N^N) space complexity.
Define an array flag[0,...,N-1][0,...,N-1]: flag[i][j] = true if s[i,...,j] is palindromic substring, else false;
step 1: flag[i][i] = true; maxLength = 1;
step 2: flag[i][i+1] = true, maxLength = 2, if s[i] == s[i+1]; else false;
step 3: please note that if s[i] == s[j] && flag[i+1][j-1] == true, then flag[i][j] = true;

Here is the accepted code:

class Solution {
public:
    bool flag[1010][1010];
    string longestPalindrome(string s) {
        int i, j;
        int longestBegin = 0;
        int maxV = 1;
        for (i = 0; i < s.length(); i++) {
            for (j = 0; j < s.length(); j++) {
                flag[i][j] = false;
            }
        }
        for (i = 0; i < s.length(); i++)  flag[i][i] = true;
        for (i = 0; i < s.length()-1; i++) {
            if (s[i] == s[i+1]) {
                flag[i][i+1] = flag[i+1][i] = true;
                longestBegin = i;
                maxV = 2;
            }
        }
        int len;
        for (len = 3; len <= s.length(); len++) {
            for (i = 0; i < s.length()-len+1; i++) {
                j = i+len-1;
                if (s[i] == s[j] && flag[i+1][j-1]) {
                    flag[i][j] = true;
                    longestBegin = i;
                    maxV = len;
                }
            }
        }
        return s.substr(longestBegin, maxV);
    }
};

Solution II: O(N) time complexity and O(N) space complexity.
Details can be found in useful links in the beginning of the article.
To simplify it, the general idea of this solution bases on the fact that: If a palindrome substring s1 is a true subset of the palindrome substring S, then the dual substring s2 (center: 2*S.center-s1.center, radius: s1.radius) is also palindromic substring.
Another trick is the progressing of original input string, i.e.
After progressing, the string s: abcdcba changes to be string str: $#a#b#c#d#c#b#a#.
By doing so, the maximum length of palindromic substring is alway odd, which has unique center.

Here is the accepted codes:

class Solution {
public:
    string longestPalindrome(string s) {
        string newS;
        newS.clear();
        newS.push_back('$');
        for (int i = 0; i < s.length(); i++) {
            newS.push_back('#');
            newS.push_back(s[i]);
        }
        newS.push_back('#');
        s = newS;
        vector<int> p(s.length(), 0);
        int idx = 1, max = 0;
        for (int i = 1; i < s.length()-1; i++) {
            if (max > i) {
                p[i] = p[(idx<<1)-i] < (max-i) ? p[(idx<<1)-i]:(max-i);
            }
            while (s[i+p[i]+1] == s[i-p[i]-1]) p[i] += 1;
            if (i + p[i] > max) {
                idx = i;
                max = i + p[i];
            }
        }

        int center = 0, radius = 0;
        for (int i = 0; i < p.size(); i++) {
            if (p[i] > radius) {
                center = i;
                radius = p[i];
            }
        }
        string res = s.substr(center-radius, (radius<<1)+1);
        newS.clear();
        for(int i = 0; i < res.length(); i++) {
            if (res[i] != '#') newS.push_back(res[i]);
        }
        return newS;
    }
};
发表在 边学边记 | 留下评论

LeetCode: Best Time to Buy and Sell Stock I/II/III

Discriptions:
I: Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

II: Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

III: Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis:
I: The problem is equaivalent to:
Given array a[n], find max(a[j]-a[i], 0) s.t. j > i.
(It’s trivial case with O(n) solution.)

II: Quite different with I, but we can take a example such as:
a[n]: 1 6 8 3 2 1 7 8 4 3 8
solution: bosoobosobs
b: buy
s: sell
o: do nothing
As greedy algorithm, we get all consective ascending sequence, and do summation.

III: Kind of extension of Problem I. We maintain two arrays left2right[n] and right2left[n];
left2right[m]: find max(a[j]-a[i], 0) s.t. m >= j > i
right2left[m]: find max(a[j]-a[i], 0) s.t. m <= i < j
The result:
res = max(left2right[m]+right2left[m]);
So we get the result in O(n) complexity;
(In our codes, right2left is reversed.)

class SolutionI {
public:
    int maxProfit(vector<int> &prices) {
        int i;
        int min = 1000000;
        int maxP = -100000;
        if (prices.empty()) return 0;
        min = prices[0];
        for (i = 1; i < prices.size();i++){
            if (prices[i] < min) min = prices[i];
            else {
                int res = prices[i] – min;
                if (res > maxP) maxP = res;
            }
        }
        if (maxP < 0) maxP = 0;
        return maxP;
    }
};

class SolutionII {
public:
    int maxProfit(vector<int> &prices) {
        int res = 0, pos;
        int min, max, i;
        if (prices.empty()) return 0;
        for (i = 0; i < prices.size()-1; i++){
            if (prices[i] < prices[i+1]) break;
        }
        if (i == prices.size()-1) return 0;
        pos = i;
        min = prices[pos];
        for (i = pos+1; i < prices.size()-1; i++){
            if (prices[i] >= prices[i-1] && prices[i] > prices[i+1]){
                max = prices[i];
                res += (max – min);
            }else if (prices[i] < prices[i-1] && prices[i] <= prices[i+1]){
                min = prices[i];
            }else continue;
        }
        if (prices[i] >= prices[i-1]) {
            max = prices[i];
            res += (max – min);
        }
       return res;
    }
};

class SolutionIII {
public:
    int maxProfit(vector<int> &prices) {
        vector<int> left2right;
        vector<int> right2left;
        int min, res, i, max;
        if (prices.size() < 2) return 0;
        min = prices[0];
        max = 0;
        left2right.push_back(0);
        for (i = 1; i < prices.size(); i++){
            if (prices[i] – min > max){
                max = prices[i] – min;
            }
            if (prices[i] < min) min = prices[i];
            left2right.push_back(max);
        }

        min = prices[prices.size()-1];
        max = 0;
        right2left.push_back(0);
        for (i = prices.size()-2; i >= 0; i–){
            if (min – prices[i] > max){
                max = min – prices[i];
            }
            if (prices[i] > min) min = prices[i];
            right2left.push_back(max);
        }

        max = 0;
        for (i = 0; i < prices.size(); i++){
            if (left2right[i] + right2left[prices.size()-i-1] > max) \
                 max = left2right[i]+right2left[prices.size()-i-1];
        }
        return max;
    }
};
发表在 边学边记 | 留下评论

InterviewStreet: Triplets

Source of the problem: https://www.hackerrank.com/challenges/triplets

My submission got 32.22 score and TLE for the other test cases. The complexity of my solution is O(N^2), which should be optimized to O(NlogN), but I don’t know how.

General idea of my submissions:
1) Record the first position and the last for each integer.
2) Two arrays, same length with the input, should be updated sequentially.
—- The 1st array Array1[i]: how many smaller integers subject to: input[j] < input[i] and j < i;
---- The 2nd array Array2[i]: how many triplets got if input[i] is the third number of triplets.
--- to update Array2[i], just summarize Array1[j] which subject to: input[j] < input[i] and j < i; It's worth noting the repeated integers.
3) Do summation of all Array2[i], notice repeated integers.

P.S.: You have to use 'long long int' for output format. Or else you will got WA. When N = 100000, the maximum results can be C_{100000}^{3}, which is beyond 'unsigned int'.

Codes as follows:

typedef struct{
   unsigned int value;
   long long int two;
   long long int three;
} data;

typedef struct{
    int pre;
    int post;
} position;

map<unsigned int, position> dataPos;

long long  int getResNum(vector<data> dataVec){
    int i, j;
    for (i = 1; i < dataVec.size(); i++){
        long long int count1 = 0;
        long long int count2 = 0;
        for (j = 0; j < i; j++){
            if (dataVec[j].value < dataVec[i].value){
                if (dataPos[dataVec[j].value].post < i &&  \
                           j != dataPos[dataVec[j].value].post) {
                    continue;
                }else{
                    count1++;
                    count2 += dataVec[j].two;
                }
            }
        }
        dataVec[i].two = count1;
        dataVec[i].three = count2;
    }
    long long int res = 0;
    for (i = 1; i < dataVec.size(); i++){
        if (dataPos[dataVec[i].value].post != i) continue;
        res += dataVec[i].three;
    }
    return res;
}

int main(){
    int N, i;
    unsigned int a;
    vector<data> dataVec;
    while (scanf(“%d”, &N) == 1){
        dataVec.clear();
        dataPos.clear();
        data tmp;
        position p;
        for (i = 0; i < N; i++){
            scanf(“%u”, &a);
            tmp.value = a;
            tmp.two = tmp.three = 0;
            dataVec.push_back(tmp);
            if (dataPos.find(a) == dataPos.end()) {
                p.pre = p.post = i;
                dataPos[a] = p;
            }else{
                dataPos[a].post = i;
            }
        }
        printf(“%lld\n”, getResNum(dataVec));
    }
    return 0;
}
发表在 边学边记 | 留下评论

ubuntu下安装rpm包

做法:
1. 确认已经安装alien,如果没有:
sudo apt-get install alien

2. 转换rpm到deb包
sudo alien –scripts filename.rpm
你会在同目录下看到filename.deb

3. 安装deb包
sudo dpkg -i filename.deb

好了,安装结束。

发表在 边学边记 | 留下评论

interview street challenge — Event Tree

题目:https://www.interviewstreet.com/challenges/dashboard/#problem/4fffc24df25cd

You are given a tree (a simple connected graph with no cycles).You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest contains even number of vertices

Your task is to calculate the number of removed edges in such a forest.

Input:
The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. 2 <= N <= 100.
Next M lines contains two integers ui and vi which specifies an edge of the tree. (1-based index)

Output:
Print a single integer which is the answer

Sample Input
10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8

Sample Output :
2

算法:
从1开始为树的根,递归把树的各个节点对应的自己包括自己子树的节点数目 dist[i] 求出来。
然后从2开始遍历所有dist[i]为偶数的点,返回结果就可以。

代码:

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int a[101][101];

void mark(int *dist, int *flag, int N, int start){
    int i;
    flag[start] = 1;
    for (i = 1; i <= N; i++){
    	if (a[start][i] ==1 && flag[i] == 0) break;
    }
    if (i > N) {
    	return;
    }
    for (i = 1; i <= N; i++){
    	if (a[start][i] == 1 && flag[i] == 0){
    		mark(dist, flag, N, i);
    		dist[start] += dist[i];
    	}
    }
}

int main(){
	int N, M;
	int i, j, from, to;
	int dist[101], flag[101];
	int count;
	while (scanf(“%d%d”, &N, &M) == 2){
		for (i = 1; i <= N; i++){
			for (j = 1; j <= N; j++){
				a[i][j] = 0;
			}
			flag[i] = 0;
			dist[i] = 1;
		}
		for (i = 0; i < M; i++){
			scanf(“%d%d”, &from, &to);
			a[from][to] = a[to][from] = 1;
		}
		mark(dist, flag, N, 1);
		count = 0;
		for (i = 2; i <= N; i++){
		    if (dist[i] % 2 == 0) count++;
		}
		printf(“%d\n”, count);
	}
	return 0;
}
发表在 边学边记 | 留下评论

TC SRM159 DIV2 C题解题报告

题目:
输入一个vector,返回最长上升子序列以及能达到这个长度有多少种可能。

算法:
开两个数组a[N], b[N],a[i]表示第i个数能达到的最长上升子序列长度,b[i]表示第i个数达到最长上升子序列的可能性。
更新a[i]的方法是:
初始a[i] = 1, b[i] =0, i = 0,…, N-1;
然后 for j = 0 to i-1 中找出prices[j] < prices[i]中最大的a[j]-->max, 更新a[i] = max+1;
for j = 0 to i-1中找出所有(prices[j] < prices[i] && a[j] == max),更新b[i] += b[j]; 如果没有这样的j, b[i] = 1;
最后返回a[i]中最大的值,以及所有最大值对应的b[i]相加。
其中更新a[i]的复杂度为O(N),更新b[i]的复杂度也为O(N), 所以这里给出的是一个O(N^2)的算法。

代码:

class ThePriceIsRight {
public:
	vector <int> howManyReveals(vector <int>);
};

vector <int> ThePriceIsRight::howManyReveals(vector <int> prices) {
    int lp = lp;
    int a[lp], b[lp];
    int i, j;
    int max = 0, count = 0;
    vector<int> res;
    a[0] = b[0] = 1;
    for (i = 1; i < lp; i++){
    	int tmpMax = 1;
    	b[i] = 0;
    	for (j = 0; j < i; j++){
    		if (prices[i] > prices[j]){
    			if ((a[j]+1) > tmpMax) tmpMax = a[j]+1;
    		}
    	}
    	a[i] = tmpMax;
    	if (tmpMax == 1) b[i] = 1;
    	else{
	    	for (j = 0; j < i; j++){
	    		if (a[j]+1 == tmpMax && prices[j] < prices[i]) b[i] += b[j];
	    	}
    	}
    }
    for (i = 0; i < lp; i++){
    	if (a[i] > max) max = a[i];
    }
    for (i = 0; i < lp; i++){
    	if (a[i] == max) count += b[i];
    }
    res.push_back(max);
    res.push_back(count);
    return res;
}
发表在 边学边记 | 留下评论

TC SRM 151 DIV2 C题解题报告

题目大意是求merge sort时比较次数。

方法:
就是写一个merge sort,比较的次数是每一次归并时候所需要的次数。

代码:

class MergeSort {
public:
	int howManyComparisons(vector <int>);
};

vector<int> Merge(vector<int> a1, vector<int> a2, int &count){
    vector<int> a(a1.size()+a2.size());
    int p1 = 0, p2 = 0, len = 0;
	while (p1 < a1.size() && p2 < a2.size()) {
	    if (a1[p1] < a2[p2]){
	        a[len++] = a1[p1++];
	    }else if (a1[p1] == a2[p2]){
	    	a[len++] = a1[p1++];
	    	a[len++] = a2[p2++];
	    }else{
	        a[len++] = a2[p2++];
	    }
	    count++;
	}
	while (p1 < a1.size()){
		a[len++] = a1[p1++];
	}
	while (p2 < a2.size()){
		a[len++] = a2[p2++];
	}
	return a;
}

void MSort(vector <int> & a, int &count) {
	if (a.size() <= 1) return;
	vector<int> a1, a2;
	for (int i = 0; i < a.size()/2; i++) a1.push_back(a[i]);
	for (int i = a.size()/2; i < a.size(); i++) a2.push_back(a[i]);
	MSort(a1, count);
	MSort(a2, count);
        a = Merge(a1, a2, count);
}

int MergeSort::howManyComparisons(vector <int> numbers) {
	int count = 0;
	MSort(numbers, count);
	return count;
}
发表在 边学边记 | 留下评论