2019-07-11

字符串算法---判断回文

def isHw(a):  
    i, j = 0, len(a)-1  
    while i <= j:  
        if a[i] != a[j]:  
            return False  
 i += 1  
        j -= 1  
  
    return True  
if __name__ == "__main__":  
    print(isHw('abcdedcba'))  
    print(isHw('abcdedcb'))  
    print(isHw('abcdeedcba'))

2019-07-09

自我修养►数据结构与算法

排序---基数排序

基数排序

def radix_sort(a, r, bits):  
    if bits == 0 or len(a) == 0:  
        return a  
  
    n = 1  
    k = bits-1  
    while k:  
        n*=10  
        k-=1  
  
    radixes = [[] for _ in range(r)]  
    for e in a:  
        radixes[(e//n)%10].append(e)  
  
    new_a = []  
    for i, radix in enumerate(radixes):  
        new_a.extend(radix_sort(radix, r, bits-1))  
  
    return new_a  
  
  
if __name__ == "__main__":  
    import random  
    a = [random.randrange(1000) for _ in range(100)]  
    print(a)  
    new_a = radix_sort(a, 10, 3)  
    print(new_a)

2019-07-09

自我修养►数据结构与算法

排序---计数排序

def count_sort(a, start, end):  
    cnts = [0 for _ in range(start, end+1)]  
    for e in a:  
        cnts[e-start]+=1  
  
    print(cnts)  
    sum = 0  
    for i in range(1, len(a)):  
        cnts[i] += cnts[i-1]  
  
    new_a = a[:]  
    for e in a:  
        print(cnts, e-start)  
        new_a[cnts[e-start]-1] = e  
        cnts[e-start]-=1  
    return new_a  
  
if __name__ == "__main__":  
    import random  
    a = [random.randrange(10) for _ in range(10)]  
    print(a)  
    print(count_sort(a, 0, 10))

2019-07-09

自我修养►数据结构与算法

排序----桶排序

def partition(a, start, end):  
   tmp = a[end]  
   k = start  
   for i in range(start, end):  
      if a[i] < tmp:  
         a[k], a[i] = a[i], a[k]  
         k += 1  
   a[k], a[end] = a[end], a[k]  
   return k  
  
def quick_sort(a, i, j):  
   if i >= j:  
      return  
 mid = partition(a, i, j)  
   quick_sort(a, i, mid-1)  
   quick_sort(a, mid+1, j)  
  
def buckets_sort(a, n):  
   start, end = min(a), max(a)  
   step = (end - start) // n  
   buckets = [ [] for _ in range(step) ]  
   for e in a:  
      buckets[(e-start)//step].append(e)  
  
   start, end = 0, 0  
   for bucket in buckets:  
      quick_sort(bucket, 0, len(bucket)-1)  
      end += len(bucket)  
      a[start:end+1] = bucket[:]  
      start += len(bucket)  
  
if __name__ == "__main__":  
   import random  
   l = [random.randrange(10000) for _ in range(1000)]  
   print(len(l), l)  
   buckets_sort(l, 5)  
   print(len(l), l

2019-07-06

自我修养►数据结构与算法

归并排序

不使用辅助空间:

def mergeSort(a, start, end):
if start >= end:
return mid = start + int((end - start)/2)
mergeSort(a, start, mid)
mergeSort(a, mid+1, end)
merge_local(a, start, mid, end)

def insert(a, start, end):
tmp = a[end]
while end > start:
a[end] = a[end-1]
end -= 1
a[start] = tmp

def merge_local(a, l_i, mid, r_j):
i = l_i
for j in range(mid+1, r_j+1):
while i < j:
if a[j] < a[i]:
insert(a, i, j)
i = i+1
break
else:
i+=1
if i == j:
break

def merge(a, l_i, mid, r_j):
aux = []
i, left, right = 0, l_i, mid+1
while i < r_j - l_i + 1:
if left > mid:
aux.append(a[right])
right+=1
elif right > r_j:
aux.append(a[left])
left+=1
elif a[left] <= a[right]:
aux.append(a[left])
left+=1
else:
aux.append(a[right])
right+=1
i+=1

for k in range(i):
    a[l_i] = aux[k]
    l_i+=1
    k+=1

if name == “main“:
import random
a = [ random.randrange(100) for _ in range(20)]
print(a)
mergeSort(a, 0, len(a)-1)
print(a)

使用n的辅助空间:

def mergeSort(a, start, end):
if start >= end:
return mid = start + int((end - start)/2)
mergeSort(a, start, mid)
mergeSort(a, mid+1, end)
merge(a, start, mid, end)

def merge(a, l_i, mid, r_j):
aux = []
i, left, right = 0, l_i, mid+1
while i < r_j - l_i + 1:
if left > mid:
aux.append(a[right])
right+=1
elif right > r_j:
aux.append(a[left])
left+=1
elif a[left] <= a[right]:
aux.append(a[left])
left+=1
else:
aux.append(a[right])
right+=1
i+=1

for k in range(i):
    a[l_i] = aux[k]
    l_i+=1
    k+=1

if name == “main“:
import random
a = [ random.randrange(10) for _ in range(10)]
print(a)
mergeSort(a, 0, len(a)-1)
print(a)

2019-07-06

自我修养►队列:队列在线程池等有限资源池中的应用

队列链表实现

class Node:  
    def __init__(self, data, next):  
        self.data = data  
        self.next = next  
  
class ListQueue:  
    def __init__(self):  
        self.head, self.tail = None, None  
 def enqueue(self, node):  
        if self.tail is not None:  
            self.tail.next = node  
        self.tail = node  
  
        if self.head is None:  
            self.head = node  
  
    def dequeue(self):  
        data = None  
 if self.head is not None:  
            data = self.head.data  
            self.head = self.head.next  
        return data  
  
    def __repr__(self):  
        str = ""  
 head = self.head  
        while head:  
            str += "[%r]->"%head.data  
            head = head.next  
        str += "None"  
 return str  
  
if __name__ == "__main__":  
    l = ListQueue()  
    for i in range(10):  
        l.enqueue(Node(i, None))  
    print(l)  
  
    for i in range(5):  
        print(l.dequeue())  
    print(l)  
  
    for i in range(10):  
        print(l.enqueue(Node(i, None)))  
    print(l)

2019-07-06

自我修养►队列:队列在线程池等有限资源池中的应用

数组实现队列

class ArrayQueue:
def init(self, cap):
self._data = [-1 for i in range(cap)]
self.cap = cap
self.head, self.tail = 0, 0

def enqueue(self, data):  
    if self.tail == self.cap:  
        if self.head == 0:  
            return

for i in range(self.head, self.tail):
self._data[i - self.head] = self._data[i]
self.tail -= self.head
self.head = 0

    self._data[self.tail] = data  
    self.tail += 1  
    return data  

def dequeue(self, data):  
    if self.head == self.tail:  
        return

data = self._data[self.head]
self.head += 1
return data

2019-07-06

自我修养►数据结构与算法

生成n个从1-n的随机数

import random

def n_random(n):
n_array = [ i+1 for i in range(n) ]
nums = n

while nums:  
    number = random.randrange(nums)  
    n_array[nums-1], n_array[number] = n_array[number], n_array[nums-1]  
    nums -= 1  

return n_array

if name == “main“:
print(n_random(10))

2019-07-05

自我修养►数据结构与算法

求大于n且是2的幂的最小整数

int roundup_pow_of_two(int num)  
{  
int n = 0;  
while(num)  
{  
n++;  
num = num >> 1;  
}  
return n==0? 1 : 1<<n;  
}

2019-07-05

编程语言►C

gnu关键字之typeof

typeof是GNU C的一个关键字，用于自动推导变量的类型，类似于C++11 里的 decltype.通常用于在较复杂的上下文中推导变量的类型,linux内核代码常用于宏中。

举例如下:

int main(int argc, char *argv[])  
{  
int a = 10;  
int b = 10;  
int *pa = &a;  
typeof(pa) pb = &b;

printf(“*pb=[%d]rn”, *pb);

return 0;

1
2

通过pa的类型来推导pb的类型。

linux内核中kfifo.h中使用举例:

#define kfifo_init(fifo, buffer, size) 

({   
typeof((fifo) + 1) __tmp = (fifo);   
struct __kfifo ___kfifo = &__tmp->kfifo;  __is_kfifo_ptr(__tmp) ?  __kfifo_init(__kfifo, buffer, size, sizeof(___tmp->type)) :   
-EINVAL;   
})