## Tuesday, January 29, 2013

### [leetcode] Generate Parentheses

Problem:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example:
n=1: "()"
n=2: "()()","(())"
n=3: "((()))","()(())","()()()","(()())","(())()"
...
While this problem seems familiar to me, I didn't have good solutions at first glance. Then my first step was to observe more examples and tried to find some patterns.

Let [n] indicates all well-formed combinations of number n. Then it was not difficult to find out that we had the following patters:
[n] = { "(" + [n-1] + ")"  , [1][n-1], [2][n-2], ...., [n-2][2], [n-1][1] }
where [m][n] indicates the cartesian product of two sets.
e.g. [2][2] =  { "()()","(())" } x { "()()","(())" }
= { "()()()()","()()(())","(())()()","()()()()" }
As we can see, there will be duplicates of the product, so I use the Set container in java to avoid duplicates.

Then the main idea is to iterate from 1 to n. When calculate k, we can use the previous [1..k-1] results to generate the results of k.
```public class GenerateParentheses {
public ArrayList<String> generateParenthesis(int n) {

ArrayList<Set<String>> list = new ArrayList<Set<String>>();

int number=1;

while (number<=n){
Set<String> parentheses = new HashSet();
//generate combinations of pattern "("+[number-1]+")"
generateParentheses(number,list,parentheses);
//generate combinations of pattern [1][number-1],[2][number-2],...[number-1][1]
for(int i=1;i<number;i++){
int leftIndex=i-1;
int rightIndex=number-i-1;
for(String left:list.get(leftIndex)){
for(String right:list.get(rightIndex)){
}
}
}
//add results of this number and go on.
number++;
}
//add the elements to list required by OJ.
ArrayList<String> result = new ArrayList<String>();
Iterator<String> it = list.get(list.size()-1).iterator();
while(it.hasNext())
return result;
}

private void generateParentheses(int number,ArrayList<Set<String>> list,Set<String> parentheses){
if(number==1){
return;
}
StringBuilder sb = new StringBuilder();
for(String s:list.get(number-2)){
sb.append("(");
sb.append(s);
sb.append(")");
sb.setLength(0);
}
}
}```

I know...The code looks messy and kind of crazy with 4-nested loops.
After surfing online and discussed with others, I have a much better solution with the idea that is much easier to illustrate.

When the parameter is n, we are going to have n left parenthesis and n right parenthesis. We can add either "(" or ")" to current constructed string (initially empty string), but with some constrains:
1. No. of left parenthesis "(" much be less or equal to n.
2. Certainly, right parenthesis ")" need to be <= n, but also need to be <= no. of  "(".
Based this point, we can easily get a recursive approach :
```public class GenerateParentheis {
ArrayList<String> list;

public ArrayList<String> generateParenthesis(int n) {
list = new ArrayList<String>();
generateParenthesis("",0,0,n);
return list;
}

private void generateParenthesis(String s,int left,int right,int n){
if(left==n && right==n){
return;
}
if(left<n)
generateParenthesis(s+"(",left+1,right,n);
if(right<left)
generateParenthesis(s+")",left,right+1,n);
}
}
```

Even More
There're many problems that looks totally different at first glance, but are the same in nature.
The key in called Catalan Number. The n th Catalan number is 1/(n+1) * C(2n, n).
So when n=3, we can get Catalan number = 5, which is the total number of well-formed parenthesis combinations when n=3.

## Saturday, January 26, 2013

### Some Powerful Shell Commands

Original article at coolshell

• `!\$!\$是一个特殊的环境变量，它代表了上一个命令的最后一个字符串。如：你可能会这样：\$mkdir mydir\$mv mydir yourdir\$cd yourdir可以改成：\$mkdir mydir\$mv !\$ yourdir\$cd !\$`
• `sudo !!`
以root的身份执行上一条命令 。
场景举例：比如Ubuntu里用`apt-get`安装软件包的时候是需要root身份的，我们经常会忘记在`apt-get`前加`sudo`。每次不得不加上`sudo`再重新键入这行命令，这时可以很方便的用`sudo !!`完事。
（注：在shell下，有时候你会输入很长的命令，你可以使用!xxx来重复最近的一次命令，比如，你以前输入过，vi /where/the/file/is, 下次你可以使用 !vi 重得上次最近一次的vi命令。）
• `cd –`
回到上一次的目录 。
场景举例：当前目录为`/home/a`，用`cd ../b`切换到`/home/b`。这时可以通过反复执行`cd –`命令在`/home/a``/home/b`之间来回方便的切换。
• ‘ALT+.’ or ‘<ESC> .’
热建alt+. 或 esc+. 可以把上次命令行的参数给重复出来。
• `^old^new`
替换前一条命令里的部分字符串。
场景：`echo "wanderful"`，其实是想输出`echo "wonderful"`。只需要`^a^o`就行了，对很长的命令的错误拼写有很大的帮助。（也可以使用 !!:gs/old/new
• du -s * | sort -n | tail
列出当前目录里最大的10个文件。
• :w !sudo tee %
在vi中保存一个只有root可以写的文件
• date -d@1234567890
时间截转时间
• > file.txt
创建一个空文件，比touch短。
• mtr coolshell.cn
mtr命令比traceroute要好。
• 在命令行前加空格，该命令不会进入history里。
• echo “ls -l” | at midnight
在某个时间运行某个命令。
• curl -u user:pass -d status=”Tweeting from the shell” http://twitter.com/statuses/update.xml
• curl -u username –silent “https://mail.google.com/mail/feed/atom” | perl -ne ‘print “\t” if /<name>/; print “\$2\n” if /<(title|name)>(.*)<\/\1>/;’
检查你的gmail未读邮件
• ps aux | sort -nk +4 | tail
列出头十个最耗内存的进程
• `man ascii`
显示ascii码表。
场景：忘记ascii码表的时候还需要google么?尤其在天朝网络如此“顺畅”的情况下，就更麻烦在GWF多应用一次规则了，直接用本地的`man ascii`吧。
• `ctrl-x e`
快速启动你的默认编辑器（由变量\$EDITOR设置）。
• `netstat –tlnp`
列出本机进程监听的端口号。（netstat -anop 可以显示侦听在这个端口号的进程）
• `tail -f /path/to/file.log | sed '/^Finished: SUCCESS\$/ q'`
当file.log里出现Finished: SUCCESS时候就退出tail，这个命令用于实时监控并过滤log是否出现了某条记录。
• `ssh user@server bash < /path/to/local/script.sh`
在远程机器上运行一段脚本。这条命令最大的好处就是不用把脚本拷到远程机器上。
• ssh user@host cat /path/to/remotefile | diff /path/to/localfile -
比较一个远程文件和一个本地文件
远程关闭一台Windows的机器
• `screen -d -m -S some_name ping my_router`
后台运行一段不终止的程序，并可以随时查看它的状态。`-d -m`参数启动“分离”模式，`-S`指定了一个session的标识。可以通过`-R`命令来重新“挂载”一个标识的session。更多细节请参考screen用法 `man screen`
• `wget --random-wait -r -p -e robots=off -U mozilla http://www.example.com`
下载整个www.example.com网站。（注：别太过分，大部分网站都有防爬功能了：））
• `curl ifconfig.me`
当你的机器在内网的时候，可以通过这个命令查看外网的IP。
• convert input.png -gravity NorthWest -background transparent -extent 720×200  output.png
改一下图片的大小尺寸
• `lsof –i`
实时查看本机网络服务的活动状态。
vim一个远程文件
• `python -m SimpleHTTPServer`
一句话实现一个HTTP服务，把当前目录设为HTTP服务目录，可以通过`http://localhost:8000`访问 这也许是这个星球上最简单的HTTP服务器的实现了。
• `history | awk '{CMD[\$2]++;count++;} END { for (a in CMD )print CMD[a] " " CMD[a]/count*100 "% " a }' | grep -v "./" | column -c3 -s " " -t | sort -nr | nl | head -n10`
(有点复杂了，history|awk ‘{print \$2}’|awk ‘BEGIN {FS=”|”} {print \$1}’|sort|uniq -c|sort -rn|head -10)
这行脚本能输出你最常用的十条命令，由此甚至可以洞察你是一个什么类型的程序员。
• tr -c “[:digit:]” ” ” < /dev/urandom | dd cbs=\$COLUMNS conv=unblock | GREP_COLOR=”1;32″ grep –color “[^ ]“
想看看Marix的屏幕效果吗？（不是很像，但也很Cool!）

## Friday, January 25, 2013

### From 韩寒

-- 韩寒 《春萍，我做到了》

## Wednesday, January 23, 2013

### Majority Vote Algorithm with Linear Time & Constant Space

I saw a problem on some certain forum days ago:
Design an algorithm that, given a list of N elements in an array, finds all the elements that appear more that n/3 times in linear time and using constant space only.

Well, another constant space problem. Without this constrain, we can easily achieve an linear time algorithm by using a hashmap or just another array.
I didn't have good solutions. And then I searched online, and found that there was a particular name for this problem: Majority Vote. And there's a neat algorithm here .

While this algorithm seemed not that straightforward to me at first, the idea behind it was quite simple:
The majority ( if there exists ) will remain the same when we delete 3 different elements from list each time, taking the problem I stated at first as the example.

### Untitled

After all these years, there's only you still being on my side.
Thank you, Amanda.