jit-hakase

# 分治算法

## 二分查找

``````def part_find(A, n, start_idx):
if not A:
return -1

mid = len(A)//2

if A[mid] == n:
return mid+start_idx
elif A[mid] > n:
return part_find(A[:mid], n, start_idx)
elif A[mid] < n:
return part_find(A[mid+1:], n, start_idx+mid+1)

A = [i for i in range(10)]
idx = part_find(A, 1, 0)
print(idx)
``````

## 排序

### 归并排序

``````def merge_sort(A):
if len(A) <= 1:
return A
mid = len(A)//2
left = merge_sort(A[:mid])
right = merge_sort(A[mid:])

def merge(left, right):
T = []
while left and right:
T.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
while left:
T.append(left.pop(0))
while right:
T.append(right.pop(0))
return T

return merge(left, right)

A = [5, 3, 4, 7, 2, 1, 9, 8, 6, 0]
B = merge_sort(A)
print(B)
``````

### 快速排序

``````def quick_sort(A):
if not A:
return []
key = A[0]
lesser = quick_sort([n for n in A if n < key])
greater = quick_sort([n for n in A if n > key])
return lesser + [key] + greater

A = [5, 3, 4, 7, 2, 1, 9, 8, 6, 0]
B = quick_sort(A)
print(B)
``````

## 排列组合

### 排列数

``````N = 3
L = [i for i in range(1, N+1)]

def A(cur):
if cur == len(L)-1:
print(L)
return

for i in range(cur, len(L)):
L[cur], L[i] = L[i], L[cur]
A(cur+1)
L[cur], L[i] = L[i], L[cur]

A(0)
``````

### 组合数

``````N, M = 5, 3
L = [None for i in range(M)]

def C(n, m):
for i in range(n, m-1, -1):
L[m-1] = i
if m > 1:
C(i-1, m-1)
else:
print(L)

C(N, M)
``````

## 棋盘覆盖

``````N, CNT = 4, 0

M = [[0 for j in range(N)] for i in range(N)]

def chess_fill(bx, by, x, y, size):
if size == 1:
return

global CNT
CNT += 1
cnt = CNT
size //= 2
ex, ey = bx+size, by+size

# left top area
if x<ex and y<ey:
chess_fill(bx, by, x, y, size)
else:
M[ex-1][ey-1] = cnt
chess_fill(bx, by, ex-1, ey-1, size)

# right top area
if x>=ex and y<ey:
chess_fill(ex, by, x, y, size)
else:
M[ex][ey-1] = cnt
chess_fill(ex, by, ex, ey-1, size)

# left bottom area
if x<ex and y>=ey:
chess_fill(bx, ey, x, y, size)
else:
M[ex-1][ey] = cnt
chess_fill(bx, ey, ex-1, ey, size)

# right bottom area
if x>=ex and y>=ey:
chess_fill(ex, ey, x, y, size)
else:
M[ex][ey] = cnt
chess_fill(ex, ey, ex, ey, size)

x, y = 1, 1
chess_fill(0, 0, x, y, N)

for i in range(len(M)):
for j in range(len(M[i])):
print(M[i][j], end=' ')
print()
``````

### jit-hakase

#### 暂无文章

IT兄弟连 HTML5教程 HTML5表单 新增的表单属性1

HTML5 Input表单为<form>和<input>标签添加了几个新属性，属性如表1。 1 autocomplete属性 autocomplete属性规定form或input域应该拥有自动完成功能，当用户在自动完成域中开始输入时，浏览器...

45分钟前
5
0
OSChina 周五乱弹 —— 葛优理论+1

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @这次装个文艺青年吧 ：#今日歌曲推荐# 分享米津玄師的单曲《LOSER》: mv中的舞蹈诡异却又美丽，如此随性怕是难再跳出第二次…… 《LOSER》-...

1K
16
nginx学习笔记

5
0
Spring Security 实战干货：玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战，如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证（Authentication），认证...

15
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie

19
0