记录一些LeetCode中等题解法。

15. 3Sum

题目：给定一个整数数组，求在数组中取三个数相加和为0的所有非重复元组。

做法：遍历数组建立map，使得查找某个值是否在数组中的操作变为O(1)，双重循环遍历数对，计算0减去这两个数得到M， 在map中查找M，如果找到则得到一个三元组，在插入结果数组之前，排序后用map去重。这个方法比较明显但是相对较慢，可以找到一个更好的解法。首先对数组排序，依次遍历各个数，相当于在剩下的数中选取两个指定和的数，用两个指针指向头和尾，根据两个指针指向的数之和与目标和的大小关系，移动指针寻找和为指定值的两个数，如果找到了就记录一下，然后把头尾指针移到和当前值不等的数上，在头尾重合的时候终止。遍历完第一个数后，要跳过和第一个数相等的数，这样最后就没有重复的三元组。

16. 3Sum Closest

题目：给定一个整数数组和目标整数，求在数组中取三个数相加离目标整数最近的整数。

做法：对数组排序，遍历数组中的除了后两个数以外的数，在剩下的数中记录头尾指针，如果对应的三个数的和比已经记录的最接近目标值的数还要接近目标值，则更新已经记录的值，根据和与目标值的大小关系移动头尾指针，大于目标值则尾指针减一，小于目标值则头指针加一。

18. 4Sum

题目：给定一个整数数组和目标整数，求所有和为目标整数的非重复四元组。

做法：对数组排序，双重循环遍历数对，根据情况移动保证前两个数组成的元组不重复，如果加上剩下的数中最大的两个依然小于目标值，或者加上最小的两个都大于目标值则跳过，接着就按照正常的两数和用头尾指针移动并去重，最后得到的是不重复的四元组。

454. 4Sum II

题目：4个等长整数数组，在4个数组中各取一个数求和为0，求取法数量。

做法：用map记录前两个数组中数对的和，key为和，value为数量，遍历后两个数组中的数对c和d，在前面记录的map中寻找0-c-d，如果找到了就增加对应数量的取法。

39. Combination Sum I

题目：给定一个整数集合和目标整数，集合中的数可以多次使用，求所有和为目标整数的非重复元组。

做法：对数组排序，递归调用，参数包含原整数数组，当前已经使用的数构成的数组，与目标整数的差值，遍历数组的起始位置。如果与目标整数的差值为0，将当前数组加入结果数组，否则遍历原整数数组，如果当前数小于等于当前目标值，将当前数加入已用数组，递归调用，然后把当前数弹出。

40. Combination Sum II

题目：给定一个整数数组和目标整数，数组中的数只能使用一次，求所有和为目标整数的非重复元组。

做法：与前一道题的差别在于当前遍历的数不能和上一个数相同，并且递归时遍历数组的起始位置要递增1。

74. Search a 2D Matrix

题目：每行递增排序的二维数组，并且每一行的开头大于前一行的末尾，查找是否包含目标值。

做法：相当于一个排序数组的二分查找，需要对一维下标和二维下标转化。

240. Search a 2D Matrix II

题目：每行每列都是递增排序的二维数组，查找是否包含目标值。

做法：如果取中点，划分出来的两部分不能形成子结构。初始为整个矩形区域，需要每次选取剩余矩形的右上角，如果右上角小于目标值，则去掉第一行，如果右上角大于目标值，则去掉最右边的列，是一个O(M+N)的解法。

137. Single Number II

题目：线性时间，O(1)空间，求每一个元素只可能出现一次或三次的整数数组中出现一次的数。

做法：这里的线性时间需要用到整数32位的限制，遍历一次数组，计算最末位的1的和，该和模3的结果是只出现一次的数的最末位的值，然后一次遍历32位，然后拼起来就得到结果。

260. Single Number III

题目：线性时间，O(1)空间，给定整数数组中有两个数只出现一次，其他的数都是出现两次，求只出现一次的两个数。

做法：这里需要用到异或的一个特性，如果一个数组只有一个数出现一次，其他数都是两次，对数组依次异或，最后的结果就是只出现一次的那个数。所以对原数组依次异或，得到的结果是那两个只出现一次的数的异或值，需要找到这个异或值的某位为1的位，根据这个位是否为1将原数组分成两组，对这两组数依次异或得到的两个值就是结果。

220. Contains Duplicate III

题目：给定长度为N的数组，整数K和T，如果可以在数组中找到两个数，下标差小于等于K，值的差的绝对值小于等于T，返回true，否则返回false。

做法：对每个数，需要考察前后下标在K以内的数，但是如果要遍历一次数组，实际需要考察每个数的前K个数里是否有满足条件的数。使用一个大小为K的滑动窗口，在遍历初期窗口大小可以小于K，该窗口内的数需要排序，并且需要经常插入和删除，所以使用map，map默认是排序的。对遍历的当前值A，在map中查找第一个大于等于A-T的数，如果该数与A的差的绝对值值小于等于T，则查找成功，否则维护窗口，继续遍历。

396. Rotate Function

题目：给定长度为N的数组，它有N个旋转数组，用0~N-1对应乘以旋转数组，求最大值。

做法：遍历原数组，记录0~N-1与对应元素的和Sum，以及所有元素的和S，记录初始最大值为Sum，遍历N-1次，每次进行一些操作，修改当前Sum，求与当前最大值的最大值，具体执行的操作示例如下。

0*4 + 1*3 + 2*2 + 3*6 初始值Sum

-1*4 + 0*3 + 1*2 + 2*6 (-= S)

0*4 + 0*3 + 1*2 + 2*6 (+= Ai)

3*4 + 0*3 + 1*2 + 2*6 (+= Ai * (N-1))

一开始i是0，操作完后从1开始，每次对应0*X的位置。

421. Maximum XOR of Two Numbers in an Array

题目：O(N)求非负整数数组取两个数进行异或运算的最大值。

做法：似乎涉及32位整数位运算的这个32的常数不算logN。把每个数按照二进制建二叉前缀树，对数组中的每个数，依次遍历二进制表示的各个位，如果为1，在树中尝试寻找0，如果没有0，就找1，为0则相反，找31次可以得到和该数异或的最大值。

424. Logest Repeating Character Replacement

题目：给一串大写字母和一个数字K，可用任意大写字母替换原串中某字母K次，求替换后最长相同字母子串长。

做法：滑动窗口初始化begin=end=0，同时维护窗口中26个大写字母各有几个。每次遍历先获取一个新的字母，修改对应字母的数量，递增end为后续移动窗口做准备。end-begin是当前窗口大小，end-begin-MAX(26个字母数量)是使得窗口内所有字母相同需要的替换次数，当这个次数大于K时，递增begin，修改对应字母数量。

窗口的初始长度为0，保证不需要替换也可以满足所有字母相同，窗口长度增加时如果使窗口内不满足条件，对于新增的字母，结果子串是否包含它有两种情况，如果不包含，当前的窗口就是从字符串头到这里的最大满足条件的窗口（如果此前有一个大于此窗口P的满足条件的窗口Q，此窗口P的左边缘会大于窗口Q的左边缘，遍历时一定会有当前左边缘与窗口Q左边缘重合的时候，不论当前右边缘是多少，在逐渐递增时一定会获得窗口Q），如果包含，把窗口的头去掉，包含进这个字母，得到的新窗口不一定满足条件（例如ABABACB，K=2，执行到C的时候，会把第一个A去掉，剩下的BABAC不满足条件）， 接下来移动窗口是为了找到比现在的窗口大的满足条件的窗口，如果接下来再也找不到更大的窗口，就会输出之前得到的窗口大小，如果某个窗口扩充1格可以满足条件，窗口就会增大1。相当于优化了双重循环遍历所有begin和end，根据串内情况计算是否满足条件，每个begin不需要遍历所有的长度，以某个点开始，如果长度为20的串是满足条件的，则长度1-19的都满足条件，如果已经找到了长度为20的串，下一个begin+1就不需要考察end=begin+1了，直接看begin+20，写成双重循环加break计算量是差不多的。

面试考上机，不能用编译器，不能用long long，LeetCode里的第八题atoi，1小时没写完，真惨。我这里显示是5个月前做过，当时写了好久，用的方法也没有规划，速度较慢。当时上机的时候优化了一下，如果能写完速度应该还行。看来做过的题如果没有巩固，下次再碰到不一定能在规定时间内完成，不过要巩固的东西太多了，都掌握还是很困难的。

最近两天刷了一下LeetCode的中等难度题，直接从第二页开始，一天15题，一天17题，其中有一题没想出思路，看了答案。发现有些题目有“Follow up”，如果没有按照更高的要求完成，写起来相对比较容易，后续如果有时间再做一遍，应该要研究一下。现在注意到每次AC都会显示所写的代码在运行时间上打败了多少人，大部分都没办法做到时间最优，经常为了省事多遍历一次，如果靠自己想优化时间感觉很困难，过一遍别人的最优代码吸取一下经验，下一轮可能就能好一点。像那些树和图的题，如果调试的话写起来比较麻烦，其中刚好有很多简单题，直接交的话刷得快一点。好多题都是用递归写的，其中有些题如果不用笔来写，还是挺绕的，部分题目为了避免超时要加一个数组持久化，感觉如果转成动态规划会快一些。目前就一道明显的动态规划，后面应该会有更难的题。

我在参与新类型Kaggle竞赛时采用的步骤如下，在赛程一半的时候进入（很多图像类竞赛没办法用Kernel跑完，可以在Discussion里找github上的代码，或者直接上github搜baseline代码，用谷歌搜比赛名也会出来不少github代码）。

1. 仔细阅读Overview和Data中的内容。

2. 下载数据后，对Kernels分数排序，优先查看分数高的和票数高的，如果某个Kernel是fork别人的，先看源头，选择几个采用不同方法的代码复制下来跑，感受下运行时间和效果。

3. 按照方法名称搜原理，基本看懂这个方法的用途、优缺点、有哪些参数影响较大。

4. 查看该方法的文档，对照着手上的代码看懂，然后把文档看几遍，里面会有少量技巧和调参方法，然后搜一下他人对参数的理解。

5. 手工调参，看时间和效果的变化（本地和提交的差距）。

6. 查看Kernels中的EDA，增加对这些数据的感受，大概记一下数据的分布、范围、意义。
   

7. 查看Kernels中fork别人然后改进的代码，找一下哪里的代码变了，分析一下为什么好，是否会过拟合。

8. 尝试自己想一些预处理方法，或者是特征工程，看效果。

9. 然后再手工调参，注意观察Discussion里大家的讨论，有时候会有一些灵感，也可以直接根据提示写代码执行。

10. 在觉得排名还可以时，可以使用多折平均，分数一般都会好一些，而且减少过拟合的概率。

11. 调参可以使用Grid或者Bayesian Optimization。

12. 使用不同方法得到相似分数的结果进行平均，通常分数可以高一截。

13. 尝试stacking，方式很多，有时会过拟合，处理得好可以提高非常多，融合多个方法，多层stacking。

14. 手工平均可以根据验证集的分数选择合适的权重，也可以根据测试集分数选择权重。注意在选择哪些结果进行平均时，可以计算一下相关系数corr，选择相关系数小并且在测试集表现不错的结果进行平均。
    

15. 有些情况下伪标签效果不错。

16. 选择最终的两个提交很重要，如果测试数据非常多，分布也很均匀（比如正例只有1％就是不均匀），基本上可以尽情过拟合。根据一定逻辑进行后处理风险很大。小测试数据对stacking很敏感，不过直接平均的方法在小数据上一般都还行。

17. 可以看到这里用的很多方法，在工作环境中是没有的，我猜测优化单模型是主流，而且我在参与过程中花时间最多的也是优化单模型，融合水平很低。如何根据Kaggle中学到的知识解决实际问题，是我非常想知道的。
    

Web系统结构

http://www.cnblogs.com/chy2055/p/5199008.html

Linux命令

https://www.cnblogs.com/yjd_hycf_space/p/7730690.html

设计模式

https://www.cnblogs.com/geek6/p/3951677.html

论坛数据库设计

https://blog.csdn.net/samjustin1/article/details/52748542

Redis

作为缓存，空间有限，我猜热门帖和新帖新回复得缓存。

设计简单的LSTM、GRU模型，其中的embedding_matrix见上一篇文章。

from sklearn.cross_validation import train_test_split
from keras.models import Model
from keras.layers import Dense, Embedding, Input, concatenate, Flatten, SpatialDropout1D
from keras.layers import LSTM, Bidirectional, GlobalMaxPool1D, Dropout, CuDNNLSTM, GRU, CuDNNGRU, GlobalAveragePooling1D, GlobalMaxPooling1D
from keras.preprocessing import text, sequence
from keras.callbacks import EarlyStopping, ModelCheckpoint, ReduceLROnPlateau, TensorBoard, LearningRateScheduler, Callback
from keras.optimizers import Adam, Adadelta, SGD, RMSprop, Nadam
from keras import backend as K
def get_model():
    inp = Input(shape=(maxlen,))
    x = Embedding(nb_words, embed_size, weights=[embedding_matrix], trainable=False)(inp)
    x = SpatialDropout1D(0.2)(x)
    x = Bidirectional(CuDNNLSTM(256, return_sequences=True))(x)
    x = Dropout(0.2)(x)
    x = Bidirectional(CuDNNGRU(128, return_sequences=True))(x)
    x = Dropout(0.2)(x)
    avg_pool = GlobalAveragePooling1D()(x)
    max_pool = GlobalMaxPooling1D()(x)
    x = concatenate([avg_pool, max_pool])
    x = Dense(64, activation="relu")(x)
    x = Dense(6, activation="sigmoid")(x)
    model = Model(inputs=inp, outputs=x)
    opt = Adam(lr=1e-3)
    model.compile(loss='binary_crossentropy', optimizer=opt, metrics=['accuracy'])
    return model
INPUT = './'
batch_size = 32
epochs = 10
model = get_model()

X_train, X_val = train_test_split(train_sequence, random_state=17, train_size=0.90)
y_train, y_val = train_test_split(y, random_state=17, train_size=0.90)

exp_decay = lambda init, fin, steps: (init/fin)**(1/(steps-1)) - 1
steps = int(len(train_df)/batch_size) * epochs
lr_init, lr_fin = 0.001, 0.0005
lr_decay = exp_decay(lr_init, lr_fin, steps)
K.set_value(model.optimizer.lr, lr_init)
K.set_value(model.optimizer.decay, lr_decay)

num = 0
if not os.path.isdir(INPUT+"models/"):
    os.mkdir(INPUT+"models/")
if not os.path.isdir(INPUT+"models/"+str(num)):
    os.mkdir(INPUT+"models/"+str(num))
file_path_best=INPUT+"models/"+str(num)+"/"+"weights_best"+str(num)+".hdf5"
checkpoint_best = ModelCheckpoint(file_path_best, monitor='val_loss', verbose=1, save_best_only=True, mode='min')
early = EarlyStopping(monitor="val_loss", mode="min", patience=3)

callbacks_list = [checkpoint_best, early]
model.fit(X_train, y_train, batch_size=batch_size, epochs=epochs, validation_data=(X_val,y_val), callbacks=callbacks_list)

if os.path.isfile(file_path_best):
    print ('load ',file_path_best)
    model.load_weights(file_path_best)

y_test = model.predict([test_sequence], batch_size=256, verbose=1)