LeetCode 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language. Example 1:

Example 2:

Example 3:
Continue reading LeetCode 269. Alien Dictionary

LeetCode 611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/description/ 有点类似3Sum的题目。形成三角形的充要条件是最小两边之和大于第三边。可以先给数组排序,然后确定一个最大边,然后在它左边找另外两边。 时间复杂度是O(n*log(n) + n^2) = O(n^2)

   

LeetCode 523. Continuous Subarray Sum

https://leetcode.com/problems/continuous-subarray-sum/description/ 这道题跟https://leetcode.com/problems/subarray-sum-equals-k/description/ 其实是很像的,但本题的特点就是corner case非常多…

 

LeetCode 23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/description/ Use max heap, the time complexity is O( log(k) * N )

 

LeetCode 222. Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/description/ 简单的二分法分治,探测(子)树的左右侧是否相等即可。 (下面代码没实现)想要更快的话,其实自从第一次算出左侧的深度后,后面的左测深度直接可以通过减法求出,不用再去探测一次了。

 

Windows 下使用MinGW编译Cython

用Visual C++编译器也是可以的(找不到vcvarsall.bat可以看这篇),不过为了后面移植方便,目前的项目还是用MinGW. 步骤其实很简单,参考http://cython.readthedocs.io/en/latest/src/tutorial/appendix.html。 稍微翻译一下就是: 从这里http://www.mingw.org/wiki/HOWTO_Install_the_MinGW_GCC_Compiler_Suite 下载个MinGW Installer. 下载、安装的时候记住是32位版本的,因为64位版仍旧有些不兼容现象。 运行安装下载的程序。Cython只需要最基本的包(basic package)就行了,主要是为了里面的C++编译器 将你安装MinGW的目录设置到PATH环境变量中。默认位置应该是C:\MinGW\bin 在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会问点什么。