大二入门动态规划时，最先学得就是 LCS , LIS 和各种背包问题，后来接触二维DP和各种无厘头DP（数位DP啊，插头DP啊，状压DP啊，树状DP啊等等），以我这种智商水平，听听名字就好了。最近的算法课讲到了 DP 专题，找出了之前看的 背包九讲看了看，放出来，纪念一发当年的岁月吧。

1、更新软件并安装vim

1
2
3

sudo apt-get update
sudo apt-get upgrade
sudo apt-get install vim

2、更改 SSH 默认端口

1
2
3
4

sudo vim /etc/ssh/sshd_config
找到 Port 字段，将其修改为自己想要的端口值
sudo service ssh restart         #重启ssh服务
sudo netstat -tunlp | grep ssh   #查看ssh服务监听的端口

这里将ssh端口改成了22222，如下图（PS:不要问我为啥强行改22号端口，就是任性，额，其实有点其他用途，青大校友表示当年我就是靠这个强行免费使用校园网）：

3、安装shadowsocks-python版本

11、盛最多水的容器

双指针，算法中一个很重要的技巧，之前的三数求和就用到了双指针的技巧。

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxArea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxArea，并将指向较短线段的指针向较长线段那端移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int frontPoint = 0, endPoint = height.size()-1;
        while( frontPoint<endPoint ){
            maxArea = max( maxArea, (endPoint-frontPoint)*min(height[frontPoint], height[endPoint]) );
            if( height[frontPoint]<height[endPoint] )
                frontPoint++;
            else
                endPoint--;
        }
        return maxArea;
    }
};

谷歌coLab免费云GPU搭建教程

网上教程的链接

知乎 https://zhuanlan.zhihu.com/p/34436045

cnblogs http://www.cnblogs.com/kid551/p/8544908.html

1、注意第11步的代码替换成下列的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

!apt-get install -y -qq software-properties-common software-properties-common module-init-tools
!add-apt-repository -y ppa:alessandro-strada/ppa 2>&1 > /dev/null
!apt-get update -qq 2>&1 > /dev/null
!apt-get -y install -qq google-drive-ocamlfuse fuse

from google.colab import auth
auth.authenticate_user()

from oauth2client.client import GoogleCredentials
creds = GoogleCredentials.get_application_default()

import getpass
!google-drive-ocamlfuse -headless -id={creds.client_id} -secret={creds.client_secret} < /dev/null 2>&1 | grep URL

vcode = getpass.getpass()

!echo {vcode} | google-drive-ocamlfuse -headless -id={creds.client_id} -secret={creds.client_secret}

网上很多教程第一句中使用的是python-software-properties包，但是colab提供的操作系统是最新的18.04 ubuntu，使用该包会出错，显示E: Package 'python-software-properties' has no installation candidate。所以改成使用software-properties-common。具体的，software-properties-common 包是 python-software-properties 的备用包，当系统版本在12.04一下，使用 python-software-properties，当系统版本在12.10以上，使用software-properties-common。

2、将google云盘当成一个盘符挂载到colab上

使用 google-drive-ocamlfuse 将云盘文件夹和远程的VM链接起来，方便文件共享操作。

1
2

!mkdir -p drive
!google-drive-ocamlfuse drive

路径：\content\drive\...,后期文件操作啥的就可以与云盘交互了。

3、取消挂载

1

fusermount -u ***pathName***

注意，colab一次只能免费使用最多12小时，过期会自动释放掉之前配置的虚拟环境，那么就需要每次使用时都执行上述操作，可以将其保存成一个文件，每次使用执行一下即可。

一、Ubuntu安装及TensorFlow-Gpu安装

1、UEFI启动的ubuntu要将 \boot分区设置成 EFI分区，这样会在bios中出现启动项。注意EFI模式只识别FAT32的U盘启动盘。

2、安装 搜狗输入法

1
2
3
4
5

下载 sogou.deb
sudo dpkg -i sogou.deb       #出现安装不成功，需要依赖
sudo apt-get install -f      #安装依赖
sudo dpkg -i sogou.deb
然后在设置里按照自己的需求设置

3、设置息屏时间

4、注意一定要安装好对应的显卡版本，在 设置 >> 软件和更新 >> 附加驱动里进行选择对应的显卡驱动nvidia；命令 nvidia-smi查看GPU驱动信息。

5、安装更新 sudo apt-get update sudo apt-get install vim

6、安装 及卸载Anaconda

官网下载对应的安装包，执行命令 bash Anaconda2-4.4.0-Linux-x86_64.sh 即可进行安装，期间会选择安装路径啥的，默认即可。 安装完成后，重启 命令窗口，执行 python 命令即可看到已经安装成功。如果不成功，执行 source ~/.bashrc命令，使 bashrc生效。

卸载的话：

• 删除整个anaconda的目录 rm -rf anaconda*
• 将 ~/.bashrc文件中的关于 anaconda的行注释掉
• 生效 source ~/.bashrc

7、命令 anaconda-navigator进入图形界面的操作。其实主要还是命令行操作，下面是 conda的常用命令。注意 conda是python的环境管理工具，兼具包管理；pip只是python的包管理工具而已。

一、Divide and Conquer

　　You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values, so there are 2n values total and you may assume that no two values are the same. You’d like to determine the median of this set of 2n values, which we will define here to be the n-th　smallest value.

　　However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the kth smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible.

Give an algorithm that finds the median value using at most O(logn) queries.　　

1、problem-solving ideas and pseudo-code

首先将现实问题转化一下，变成计算机算法问题，即 找2个有序数组的并集的中位数 ，LeetCode 第四题。

(1）problem-solving ideas

求中位数需要根据数组长度是奇数还是偶数分别讨论，奇数长度时中位数为最中间的一个数，偶数长度时中位数为最中间的两个数的平均值，为了方便，可以实现一个比题目更一般化的函数，求A和B的第k小数的函数，那么中位数的问题很容易解决。

求一个有序数组的第k个数只需要O(1)的复杂度，现在有两个数组，显然花费额外空间以O(n)时间归并然后O(1)寻找不满足题目要求。既然要求log时间复杂度，一般需要使用到二分思想。

分别考虑A和B的第k/2个元素：

• 如果它们相等，则第k个数为其中的任意一个
• 如果A中的比较大，则B中前k/2个元素都不可能是第k个数了，因为这个数至少应该为A的第k/2个数，把B的前k/2去掉，然后重新寻找。
• 如果B中的比较大，则把A的前k/2个数去掉，重新寻找。

直到A和B中某个变为空时或者寻找第1个数时可以停止递归，直接找到结果。

注意，上面的k/2只是理想的简单情况，实际上A和B的长度可能不够k/2，或者k为奇数等，但这些不是主要问题，可以让A取第k/2个数字，然后A不够长，则取A的最后一个数字，然后B取剩下长度对应的那个数字，具体参考代码。

最近上课，各种机器学习，深度学习的求导公式，直接蒙圈了，一个不错的教程文档，分享一下。

1、两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> Map;
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
            Map[nums[i]] = i;
        for(int i=0; i<nums.size(); i++){
            int tmp = target - nums[i];
            if( Map.count(tmp) && Map[tmp]!=i ){
                ans.push_back(i);
                ans.push_back(Map[tmp]);
                break;
            }
        }
        return ans;
    }
};

2、两数相加

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = new ListNode(0);
        ListNode* tmp = res;
        int sum = 0;
        while( l1 || l2 ){
            if( l1 ){
                sum += l1->val;
                l1 = l1->next;
            }
            if( l2 ){
                sum += l2->val;
                l2 = l2->next;
            }
            tmp->next = new ListNode(sum%10);
            tmp = tmp->next;
            sum /= 10;
        }
        if( sum )
            tmp->next = new ListNode(sum);
        return res->next;  //解决的很是巧妙
    }
};

1、前言

　　大二的时候看见学长搭建的个人博客，感觉好高大上的样子，想着自己啥时候不再是哪个只会喊：哇、牛批、666、厉害厉害的傻逼选手，然后浪啊浪，突然有一天，CSP考试上考到了一个Markdown转HTML的大模拟题：
现场狂写2小时，黑箱测试最后只得20分，从此心理对MD留下了挥之不去的阴影，然后就没有了然后，此事不来了了之。大二的时候在CSDN上写过，但是感觉CSDN的广告是越来也严重了，上面，下面，左面，右面等等四面八方全是各种广告，于是乎，时隔三年，趁着中秋没钱出去浪啊，舍友也回家了，丧尸宿舍也搭建一个简单的个人博客吧，此文简单记录一下搭建过程。
本文使用的是 Github pages + Hexo + Next 主题。