0%

一、题目要求

Count the number of prime numbers less than a non-negative number, n.

二、分析

找到小于n的素数的个数。

三、思路

  • 1.对于每个小于n的数,判断是否是素数。判断n是否素数的方法为分别除以2-[n-1]范围内的数看是否存在可以整除的数,判断范围可缩小为2-[n/2]

时间开销:$O(n^2)$,空间开销:$O(1)$,结果:TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isPrime(n):
if n < 2:
return False
for i in range(2,n // 2 + 1):
if n % i == 0:
return False
return True

def countPrimes(n):
res = 0
for i in range(n):
if Solution.isPrime(i):
res += 1
return res
  • 2.改进IsPrime(n),若数n对2-[sqrt(n) + 1]的数均无法整除,那么n为素数,这样该函数时间复杂度优化为$O(\sqrt n)$

时间开销:$O(n^{1.5})$,空间开销:$O(1)$,结果:TLE

阅读全文 »

一、题目要求

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

二、分析

判断两个字符串是否是同构的。

三、思路

  • 1.使用两个Hash表来存放每个字母的出现位置,并比较排序后的Hash表值集合,需要两遍

时间开销:O(n),空间开销:O(n),结果:AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
A = dict()
B = dict()
for i in range(len(s)):
if s[i] in A:
A[s[i]] += [i]
else:
A[s[i]] = [i]
for i in range(len(t)):
if t[i] in B:
B[t[i]] += [i]
else:
B[t[i]] = [i]

return sorted(A.values()) == sorted(B.values())
阅读全文 »

一、题目要求

Determine whether an integer is a palindrome. Do this without extra space.

二、分析

确定一个整数是否是回文,不允许使用额外空间,这里额外空间应当理解为空间开销最多是O(1)。

三、思路

  • 1.首先想到的是转换为字符串处理,但是这样会使用额外的空间,这里的n是数字的位数

时间开销:O(n),空间开销:O(n),结果:AC

1
2
3
4
5
6
7
8
9
if x < 0:
return False
st = str(x)
length = len(st)

for i in range(length // 2):
if st[i] != st[-1 - i]:
return False
return True

类似思路Discuss中的简洁版Python代码,使用了内置的list-reverse:

1
return str(x)[::-1] == str(x)
阅读全文 »

一、题目要求

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

二、分析

若引用次数数组已经增序排列,如何优化算法?时间开销要求$O(\log n)$

三、思路

  • 1.二分查找即可

时间开销:$O(\log n)$,空间开销:$O(1)$,结果:AC

1
2
3
4
5
6
7
8
9
10
11
12
L, R ,length = 0, len(citations) - 1,len(citations)

while L <= R:
mid = L + R >> 1
if length - mid > citations[mid]:
L = mid + 1
elif length - mid < citations[mid]:
R = mid - 1
else:
return citations[mid]

return length - L
阅读全文 »

一、题目要求

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

二、分析

H-index被用来计算一个科研工作者工作的影响力大小,其计算方式为如果一个科研人员发表的h篇论文都被引用至少h次以上且并没有h + 1篇论文被引用h + 1次,那么他/她的h-indexh

三、思路

  • 1.使用hash表存储每个引用次数的文章数量,遍历hash表获取结果

时间开销:$O(n^2)$,空间开销$O(m)$[m为引用次数的规模],结果:TLE

阅读全文 »

DFP、BFGS和L-BFGS是三种重要的拟牛顿法

一、牛顿法

牛顿法同梯度下降法一样是一种逼近解法,用来求损失(或极大似然)函数的最小(最大)值,它利用了函数的二阶导数矩阵$Hession$矩阵,因此收敛速度比只利用了一阶导数的梯度下降快。

对函数$f(x)$在$X_k$点进行二阶泰勒展开,

其中$\bigtriangledown f$为$f$的梯度向量,$\bigtriangledown^2 f$为$f$的$Hession$矩阵

由于要求$f(x)$的极值,因此要找出$\bigtriangledown \varphi (x) = 0$的点,即:

可解出:

其中的$d_k = - H_k^{-1}g_k$为搜索方向,称为牛顿方向

牛顿法的问题是每次迭代需要求二阶导矩阵(Hession Matrix)及它的逆矩阵,计算量太大

二、拟牛顿法

阅读全文 »

1.介绍

  • 推荐系统分类——基于策略

    • 基于行为的策略:信息冗余且难以收集
    • 协同过滤:冷启动问题
  • 推荐系统分类——基于输入类型

    • 显示反馈
    • 隐式反馈
  • 隐式反馈的特点

    • 没有负反馈,也就是说即使用户没有行为也并不意味着用户不喜欢
    • 隐式反馈本质上是含有很多噪音的,并不能真正反映出用户的偏好
    • 显示反馈的数值反映了用户的偏好;而隐式反馈的数值反映了置信度(也就是用户有多大可能性对该物品感兴趣)
    • 隐式反馈的推荐需要合适的方法来进行评估

2.准备工作

  • 准备了用户数据矩阵$R$,这里的$R{ui}$不是偏好值,而是对用户行为的观察。论文中$R{ui}$是用户$u$全程观看电影$i$的次数。如果用户$u$观看了电影$i$的70%,那么$R_{ui}$就被设置为0.7

3.以前的研究

  • 近邻模型
  • 潜在因子模型(即PPT中的显式反馈)

4.我们的模型

  • 使用$置信度C{ui}来为偏好度$P{ui}$加权$
  • $λ(\sum_u|x_u|^2 + \sum_i|y_i|^2)$防止过拟合
  • 交替最小二乘过程,前文已经叙述
  • 每次迭代时间开销$O(f^2N+f^3M)$,其中$N$是非0观察值的数量,$M$是用户数量,$f$是特征数量
  • 特点
    • 转换直接观察值($r{ui}$)到两个解释数值:偏好度$p{ui}$和置信度$r_{ui}$
    • 输入规模线性倍数的时间开销

5.推荐解释

  • 好的推荐需要有理论解释 —— 文献10[Well Accepted]
  • 通过对于${P_{ui}}^\prime=X_u^T\times Y_i$的推导,证明推荐的数学合理性
    • $W^u$被看做是用户$u$的权重矩阵
    • 物品$i$和物品$j$在用户$u$眼中的加权相似度为$S_{ij}^u=Y_i^TW^uY_j$
阅读全文 »

一、OGD(Online Gradient Descent)

批量梯度下降法(Batch Gradient Descent)也就是相对于这里的在线梯度下降来说的离线梯度下降,它每次迭代使用所有数据计算出目标函数的梯度方向,但是代价较高

在线梯度下降,当前迭代只根据当前的数据来计算梯度,有一定偏差,迭代次数可能增加,但代价较小

随机梯度下降(SGD),随机选择一定量的数据样本在每次迭代中确定梯度,相对于BGD代价较小

二、正则化

  • 1.规则化符合奥卡姆剃刀的原则:选择能解释已知数据的最简单的模型,规则化用来保证模型的简单化(不会过分拟合)
  • 2.从贝叶斯估计的角度来看,规则化项对应于模型的先验概率
  • 3.规则化是结构风险最小化策略的实现,是在经验风险上加一个正则化项(regularizer)或惩罚项(penalty term)

公式第一项是为了拟合训练数据,不同的模型使用不同的Loss函数;第二项是为了规则化,有以下几种{0范数(norm),1范数,2范数,迹范数,Frobenius范数,核范数}等

0范数也就是L0正则,1范数就是L1正则,他们都可以使得特征变得稀疏,但L0计算代价太大,因此通常使用L1正则

2范数也就是L2正则,是特征向量各元素的平方和开根号,它的作用是放置过拟合

L2正则可以防止参数估计的过拟合,但是选择合适的λ比较困难,需要交叉验证。如果有个特征与输出结果不相关,则L2会给一个特别小的值,但是不会为0。
L1正则会产生稀疏解,即不相关的的特征对应的权重为0,就相当于降低了维度。但是L1的求解复杂度要高于L2,并且L1更为流行。

阅读全文 »

1.显式矩阵分解(Explicit Matrix Factorization)

  • (1) 用户显式的给电影目录的一个子集打分
  • (2) 目标:预测用户给新电影打的分数

  • (3) 使均方根RMSE误差最小

公式:

  • (4) 公式解析:
    • $λ$是正则化参数,控制着正则化的程度,用来避免过拟合的问题,通过交叉验证确定
    • $μ$表示所有评分的平均值,$b_u$和$b_i$描述用户和物品相对于平均值$μ$的偏差(有些用户普遍评价较低,有些用户普遍评价较高,添加一阶偏置项)
    • $X_u$表示用户$u$的潜在因子向量(特征向量),$Y_i$表示物品$i$的潜在因子向量(特征向量)

2.隐式矩阵分解

和显式矩阵不同的地方在于隐式矩阵的输入是用户的购买浏览等记录,隐式矩阵通常是稠密矩阵,而显式矩阵通常是稀疏矩阵。

公式:

  • 公式解析:
    • $C_{ui}$ 可信度,用户$u$对物品$i$隐式评价的权值
    • $P_{ui}$ 为user-item矩阵$P$的值,表示用户$u$对物品$i$的隐式评价
    • $μ$表示所有评分的平均值,$b_u$和$b_i$描述用户和物品相对于平均值$μ$的偏差(有些用户普遍评价较低,有些用户普遍评价较高,添加一阶偏置项)

3.迭代逼近的方法

由于数据量大,随机梯度下降的方法不再适合,使用易于并行的交替最小二乘法来逐步迭代逼近。

阅读全文 »