binary search and spreadsheet numeration

昨天去知道创宇的面试失败了，很感谢他们能给我这个机会。通过这次面试，我总算迈出了一步，更加明确了自己应该努力的方向。这次面试反映出的一个很严重的问题就是，手太生，学了这么长时间Python，竟然连一些常用的用法，命令都得现查文档。自己反思一下，没有自己动手写多少代码，这个是问题的关键。

面试我的雨哥人非常nice，面对我这么菜的表现没有一点不耐烦，他说的一句话让我印象深刻，“既然是有兴趣，平时就多花点时间，对得起兴趣这两个字”。我会的。

二分法查找

我想这个应该是最容易理解的算法了吧，我差点就在面试的时候完成了，well,almost…

思路很简单，因为给出的列表已经是排好顺序的了，因此直接找到中间的一个记为mid，若是要找的元素，任务完成。若mid比要找的元素大，好的，那么要找的元素肯定在start跟mid之间了，若mid比要找的元素小，那么要找的元素肯定在mid和end之间了。

 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
36
37


def binarySearch(lst, element, start, end):
    mid = (start + end)/2 
    if element == lst[mid]:
        print 'Found, %d' % mid 
    elif mid == start:
        if element == lst[mid+1]:  # 主要处理两个相邻的数的情况，这种情形下mid必然等于start
            print 'Found, %d' % (mid+1) # 因此如果end（也就是mid+1）不等于element的话，则没找到
        else:
            print 'Not found'
    elif element > lst[mid]:
        return binarySearch(lst, element, mid, end)
    elif element < lst[mid]:
        return binarySearch(lst, element, start, mid)

def binarySearch2(lst, element, start, end):
    mid = (start + end)/2
    if element == lst[mid]:
        return 'Found, %d' % mid 
    elif start > end:
        return 'Not found'
    elif element < lst[mid]:
        return binarySearch2(lst, element, start, mid-1)
    elif element > lst[mid]:
        return binarySearch2(lst, element, mid+1, end)

def binarySearch3(lst, element):
    start = 0 
    end = len(lst) - 1
    while (start <= end):
        mid = (start + end)/2
        if lst[mid] == element:
            return 'Found', mid
        elif lst[mid] > element:
            end = mid - 1
        elif lst[mid] < element:
            start = mid + 1
    return 'Not found'

上面的方法一是我自己瞎想的ugly思路，方法三是我在一站式C编程上看到的，方法二是我根据方法三的思路用递归改写的

spreadsheet numeration

这个题目其实我之前在CodeForces上做过的，可惜没有理解它的真谛，虽然当时误打误撞做出来了，还是没有效果，现在遇到还是不会做，面试中雨哥一句话点醒我，“进制转换”，是啊，这个问题实质上就是十进制转换26进制的问题。那进制转换无非就是要做除法、取余。但是也不是这么简单，有一个比较tricky的问题，就是在转换26的倍数的时候，需要做一些特殊处理才行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


def numTochar(num):
    result = ''
    ori = num 
    while num:
        mod = num % 26
        if mod == 0:
            mod = 26
            num = num/26 - 1 # special cases for 'Z' 
        else:
            num /= 26
        result = chr(mod + ord('A') - 1) + result
    return result,ori

def numTochar2(num):
    result = ''
    ori = num 
    while num:
        mod = num % 26
        if mod == 0:
            mod = 26
        num -= 1       # a more elegant solution
        num /= 26
        result = chr(mod + ord('A') - 1) + result
    return result,ori

方法一是我自己捣鼓的，方法二是我在CodeForces上看到了，效果应该是一样的，都是为了在转换26的倍数的时候能够得出正确的结果，做出的一点特殊处理，不过显然后者更加优雅，每个数在除26之前先减1,这样既对于非26倍数的数没有影响，又能巧妙的处理26的倍数时的特殊情况。

文章目录

二分法查找

spreadsheet numeration