superlayone

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

时间复杂度为O(n),n代表链表总节点数

	/**
	 * Definition for singly-linked list.
	 * struct ListNode {

superlayone

最长递增子序列 (Longest Increasing Subsequence)

假设存在一个序列data[9] ={ 2，1 ，5 ，3 ，6，4， 8 ，9， 7}，可以看出来它的LIS长度为5。

我们定义一个序列b，然后逐个考察这个序列。 此外，我们用一个变量Len来记录现在最长算到多少了

首先，把data[1]有序地放到b里，令b[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1

然后，把data[2]有序地放到b里，令b[1] = 1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，这时Len=1

superlayone

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

中序遍历BST，设置一个prev指针，记录当前节点中序遍历时的前节点，如果当前节点大于prev节点的值，说明需要调整次序。用一个pair保存prev和cur

superlayone

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

思路

superlayone

##Divide Two Integers

不使用乘法、除法以及取余操作对两个数执行除法操作

思路

a/b=exp( log(a/b) )=exp( log(a) - log(b) )

superlayone

##UNIX路径简化

今天做了一道比较有意思的题目，处理UNIX路径的字符串操作。

path = "/home/", => "/home"

path = "/a/./b/../../c/", => "/c"

路径中/表示根，.表示当前目录，..表示父级目录

superlayone

Add UAC and Set Hostname UUID

标签（空格分隔）： UAC Hostname UniqueName

---

####This code snap add a UAC privilege to .bat files

REM This batfile just add a UAC auth to .bat
reg add "HKEY_CLASSES_ROOT\batfile\shell\open" /v HasLUAShield /t REG_SZ

superlayone

C++ Singleton

前一段时间面试豌豆荚的一道题，今天参见网上的一些博客，加上自己的理解写了一个觉得比较符合面试官当时意愿的Singleton

1. Singleton模板

Singleton.h 采用模板机制，使用产生确定类型的singleton类。 顺便说一下比较混淆的类模板和模板类。类模板首先是模板，用于产生类；而模板类是由这些类模板产生的类。比如：

superlayone

##继续来写一个自认为比较完美的atoi版本

直接上代码，关键点在处理溢出的地方！另外优化了判断的逻辑

    int StrToInt(const char* str)
    {
    	int n = 0;
    	int sign = 1;
    	int c;

superlayone

##KMP match

KMP算法的关键在于求算next[]数组的值，即求算模式串每个位置处的最长后缀与前缀相同的长度， 而求算next[]数组的值有两种思路，第一种思路是用递推的思想去求算，还有一种就是直接去求解(略)。

递推:

• 根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
• 若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1
• 若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移动，显然k=next[k]