Javac Terminal Utf-8 Encoding

OS X 的terminal输出信息是utf-8编码的，

但是javac默认输出GBK，会导致乱码。

可以用javac -J-Dfile.encoding=UTF-8来使其输出utf-8编码的信息。

解决方案:

1

echo "alias javac='javac -J-Dfile.encoding=UTF-8 '">>~/.bash_profile

Reference

解决javac和java命令在Mac OSX终端里的乱码问题

Sublime Text 2 使用中文路径

文件是中文路径的话，使用build system不能正常工作。

解决方法：

在OS X上，

1

subl /Applications/Sublime\ Text\ 2.app/Contents/MacOS/sublime_plugin.py

在文件末尾添加两行代码，

1
2

reload(sys) 
sys.setdefaultencoding('utf-8')

各种排序算法

这篇东西其实是当时为了找实习而复习排序弄的，面试官无聊就喜欢问你个排序，如果你连插入排序跟选择排序都分不清楚的话还是别去找虐了。

几种排序

大致按算法难度、类型从上到下排。

算法描述都按升序排序，复杂度都指平均复杂度。

  • 冒泡排序

    模拟气泡浮上来的过程，n-1趟float，时间复杂度O( n2 )

  • 选择排序，一般指简单选择排序

    每次在无序区中选择出最大的元素，然后放到有序区跟无序区间，n-1趟，时间复杂度O( n2 )

  • 插入排序，一般指直接插入排序，还有折半插入排序、2-路插入排序、表插入排序等

    本质：元素插入到有序列。

    左边有序区，右边无序区（待排），每次将无序区最左边的元素插入到有序区中合适的位置（故涉及到元素的右移），n-1次，时间复杂度O( n2 )

  • 希尔排序，对直接插入排序的改进

    简单来说，就是取不同步长，进行多次插入排序，最后步长为1，就是以此直接插入排序。重点在于步长的选择，原始版本步长为n/( 2i )，最坏复杂度O( n2 )。现在最好的步长可以达到O( n(logn)2 )，仅次于O(nlogn)的排序。

    可以想象成取不同的行宽，按列进行插入排序。

    当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。

  • 基数排序

    这篇文章的唯一一个非比较型排序算法。基数（Radix），即数的进制。之所以能够不进行比较，是因为它按数位将数分配到Radix个桶中，再顺序进行收集。

    有LSD（Least significant digital）、MSD（Most significant digital）两种方式。需要进行k(数据中最大位数)趟，每趟分配要O(n)，收集要O(radix)，所以总复杂度O(k(n+radix))。

  • 归并排序，一般指2-路归并排序，还有非递归归并排序、自然归并排序等。

    本质：分治，有序列合并。

    二分需要O(logn)，合并需要O(n)，总时间复杂度O(nlogn)。需要O(n)的额外空间，用于存放合并有序列的临时结果。

  • 快速排序

    本质：分治，Patition。

    难点在于Patition，要做到O(n)的时间复杂度。简单来说，就是选最左边的作为pivot，并维护值，然后两个指针，从右往左扫，从左往右扫，遇到不合适的，则换到另一边。直到两个指针相遇。

    总平均时间复杂度O(nlogn)。

  • 堆排序

    本质：堆（分治）

    升序排列的话需要借助大顶堆，涉及max_heapify、sift_down两个子操作。其中sift_down类似直接插入排序中的数组右移。

    其实说白了就是二叉堆上的插入排序。

归类

冒泡、选择、插入，都可以认为是将元素划分为有序区、无序区，都要n-1趟处理（无序区拓展到有序区），时间复杂度都是O( n2 )。

希尔，实现起来很简单，采用最佳步长的话，复杂度可以达到O( n(logn)2 )，仅次于O(nlogn)的排序。而且插入排序在元素基本有序的情况下时间复杂度接近O(n)。在一些情况下还是很有优势的。

基数，非比较型排序算法，类似的还有桶排序等。在数据有一定限制（比如都在0~1000间），数据量很大（比较型算法最快也要O(nlogn)）的情况下，可以考虑非比较型算法，可以O(n)完成。

归并、快速、堆排，都应用了分治思想，平均复杂度都是O(nlogn)。这也是基于比较的排序算法的极限了。

具体实现

我希望用最简洁的代码实现算法。

因为面试一般不让写伪代码，而且是在纸上写，所以我就不用宏定义写得标准一点了。

Ps. 我原来写swap是这样写，inline int swap(int &x, int &y) { x^=y; y^=x; x^=y; }，结果被坑了，why？试想x、y地址一样的话…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
using namespace std;
inline int swap(int &x, int &y) { int t = x; x = y; y = t; }
inline int max(int x, int y) { return (x>y)? x: y; }
inline int min(int x, int y) { return (x<y)? x: y; }
#define bug(s) cout<<#s<<"="<<s<<" "

// 冒泡，O(n^2)
void bubble_sort(int *a, int n) {
    for(int k=0; k<n-1; k++) {
        for(int i = 0; i<n-1-k; i++) {
            if(a[i]>a[i+1])
                swap(a[i], a[i+1]);
        }
    }
}

// 简单选择，O(n^2)
void selection_sort(int *a, int n) {
    for(int k=0; k<n-1; k++) {
        int maxi = 0;
        for(int i=1; i<n-k; i++) {
            if(a[maxi] < a[i])
                maxi = i;
        }
        swap(a[maxi], a[n-1-k]);
    }
}

// 直接插入，O(n^2)
void insert_sort(int *a, int n) {
    for(int i=1, j; i<n; i++) {
        int t = a[i];
        for(j=i-1; j>=0 && a[j]>t; j--) a[j+1] = a[j];
        a[j+1] = t;
    }
}

// 希尔，O(n^2)
void shell_sort(int *a, int n) {
    for(int gap = n/2; gap>0; gap/=2) {
        for(int i=gap, j; i<n; i++) {
            int t = a[i];
            for(j=i-gap; j>=0 && a[j]>t; j-=gap) a[j+gap] = a[j];
            a[j+gap] = t;
        }
    }
}

// 基数，O(k*(n+r))，假设radix=10, k=5
void radix_sort(int *a, int n) {
    list<int> l[10];
    int r = 10, k = 5;
    for(int i=0, e=1; i<k; i++, e*=10) {
        for(int j=0; j<n; j++) {
            l[a[j]/e%10].push_back(a[j]);
        }
        for(int j=0, m=0; j<r; j++) {
            while(!l[j].empty()) {
                a[m++] = l[j].front();
                l[j].pop_front();
            }
        }
    }
}

// 归并，O(nlog(n))
void merge(int *a, int l, int mid, int r, int *t) {
    int i, j, c = 0;
    for(i=l, j=mid+1; i<=mid && j<=r;) {
        if(a[i]<a[j]) t[c++] = a[i++];
        else t[c++] = a[j++];
    }
    while(i<=mid) t[c++] = a[i++];
    while(j<=r) t[c++] = a[j++];
    for(c=0; c<r-l+1; c++) a[l+c] = t[c];
}
void m_sort(int *a, int l, int r, int *t) {
    if(l<r) {
        int mid = (l+r)>>1;
        m_sort(a, l, mid, t);
        m_sort(a, mid+1, r, t);
        merge(a, l, mid, r, t);
    }
}
void merge_sort(int *a, int n) {
    int *t = (int*)malloc(sizeof(int)*n);   // 统一用一个临时空间
    m_sort(a, 0, n-1, t);
    free(t);
}

// 快速排序，O(nlogn)
int patition(int *a, int l, int r) {
    int t = a[l];   //pivot
    while(l<r) {
        while(l<r && a[r]>=t) r--;
        a[l] = a[r];
        while(l<r && a[l]<=t) l++;
        a[r] = a[l];
    }
    a[l] = t;
    return l;
}
void q_sort(int *a, int l, int r) {
    if(l<r) {
        int q = patition(a, l, r);
        q_sort(a, l, q-1);
        q_sort(a, q+1, r);
    }
}
void quick_sort(int *a, int n) {
    q_sort(a, 0, n-1);
}

// 堆排序，O(nlogn)
#define lson(e) (e)<<1|1
void sift_down(int *a, int n, int i) {  // 类似直接插入排序的sift
    int t = a[i];
    for(int j=lson(i); j<n; i=j, j=lson(i)) {
        if(j+1<n && a[j]<a[j+1]) j++;   // 取较大的节点
        if(t>a[j]) break;
        a[i] = a[j];
    }
    a[i] = t;
}
void max_heapify(int *a, int n) {
    for(int i=n/2-1; i>=0; i--) {
        sift_down(a, n, i);
    }
}
void heap_sort(int *a, int n) {
    max_heapify(a, n);
    for(int i=n-1; i>=1; i--) {
        swap(a[0], a[i]);
        sift_down(a, i, 0);
    }
}

int main() {
    int a[] = {5,4,3,1,6,8,9,16,15};
    int n = sizeof(a)/sizeof(a[0]);
    // bubble_sort(a, n);
    // selection_sort(a, n);
    // insert_sort(a, n);
    // shell_sort(a, n);
    // radix_sort(a, n);
    // merge_sort(a, n);
    // quick_sort(a, n);
    heap_sort(a, n);
    for(int i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    // 1 3 4 5 6 8 9 15 16
}

Prolog语言

Not Finished yet

选了个人工智能的选修，教的是prolog（为啥不教lisp..）

prolog好老了，看了下介绍，貌似是种描述型语言，不带流程控制，依靠数据间的关系（逻辑），自动进行推理（所谓智能）。

语言基本内容

项

语句

只有三种语句，事实、规则、问题（目标）。 语句都要用点(.)结束。

基本就是离散数学里的数理逻辑部分那个意思，前提、产生式、结论。

Prolog语言是一种以一阶谓词为基础的逻辑性语言（Programming in logic）。

从命题逻辑，到谓词逻辑（加入谓词、量词）形成一阶逻辑系统。回想了下，数理逻辑好像很厉害的样子，不过学完了也记不得多少理论的东西了…

事实

格式：P. （P表示一个谓词公式，即<谓词名>(<项表>)） 含义：无条件成立，恒为真 eg. like(monkey, banana)

规则

格式：P :- P1, P2, …, Pn. （:- 表示 蕴含，即->，,表示 合取/与，及） 含义：若P1, …,Pn均为真，P为真

问题（目标）

格式：Q1,Q2,…Qm. 含义：待回答的问题，即Q1,…Qm同时为真吗？

表

谓词

后续

Ps.由于课没去过几次，今天看ppt发现课上讲的是Turbo Prolog（呵呵..我说咋差这么大呢），Wiki上说

Visual Prolog, formerly known as PDC Prolog and Turbo Prolog, is a strongly typed object-oriented dialect of Prolog, which is very different from standard Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm PDC (Prolog Development Center) that originally produced it.

Prolog好几种方言啊，咱还是用GNU吧（找到个for OS X的IDE）。

你在为自己战斗 

你懂么？
没什么好愧疚的，你只是在为自己战斗而已。
总会受伤。
你会继续前进，
因为你是在为自己战斗。

唯心主义，
你只相信你所感受到的。
所以你的心情能决定一切。
这种人是能无敌，
还是走向毁灭，
一念之间而已。

你真是个奇葩。
哦，这我已经习惯了。

没事，
你只要学会控制你的情绪就可以了。
而关键在于，
你要放下压力。
压力源于何处？
绝对不是来自本身，而是别人。
所以你应该放下你所承担的，
别人要求的，或是自己认为的。

没有压力，没有畏惧，你便无敌。

也许这是对的。
你只需在心中默念，
输也是我，
赢也是我，
我有什么好怕的。
我是我，
里外保持一致的我，
各种维度一致的我。

人应当这样纯粹。

. . .

你不懂我在说什么？
其实我也不懂。。。

2012微软编程之美全国挑战赛回顾

今天MSTC的人突然说要采访往届参赛选手，囧，都过去快一年了，回忆下。。

2012编程之美是MSRA举办的，分为初赛跟决赛。 初赛比的是AI对战，北航的MSTC做的海战游戏并提供了3种不同语言的SDK，海选，网上提交代码。 决赛取64名，地点在北京海淀的微软大厦，比的是工程类题目，解决问题，Topic是“大数据可视化”，形式是结对编程，2天时间。当时是3个题目任选，我选的是“字云”。决赛没比好，时间不够，没入围10强。

要说比赛让我收获了什么：

  • 初赛是写AI，以前完全没接触过的东西。涉及到一些状态机理论，计算几何，数学建模（根据各种伤害公式等），以求得到一个最优化的AI策略。还是非常有意思的。
  • 决赛是“大数据可视化”，当时我们是用C#/WPF写（其实当时真是各种不会，现在再考虑这个问题脑中蹦出的解决方案就多很多了），本来是想用Siverlight（我当时技术特征纯MS…）因为什么东西卡住又换到WPF了。除去通过工程技术方面的摸索得到的收获，还有两点是我比较重视的。一个是“结对编程”，引入了Team Work的因素，锻炼了与人交流、项目分工等等的能力。那种背靠背相互依赖的感觉真的让人很享受。另一个就是“马拉松式”的编程，只给我们2天时间（其实除去吃饭睡觉时间远远不到，大概就2x8小时），那种紧张感，抓到一个想法就拼命coding，很迷人。。（其实我喜欢ACM也有这部分原因，可以高频率敲击键盘。。）

。。。就这样吧，最后放上一张图，在那个什么Sky Garden拍的，话说微软的楼确实不错。。 编程之美北京

Vim学习笔记（四）- 插件篇

主要是根据前辈的一篇博文，谁说Vim不是IDE？（三）写的，自己实践整理的一个记录。

下一步计划是消化这两篇：

1.谁说Vim不是IDE？（四）

2.Maple’s Vim config

先是熟悉ctags，然后把vim搞成IDE，完善自己的.vimrc。

pathogen

通过管理runtimepath来简化插件安装、运行时的文件，使其能位于自己自定义目录（默认为 bundle）下。

项目位于github

插件安装

1、执行

1
2
3

mkdir -p ~/.vim/autoload ~/.vim/bundle; \
curl -Sso ~/.vim/autoload/pathogen.vim \
    https://raw.github.com/tpope/vim-pathogen/master/autoload/pathogen.vim

2、在 .vimrc 中增加代码

1

call pathogen#infect()

Command-T

用于在一个给定目录下快速定位文件，Go To File的功能。

插件安装

1、下载

command-t-1.4.vba

2、安装至bundle目录下

1

mkdir ~/.vim/bundle/command-t

1

vim command-t-1.4.vba

执行 :UseVimball ~/.vim/bundle/command-t

3、编译C扩展

1
2
3

cd ~/.vim/bundle/command-t/ruby/command-t
ruby extconf.rb
make

Powerline

一个增强的窗口状态栏。

插件安装

1、安装到bundle

1
2

cd ~/.vim/bundle
git clone git://github.com/Lokaltog/vim-powerline.git

2、安装字体

安装一些 vim-powerline patched fonts，我用的是Menlo，然后安装到系统

3、在.vimrc中设置状态栏主题

1
2
3
4
5
6
7

"powerline{
"set guifont=PowerlineSymbols\ for\ Powerline
set guifont=Menlo\ for\ Powerline
set nocompatible
set t_Co=256
let g:Powerline_symbols = 'fancy'
"}

Vim学习笔记（三）

这次主要是一些跟窗口有关的操作。

Vim窗口操作

分割窗口

1.打开已有文件

:split - 水平分，可以简写成 sp

:vsplit - 垂直分，可简写成 vs

2.新建文件

:new+{name} - 水平新建窗口，name为文件名

:vnew+{name} - 垂直

选择窗口

ctil+w {h|j|k|l} 上下左右切换窗口

比较文件

:diffsplit {filename} - 对{filename}开一个新窗口，并比较。同vimdiff命令。

:diffpatch {patchfile} - 给当前buffer打上{patchfile}补丁后显示。

:diffthis - 使当前窗口加入diff。

就是这样

其实这些话是前段时间写的，但是…我有拖延症嘛…

就是这样
觉得什么都能做
却什么都不做
其实事实上你不做你怎么知道自己能做
不做是因为没有激情
没有激情是因为不知道自己到底想要什么
觉得自己什么都能做，而做什么都好像没有意义
哎
我是如此地了解自己，又如此地不了解自己

5Lmf6K645oiR5LiN54ix5L2g

NUxtZjZLNjQ1b2lSNUxpTjU0aXg1TDJnNzd5TTVMbWY2SzY0NW9pUjVZK3E1cGl2NWErQzVhK2U0NENDQ3VhVm1lYUlrZSs4ak9hQWp1UzVpT1M0amVhRHMrUzlvT09BZ2c9PQ==