ITPub博客

在上一篇文章当中我们讲解了bellman-ford算法和spfa算法，其中spfa算法是我个人比较常用的算法，比赛当中几乎没有用过其他的最短路算法。但是spfa也是有缺点的，我们之前说过它的复杂度是，这里的E是边的数量。但有的时候边的数量很多，E最多能够达到，这会导致超时，所以我们会更换其他的算法。这里说的其他的算法就是Dijks

这道题非常巧妙，是一道思维题。我们很容易想到，间隔的最小距离取决于出现次数最多的数。 假设这个数是u，出现了v次。那么我们把它均分到n个空格当中，v个数有v-1个间隔，所以每个间隔最大是m = (n - 1) // (v-1)。n-1是因为末尾的元素不产生空格但是会占据位置。我们只需要把剩下的数填入这v-1个空格当中就可以了，它们之间的间隔一定不会小于m。

今天是pandas数据处理第8篇文章，我们一起来聊聊dataframe的合并。 常见的数据合并操作主要有两种，第一种是我们新生成了新的特征，想要把它和旧的特征合并在一起。第二种是我们新获取了一份数据集，想要扩充旧的数据集。这两种合并操作在我们日常的工作当中非常寻常，那么究竟应该怎么操作呢？让我们一个一个来看。

昨天的问题看起来很简单，只是一个寻常的模拟题，只要我们照着题目的要求操作就可以了。但是当你实际这么做你会发现是不行的，原因也很简单，因为数据的范围太大了。草地中草的生长速率以及割草的最长时间都是这个量级，在这个量级下线性的复杂度都是不可以接受的。

点击上方蓝字，关注并星标，和我一起学技术。今天是机器学习专题的第33篇文章，我们继续来聊聊SVM模型。在上一篇文章当中我们推到了SVM模型在线性可分的问题中的公式推导，我们最后得到的结论是一个带有不等式的二次项：想要了解具体推导过程的同学，可以参考我的上一篇文章：机器学习|深入SVM原理及模型推导（

最短路问题也属于图论算法之一，解决的是在一张有向图当中点与点之间的最短距离问题。最短路算法有很多，比较常用的有bellman-ford、dijkstra、floyd、spfa等等。这些算法当中主要可以分成两个分支，其中一个是bellman-ford及其衍生出来的spfa，另外一个分支是dijkstra以及其优化版本。floyd复杂度比较高，一般不太常用。

这道题的思路很简单，我们完全可以模拟一下这个英雄的魔法值的变化过程。在游戏开始的时候是n，然后每秒钟如果魔法值超过x则召唤一个召唤兽，否则什么也不做等待魔法恢复。那么我们只需要重复m次这个过程就可以统计出一共召唤出了多少个召唤兽。 这的确非常简单，但有一个很大的问题就是m的范围是10的九次方这个量级，显然我们用循环的方法是不行的，一定会超时。既然循环不行，那么就只能通过数学方法来计算了。

点击上方蓝字，关注并星标，和我一起学技术。昨日题解每日一题|字符串转换问题这道题同样来源于codeforces，链接：https://codeforces.com/gym/102625/problem/B这道题干想还是有点难度的，在codeforces当中做出来的人也不多。我们首先来思考一点，假设没

离散对应的反面是连续，离散化也就是将连续性的数值映射到一个离散的值。举个很简单的例子，比如说现在有一个特征是用户的收入，我们都知道贫富差距是非常巨大的，一个马云的收入顶的上成千上万人收入之和。而最穷的人收入非常少，甚至每天不到一美元。 我们来设想一下，假设我们将收入这个值作为特征放入模型，会发生什么。如果是线性模型，很显然模型会被这个特征值给带跑偏。我们来看下线性回归的公式：

约瑟夫问题是一道非常经典的问题，有很多非常巧妙的解法，我们今天分享其中比较简单的两种。 第一种方法是模拟法，也就是说我们用一个n个节点的链表来模拟算法运行的过程，直到链表当中只剩下一个元素为止。这样当然是可以的，实现难度也不是很大，但是有一个缺点是计算的复杂度很高，是。当n和m都很大的时候，我们是无法很快得出答案的。 这个时候就需要用第二种方法了，第二种方法就是递推法，

今天是算法和数据结构专题的第32篇文章，我们来聊聊拓扑排序的问题。 拓扑排序是图论当中一个非常简单也非常常用的算法，它有很多的功能。它可以用来检测有向图当中是否存在环，也可以用来解决存在依赖的调度问题。下面我们就来看看这个算法的庐山真面目吧。

这是一个非常经典的算法问题，对应的解法称作蓄水池算法。别看它有一个专门的算法名称，但是它的思维非常简单。 假设我们一共有n个人参与抽奖，在当下n未知，奖品一个有k个。我们用一个长度为k的数组存储中奖的人的信息。首先，我们将前k个出现的候选人放入数组当中。 从第k+1个出现的候选人开始，我们假设当前的候选人的序号是i，i > k。我们随机一个1 ~ i的数

这是一道经典的贪心问题，由于我们可以随意地从A和B中获取元素，我们又希望得到的结果的字典序最小。我们很容易分析出要尽量将小的元素放在前面，而大的元素放在后面。 基于这样的原理，我们很容易想到算法，可以用两个指针分别指向A和B的开头。每次都选择其中较小的那一个。比如1 3 5和2 4 6，一开始是1和2比，由于1小于2，所以选择1。A的指针移动一位指向3，下一轮比较3和2，由于2小于3，所以选择2

SVM模型大家可能非常熟悉，可能都知道它是面试的常客，经常被问到。它最早诞生于上世纪六十年代。那时候虽然没有机器学习的概念，也没有这么强的计算能力，但是相关的模型和理论已经提出了不少，SVM就是其中之一。 SVM完全可以说是通过数学推导出来的模型，由于当时还没有计算机，所以模型当中的参数都是数学家们用手来算的。它有一个巨大的应用就是前苏联的计划经济体系，我们知道在计划经济当中，国家有多少社会资源

死锁的原理非常简单，用一句话就可以描述完。就是当多线程访问多个锁的时候，不同的锁被不同的线程持有，它们都在等待其他线程释放出锁来，于是便陷入了永久等待。比如A线程持有1号锁，等待2号锁，B线程持有2号锁等待1号锁，那么它们永远也等不到执行的那天，这种情况就叫做死锁。 关于死锁有一个著名的问题叫做哲学家就餐问题，有5个哲学家围坐在一起，他们每个人需要拿到两个叉子才可以吃饭。

今天是LeetCode专题的第59篇文章，我们一起来看看LeetCode第93题，有效ip地址（Restore IP Addresses）。 这题的官方难度是Medium，点赞1296，反对505，通过率35.4%。从各项指标来说看起来有些中规中矩，实际上也的确如此。这道题的解法和立意都有些显得新意不足，但总体来说题目的质量还是可以的，值得一做。

今天是pandas数据处理专题的第六篇文章，我们来聊聊DataFrame的排序与汇总运算。 在上一篇文章当中我们主要介绍了DataFrame当中的apply方法，如何在一个DataFrame对每一行或者是每一列进行广播运算，使得我们可以在很短的时间内处理整份数据。今天我们来聊聊如何对一个DataFrame根据我们的需要进行排序以及一些汇总运算的使用方法。

今天是算法与数据结构专题的第31篇文章，我们一起来聊聊二分图匹配与匈牙利算法。 在上一篇文章当中我们介绍了一个有趣的稳定婚姻问题，模拟了男男女女配对的婚恋场景，并且研究了一下让匹配更加稳定的Gale-Shapley算法。如果错过了这篇文章的同学可以从下方的传送门回顾一下婚姻稳定问题的具体内容。

大家好，这是一个全新的专题，设立的初衷是分享一些我觉得比较有趣的算法题或者是各类问题。帮助大家锻炼思维，提升算法能力。 本专题将会持续更新，直到我找不到有趣的问题为止。所以如果大家做过什么有趣的问题，或者有什么印象深刻的问题，可以给我留言，帮助我把这个专题一直做下去。 今天我选的是一道经典的思维题，红眼睛与蓝眼睛。

今天是LeetCode专题第56篇文章，我们一起来看看LeetCode第90题，子集II(Subsets II)。 这题的官方难度是Medium，通过率46.8%，点赞1686，反对73。看得出来是一道偏基础，然后质量很高的题。既然有Subsets II自然有Subsets I，它的前作是78题，和78题相比，题意稍稍有些改动，如果没做过78题的，建议可以先看下，有个对比。