翻墙技巧:使用AWS搭建自己的VPN

翻墙,一直是个让大家头疼的问题。网上各种免费、收费VPN良莠不齐,时好时坏。如果VPN在你最需要的时候掉链子,着实令人沮丧。今天,我们自己动手丰衣足食,来搭建自己的VPN。

 

  1. 首先要有一个AWS(http://aws.amazon.com)账号,可免费注册。
  2. 创建一个EC2 instance,这里使用的是AWS自带的Ubuntu AMI,type是t2.micro(该type前12个月免费)。不需要进行特别设置,直接启动即可。如果之前没有创建过私钥,请创建一个用于SSH连接。
  3. 使用SSH连接到该instance (地址就是控制面板中的public DNS)。这里使用的Ubuntu AMI的用户名是ubuntu。 
  4. 输入以下命令,获得root权限

    sudo -s 
  5. 安装pptp

    apt-get update
    aptitude install pptpd
  6. 编辑pptp配置文件

    sudo vim /etc/pptpd.conf

    在最后一行添加以下代码

    localip 192.168.240.1
    remoteip 192.168.240.2-9
  7. 编辑pptpd-options,配置DNS

    sudo vim /etc/ppp/pptpd-options

    找到包含ms-dns的行,删除注释。这里我们使用Google Public DNS,修改为

    ms-dns 8.8.8.8
    ms-dns 8.8.4.4
  8. 配置VPN的用户名和密码。将USERNAME和PASSWORD改为自己的用户名和密码,运行以下命令

    echo "USERNAME pptpd PASSWORD *" | sudo tee -a /etc/ppp/chap-secrets
  9. 重启pptp服务

    sudo /etc/init.d/pptpd restart
  10. 配置数据转发

    sudo vim /etc/sysctl.conf

    将下面一行的注释去掉

    net.ipv4.ip_forward=1
  11. 运行以下命令,重新加载

    sudo sysctl -p
  12. 修改iptables,设置网络地址转换

    sudo iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

    编辑rc.local设置开机自动运行

    sudo vim /etc/rc.local

    在exit 0上面加一行

    iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
  13. 重启pptp服务

    sudo /etc/init.d/pptpd restart
  14. 最后进入AWS EC2的控制台,新建一个security group (Security Groups面板 – Create Security Group)。姑且将名称设置为VPN(任意名称都可以)。将inbound和outbound都设置为

    All TCP, TCP, 0-65535 0.0.0.0/0

    All UDP, UDP, 0-65535 0.0.0.0/0

    All IMCP, All, N/A 0.0.0.0/0

  15. 将刚才设置了pptpd的EC2 instance的security group设置为VPN或者你自己起的名字 (Instances面板 – 选中相应的instance – Actions – Networking – Change Security Groups)
    到此我们的VPN服务器就可以用了。

  16. 在自己的电脑上设置VPN,输入刚才的public DNS,自己设置的用户名和密码。不同的系统设置方法也不同,这里不再详细说明。

 

LeetCode #274 H-Index

题目:

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the otherN − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

 

分析:

方法一:

O(nlogn)时间,O(1)空间。
现将数组排序。然后从大到小遍历,一边计数一边比较计数与当前的引用数,直到计数大于引用数。

阅读全文

LeetCode #221 Maximal Square

题目:

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

 

分析:

已知一个矩阵,其中的元素要么是0要么是1。求全部由1构成的最大正方形的面积。

本题可以使用动态规划解决。声明一个二维数组state,其中的每个元素的值为以该位置为右下角的最大正方形的边长。每加入一个新的元素,可以在它上方、左方、左上方3个已有正方形的基础上构成一个新的正方形。

阅读全文

经典动态规划问题:最长递增子序列(LIS)

问题

给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1, 2, 8},则其最长的单调递增子序列为{5,6,7,8},长度为4.

 

解法1:最长公共子序列法

这个问题可以转换为最长公共子序列问题。如例子中的数组A{5,6, 7, 1, 2, 8},则我们排序该数组得到数组A‘{1, 2, 5, 6, 7, 8},然后找出数组A和A’的最长公共子序列即可。显然这里最长公共子序列为{5, 6, 7, 8},也就是原数组A最长递增子序列。最长公共子序列算法在算法导论上有详细讲解,这里简略说下思想。

假定两个序列为X={x1, x2, …, xm}和Y={y1, y2, …, yn),并设Z={z1, z2, …, zk}为X和Y的任意一个LCS。

阅读全文

LeetCode #268 Missing Number

题目:

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.

 

分析:

已知一个数组包含了0到n的所有整数,除了一个数不在里面。求这个缺失的数。

如果不缺这个数,根据等差数列求和公式,所有的数加起来应该等于(1 + n) * n / 2。但是现在少了某个数x,此时求和的结果应该比(1 + n) * n / 2正好少x。

注意,当n很大的时候直接计算(1 + n) * n / 2会导致溢出,因此我们采用一边加一边减的方式。

阅读全文

LeetCode #33 Search in Rotated Sorted Array

题目:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

 

分析:

在一个旋转过的有序数组中查找一个数,如果该数不存在,返回-1。

方法一:

首先通过二分查找找出数组中最小值的位置。这样我们可以将数组分成2段,使得每一段都是有序的。之后看要查找的数(target)的值落在哪一段,然后再在这一段里进行一次二分查找即可。

方法二:(推荐)

对于每一轮二分查找,中点的左侧和右侧必然有有一边是有序的。我们看看target是不是在有序的这个范围内,是的话就查这一边,不是的话就查另一边。

阅读全文

已知前序遍历、中序遍历、后序遍历结果其中之二,生成二叉树

一、已知前序遍历和中序遍历

假设我们用2个数组preorder和inorder来表示前序和中序遍历的结果。

要生成的二叉树的任意子树都对应于preorder和inorder的某个子数组。该子树的根节点对应于preorder子数组的第一个元素,然后在inorder中查找该该元素。对于inorder中的的子数组,根节点元素左侧的子数组对应左子树,右侧的子数组对应右子树。之后使用递归重复该过程。

下面给出一段Java示例代码:

阅读全文

LeetCode #134 Gas Station

题目:

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

 

分析:

在一个环线上有很多加油站。在加油站i可以加油gas[i]升,从加油站i到加油站i+1要费油cost[i]升。问从哪个加油站出发才能绕环线一圈。如果没有,则返回-1。(油箱无上限。假设每个case都有唯一解。)

乍一看,又是加油又是费油好麻烦,其实都是唬人的。简单来说就是一个变量初始值为0,从i到j要变化gas[i]-cost[i],在遍历一圈的过程中不能小于0。

随便写几个值,手动算一下,我们发现了如下规律:

阅读全文

LeetCode #131 Palindrome Partitioning

题目:

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

 

分析:

将一个字符串分割成若干子串,使得每一子串都是回文字符串。返回所有的分法。

一般回溯题,没有什么特别坑人之处。基本思路就是使用递归尝试各种可能的分割位置,使用一个List记录当前已经切下来的子串。每次切的时候判读一下刚切下来的这部分是不是回文的。

阅读全文

LeetCode #208 Implement Trie (字典树基本方法实现)

题目:

Implement a trie with insertsearch, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

 

分析:

实现字典树的insert,search,startsWith方法。

对于每个节点,使用TrieNode数组来表示字母到节点的映射关系。isWord用来记录该节点对应的字符串是不是一个单词。

阅读全文

return top