旋转数组最小值II
题目
一个有序的数组，在从某一个位置开始，旋转到数组的另一端
举例：
0 1 2 3 4 5 6 -> 4 5 6 0 1 2 3
在这个变换之后的数组中，找到最小值。
注意：
- 有可能不旋转的哦。
- 数组元素有重复
深度学习、自然语言处理和表征方法
简介
过去几年，深度神经网络在模式识别中占绝对主流。它们在许多计算机视觉任务中完爆之前的顶尖算法。在语音识别上也有这个趋势了。
虽然结果好，我们也必须思考……它们为什么这么好使？
在这篇文章里，我综述一下在自然语言处理（NLP）上应用深度神经网络得到的一些效果极其显著的成果。我希望能提供一个能解释为何深度神经网络好用的理由。我认为这是个非常简练而优美的视角。
旋转数组的最小值
题目
一个有序的数组，在从某一个位置开始，旋转到数组的另一端
举例：
0 1 2 3 4 5 6 -> 4 5 6 7 0 1 2
在这个变换之后的数组中，找到最小值。注意：有可能不旋转的哦。
题目来自Leetcode: Find Minimum in Rotated Sorted Array
最长01子串
最长01子串
原题
给定一个数组，数组中只包含0和1。请找到一个最长的子序列，其中0和1的数量是相同的。
例1：10101010 结果就是其本身。
例2：1101000 结果是110100
请大家展开自己的思路。
分析
这个题目，看起来比较简单，一些同学可能认为题目的描述符合动态规划的特征，然后就开始用动态规划解，努力找状态转移方程。这些同学的感觉，是很正确的。但，找状态转移方程，我们要对原来的数组进行变换一下。
原来是0和1的串，我们将0都换为-1。这样题目目标就变成，找到一个最长的子串，子串数字和是0。设原数组为A, DP[i]表示从0开始到i的子数组和。DP遍历一遍数组即可。例1中的数组产生的DP为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
这个例子，最后一个值是0，并且长度是偶数位。直接满足了结果。
再看例子2：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 1 | 2 | 1 | 0 | -1 |
5的位置为0，最长子串从0开始到5，长度为6。
上面这两个例子，所求的子串都是从头开始，如果不是从头开始，会是什么样的呢？看这个例子：1101100
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 1 | 2 | 3 | 2 | 1 |
通过观察上面的表格，我们可以得到，DP[0]==DP[6]==DP[2]，DP[1]==DP[3]. 根据DP的定义，如果DP[i]==DP[j]，i
一种方法，我们用map保存DP的值到位置的映射，如下表：
| DP值 | 位置 | 最大位置 | 最小位置 | 最大长度 |
|---|---|---|---|---|
| 1 | 0，2，6 | 6 | 0 | 6 |
| 2 | 1，3 | 3 | 1 | 2 |
| 3 | 4 | 4 | 4 | 0 |
| 最长子串长度 | 6 |
我们最终的算法，要综合考虑最常穿是否从头开始的。
上面的这个思路，时间复杂度是O(n),空间复杂度也是O(n).
还有其他的思路，例如DP保存的是[0,i]的1的个数，那么DP[j] - DP[i] * 2 == j - i则表明A[i+1]…A[j]是一个满足条件的串，找到j-i最大的，就是最终的结果，这个思路的时间复杂度为O(n^2),空间复杂度为O(n).
社交圈子挖掘的问题
这是博客搬家到博客园之后的第一篇文章，也是我最近对微博社交圈子挖掘的一些思考和总结，最近主要的思考和研究，主要针对一下几个问题：
- 层次性
- 重叠性
- ego network
- 有向社交网络
- 带权社交网络
- 统一解决上面的问题（!）
这几个，都是社交圈子挖掘时候我们所面临的问题，在挖掘逐渐深入的过程中，问题会一个一个显现出来。我们就要一个一个解决掉，最后要能够统一在一个方法，一个框架中。我在思考的过程中，也阅读了之前的研究，绝大部分都是针对其中的一个问题，或者两个问题。很少能够解决全部的问题。那我下面尝试分析一下这些问题的产生原因，以及一些可尝试的方法。
层次性
层次性是一个社会属性，在我们的社交圈子中非常的明显。比如，我的一个大一点的圈子是计算所，小一点的圈子是实验室。这种层次结构非常多，很多这个包含关系的层次结构。而且，层次结构也是很重要的，在网络中学习、了解网络的结构性质很有帮助。有一个应用，比如说，猎头在找人的时候，想知道哪些人都是百度的，可是并不是每个人都在自己的profile中写了公司是百度的资料，这个时候，就可以通过圈子挖掘的算法，将潜藏的信息挖掘出来。不同的层次，可能代表着公司中的不同的组。这个需要在实验过程中，自己体会，很有乐趣。针对层次性的问题，一个很直接的揭发就是层次聚类。可以根据不同的阈值获得不同层次的结果。不过，这个方法，要针对不同的层次，设定不同的阈值，并不是那么直接。
重叠性
这个是有社会中人的属性决定的：人会有小学同学、中学同学、大学同学、以前的同事、现在的同事、家人，兴趣小组等等关系圈子。首先，以个人为中心，个人出现在所有的这些圈子中（这也是下面要谈的ego network的问题），具有重叠性。另外，现实中，我的小学同学可能是在中学、大学都是同学，甚至非常有缘分的，工作了还是同事。所以重叠性是客观存在的，我们要正视这个问题。目前，在我的实验中，k-clique算法，针对重叠性，要过比较好。我之前的博客，也有介绍，大家可以看看效果。不过，一般的聚类和基于图划分的方法，都不具备这个特点。但这是很重要的一个性质。
Ego network
以前，在做社交网络的时候，并没有明确提出要针对个人、以个人为中心进行检测。基本都是对整个网络进行划分，对划分的评价也是针对整个网络进行的，比如Q函数。那为什么要构建ego network，以个人为中心进行检测呢？直观上说，没有问题。那么深层的原因呢？这个仍旧要从社会因素、社会的个体因素的角度理解。以微博为例（微博可以认为是一个社会的缩影），微博上的用户活跃度不同，最直观的表现有：1）更新微博比较频繁；2）关注、粉丝比较多；3）关注、粉丝变化也比较多。有的用户喜欢和朋友们交流，有的用户不喜欢。有的用户觉得微博是媒体，有的用户觉得微博是SNS。这些特点，都会让不同用户的关注、粉丝结构变化比较大。间接的结果就是用户的圈子大小、多少不同。所以，圈子挖掘要针对个人构建ego network，然后对该网络进行分析等。既然是针对不同的用户，构建不同的个人网络。我们是否还能够采用统一的阈值呢？当然不能。所以，针对不同的用户，学出相应的阈值，是非常重要的。这也是我最近研究的重点之一。
有向和带权的社交网络
我在做社交圈子挖掘的时候，主要针对的是微博。由于微博自身的媒体、SNS的性质，微博的关系是有方向的。所以，我们在挖掘过程中，是否能够充分利用这一点呢。另外，产生关注关系的原因有很多，比如有的人会碍于面子的原因关注的。还有，用户之间的交互有的多有的少。这些因素就直接导致了，社交网络是一个带权的网络，社交网络中的边的权重，可以理解为用户之间的紧密度。我们可以考虑不同的紧密度计算方法。比如互相转发，评论，@的次数之类的。总而言之，充分考虑方向和权重的因素。能够很大程度上提升效果。在我的尝试方法中，这两个也是重要的因素。
总结
上面干巴巴的说了很多问题。可能不是很有趣，但确实是我们在做社交挖掘过程中需要注意的问题。上面是一些点，如何将这些点，有机的结合在一起，将是一件更有挑战的事情。到目前为止的研究，已经有一些尝试，我会逐渐在后续的博客中，和大家分享。
后记
博客写多了，就会发现，大家更喜欢有例子，有数据，有结果的博文。所以，我想类似这种概述性质的，还是少写为妙。多将一些论文中的观点总结，写出来，实现并且给出结果。这样会更有帮助，让大家直观的知道这些方法的优缺点。我想我更多的路子，会是这样。并且，我真心希望更多的关注社交网络的同学一起讨论。我们国内也可像国外的大学一样，做出一些社交网络挖掘的工具，让老外用我们的。