leetcode 4 寻找两个正序数组的中位数

这道题很有意思,题目是给定两个大小为 m 和 n 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的中位数,要求设计一个时间复杂度为 O(log (m+n)) 的算法。常规做法就是先合并两个数组,然后排序取中位数即可,但是这样的时间复杂度是O(nlog (m+n))。 O(log (m+n)) 很明显是二分的思路,如果可以想到对k进行二分的话题目就变简单了,可惜第一次思考的时候局限在对数组进行二分。在考虑到对k进行二分之后,还需要注意很多的边界条件。

阅读更多

poj1019 Number Sequence数字序列

这道题其实不难,就是有些绕。题目给了一个数字序列的规律,要求输出数字序列第i位数字。第一次没注意输出了第i个数字wa了。eg: …12345678910…,第10位数字是1。解题过程就两点:1是找到第i位对应的子串,2是找到子串中对应的数字并输出。

阅读更多

poj1013 Counterfeit Dollar假币

这是一道枚举题,第一次思考的时候一直陷在如何在三次称量之内找到假币,但是这道题已经明确了三次称量必定找到假币,所以呢,只需要枚举就可以了。假设一枚硬币是假的或轻或重,然后判断是否符合三个条件。需要注意的是,最后输出的是第几枚硬币是轻的还是重的,刚开始没有注意到这个细节wa了好几次。下面看下详细题目。

阅读更多

poj1050 To the Max求最大矩形和

Description: Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:

阅读更多

poj1656 Counting Black数黑色

Description:There is a board with 100 * 100 grids as shown below. The left-top gird is denoted as (1, 1) and the right-bottom grid is (100, 100).

阅读更多

poj2909 Goldbach's Conjecture哥德巴赫猜想

Description: For any even number n greater than or equal to 4, there exists at least one pair of prime numbers p1 and p2 such that n = p1 + p2

阅读更多

poj1003 Hangover

Hangover: How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We’re assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 ++ 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.

阅读更多

cross特征总结

cross特征是机器学习中一类非常有用的特征,例如在推荐系统领域,用户和商品的交叉特征往往可以给模型带来极大的增益,例如<性别女, 口红>的交叉特征,当一个用户是女性且商品是口红时,点击的概率就会很高;反之<男,口红>点击的概率就很低了。下面总结一些cross特征相关的工作,比较典型有FM, FFM, 各类NN模型等。DNN模型不在文本讨论之列,DNN的全连接层带交叉特征的能力,但是有些情况下我们需要构造一些更加直接的cross特征。

阅读更多

关于思维逻辑的几点思考

今天中秋,刚刚晚上下班回来后就22:30了,然后处理了下工作上的事情,然后放松了会洗了个澡,然后就现在00:43了。总是说生活要有一些仪式感的,哎,时间所迫生活已然不易。

阅读更多

COLD Towards the Next Generation of Pre Ranking System

目前主流的以双塔结构为基础的粗排系统被定义为第三代粗排系统,其离线计算得到用户和广告的向量,同时以向量内积的方式在线计算得到用户和广告的分数进行排序过滤。该架构的优点在于性能开销小,但是也有如下缺点:

阅读更多