• 数据结构与算法(python)
  • chapter_2 二分法(Binary Search)

数据结构与算法(python)

chapter_2 二分法(Binary Search)

第一境界（二分位置 之 OOXX）

• 二分查找
• 第一个错误的代码版本
• 在大数组中查找
• 寻找旋转排序数组中的最小值
• 搜索二维矩阵
• 搜索二维矩阵 II
• 搜索区间
• 目标出现总和
• 山脉序列中的最大值

第二境界（二分位置 之 Half half）

• 寻找峰值
• 搜索旋转排序数组star

第三境界（二分答案）

• x的平方根
• 木材加工
• 书籍复印
• 两个整数相除

• day 1
  • 二维数组中的查找

每日一刷 2018/8/27
推荐教材：https://facert.gitbooks.io/python-data-structure-cn/

day 1

二维数组中的查找

1
2
3
4
5
6
7

# 一开始想到的暴力做法
def Find(arr, target):
    for i in range(len(arr)):
        for j in arr[i]:
            if j == target:
                return True
    return False

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

# 优化后
def Find(array,target):
    col_num = len(array[0])
    row_idx = len(array) - 1
    col_idx = 0
    while row_idx > -1 and col_idx < col_num:
        if array[row_idx][col_idx] == target:
            return True
        elif array[row_idx][col_idx] < target:
            col_idx += 1
        else:
            row_idx -= 1
    return False

• 数据准备
  • 把数据处理成DSSM要求的格式，一个query，一个pos_doc，四个neg_doc

1
2
3
4
5
6
7
8
9
10

import numpy as np
import pandas as pd
import torch 
import torch.nn as nn
import torchvision.datasets as dsets
import torchvision.transforms as transforms
from torch.autograd import Variable
import torch.nn.functional as F
from config import opt
from sklearn.externals import joblib #jbolib模块

数据准备

把数据处理成DSSM要求的格式，一个query，一个pos_doc，四个neg_doc

1
2
3
4

# 处理q1,q2
import numpy as np
import pandas as pd
train = pd.read_csv('mojing/train.csv')

1

train.head()

• super函数使用基础

super函数使用基础

实际上，大家对于在Python中如何正确使用super()函数普遍知之甚少。你有时候会看到像下面这样直接调用父类的一个方法：

1
2
3
4
5
6
7

class Base:
    def __init__(self):
        print('Base.__init__')
class A(Base):
    def __init__(self):
        Base.__init__(self)
        print('A.__init__')

尽管对于大部分代码而言这么做没什么问题，但是在更复杂的涉及到多继承的代码中就有可能导致很奇怪的问题发生。比如，考虑如下的情况：

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

class Base:
    def __init__(self):
        print('Base.__init__')
class A(Base):
    def __init__(self):
        Base.__init__(self)
        print('A.__init__')
class B(Base):
    def __init__(self):
        Base.__init__(self)
        print('B.__init__')
class C(A,B):
    def __init__(self):
        A.__init__(self)
        B.__init__(self)
        print('C.__init__')

xboost在windows安装需要自己编译，编译的过程比较麻烦(需要安装visual studio等)，而且需要复杂的软件环境。为了免去编译，我这里把编译好的文件供大家下载安装。有了编译好的文件，xgboost的安装变得超级简单（注：编译好的dll文件仅适用于windows64位操作系统）

1. 下载我提供的xgboost代码和编译好的dll文件:
   xgboost-master.zip
   libxgboost.dll

2. 将xgboost-master.zip 文件解压缩到python的…\Anaconda3\Lib\site-packages目录下

3. 复制libxgboost.dll文件到 ….\site-package\xgboost-master\python-package\xgboost\目录

4. 打开cmd，命令行进入 ….\site-package\xgboost-master\python-package\ 目录

5. 执行命令：python setup.py install

6. Done!

• 算法描述

Dijkstra 算法，用于对有权图(正)进行搜索，找出图中两点的最短距离，既不是DFS搜索，也不是BFS搜索。
把Dijkstra 算法应用于无权图，或者所有边的权都相等的图，Dijkstra 算法等同于BFS搜索。

算法描述

算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

• pycharm远程配置

pycharm远程配置

pycharm远程配置：
file->Settings->Project Interpreter->加入远程ssh的连接和python的执行文件地址
然后再加一个path mappings（本地和远程的文件存储地址）

文件同步配置：
Tools->Deployment->Configuration->添加一个新SFTP
Root path选远程文件夹
Web server root URL: http:///
Mappings选local path工程目录，其他的都为/

done!

• 本地编译打包Spark应用准备

本地编译打包Spark应用准备

1.1 文本所介绍的本地编译都是在windows系统下完成的，首先需要确定电脑上已经安装好了JDK和Scala并且配置好了环境变量, 如果配置完成在cmd中输入java -version和scala -version你将看到version信息
我所用的jdk版本是1.7.0和scala版本2.11.8，大家可以自行下载然后选择默认位置安装(记住默认位置，后续要设置环境变量)。注意一点：开发Spark-1.5应用程序，必须使用Scala-2.10.4版本；开发Spark-2.0应用程序，必须使用Scala-2.11.8版本

1.2 安装完了jdk和scala以后如果打开cmd输入以上命令如果可以显示以上信息则忽略此步，如果出现不是内部或外部命令的提示则需要设置环境变量。具体步骤是 右击【我的电脑】–【更改设置】–【高级】–【环境变量】–系统变量(S)下新建变量名JAVA_HOME,变量值C:\Program Files\Java\jdk1.7.0_17(默认安装路径)，然后在Path变量下添加;%JAVA_HOME%\bin;%JAVA_HOME%\jre\bin
系统变量下新建变量名SCALA_HOME，变量值C:\Program Files (x86)\scala，然后在Path变量下添加;C:\Program Files (x86)\scala\bin，保存并退出。这时cmd中输入命令就能显示了

在知乎上看到一些相关的内容，于是选择了在github上用jekyll搭建博客。