App推荐——TaoMix2 干活、睡觉专用辅助声音

之前MUJI Sleep给我的印象很深,也是用来辅助睡眠的。今天发现一个进阶版的,这个App也是用来播放一些自然声响的,但它的特点是可以混音:里面有个白色的点,播放的时候会在几种音源之间游走。比如,可以在水声、鸟叫声、树叶声中间各种游动,应该是掺杂比例的不同。

 

不知为何,想起了高斯混合模型…

 

Android: https://play.google.com/store/apps/details?id=air.com.demute.TaoMix&hl=zh_CN

iOS: (TaoMix与TaoMix2)

https://itunes.apple.com/cn/app/taomix-create-your-own-relaxing/id660104097?mt=8

https://itunes.apple.com/cn/app/taomix-2-yong-zi-ran-sheng/id1032493819?mt=8

Windows 下使用MinGW编译Cython

用Visual C++编译器也是可以的(找不到vcvarsall.bat可以看这篇),不过为了后面移植方便,目前的项目还是用MinGW.

步骤其实很简单,参考http://cython.readthedocs.io/en/latest/src/tutorial/appendix.html

稍微翻译一下就是:

  1. 从这里http://www.mingw.org/wiki/HOWTO_Install_the_MinGW_GCC_Compiler_Suite 下载个MinGW Installer. 下载、安装的时候记住是32位版本的,因为64位版仍旧有些不兼容现象。
  2. 运行安装下载的程序。Cython只需要最基本的包(basic package)就行了,主要是为了里面的C++编译器
  3. 将你安装MinGW的目录设置到PATH环境变量中。默认位置应该是C:\MinGW\bin
  4. 在Python安装目录下创建配置文件。如果Python是安装在C:\Python27目录下,那就创建C:\Python27\Lib\distutils\distutils.cfg,然后文件内容为

     

这样就可以使用GCC编译啦~

 

翻译:次梯度以及一阶最优性条件(Subgradient and First-order Optimality Condition)

本文是对文章Basics of Convex Analysis的部分翻译,若本文对您的任何权益造成侵犯,请联系我。

This article is a partial translation of Basics of Convex Analysis, if this infringes any of your rights, please contact me.


次梯度以及一阶最优性条件

若下述不等式成立:

则我们说是函数点上的一个次梯度,并且属于在该点(用表示)的一个次微分。

上述不等式表明函数的图像(graph)是由不等式右侧定义的超平面所(hyperplane)支撑的。一个次梯度因此也是这众多支持超平面其中一个的“斜率(slope)”。如果该函数在点处可微,则这样的次梯度有且仅有一个(即标准梯度),与此对应地,也只有一个支持超平面。相对地,如果一个函数在点处不可谓(比如,在处有个扭曲)那么就能有无穷多个支持超平面,并且相对应地,在该点的次微分是一个连续的次梯度的集合。

一个典型的例子是绝对值函数,它在0点是不可导的。但在这个点上,它可以由组成的所有直线支持。这个集合即该函数在0点的次微分,用表示。

函数的演示(粗线表示)以及其中两个支持直线(虚线表示)。这两条支持直线都有次微分中的斜率。注意,那条水平线也是支持超平面之一,表明。并且因此由一阶条件(下文定义),这个函数在原点有一个极小值。

现在,通过定义非限制问题中的一个最优点,必有,并且因此0必须是函数点处的一个子梯度。

这就是一阶最优性条件(FOC):

如果我们将次微分看做一个运算符那么,直观地,寻找极小可以看做“逆转”次微分并计算它在点0的值的过程,即。我们稍后再进一步介绍,但这个逆转次微分运算符的思路是非常重要的。

在继续之前,有必要提一下(并且这并不难理解)下述包含关系对于次微分的和是成立的:

对关注的大部分问题而言,上述关系可以强化为相等的关系, 但注意如果,则上述包含关系意味着,这对于证明是个极小值而言(这正是我们最感兴趣之处)足矣。


 

LeetCode 47. Permutations II

用回溯法完成,跟普通排列问题不同的是,需要排除掉一些重复“路径”。

可以这样做,先把输入数组排个序,这样重复的数就在相邻位置了。随后在回溯探求的过程中,我们要保证相同值的两个数nums[i], nums[j],如果i<j,那遍历只能有一种次序:nums[i]先,nums[j]后。

换句话说,就是判断这种情况是需要提前终止的:两个数nums[i]==nums[j] && i<j,但是nums[i]还没有被遍历。所以找个东西记录一下访问就行了。

时间复杂度是O(N!),空间复杂度是O(N)

 

LeetCode 368. Largest Divisible Subset

思路:

想到一个词叫“传递性”,在这边应该也适用。就是如果b%a==0,然后c%b==0,那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了,应该是动态规划的思想,results[i]保存包含数组元素nums[i]的最佳集合,构建集合的时候,首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳(相当于找到c%b==0,当然这里的b是之前results[j]里面的最大元素,即nums[j])然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合,如此继续…

时间复杂度应该是O(n^2)

 

LeetCode 424. Longest Repeating Character Replacement

思路很重要。

给定一个长度n的字符串s和限制k,将s中的部分字符替换(替换次数<=k)后,能得到连续字符(如AAAA)的长度最大为多少?

使用滑动窗口的思路可以在O(n)时间复杂度的情况下解决这个问题。需要记录当前窗口内各个字符的计数值(可以看做分布情况)以及当前窗口的起始点,窗口内最多字符的计数best。我们知道,最多字符的计数best+修改数量k如果还是不能使得当前窗口内的字符都统一的话,就得把窗口缩小(起始点后挪)。窗口缩小时记得把窗口计数更新一下。

这里有一个tricky的地方,best值本来在滑动窗口的时候是要更新的,因为可能窗口过了这个best会变小。但是由于我们要找的只是个最优的值,所以这个情况并不需要考虑对best进行更新,反正它也成不了最优。

代码

 

LeetCode 295. Find Median from Data Stream

题目大意是给定一个int数据流,判断当前整个数组的中位数值。由于数据流是可以不断增加的,因此采用两个堆(最大堆*1+最小堆*1)来实现。

这东西思路网上都有,每次新进一个数,维护堆就行了。维护一次的复杂度是O(logN),对应整个数组的复杂度是O(N logN)

STL 堆相关的三个函数 make_heap(), push_heap(), pop_heap()

STL是个好东西,在<algorithm>库里面就有三个与堆有关的函数,利用vector存储堆元素就可以调用这些函数来建立、更新堆。

make_heap(first, last, comp)是建立堆的函数,输入的first, last对应begin()和end()的iterator,comp函数可选,与库中sort()用到的方法相同,自定义的时候比较两个元素x, y的偏序关系,返回true说明x应该排在前面。相关的有两个仿函数叫less<T>() 和greater<T>(),直接用来比较<和>关系的。

push_heap(first, last, comp)使用时,将新元素放在数组末尾(代表堆的末叶节点),然后调用这个函数更新堆,是一个sift-up的过程。

pop_heap(first, last, comp)会将堆顶元素调整到数组末尾用于pop,同时调整更新堆。

代码

 

Indeed Tokyo 笔试题一道

Indeed的笔试一次一共4道,鄙人第一次做,前三题1hr就搞定了,唯独最后一题百思不得其解,后来看了大神的思路后幡然醒悟,确实脑子没转过来啊!

题目大致如下:

输入字符串 str=a[0] a[1] ... a[N] ,其中0<N<=10^5。字符串的每一位是0-9或?,需要用0-9填充各个问号的值,使得整个字符串成为一个数(允许前导0),并且满足任意连续10位上的字符(或理解成数字) a[i] a[i+1] ... a[i+9] 不重复,输出解的个数。

例如,输入”04??2?7″,输出应当为120.

 

最简单的思路当然是回溯,回溯用递归的话容易爆栈,可以自己定义栈结构。但实现完了我发现效率太低了。这种解法的时间复杂度是O(N!).

网上给了一个十分简单的思路:只计算str前10个字符有多少可能性

这样做可行否?不妨试试看。

假设已经知道了前10个字符a[0]…a[9]能得到解的数目(定作M),那么根据规则,在a[10]的时候要考虑a[1]…a[9]的情况,对于每一种a[1]到a[9]的情况而言,由于已经决定了9个数字了,那么第10个数字显然已经确定了。从这我们可以知道,解的个数肯定是不大于M的,因为假设a[10]不是个”?”并且a[10]又不等于缺的那个数字的话,那这个case是要被毙掉的。然后以此类推,检测a[11], a[12], .. a[N]. 按照这种算法,整个问题的时间复杂度是O(10! * N)=O(N).

==更新==

还有一个更高效的解法,主要思路是利用后面“循环数”得到的确定信息来填充前面的?,然后直接计算组合数即可。具体可以看http://gaomf.cn/2016/10/26/String_Fill/

========

伪代码如下:

换个说法就是,后面的数字肯定是前面10个数字的循环,因为新加的a[i]肯定是得顶替上a[i-10]的位置的。