haidixipan-CSDN博客

原创算法中的小技巧trick汇总

1. 数字&（数字-1）可以将数字的二进制表现形式去掉最低一位的“1”2.数组下标，可以被利用起来进行复杂度位O(n）的排序，前提是要排序的数字要在一定范围内，且空间复杂度没有要求3.判断一个单项链表是否有环，可以设计双指针便利整个链表，一个步进1，一个步进2，二者如果二者相遇，那么就可以证明有环，否则一直到结束都没有相遇则证明无环证明：步进1的假设位小A，步进2的假设为小B，小B先跑进环（跑进后就一直在环里循环了），如果小B跑了N步，后小A进环，则他俩能否相遇呢？答案是肯定的，小B跑的

2022-01-19 16:15:30 292

原创关于卷积的思考

经常看人工智能相关书籍介绍卷积。上来给如下面一行公式然后在给出下面一段代码怎么看怎么不觉得这段代码和上面的公式有任何联系。实际上公式一般给出的是时域上的卷积，代码给出的是频域上的乘积。作者可能连这层意思还没搞懂。时域与频域经过傅里叶变换可以相互转换，所以二者本质上是一个东西，而处理的数据不很相同。对于深度学习计算说，不管是图像、文本、还是音频，我们容易拿到的是他们的离散数据信息，而其本质上属于频域数据（非连续）因此，在做卷积时对应的也是频域乘积操作。这个过程本质上是对数据进行

2021-11-11 16:29:29 753

原创 38.leetcode38 Count and Say

本题难度为easy,给了5个字符串，根据规律推测出后续行数的字符，题目要求输入行数返回当行字符。答案里面讲输入行数分成了3类，1.如果为0返回空字符2.如果小于等于5直接返回已有字符3.大于5后开始每行按照规律计算，直到输入行数并返回值38.Count and SayEasy12839542Add to ListShareThe count-and-say sequence is the sequence of integers with the first five term.

2020-06-30 16:13:34 143

原创 25.leetcode 25 Reverse Nodes in k-Group

本题是一个hard链表翻转问题，关键点如下：1.子链表翻转，需要有一个头节点指引返回结果的head2.题目有空间要求，合适的做法是先计数再做子链表翻转代码如下：# Definition for singly-linked list.# class ListNode(object):# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass So

2020-06-16 11:46:41 115

原创 37.Sudoku Solver

这道题是一道数独结题，是36题的延伸。考点一：需要有三个集合分别存储每行、每列、每个小九宫格已经存在的数字供后续判断是否要填充考点二：判断有效性，需要有一个函数判断填充的数字是否有效，影响范围只有上述三个字典，因此需要遍历0~9，找到和三个字典里的数字不冲突的第一个数字即可。（找到第一个合适的就可以，不用考虑是否会对其他位置的数字有影响）考点三：提升性能学会使用递归上代码：import collectionsclass Solution(object): def solveSu..

2020-06-11 17:02:24 109

原创 LEETCODE刷题榜

2.leetcode2 Add Two Numbers链表相加3.leetcode3 Longest Substring Without Repeating Characters4.leetcode4 Median of Two Sorted Arrays5.leetcode 5. Longest Palindromic Substring最长回文子串6.leetcode6. ZigZag Conversion7.leetcode 7. Reverse Integer8.leetco

2020-06-10 10:14:33 189

原创 20.推荐召回算法之k近邻算法：局部敏感哈希、kdtree、balltree算法分析与比较

推荐系统里面临的比较大的问题是1.召回 2.排序。召回是从百万、千万甚至上亿的候选中找到用户可能喜欢的商品（可以不那么精细），排序一般是设计怎样排序才能使点击率更高。考虑一个新闻推荐场景，假设一个用户曾经看过美妆、育儿、明星类的新闻，怎样在ta下一刷中把用户可能感兴趣的找到并推给用户呢？比较简单的做法是，将每条新闻分一个类（如体育、美妆、育儿、八卦、明星、电影），根据分类将候选召回再排序。...

2018-12-29 18:01:44 5785 1

原创 19.有哪些文本表示模型，他们各有什么优缺点

1.词袋模型/N-gram每篇文章表示成一个N维向量，每一维度表示一个单词，值为这个词对这篇文章的重要程度，计算公式为：TF-IDF(t,d) = TF(t,d)*IDF(t)其中，TF(t,d)为单词t在文档d中出现的频率，IDF(t) = log(文章总数/(包含单词t的文章总数+1)) ，IDF公式可理解为如果一个词出现的文章数越多那么说明它越是一个通用词，通用词对文档内容贡献度...

2018-12-04 13:58:33 1602

原创 18.如何验证求目标函数梯度功能的正确性

给定优化问题：,假设已经用代码上线了求目标函数值和求目标哈桉树梯度的功能，请问，如何利用求目标函数值的功能来验证求目标函数梯度的功能是否正确？根据梯度的定义，目标函数的梯度向量为：，其中每一个元素为目标函数(优化函数)对这一模型参数求的偏导数。回顾一下偏导数的定义：，即函数L(\theta )在这点的斜率，ei为维度与\theta 一样的向量，只有在i这个维度为1，其余为0。...

2018-11-23 18:04:20 1095 1

原创 17.LDA与word2vec区别

LDA涉及到的数据知识不是一般的多，这里不做详细阐述，可参考如下博客：https://blog.csdn.net/v_july_v/article/details/41209515总的来说LDA与word2vec区别如下：区别 LDA word2vec 输出文档-主题概率分布矩阵和主题-词概率分布矩阵词对应的词向量训练方法利用文档中单词的贡献关...

2018-11-21 19:46:41 2098

原创 16.Word2Vec是如何工作的

Word2Vec是一种比较常用的词嵌入模型，它实际是一种浅层的神经网络，有两种网络结构，分别是CBOW和skip-gram.CBOW的目标是根据上下文出现的词语来预测当前词的生成概率；而skip-gram是根据当前词来预测上下文中各词的生成概率，看起来两种网络结构是互为镜像的，如下图。由上图，两种网络模型都可以表示成输入层、映射层与输出层。w(t)为当前词，w(t-2)、w(t-1...

2018-11-19 11:48:32 307

原创 15.xgboost步长如何设定

xgboost的步长即是parameter里的eta(learning rate),官方对它的定义如下：eta [default=0.3, alias: learning_rate]Step size shrinkage used in update to prevents overfitting. After each boosting step, we can directly get...

2018-11-16 11:33:53 1337 1

转载 14:回归类问题阈值如何确定

在用逻辑回归做潜在用户挖掘时,阀值(Z)的选取是一个头疼的问题。取太高，查全率虽然高了，但是查询条件过于严格，挖掘出的潜在用户过少。取的太低，资源浪费的太多。对于一般的营销而言，这个问题很好解决，只要按照预算，从高往下选取就可以了。但对于其他没有预算约束的情况就比较麻烦。希望下面的公式可以给予一些启发Z=Ln（(qc)/(QC)）q-发生显性结果的先验概率，比如信用卡用户发生违约的以往概率...

2018-11-14 20:33:19 8722

原创 13.解决样本不均衡问题

实际工作中经常遇到样本不均衡问题，比如某P2P平台预测用户信誉，1为信誉良好，0为有违约记录，样本采集下来为1的样本占绝大多数（比如90%），此时如果你用分类模型，目标函数是准确率，那么即使你全部预测为1，那么准确率也为90%，会极大的影响模型效果。因此在我们在训练模型之前，先要处理样本均衡的问题，总结方法如下：1.上下采样：上采样为增加小众样本数量（一份数据复制多份），下采样为减少大众样...

2018-11-07 16:05:02 716

转载 9:极大似然估计

极大似然估计，也叫最大似然估计，是参数估计的一种方法，一般用来推测数据分布函数相关参数。极大似然估计步骤：1.先假设数据属于某一分布（正太分布、泊松分布等），得到概率分布函数2.对概率分布函数求导，另导数等于0（若有多处为0，选另样本点概率最大的参数），根据样本点数据，求参数值为什么叫似然：对于无法穷举的问题，可根据样本数据估计实际分布，不是真实但近似真实以下参考wiki...

2018-10-31 15:03:38 946

原创 8.softmax

softmax为归一化函数，形式如下： for j = 1, …, K.如上式，softmax将元素限制在（0，1）范围内，特点是会凸显最大值并抑制远低于最大值的元素 Python使用numpy计算的示例代码:import numpy as npz = np.array([1....

2018-10-29 17:12:33 108

原创 6.随机森林,GBDT,Adaboost

参考链接：https://blog.csdn.net/lyf52010/article/details/798223821.随机森林，属于bagging的一种（bagging与boosting的区别见：https://blog.csdn.net/haidixipan/article/details/83105932），即 1）从样本中有放回的采样 2) 从特征中随机选取...

2018-10-26 11:20:34 194

转载 6.LSTM

LSTM(Long short-term memory)与RNN不同的是，在处理文本信息时，后者对间隔比较长的文本之间的关联处理的不够好，而LSTM网络相对RNN可以记住大段文本的有用信息。LSTM构成：1.遗忘门：首先决定丢弃哪些不重要的信息2.输入门：决定要保留哪些新的信息3.输出门：决定输出的状态LSTM详细的介绍如下文（转自：http://colah.github.io...

2018-10-24 15:41:10 210

原创 5.RNN原理

一.RNN 循环神经网络(RNN, Recurrent Neural Networks) 参考链接：https://blog.csdn.net/heyongluoyao8/article/details/48636251构成：输入层，隐藏层（多个），输出层特点：1.隐藏层间的节点是可以互联的(包括自己和自己互联)2.输出层可以作为隐藏层的输入3.隐藏层可以跨层连接用途：...

2018-10-23 20:33:58 224

原创 3.ROC，准确率、召回率

ROC曲线一般用于分类问题，衡量分类模型好坏的一个指标首先对样本进行如下划分预测真预测假实际真 TP（True Positive） FN(False Negative) 实际假 FP(False Positive) ...

2018-10-22 17:38:33 306

原创 3.L1和L2的区别；L1为什么能稀疏矩阵L2不能；L2为什么能解决过拟合

1.L1和L2的区别L1:预测值与实际值差值的绝对值之和L2:预测值与实际值差值的平方之和 2.L1为什么能稀疏矩阵L2不能:参考链接：https://blog.csdn.net/autocyz/article/details/76511527，矩阵指的是模型参数组成的矩阵，稀疏是指模型参数很多是0。为什么L1可以呢，从一个特征的模型来观察，损失函数为 F(w)=f+ ...

2018-10-19 19:36:41 1930

原创 2.bagging和boosting的区别

区别总结 Bagging Boosting 样本选择有放回的选取全量选取样本权重权重相等错误率大的样本权重越大分类器权重权重相等准确率...

2018-10-17 10:32:44 152

原创 1.内容推荐系统的建模过程和特征的选择方法

内容推荐系统的目标是将用户感兴趣的内容推荐给用户。一、建模过程基于内容的推荐系统面临的问题有1.怎么从海量级物料中挑出用户感兴趣的内容 2.用户最感兴趣的内容如何第一时间呈现给用户问题1，1）利用统一的标签体系，将用户和物料分别打标签，然后从海量视频中捞出与用户标签相符的物料2）利用itemCF,通过用户当前与历史场景下喜欢的内容，找出他们的相关的内容问题2，1）将问题...

2018-10-16 11:25:58 913

原创 leetcode 36. Valid Sudoku

本题判断数独题，难度medium，行和列单独设置一个字典好判断，九宫格号如何计算时本题难点。根据数字下标我们发现，行号/3 * 10 + 列号/3*100可以把九宫格区分开来，然后再判断九宫格里有无此数字即可，详见代码。Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated accor...

2018-04-28 14:11:29 113

原创 leetcode 35. Search Insert Position

本道为easy，考察二分查找Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You may assume no duplicates in ...

2018-04-26 11:00:04 77

原创 leetcode 34. Search for a Range

本题的解决思路是先找到target的开始位置，然后顺着开始位置找到结束为止，注意找开始位置的用法Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.Your algorithm's runtime comple...

2018-04-25 10:44:01 93

原创 leetcode 260. Single Number III

本题的思路是寻找一组数种出现一次的两个数，此题有如下特点：1.数异或自己等于02.两个不一样的数异或不为0具体思路看代码Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two...

2018-04-20 17:13:42 116

原创 leetcode 33. Search in Rotated Sorted Array

循环递增数组有一个性质：以数组中间元素将循环递增数组划分为两部分，则一部分为一个严格递增数组，而另一部分为一个更小的循环递增数组。本题的思路每次二分查找，判断target在一侧有序的数组还是在无序的数组里，在判断有序数组里一定要记着比较数组最大和最小值。Suppose an array sorted in ascending order is rotated at some pivot unkno...

2018-04-20 10:03:31 112

原创 leetcode 31. Next Permutation

本题借用乔的解题思路：题意为：比如给你个列表是[1,2,3,4]，它的值就是1234，你要找到这四个数字能排出来的刚刚大于1234的数，也就是1243。如果给的是4321，没有比它更大的，就返回最小的也就是1234Implement next permutation, which rearranges numbers into the lexicographically next greater ...

2018-04-18 11:25:13 114

原创 leetcode 29 Divide Two Integers

本体借用乔同学的解体思路：Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.Return the quotient after dividing dividend by divisor.Example 1:Input...

2018-04-16 23:41:08 114

原创 leetcode28. Implement strStr()

easy题，考虑一下异常就可以了Implement strStr().Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.Example 1:Input: haystack = "hello", needle = "ll"Output: 2...

2018-04-12 17:13:30 79

原创 leetcode 27. Remove Element

本题跟上题思路一样，从后往前遍历，直接上代码Given an array and a value, remove all instances of that value in-place and return the new length.Do not allocate extra space for another array, you must do this by modifying the...

2018-04-11 13:43:05 83

原创 leetcode 26. Remove Duplicates from Sorted Array

本题为给一个有序数组，让你返回无重复元素个数，并且原数组只保留无重复元素，因为要删除数组元素，因此遍历的时候要从后往前遍历，防止原元素顺序紊乱。Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.Do not al...

2018-04-10 14:05:25 87

原创 leetcode24. Swap Nodes in Pairs #python

本题主要思路是定义快慢指针，各每次走两步，再进行值交换。注意题目要求不能改值，代码如下Given a linked list, swap every two adjacent nodes and return its head.For example,Given 1->2->3->4, you should return the list as 2->1->4-&gt...

2018-04-03 15:32:01 108

原创 leetcode23. Merge k Sorted Lists # #python

本题与merge2 sorted linked lists很类似，也自然的想到了调用之前实现的的方法。在网上看了一些python的解决方案，有提到最小堆的，感觉有点晦涩难懂，并且运用了python自带的heap函数，一般工作中比较难遇到，也难想到。作者开始的思路是，先实现2 sorted linked lists 函数，然后再对lists做一个for循环，每次将一个list合并到已经排好序的lis...

2018-04-02 23:45:14 232

原创 leetcode 22. Generate Parentheses #python

本题之前一直纠结如何循环调用，后来看网上思路有人用到递归，整理后的代码如下，基本思路是：1.左边括号数要大于右边括号数2.在1的原则下，每次递归为字符串赋值"("或")"3.每次递归生成两个分支，分别往下去找，最终找到所有组合Given n pairs of parentheses, write a function to generate all combinations of well-for...

2018-03-31 09:11:38 229

原创 leetcode21. Merge Two Sorted Lists

本题思想为递归排序，原理是从两个数组中取出head进行比较，把小的放到目标数组中。Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.Example:Input: 1-&...

2018-03-30 13:38:59 92

原创 leetcode 20. Valid Parentheses

本体的思路集中在理解题意和栈的关系，每当看到一个左括号，就压栈一个右括号，当遇到一个右括号，看一下此右括号是否和栈顶字符相同，相同则继续，否则一定是违规的。Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.The ...

2018-03-29 16:47:05 96

原创 leetcode 18. 4Sum

本题可以套用3sum,在最外层多套用一层循环，详见代码Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of targ...

2018-03-29 16:17:16 139

原创 leetcode 17. Letter Combinations of a Phone Number

本题不是特别难，从后往前套两层for循环基本就出来了。不用递归看起来舒适些Given a digit string, return all possible letter combinations that the number could represent.A mapping of digit to letters (just like on the telephone buttons) is...

2018-03-28 19:13:13 109

空空如也

空空如也