Coding Note

算法复杂度分析

算法分析

构造数组前段总和first = A[0]以及数组后端总和last = sum(A) - A[0]，第一个差值便是abs(first - last)。遍历数组时，不必每次都重新构造数组前段总和以及数组后端总和，只需向first增加当前遍历元素，想las减去当前遍历元素，另外，也只要一个变量min_diff来记录最小差值即可。

源代码

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

def solution(A):
    # write your code in Python 2.7
    first = A[0]
    last = sum(A) - A[0]
    N = len(A)
    min_diff = abs(first - last)
    for i in xrange(1, N - 1):
        num = A[i]
        first += num
        last -= num
        min_diff = min(abs(first - last), min_diff)
    return min_diff

算法复杂度分析

算法分析

可以想象有一个数组长度为N+1，数组元素为1,2,…N,N+1，这样便可以用等差求和公式算出该数组的总和。用总和减去输入数组A的和便可以知道数组A缺失了哪个元素。注意python sum()的算法复杂度为O(N)，故该算法的算法复杂度是O(N)。

源代码

1
2
3
4
5
6

def solution(A):
    # write your code in Python 2.7
    N = len(A)
    start = 1
    end = len(A)+1
    return (N+1)*(start+end)/2 - sum(A)

算法复杂度分析

算法复杂度不依赖于输入数据的多少，该算法总是在固定时间内完成。

算法分析

已知长度Y-X，步长D，求步数。难点在于长度能否整除步长，若能整除，返回步长，若不能整除，对步长向上取整。向上取整可以同python math库里的ceil函数。如果不想加载math库，只用python内建函数可以吗？其实也是可以的。难度在对于求得的步长是否+1上。由于python除法/会截断小数部分，我们可以用取余%操作判断长度能否整除步长，若能整除，返回步长，若不能整除，对步长+1即可。

Python 数值转换

python 数值转换函数int()把bool型转换为int型整数值，int(True) => 1 int(False) => 0

源代码

1
2
3

def solution(X, Y, D):
    # write your code in Python 2.7
    return (Y-X)/D + int((Y-X)%D > 0)

算法复杂度分析

其中，K是数组中互不相同数的个数

算法分析

遍历数组，算出每个数出现的次数。如果出现的次数为奇数，则返回该数。要点是选择用于记录不同数出现次数的计数器的数据结构和计数方法。对于计数器的数据结构，python built-in的字典可以满足O(1)的读取和记录。对于计数方法，则不必详细记录出现次数，标记奇偶即可。在特定条件下，应该也可以使用位操作，利用二进制0，1比特来标记奇偶，以便使用更小的内存空间。

源代码

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

def solution(A):
    # write your code in Python 2.7
    count = {}
    for num in A:
        if num in count:
            count[num] = (count[num] + 1) % 2
        else:
            count[num] = 1

    for k in count:
        if count[k] == 1:
            return int(k)

算法复杂度分析

算法分析

并不是要真的右移K次数组，K对N取模，可求出实际要右移的次数K = K%N。利用python数组切片操作，以N-k为切点，将数组分成前后两部分，颠倒前后顺序拼接后便可得到右移K次的数组。

Pyhton数据切片

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• 给切片起始、终止值和步长，
• a[0:5:2] # [0, 2, 4]
• 给切片起始和终止值，步长值缺省时其默认值为1
  • a[0:5] # [0, 1, 2, 3, 4]
  • a[0:] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  • a[:5] # [0, 1, 2, 3, 4]
  • a[:] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
• 给负值
• a[-1] # 9
• a[-2:] # [8, 9]
• a[:-2] # [0, 1, 2, 3, 4, 5, 6, 7]

源代码

1
2
3
4
5
6
7
8
9
10

def solution(A, K):
    # write your code in Python 2.7
    # N number of array A
    N = len(A)
    if (N == 0):
        return A
    K = K%N
    first = A[N-K:]
    last = A[:N-K]
    return first+last

参考

• Python数组切片算法复杂度分析
• Python数组切片操作解释

算法复杂度分析

算法分析

利用python built-in函数bin()将十进制输入转换为二进制字符串，遇到字符‘0’，计数器count += 1，遇到字符‘1’，计数器清空。变量max记录count最大值，函数最后返回max。但是有一个问题，转换为二进制表示的N没有前导0，但需要注意处理后缀0，以免错误计数。否则，若二进制表示为1001000时，函数返回3而不是2。

源代码

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

def solution(N):
    # write your code in Python 2.7
    if (N > 2147483647 or N < 1):
        return 0
    s = bin(N)[2:]
    last = s.__len__()-1
    while (s[last] == '0'):
        last -= 1
    s = s[0:last+1]
    count = 0
    max = 0
    for c in s:
        if (c == '0'):
            count += 1
            if (count > max):
                max = count
        else:
            count = 0
    return max

目录

• 为什么要学习Vim
• 学习Vim的正确姿势
• 配置Vim的省时办法
• Vim插件使用

为什么要学习Vim

Vi或者Vim（Vi加强版）是众多Linux发行版中终端环境自带的文本编辑器，但似乎熟练掌握Vi/Vi不是在Linux上进行软件开发活动的必要条件。因为在Linux上开发软件的过程中，我们总是能找到更便于上手的，学习曲线更平缓的替代工具，比如gedit，sublime或者atom。然而在某些情况下，掌握Vi/Vim却显得十分的必要，比如需要远程链接到一台上个世纪的古董服务器上修改几行配置代码时，使用Vi/Vim进行编辑几乎是你的唯一选择，毕竟Vi诞生于1976年，比Linux的第一个版本发行时还要早17年，此外Vi/Vim可以直接运行在终端环境中，而gedit，sublime或者atom却需要在桌面环境的支持下才能运行。

目录

• 开发分支 DEV
• 测试分支 TEST
• 缓冲分支 STAGING
• 生产分支 PROD

一般来说，利用git进行多人协作的网站开发项目都有不止一个分支，其中每一个分支对应于网站部署的一个架构。虽然网站部署架构千差万别，但几乎都是从开发环境（DEV）开始并以生产环境（PROD）结束，所以对应到git分支上就是 开发分支，测试分支，缓存分支和生产分支。

开发分支 DEV

开发分支是本地开发环境上用于开发新功能的分支，开发人员可以方便的在本地进行单元测试

目录

• 什么时候使用Cherry-pick
• 一个例子

一般来说，掌握了git的commit，branch，merge几个命令就足以应付90%的工作场景了，但是有时候我们也需要处理稍微复杂一点的工作场景，比如整理提交记录。

什么时候使用Cherry-pick

Cherry pick 直译成中文就是采樱桃，樱桃有好有坏，挑选樱桃的过程就形象的类比了我们应用该命令挑选提交（Commit）的过程。
一般来说，利用git进行多人协作的网站开发项目都有不止一个分支，其中每一个分支对应于网站部署的一个架构。在多分支环境下，如果我们想要将一个或者一些在其他分支下提交（Commit）复制到当前分支所在的位置（HEAD）的话，cherry-pick 是最直接，最方便的办法了。

目录

• 通过conig命令设置Git别名
• 通过config文件设置Git别名

刚刚进公司时，发现同事在使用Git时都是输入一些我从来没见过的命令，比如git st, git ci什么的，但是这些命令在自己的电脑上却不存在。更有甚者，有同事优雅的在终端上输入git fuck命令，git竟把远端的branch fetch回本地了，我的天，难道自己用的是假git吗？
我弱弱问身边的同事，这才知道git别名的存在，借助于git别名我们就可以为git已有的命令取个上口好记的别名了。

通过conig命令设置Git别名

通常情况下，git最常用的几个命令是 git branch, git checkout, git commit 和git status。如果只是为这几个命令设置git别名，最简单的方法是在终端中输入以下命令

1
2
3
4

git config --global alias.br branch
git config --global alias.co checkout
git config --global alias.ci commit
git config --global alias.st status

通过config文件设置Git别名

不过，如果我们一次想设置的别名比较多，那么我们可以通过修改~/.gitconfig文件来实现。
这时我们可以通过添加以下字段来完成和上述一样的设置.