Posted on

Fizz Buzz

难度：Easy

题目描述

写一个程序，输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数，输出“Fizz”；

  2. 如果 n 是5的倍数，输出“Buzz”；

  3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

解

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> res;
        for (int i = 1; i <= n; ++i) {
            if (i % 15 == 0) res.push_back("FizzBuzz");
            else if (i % 3 == 0) res.push_back("Fizz");
            else if (i % 5 == 0) res.push_back("Buzz");
            else res.push_back(to_string(i));
        }
        return res;
    }
};

知识点：

  1. 向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

标准库vector类型使用须要的头文件：#include <vector>。

Vector的定义和初始化：

1
2
3
4
5
6
7
vector< typeName > v1;       //默认v1为空，故以下的赋值是错误的v1[0]=5;
vector<typeName>v2(v1); 或v2=v1;或vector<typeName> v2(v1.begin(), v1.end());//v2是v1的一个副本，若v1.size（）  >v2.size()则赋值后v2.size()被扩充为v1.size()。
vector< typeName > v3(n,i);//v3包括n个值为i的typeName类型元素
vector< typeName > v4(n); //v4含有n个值为0的元素
int a[4]={0,1,2,3,3}; vector<int> v5(a,a+5);//v5的size为5，v5被初始化为a的5个值。后一个指针要指向将被拷贝的末元素的下一位置。
vector<int> v6(v5);//v6是v5的拷贝
vector< 类型 > 标识符（最大容量，初始全部值）

Vector的基本函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6．front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据

2.to_string

#include <string>

1
2
3
4
5
6
7
8
9
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

Posted on

吃饭饭

Posted on

最小栈

难度：Easy

题目描述

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索（retrievie）栈中的最小元素。

示例

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -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
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        s1.push(x);
        if (s2.empty() || x <= s2.top()) s2.push(x);
    }
    
    void pop() {
        if (s1.top() == s2.top()) s2.pop();
        s1.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
    
private:
    stack<int> s1, s2;
};

思路

用两个栈，s1来按顺序存储push进来的数据，s2的栈顶用来存最小值

知识点

stack(堆栈）是一个容器的改编，它实现了一个先进后出的数据结构（FILO）。
定义stack对象的示例如下：

1
2
stack<int> s1;
stack<string> s2;

stack的基本操作如下：

函数名 功能 复杂度
size() 返回栈的元素数 O(1)
top() 返回栈顶的元素 O(1)
pop() 从栈中取出并删除元素 O(1)
push(x) 向栈中添加元素x O(1)
empty() 在栈为空时返回true O(1)

解法二

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
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        min_val = INT_MAX;
    }
    
    void push(int x) {
        if (x <= min_val) {
            st.push(min_val);
            min_val = x;
        }
        st.push(x);
    }
    
    void pop() {
        int t = st.top(); st.pop();
        if (t == min_val) {
            min_val = st.top(); st.pop();
        }
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_val;
    }
private:
    int min_val;
    stack<int> st;
};

知识点

常量INT_MAX 表示最大整数 2^31-1，INT_MIN表示最小整数-2^31

Posted on

paper：
Fast R-CNN -arXiv:1504 ICCV2015

Introduction

R-CNN之后，RGB大神又单枪匹马干出了Fast R-CNN。相较于前者，Fast R-CNN更加Deep Learning化了，一是只对整幅图进行一次特征提取；二是将bounding box的分类和回归联合起来，进行多任务的训练。

Implementation

1539947950822

Faster R-CNN的流程如下：

  1. 和R-CNN一样，用selective search算法在输入图片上提取约2000个候选框。
  2. 将图片输入CNN网络中，得到特征图（feature map）。
  3. 对于每个候选框，都可以在特征图上找到与其相对应的特征框，然后用ROI池化层（region of interest pooling layer）将每个特征框池化到固定的大小。
  4. 将特征框输入全连接层（FC layers）得到特征向量。
  5. 将特征向量分别通过两个不同的全连接层，其中一个输出softmax的分类得分，另一个输出bounding box的regression。
  6. 利用窗口得分分别对每一类物体进行非极大值抑制剔除重叠建议框，最终得到每个类别中回归修正后的得分最高的窗口。

1.RoI pooling layer

1
像AlexNet CNN等网络在提取特征过程中对图像的大小并无要求，只是在提取完特征进行全连接操作的时候才需要固定特征尺寸，利用这一点，Fast R-CNN可输入任意size图片，并在全连接操作前加入RoI池化层，将建议框对应特征图中的特征框池化到H×W 的size，以便满足后续操作对size的要求

RoI池化层使用max pooling 将特征框固定为HxW大小。若特征框大小为h×w，则设定每个子窗口大小为h/H×w/W，然后对每个子窗口采用max pooling下采样操作，每个子窗口只取一个最大值，则特征框最终池化为H×W的大小。

2.训练

2.1预训练

采用了AlexNet、VGG_CNN_M_1024 、VGG-16三种网络在ImageNet上进行预训练。之后，对网络进行了三处修改：

  1. 最后一层max pooling 改为 RoI pooling
  2. 最后的fully connected layer 和softmax替换为两个子网络，其一是全连接层加K+1个分类的softmax，其二是全连接层加bounding box回归器
  3. 改为双输入，即图像和其对应的region proposal

2.2 检测任务上的微调

多任务损失

Fast R-CNN有两个输出，第一个是K+1个类别的离散概率分布p=( p_{0}, …, p_{K})，第二个是bounding-box regression的offset

Posted on

二叉树的直径

难度：Easy

题目描述

给定一棵二叉树（ binary tree ），你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点（nodes）路径（path）长度中的最大值。这条路径可能穿过根结点（root）。

示例

给定二叉树 

1
2
3
4
5
1
     / \
    2   3
   / \     
  4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。 

1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        int res = getHeight(root->left) + getHeight(root->right);
        return max(res, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        if (m.count(node)) return m[node];
        int h = 1 + max(getHeight(node->left), getHeight(node->right));
        return m[node] = h;
    }

private:
    unordered_map<TreeNode*, int> m;
};

思路：

其实就是根结点的左右两个子树的深度之和再加1。那么我们只要对每一个结点求出其左右子树深度之和，再加上1就可以更新结果了。为了减少重复计算，我们用哈希表建立每个结点和其深度之间的映射，这样某个结点的深度之前计算过了，就不用再次计算了。

知识点：

Posted on

551 学生出勤纪录 I

难度：Easy

题目描述

给定一个字符串来代表一个学生的出勤纪录，这个纪录仅包含以下三个字符：

  1. ‘A’ : Absent，缺勤
  2. ‘L’ : Late，迟到
  3. ‘P’ : Present，到场

如果一个学生的出勤纪录中不超过一个’A’(缺勤)并且不超过两个连续的’L’(迟到),那么这个学生会被奖赏。

你需要根据这个学生的出勤纪录判断他是否会被奖赏

示例

1
2
3
4
输入: "PPALLP"
输出: True
输入: "PPALLL"
输出: False

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool checkRecord(string s) {
        int numA =0, numL = 0;
        for (char c : s){
            if(c == 'A'){
                if (++numA > 1) return false;
                numL = 0;
            }
            else if(c == 'L'){
                if (++numL > 2) return false;
            }
            else{
                numL = 0;                
            }
        }
        return true;
    }
};

知识点：

对字符串的遍历： for（char c：s）

解法二

1
2
3
4
5
6
class Solution {
public:
    bool checkRecord(string s) {
        return (s.find("A") == string::npos || s.find("A") == s.rfind("A")) && s.find("LLL") == string::npos;
    }
};

知识点：

string中的find()函数：若查找成功，返回按查找规则找到的第一个字符或子串的位置；若查找失败，返回string::npos。
rfind()与find()的差别在于查找顺序不一样，rfind()是从指定位置起向前查找，直到串首。
参见 https://www.cnblogs.com/zpcdbky/p/4471454.html

解法三

1
2
3
4
5
6
class Solution {
public:
    bool checkRecord(string s) {
        return !regex_search(s, regex("A.*A|LLL"));
    }
};

思路：

使用正则匹配，找出不合题意的情况，然后取反即可。正则匹配式是A.*A|LLL，.*表示有零个或者多个，那么A.*A就是至少有两A的情况，LLL是三个连续的迟到，|表示两个是或的关系，只要能匹配出任意一种情况，就会返回false。

知识点：

regex_search()返回true或false，搜索字符串中存在符合规则的子字符串 。参考：https://blog.csdn.net/qq_34802416/article/details/79307102

正则表达式中，.*表示零个或多个。

552 学生出勤纪录 II

难度：Hard

挖坑

Posted on

paper：

Rich feature hierarchies for accurate object detection and semantic segmentation -arXiv:1311 CVPR2014

参考文章：

https://blog.csdn.net/wopawn/article/details/52133338

http://www.cnblogs.com/makefile/p/nms.html

Introduction

12年、13年，Alexnet 和 VGGnet 相继诞生， 在分类任务中将传统方法重重地踩在了脚下，深度卷积神经网络开始在计算机视觉领域大放异彩。比分类任务更进一步的检测任务，当然不会被研究者们放过，于是RGB大神（Ross Girshick）的R-CNN横空出世。

1539947950822

R-CNN 全称为Regions with CNN features，也就是说，它将图像中的某些候选区域（regions）放到CNN中，然后对得到的特征（features）进行检测。从上图可以看出，它的总体流程如下：

  1. 从输入图像提取约个2000候选区域
  2. 对于每个区域，都让其通过一个CNN，得到定长的特征向量
  3. 对于每个feature， 用SVM进行分类

R-CNN是将Deep Learning引入目标检测的开山之作，虽然此时的它还略显臃肿（进行了太多次的CNN运算）。此外，这篇论文还提出了一个重要的思想，即一个任务的预训练模型（如ImageNet）对于另一个任务的训练有很大的帮助，能够缩短其训练时间，也能让其Loss Function更有效地收敛。

也正是由于R-CNN是开山之作，它只是将CNN用于特征提取，其他很多操作仍然采用传统方法，这些方法在后续成熟版本中已经弃用，对于这些细节，如果实在是搞不懂，可以跳过。Faster R-CNN才是重中之重。

Implementation

1.模型设计

首先，使用传统的selective selective方法，从输入图像提取约个2000候选区域（Region Proposal），但是后面的工作（如Faster RCNN）中都用CNN来提取候选区域了，所以SS在这就不做介绍了。想了解的可以看这篇文章https://blog.csdn.net/mao_kun/article/details/50576003

之后，对于每个候选区域，都让其经过Alexnet的卷积层，从而提取出4096维的特征向量。由于Alexnet要求输入的图像大小为227x227，因此对于各种不同大小和纵横比的区域，在通过Alexnet之前需要进行卷曲操作（wrap），从而得到定长的输入Alexnet的图像。

对于每个候选区域，将其4096维的特征向量做每个类别的SVM分类（若类别数目为N，则有N个SVM分类器，每个SVM做二分类，即属于或不属于该类别），得到相对于每个类别的分数。即2000x4096维的特征矩阵与4096xN维的SVM参数矩阵相乘，得到2000xN维的分数矩阵。

对于同一类的2000个候选区域的分数，使用非极大值抑制（non-maximun suppresion，NMS）剔除掉一些重复的相近的候选框，保留一些得分最高的候选框，即保证对于每个物体，只有一个得分最高的框将其选中。关于NMS，详见附录B。

最后，对于N个类别中剩余的候选框，使用N个回归器做回归（称为Bounding-box regression），使得候选框的定位更加准确，得到最终的结果。

2.训练过程

2.1 预训练（pre-training）

在ILSVRC数据集上对AlexNet进行分类训练，得到预训练模型，该模型保存了训练完毕后的AlexNet的参数。

2.2 微调（fine-tuning）

将分类任务上的AlexNet迁移到检测任务上，需要对训练好的AlexNet进行微调，此时输入为候选区域变形后的227x227大小的图像，输出需要将原来的1000维（1000类）改为N+1维（N个类别+背景）。

选定候选区域与标准框（ground truth）的IoU（见附录A）大于等0.5的为正样本，小于0.5的为负样本。即使是这样分，负样本仍比正样本多得多。因此，在每一次的SGD迭代中，选择32个正样本和96个负样本（3:1）为一个mini-batch。

学习率（learning rate）设为0.001，是预训练时的1/10，从而保证在学习新东西时不至于忘记之前的记忆 。

2.3 分类训练

对于每个类别的SVM分类器，选择ground-truth 框作为正样本， 选择与ground-truth的IOU小于0.3的候选框为负样本。同样的，负样本的数目远多于正样本的数目，需要采用负样本挖掘算法（hard negetive mining）选取一部分负样本进行训练。详见附录C。

2.4 回归训练（bounding box regression）

详见附录D。

附录

A.IoU


即A与B的交集（intersection）与A与B的并集（union）之比：(A∩B)/(A∪B)

B. 非极大值抑制（Non-maximun suppresion，NMS）

在得到每一类的2000个候选区域后，会遇到上图所示情况，同一个目标会被多个建议框包围，这时需要非极大值抑制操作去除得分较低的候选框以减少重叠框。

其基本操作流程如下：

  1. 对于每一类，按scores大小排序

  2. 找到scores最大的候选框，将其保留，然后分别与其他候选框计算IoU，若IoU大于设定的阈值，则剔除得分较小的那个候选框

  3. 所有候选框遍历完毕后，选择socres第二大的候选框，将其保留，重复步骤2。

  4. 重复步骤3，直到所有的候选框都被筛选过。

注：对于得分低于某一阈值的候选框，应该直接剔除， 但是文章没有说明何时剔除。

Python代码实现

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
import numpy as np

def py_cpu_nms(dets, thresh):
    """Pure Python NMS baseline."""
    x1 = dets[:, 0]
    y1 = dets[:, 1]
    x2 = dets[:, 2]
    y2 = dets[:, 3]
    scores = dets[:, 4]
    
    #每一个检测框的面积
    areas = (x2 - x1 + 1) * (y2 - y1 + 1)
    #按照score置信度降序排序
    order = scores.argsort()[::-1]

    keep = []  #保留的结果框集合
    while order.size > 0:
        i = order[0]
        keep.append(i)  #保留该类剩余box中得分最高的一个
        xx1 = np.maximum(x1[i], x1[order[1:]])
        yy1 = np.maximum(y1[i], y1[order[1:]])
        xx2 = np.minimum(x2[i], x2[order[1:]])
        yy2 = np.minimum(y2[i], y2[order[1:]])

        #计算相交的面积,不重叠时面积为0
        w = np.maximum(0.0, xx2 - xx1 + 1)
        h = np.maximum(0.0, yy2 - yy1 + 1)
        inter = w * h
        #计算IoU：重叠面积 /（面积1+面积2-重叠面积）
        ovr = inter / (areas[i] + areas[order[1:]] - inter)
		#保留IoU小于阈值的box
        inds = np.where(ovr <= thresh)[0]
        order = order[inds + 1] #因为ovr数组的长度比order数组少一个,所以这里要将所有下标后移一位

    return keep

C

D. Bounding box regression


如上图所示，绿色框为实际标准的卡宴车辆框，即Ground Truth；黄色框为selective search算法得出的建议框，即Region Proposal。即使黄色框中物体被分类器识别为卡宴车辆，但是由于绿色框和黄色框IoU值并不大，所以最后的目标检测精度并不高。采用回归器是为了对建议框进行校正，使得校正后的Region Proposal与selective search更接近， 以提高最终的检测精度。论文中采用bounding-box回归使mAP提高了3~4%。


如上图，黄色窗口P表示Region Proposal，绿色窗口G表示Ground Truth，红色窗口表示Region Proposal进行回归后的预测窗口，现在的目标是找到P到红色窗口的线性变换（当Region Proposal与Ground Truth的IoU>0.6时可以认为是线性变换），使得红窗与G越相近，这就相当于一个简单的可以用最小二乘法解决的线性回归问题。

定义P窗口的数学表达式：
$$
P=\left ( P_{x}, P_{y}, P_{w}, P_{h}\right )
$$
分别表示P窗口的横坐标、纵坐标、宽和高，另两个窗口同理。

则P窗口的回归过程如下：
$$
\widehat{G}{x}=P{w}d_{x}\left (P\right)+P_{x}
$$
$$
\widehat{G}{y}=P{h}d_{y}\left (P\right)+P_{y}
$$
$$
\widehat{G}{w}=P{w}\exp \left ( d_{w}\left ( P \right ) \right )
$$
$$
\widehat{G}{h}=P{h}\exp \left ( d_{h}\left ( P \right ) \right )
$$

每一个d(P)都是一个Alex Net Pool5层特征的线性函数，即

$$
d_{}(P)=w_{}^{T}\phi _{5}(P)
$$

这里的

Posted on 
1
2
3
4
target ... : prerequisites ...
    command
    ...
    ...

target

可以是一个object file（目标文件），也可以是一个执行文件，还可以是一个标签（label）。对 于标签这种特性，在后续的“伪目标”章节中会有叙述。

prerequisites

生成该target所依赖的文件和/或target

command

该target要执行的命令（任意的shell命令）

$<表示所有的依赖 目标集 , $@表示目标集

每条命令的 开头必须以 Tab 键开头，除非，命令是紧跟在依赖规则后面的分号后的。

在Makefile的命令行前加一个减号 - （在Tab键之后） ，标记为不管命令出不出错都认为是成功的

变量的赋值及使用

1
2
3
objects = program.o foo.o utils.o
program : $(objects)
    cc -o program $(objects)

条件判断

1
2
3
<conditional-directive>
<text-if-true>
endif

其中 <conditional-directive> 表示条件关键字 ，包括ifeq 、ifneq 、ifdef 、ifndef

函数调用

1
$(<function> <arguments>)

Posted on

import keras 的时候 遇到 No module named ‘tensorflow.python’

解决：重装tensorflow

读CSV文件时，报错UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0xbf in position 2: illegal multibyte sequence

解决：open(csv_path, 'r', encoding='UTF-8')

用utf-8编码时，print出来的csv开头有\ufeff，因此encoding应该为‘UTF-8-sig’

读CSV文件时，报错’utf-8’ codec can’t decode byte 0xb4 in position 0: invalid start byte

解决：保存时 加 encoding=’UTF-8’或’UTF-8-sig’

pytorch load 预训练模型的时候
报错：
Missing key(s) in state_dict: “network.0.conv.weight”, ……
Unexpected key(s) in state_dict: “module.network.0.conv.weight”, ……
是用torch0.4.1版本训练，用0.4.0版本预测的时候报的异常 ？？
解决：

1
model.load_state_dict({k.replace('module.',''):v for k,v in torch.load(checkpoint_path)['state_dict'].items()})

Python 报错NotImplementedError
在面向对象编程中，可以先预留一个方法接口不实现，在其子类中实现。如果要求其子类一定要实现，不实现的时候会导致问题，那么采用raise的方式就很好。而此时产生的问题分类 是NotImplementedError。

pytorch: ‘list’ object has no attribute ‘cuda’

pytorch: cuda runtime error(59) in loss.backward()
From the error message it looks like you are using indexing with wrong indices.
A good way to debug these errors is to simply run the exact same code on CPU（ model.cpu()）, that way you will get a proper stack trace with the exact line that crashed.

pytorch: Assertion cur_target >= 0 && cur_target < n_classes failed
label 从0开始