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编译啦~

 

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]的位置的。

 

LeetCode 173. Binary Search Tree Iterator

思路

画一个简单的BST,然后可以看出有三种情况

  • 如果当前节点有右孩子,那就在右子树里找到值最小的那个,显然是右子树里最左下侧的那个节点
  • 如果当前节点没有右孩子,由于左子树的值肯定都比当前节点的值小,左右要找父节点
    • 如果找到某个父节点的值比当前节点值大,那这个父节点就是下一节点
    • 否则,当前节点就是最后一个节点

因此,需要一个栈结构记录当前节点的父亲们(有点像调用栈)。

测试例:NULL根节点,只有一个节点,只有单侧树

代码

 

LeetCode 102. Binary Tree Level Order Traversal

练手水题,直接贴代码。快转正面试了,虚啊,鬼晓得BOSS会问点什么。

 

LeetCode 385. Mini Parser

思路

一开始还以为又回到了编译原理,想到了状态转换图啊之类的。后来发现这个题目没有这么变态,要考虑的是个栈的问题。

为什么会想到栈呢?因为看到了括号,因为括号结束的时候我们要把某个部分的内容添到更大的括号里头去。

我的处理方式是:

  • 构造一个工作栈,一开始是空的
  •  碰到数字
    • 生成一个只包含数字的NestedInteger
      • 如果工作栈空,那么字符串就是个纯数字,直接返回
      • 如果工作栈非空,那么这个字符串就要加到当前工作栈顶端的元素后面(考虑情况[35,345]这种)
  • 碰到'[‘
    • 新建一个空的NestedInteger(至于里面填什么,不是这里要考虑的事儿)
    • 把它压入栈
  • 碰到’]’
    • 取出当前栈顶元素formerTop
    • 判断栈是否空了
      • 非空,则formerTop要加到当前栈顶的后面
      • 空,可以返回了
  • 碰到’,’
    • 其实没什么用,往前挪动吧

这个步骤还能再精简一下的,判断栈是否空,是否返回的部分是重复了

代码

题目

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Example 1:

Example 2:

LeetCode 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

分析

这个题目直接扫一遍就行了,复杂度是O(min(strlen)),strlen是字符串的长度

代码

 

LeetCode 62. Unique Paths

原题:https://leetcode.com/problems/unique-paths/

robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

思路

这是个经典的题目,反正就是动态规划的思路?说是动态规划,其实就是下一个状态怎么来的问题。此处的下一状态就是一个格子solution[m][n]他的结果是怎么来的问题,由于限定只能往右或者往下走,所以这个格子的走法无非是 从(m,n-1)和(m-1,n)走过来两种,只要把这两个状态的结果相加就是当前总的走法了。

解法

复杂度应该是O(m*n),做的时候在左侧和上侧加了个0边便于计算

 

LeetCode 278. First Bad Version

做点简单的题目练练手,最近天天在写Scope脚本,都快忘记怎么写其他代码了。

吐槽一下垃圾长城宽带,上LeetCode都要自己开代理,不然根本加载不了

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

分析

这其实就是个变种的二分查找,只要注意找到一个bad version的时候,往前多看一个版本就能决定是否要继续二分下去了。

代码

 

Spring MVC POST FormData乱码问题(不使用web.xml)

在使用jQuery ajax一个FormData的时候(我要同时传文件和数据,所以用了FormData),发现上传的表单数据里,中文都是乱码。查到的结果就是说Servlet在没有读到ContentType的时候,会默认使用ISO-8859-1编码。具体原因可以参考《Spring MVC的Post请求参数中文乱码的原因&处理

Web.xml上添加Filter有个等效的Java写法,我的项目里没有web.xml配置文件:)

其实就是在extends AbstractAnnotationConfigDispatcherServletInitializer的时候override一个方法

然后就好了,很方便

LEOPOLD FC660m Mac OS X Karabiner键位修改文件(private.xml)

很惭愧,就做了一点微小的工作,谢谢大家。

——你懂得

先后尝试minila和fc660m,感觉还是喜欢大空格和大右Shift,而且白色更好看哈哈哈!

660m对OS X的兼容性不如minila,不过既然有了Karabiner,基本就没问题了。

主要修改了空格键右侧的两个按键,正确对应到command和option了,

右上角的Insert减默认是映射到了Help按键,我本来是想改成Insert的,结果似乎改不好(不知道有没有高手说下为啥),只能作罢改成~`这个按钮了(就是原本在1字左边那个),这样Chrome底下切换窗口也方便了。

屏幕快照 2016-06-04 下午4.23.04

文件下载:http://pan.baidu.com/s/1mhFr3FM