常用的排序算法

排序是最基本的算法,面试中可能都不直接考,但经常涉及到排序算法的变种

我尝试了下自己手写,发现全部写对,困难不小。

头文件,习惯性将常用的头文件都加入进去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <deque>
#include <map>
#include <stack>
#include <time.h>
#include <fstream>
using namespace std;
const int maxn=100000;

Read More

C++的黑科技

周二面了腾讯,之前只投了TST内推,貌似就是TST面试了

其中有一个问题,“如何产生一个不能被继承的类”,这道题我反反复复只想到,将父类的构造函数私有,让子类不能调用,最后归结出一个单例模式,但面试官说,单例模式作为此题的解答不够灵活,后来面试官提示说,可以用友元+虚继承,可以完美实现这样一个类

当然那时我还不太明白,友元与虚继承我都极少接触过,只是知道有这些东西,回头搜了一下“不能被继承的类”的做法,具体如下:

Read More

转载 linux下打开windows txt文件中文乱码问题

原文链接

在linux操作系统下,我们有时打开在windows下的txt文件,发现在windows下能正常显示的txt文件出现了中文乱码。

出现这种情况的原因为两种操作系统的中文压缩方式不同,在windows环境中中文压缩一般为gbk,而在linux环境中为utf8,这就导致了在windows下能正常显示
txt文件在linux环境下打开呈现了乱码状态。

解决方法:在linux用iconv命令,如乱码文件名为shujujiegou.txt,那么在终端输入如下命令:

1
iconv -f gbk -t utf8 shujujiegou.txt > shujujiegou.txt.utf8

访问Google及Gmail的host IP

目前测试能用的host IP

截止2014-07-16

1
2
3
4
5
6
7
8
173.194.64.84 accounts.google.com
173.194.64.84 www.google.com
173.194.64.84 mail.google.com
173.194.64.84 www.google.com.hk
173.194.64.84 www.l.google.com
173.194.64.84 accounts.google.com.hk
74.125.224.197 adwords.google.com
209.116.186.221 plus.google.com

Hello, Hexo! Goodbye, Octopress!

最终,从Octopress迁移到Hexo

Octopress有些缺点,让我一直很难以忍受,虽然感觉很Geek,但内心里一直想找个可以代替它的,这些所谓的缺点,事实上大部分都是由于前端引起的,我不是个前端程序员,我不会设计漂亮的前端页面,但我也有自己的品味,不想将就。

先说说我对Octopress的不满:

  • 字体太大,仿佛所有用Octopress框架的,字体都不小,虽然可以调,但调完后在这个框架里又没那么好看了

  • Tags或Tag Cloud都太丑,我只能勉强看懂这些CSS,这是从github上面用的其它开源插件

  • 所有第三方主题,我都认真看了一遍,我居然没有找到一款符合我口味的。

  • 右边的SideBar太难看

Read More

二分查找

在微博上看到一篇文章,关于二分查找:当我写二分查找时,我想些什么

于是想到刚看过的《编程珠玑》上的一句话,“90%的人无法正确写出二分查找”

自己动手:

int BinarySearch(int A[], int n, int target)
{
    int left=0, right=n-1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(A[mid] == target) return mid;
        if(target > A[mid]) left=mid+1;
        else right=mid-1;
    }
    return -1;
}

写完了后,去看这篇文章的答案,发现有很多问题,果然也属于那“90%”。

Read More

点集的一些几何特征

点集有很多特征,这里提到的有:最小凸包,最小外接矩形,最大内接三角形,最大内接四边形。

编程里面,如何求取点集的这些特征呢?

预处理知识

  • 对于三个点,p0,p1,p2,如何判断以p0为中心,p0p1到p0p2是顺时针还是逆时针?

求向量p0p2与p0p1的叉积,若大于0,则说明是p0p2在p0p1的顺时针方向,若小于0,则说明p0p2在p0p1的逆时针方向。

Read More