学习OpenCV-Python——处理文件,摄像头,跟图形界面

读写图像文件

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
import numpy,cv2
# 我们尝试创建一张3*3的全黑的图,每个像素都是8bit的整数(0~255)
>>> img = numpy.zeros((3,3), dtype=numpy.uint8)
>>> img
array([[0, 0, 0], [0, 0, 0], [0, 0, 0]], dtype=uint8)
# 现在我们开始创建BGR图
# 现在每个像素都被三个数组所表示,分别表示BGR
# 注:BGR和RGB是同一颜色空间,只不过reversed而已
>>> img = cv2.cvtColor(img, cv2.COLOR_GRAY2BGR)
>>> img
array([[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]],
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]],
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]], dtype=uint8)
>>> img.shape
(3,3,3)
# 把PNG转换为JPG
# imread()返回的是BGR格式,即使这个图像是灰度图
# 如果你是在Python IDLE中运行的。当前目录为Python的安装路径
image = cv2.imread('MyPic.png')
cv2.imwrite('MyPic.jpg', image)
# 我们可以自定义imread(),有如下枚举成员
# IMREAD_ANYCOLOR = 4
# IMREAD_ANYDEPTH = 2
# IMREAD_COLOR = 1
# IMREAD_GRAYSCALE = 0
# IMREAD_LOAD_GDAL = 8
# IMREAD_UNCHANGED = -1
grayImage = cv2.imread('MyPic.png', cv2.IMREAD_GRAYSCALE)
cv2.imwrite('MyPicGray.png', grayImage)

转换

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
'''
一个byte的整数(0~255)。现在很多图像应用都用一个byte代表一个channel,
OpenCV图像是2D或者3D的数组(.array type)。一个8bit的灰度图是二维数组的,一个24bitBGR图是三维数组的。
一个8bit左上角像素是白色的灰度图,image[0, 0] 是 255。
一个24bit左上角像素是蓝色的BGR图,image[0, 0] 是 [255, 0, 0]。
image.item((0, 0)) 或 image.setitem((0, 0), 128) 比 image[0, 0] 或 image[0, 0] = 128 有效率
'''
# 可以把每个channel 8bit 的图像转换为pyhton的内置对象byteArray
byteArray = bytearray(image)
# 我们可以通过 reshape 函数得到numpy数组
# 注意对于BGR图,height*width*3必须与原图相等;对于灰度图height*width必须与原图相等
grayImage = numpy.array(grayByteArray).reshape(height, width)
bgrImage = numpy.array(bgrByteArray).reshape(height, width, 3)
# 下面的例子随机生成一幅图像
import cv2
import numpy
import os
# 随机生成 120,000 bytes 的数组.
randomByteArray = bytearray(os.urandom(120000))
flatNumpyArray = numpy.array(randomByteArray)
# 转换数组为 400x300 的灰度图
image.grayImage = flatNumpyArray.reshape(300, 400)
cv2.imwrite('RandomGray.png', grayImage)
# 转换数组为 400x100 BGR图.
bgrImage = flatNumpyArray.reshape(100, 400, 3)
cv2.imwrite('RandomColor.png', bgrImage)

通过numpy.array访问图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import cv2
import numpy as np
img = cv2.imread('MyPic.png')
img[0,0] = [255, 255, 255]
img[:, :, 1] = 0 #设置G维的值全部为0
# 前两个参数为x,y坐标。最后一个参数0,1,2分别代表BGR
print img.item(150, 120, 0)
img.itemset( (150, 120, 0), 255)
# prints 255
print img.item(150, 120, 0)
>>> print img.shape
(149, 320, 3)
#图像所有的像素数量
>>> print img.size
143040
#8 bit 无符号
>>> print img.dtype
uint8

读写视频文件

1
2
3
4
5
6
7
8
9
10
11
12
# OpenCV只支持avi的格式,而且生成的视频文件不能大于2GB,而且不能添加音频。
# 读取的每一帧都为BGR格式
import cv2
videoCapture = cv2.VideoCapture('MyInputVid.avi')
fps = videoCapture.get(cv2.CAP_PROP_FPS)
size=(int(videoCapture.get(cv2.CAP_PROP_FRAME_WIDTH)),int(videoCapture.get(cv2.CAP_PROP_FRAME_HEIGHT)))
videoWriter = cv2.VideoWriter( 'MyOutputVid.avi',cv2.VideoWriter_fourcc('I','4','2','0'), fps, size)
success, frame = videoCapture.read()
while success:
videoWriter.write(frame)
success, frame = videoCapture.read()

支持的格式

  • cv2.VideoWriter_fourcc(‘I’,’4’,’2’,’0’): This option is an uncompressed YUV encoding, 4:2:0 chroma subsampled. This encoding is widely compatible but produces large files. The file extension should be .avi.
  • cv2.VideoWriter_fourcc(‘P’,’I’,’M’,’1’): This option is MPEG-1 The file extension should be .avi.
  • cv2.VideoWriter_fourcc(‘X’,’V’,’I’,’D’): This option is MPEG-4 and a preferred option if you want the resulting video size to be average. The file extension should be .avi.
  • cv2.VideoWriter_fourcc(‘T’,’H’,’E’,’O’): This option is Ogg Vorbis. The file extension should be .ogv.
  • cv2.VideoWriter_fourcc(‘F’,’L’,’V’,’1’): This option is a Flash video. The file extension should be .flv.
  • cv2.VideoWriter_fourcc(‘U’,’2’,’6’,’3’): H263 codec
  • cv2.VideoWriter_fourcc(‘I’,’2’,’6’,’3’): H263I codec
  • cv2.VideoWriter_fourcc(‘D’,’I’,’V’,’X’): MPEG-4 codec
  • cv2.VideoWriter_fourcc(‘M’,’P’,’4’,’2’): MPEG-4.2 codec
  • cv2.VideoWriter_fourcc(‘D’,’I’,’V’,’3’): MPEG-4.3 codec

使用摄像头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import cv2
cameraCapture = cv2.VideoCapture(0)
fps = 30 # an assumption
size = (int(cameraCapture.get(cv2.CAP_PROP_FRAME_WIDTH)),int(cameraCapture.get(cv2.CAP_PROP_FRAME_HEIGHT)))
videoWriter = cv2.VideoWriter( 'MyOutputVid.avi', cv2.VideoWriter_fourcc('I','4','2','0'), fps, size)
success, frame = cameraCapture.read()
numFramesRemaining = 10 * fps - 1
while success and numFramesRemaining > 0:
videoWriter.write(frame)
success, frame = cameraCapture.read()
numFramesRemaining -= 1
cameraCapture.release()
'''
在这里videoCapture的get方法不会返回fps,而是总会返回0。
官方文档解释:“When querying a property that is not supported by the backend used by the VideoCapture class, value 0 is returned.”
'''
# 我们也可以用grab() 和 retrieve()
success0 = cameraCapture0.grab()
success1 = cameraCapture1.grab()
if success0 and success1:
frame0 = cameraCapture0.retrieve()
frame1 = cameraCapture1.retrieve()

在窗口中显示图像

1
2
3
4
5
6
7
import cv2
import numpy as np
img = cv2.imread('MyPic.jpg')
cv2.imshow('my image', img)
cv2.waitKey()
# 销毁所有OpenCV创建的窗口
cv2.destroyAllWindows()

实战

将上面所学的知识,自己将OpenCV的API利用OOP的思想封装成更高层。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
# coding:utf-8
import time
import cv2
import numpy
class CaptureManager(object):
def __init__(self, capture, previewWindowManager=None, shouldMirrorPreview=False):
# 绘制窗口,bool
self.previewWindowManager = previewWindowManager
# 镜像旋转(在窗口中问不是在文件中),bool
self.shouldMirrorPreview = shouldMirrorPreview
self._capture = capture
# 频道
self._channel = 0
self._enteredFrame = False
self._frame = None
# 写入图像
self._imageFilename = None
self._videoFilename = None
self._videoEncoding = None
self._videoWriter = None
self._startTime = None
# 从开始到现在帧数
self._framesElapsed = long(0)
# OpenCV没办法获取FPS,如果需要可以用time.time()计算
self._fpsEstimate = None
@property
def channel(self):
return self._channel
@channel.setter
def channel(self, value):
if self._channel != value:
self._channel = value
self._frame = None
@property
def frame(self):
if self._enteredFrame and self._frame is None:
_, self._frame = self._capture.retrieve()
return self._frame
@property
def isWritingImage(self):
return self._imageFilename is not None
@property
def isWritingVideo(self):
return self._videoFilename is not None
def enterFrame(self):
"""捕获下一帧,如果有的话"""
assert not self._enteredFrame, \
'previous enterFrame() had no matching exitFrame()'
if self._capture is not None:
self._enteredFrame = self._capture.grab()
def exitFrame(self):
"""绘制窗口. 写入文件. 释放."""
if self.frame is None:
self._enteredFrame = False
return
# 获取FPS
if self._framesElapsed == 0:
self._startTime = time.time()
else:
timeElapsed = time.time() - self._startTime
self._fpsEstimate = self._framesElapsed / timeElapsed
self._framesElapsed += 1
# 绘制窗口
if self.previewWindowManager is not None:
if self.shouldMirrorPreview:
mirroredFrame = numpy.fliplr(self._frame).copy()
self.previewWindowManager.show(mirroredFrame)
else:
self.previewWindowManager.show(self._frame)
# 写入图像
if self.isWritingImage:
cv2.imwrite(self._imageFilename, self._frame)
self._imageFilename = None
# 写入视频
self._writeVideoFrame()
# 释放
self._frame = None
self._enteredFrame = False
def writeImage(self, filename):
"""写入一帧到图像"""
self._imageFilename = filename
def startWritingVideo(self, filename, encoding=cv2.VideoWriter_fourcc('I', '4', '2', '0')):
"""开始准备写入视频"""
self._videoFilename = filename
self._videoEncoding = encoding
def stopWritingVideo(self):
"""停止写入视频"""
self._videoFilename = None
self._videoEncoding = None
self._videoWriter = None
def _writeVideoFrame(self):
if not self.isWritingVideo:
return
if self._videoWriter is None:
fps = self._capture.get(cv2.CAP_PROP_FPS)
if fps == 0.0:
# 不能捕获帧数就用之前自己测量的
if self._framesElapsed < 20:
# 等待帧数稳定下来
return
else:
fps = self._fpsEstimate
size = (int(self._capture.get(cv2.CAP_PROP_FRAME_WIDTH)), int(self._capture.get(cv2.CAP_PROP_FRAME_HEIGHT)))
self._videoWriter = cv2.VideoWriter(self._videoFilename, self._videoEncoding, fps, size)
self._videoWriter.write(self._frame)
class WindowManager(object):
def __init__(self, windowName, keypressCallback=None):
self.keypressCallback = keypressCallback
self._windowName = windowName
self._isWindowCreated = False
@property
def isWindowCreated(self):
return self._isWindowCreated
def createWindow(self):
cv2.namedWindow(self._windowName)
self._isWindowCreated = True
def show(self, frame):
cv2.imshow(self._windowName, frame)
def destroyWindow(self):
cv2.destroyWindow(self._windowName)
self._isWindowCreated = False
def processEvents(self):
keycode = cv2.waitKey(1)
if self.keypressCallback is not None and keycode != -1:
keycode &= 0xFF
self.keypressCallback(keycode)
class Cameo(object):
def __init__(self):
self._windowManager = WindowManager('Cameo', self.onKeypress)
self._captureManager = CaptureManager(cv2.VideoCapture(0), self._windowManager, True)
def run(self):
"""开始循环"""
self._windowManager.createWindow()
while self._windowManager.isWindowCreated:
self._captureManager.enterFrame()
frame = self._captureManager.frame
self._captureManager.exitFrame()
self._windowManager.processEvents()
def onKeypress(self, keycode):
"""
处理案件
space -> 截屏
tab -> 开始/停止录像
escape -> 退出
"""
if keycode == 32: # space
self._captureManager.writeImage('screenshot.png')
elif keycode == 9: # tab
if not self._captureManager.isWritingVideo:
self._captureManager.startWritingVideo('screencast.avi')
else:
self._captureManager.stopWritingVideo()
elif keycode == 27: # escape
self._windowManager.destroyWindow()
if __name__ == "__main__":
Cameo().run()

学习OpenCV-Python——安装

所需库
NumPy
SciPy
在windows上OpenCV 2 对python 32bit的支持比64bit好

安装编译好的版本(no support for depth cameras)

官网下载后。
复制 \opencv\build\python\2.7\cv2.pyd 到 Python安装目录\Lib\site-packages

自己编译

略。如有需要再写。

samples

C:\opencv\sources\samples 下
一个例子



《Secret Symphony》



爱尔兰的民谣风再加点爵士味的编曲。对比前几张专辑,感觉有些逊色。但曲风蛮适合秋日午后的。舒适而慵懒的感觉。

Katie Melua 8岁时移居到北爱尔兰的贝尔法斯特(BELFAST),5年前又举家迁移到英国,1年前在表演艺术学校BRIT SCHOOL上课的KATIE被知名制作人MIKE BATT挖掘(这位资深制作人近期的作品包括棒辣妹和陈美的专辑),于是和独立厂牌/经纪公司DRAMATICO签下5张唱片合约。小时梦想从政或是朝历史学家方向发展的KATIE,原先并没对写歌和音乐怀有远大志向。她15岁那年参加电视歌唱比赛,演唱MARIAH CAREY的《WHITOUT YOU》,获得冠军;在这之前,她只想象自己是能带给世界和平的人。2年前,KATIE开始写歌,她自称在音乐方面受到皇后合唱团(QUEEN)、琼妮·米歇尔(JONI MITCHELL)、鲍勃·迪伦(BOB DYLAN)、埃拉·菲茨杰拉德(ELLA FITZGERALD)和印度音乐以及爱尔兰民谣等多类乐风的影响。在这锋芒初露的实力派新人KATIE MELUA身上,我们可以看到即将燃烧的无限可能。


说说东野圭吾的一些作品及个人见解

话说东野圭吾,大概是50年代开始兴起的本格派推理小说最出名的作家(至少在国内)。东野的书算是看了不少,对我来说可算是日系推理小说入门的领路人了。今天就来说说东野。

东野本是一个工科男(毕业于大阪府立大学电气工学专业),偶尔写写小说。后来在85年的时候凭借《放学后》获得第31回江户川乱步奖。从此走上职业作家的不归路。

推荐下东野的几部个人觉得可以一看的作品

《白夜行》




临近千禧年的作品,东野的代表作。以“泡沫经济”时的日本为背景,小说时间跨度非常大,场面宏大,人物刻画有血有肉,笔法看似白描,实则充满张力,十分老练,实在是上乘之作。社会派的著名代表作之一,合上书本之后,回想在脑海中不是各种trick,各种动机什么的,而是各种关于人性关于社会的种种。就算脱去推理小说的外衣,这本书依旧是一本超级棒的小说。值得两看。

嫌疑人X的献身




《嫌疑人X的献身》首版于零五年,也算是东野偏后期的作品了。个人觉得东野的巅峰在《白夜行》,之后的几年都一直没什么出名的作品。零四年出了个《白夜行》的姊妹篇《幻夜》个人觉得实在一般,大概是因为有《白夜行》在先的缘故吧。而《嫌疑人X的献身》的出版,仿佛让人觉得旧日巅峰的东野回来了。巅峰时的东野的作品是怎么的?就是给你一种看完了合上书本,心里的震撼久久不能平息的感觉。

《解忧杂货店》




这本书最近好火啊,大概是最近东野最出名的作品了。其实看完这本小说,我甚至怀疑不是出自东野之手。因为,这根本就是一本鸡汤版的故事会。我觉得文青或者小孩看看还可以,但是如果真的想看推理小说的话,我推荐还是不要买这本书好( 毕竟被誉为,奇幻温情小说)。不过,如果你缺少一本鸡汤版的故事会,这本书还是值得一看的。

《恶意》




虽说推理小说不到最后都不知道结局怎么样,但是如果太过刻意制造这种感觉就有点不像样了,这本书就是一个例子。一开始就告诉读者凶手是谁,然后一直在找动机,过了三分之二又告诉读者,“事情可不是你想的那么简单哦。”。读到最后没《嫌疑人X的献身》有那种抽丝剥茧,豁然开朗的感觉。当然,铁杆粉可以一读。
下面是个人不推荐,铁杆粉可一读的书

《放学后》




开头说了东野凭借《放学后》获得第31回江户川乱步奖,从此走上职业作家的不归路。这是一本东野早期的作品,文笔相对于巅峰时期的东野,显得很稚嫩。无论密室,trick,动机,还是最后的结局,都是一本一般般的作品。密室有点让人汗颜,trick平凡,动机扯蛋,结局我勒个去。当然,如果你是东野的铁杆饭,我还是建议你去看看。毕竟这本书又不厚。(逃

《秘密》




这本书不如看电影好,书写得一般,电影个人觉得还不错啦。

《幻夜》




因为是《白夜行》的姊妹篇也是其续篇。《白夜行》给100分的话,《幻夜》最多60分。另外,东野是有多喜欢恶女啊。。。。

《流星之绊》




又一温情鸡汤故事会。

《宿命》




简介还说这本是东野的代表作之一,这话怎么说得出口啊。

《神探伽利略》




看电视剧啊,汤川帅。书真心垃圾。

同步 异步 阻塞与非阻塞

同步

所谓同步,就是在发出一个功能调用时,在没有得到结果之前,该调用就不返回。按照这个定义,其实绝大多数函数都是同步调用(例如sin, isdigit 等)。但是一般而言,我们在说同步、异步的时候,特指那些需要其他部件协作或者需要一定时间完成的任务。最常见的例子就是 SendMessage。该函数发送一个消息给某个窗口,在对方处理完消息之前,这个函数不返回。当对方处理完毕以后,该函数才把消息处理函数所返回的 LRESULT值返回给调用者。

异步

异步的概念和同步相对。当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者。以 CAsycSocket类为例(注意,CSocket从CAsyncSocket派生,但是起功能已经由异步转化为同步),当一个客户端通过调用 Connect函数发出一个连接请求后,调用者线程立刻可以朝下运行。当连接真正建立起来以后,socket底层会发送一个消息通知该对象。这里提到执行部件和调用者通过三种途径返回结果:状态、通知和回调。可以使用哪一种依赖于执行部件的实现,除非执行部件提供多种选择,否则不受调用者控制。如果执行部件用状态来通知,那么调用者就需要每隔一定时间检查一次,效率就很低(有些初学多线程编程的人,总喜欢用一个循环去检查某个变量的值,这其实是一种很严重的错误)。如果是使用通知的方式,效率则很高,因为执行部件几乎不需要做额外的操作。至于回调函数,其实和通知没太多区别。

阻塞

阻塞调用是指调用结果返回之前,当前线程会被挂起。函数只有在得到结果之后才会返回。有人也许会把阻塞调用和同步调用等同起来,实际上他是不同的。对于同步调用来说,很多时候当前线程还是激活的,只是从逻辑上当前函数没有返回而已。例如,我们在CSocket中调用Receive函数,如果缓冲区中没有数据,这个函数就会一直等待,直到有数据才返回。而此时,当前线程还会继续处理各种各样的消息。如果主窗口和调用函数在同一个线程中,除非你在特殊的界面操作函数中调用,其实主界面还是应该可以刷新。socket接收数据的另外一个函数recv则是一个阻塞调用的例子。当socket工作在阻塞模式的时候,如果没有数据的情况下调用该函数,则当前线程就会被挂起,直到有数据为止。

非阻塞

非阻塞和阻塞的概念相对应,指在不能立刻得到结果之前,该函数不会阻塞当前线程,而会立刻返回。
对象的阻塞模式和阻塞函数调用
对象是否处于阻塞模式和函数是不是阻塞调用有很强的相关性,但是并不是一一对应的。阻塞对象上可以有非阻塞的调用方式,我们可以通过一定的API去轮询状态,在适当的时候调用阻塞函数,就可以避免阻塞。而对于非阻塞对象,调用特殊的函数也可以进入阻塞调用。函数select就是这样的一个例子。


转自互联网

Mysql备份与恢复

1
2
3
4
5
6
7
8
备份一个数据库
mysqldump -u username -p dbname table1 table2 ...-> BackupName.sql
备份多个数据库
mysqldump -u username -p --databases dbname2 dbname2 > Backup.sql
备份所有数据库
mysqldump -u username -p -all-databases > BackupName.sql
还原使用mysqldump命令备份的数据库
mysql -u root -p [dbname] < backup.sq

记忆体化的装饰器

我们先看一个斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def fib(i):
if i<2:return 1
return fib(i-1)+fib(i-2)
print(fib(10)) #没问题
print(fib(100)) #似乎挂掉了
我们再看看加了记忆体化的装饰器的版本
from functools import wraps
def memo(func):
cache={}
@wraps(func)
def wrap(*args):
if args not in cache:
cache[args]=func(*args)
return cache[args]
return wrap
@memo
def fib(i):
if i<2:return 1
return fib(i-1)+fib(i-2)

试着再运行一次?没问题了吧?
那么这个装饰器函数有什么用?
我们举个例子,我们执行fib(6)的时候,普通情况下函数的调用是这样的




其实思路很简单,就是把递归调用的函数用一个空间存储起来。从而函数的调用变成了如下:


每天一道编程题——构造回文

给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?输出需要删除的字符个数。

输入描述:
输入数据有多组,每组包含一个字符串s,且保证:1<=s.length<=1000.
输出描述:
对于每组数据,输出一个整数,代表最少需要删除的字符个数。

输入例子:
abcda
google
输出例子:
2
2

其实就是一个最长公用子序列(LCS)问题。
先看看LCS的算法吧
(关于装饰器memo,详情请看记忆体化的装饰器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'''
递归版
'''
def rec_lcs(a, b):
'''
思路:从字符串的末尾开始,逐个匹配,不符合的砍掉。
'''
@memo
def L(i, j):
if min(i, j) < 0: return 0 # 越界
if a[i] == b[j]: return 1 + L(i - 1, j - 1) # match得到的,左右各-1,结果+1,继续递归
return max(L(i - 1, j), L(i, j - 1)) # 不符合的砍掉。砍掉左边或右边
return L(len(a) - 1, len(b) - 1)
print rec_lcs('spock', 'asoka')
# 3

运行过程如图所示




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
迭代版
'''
def lcs(a, b):
'''
cur[i-1]对应递归版本的L(i-1,j)
pre[i],pre[i-1]对应递归版本的L(i,j-1)与L(i-1,j-1)
'''
n, m = len(a), len(b)
pre, cur = [0] * (n + 1), [0] * (n + 1)
for j in range(1, m + 1):
pre, cur = cur, pre
for i in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[i] = pre[i - 1] + 1
else:
cur[i] = max(pre[i], cur[i - 1])
return cur[n]

运行过程如图所示




原题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def lcs(a, b):
'''
cur[i-1]对应递归版本的L(i-1,j)
pre[i],pre[i-1]对应递归版本的L(i,j-1)与L(i-1,j-1)
'''
n, m = len(a), len(b)
pre, cur = [0] * (n + 1), [0] * (n + 1)
for j in range(1, m + 1):
pre, cur = cur, pre
for i in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[i] = pre[i - 1] + 1
else:
cur[i] = max(pre[i], cur[i - 1])
return cur[n]
if __name__=='__main__':
while True:
try:
a=raw_input()
A = [i for i in a.strip()]
print len(A)-lcs(A,list(reversed(A)))
except:
break


来自腾讯2017暑期实习生编程题

每天一道编程题——年终奖

小东所在公司要发年终奖,而小东恰好获得了最高福利,他要在公司年会上参与一个抽奖游戏,游戏在一个66的棋盘上进行,上面放着36个价值不等的礼物,每个小的棋盘上面放置着一个礼物,他需要从左上角开始游戏,每次只能向下或者向右移动一步,到达右下角停止,一路上的格子里的礼物小东都能拿到,请设计一个算法使小东拿到价值最高的礼物。
给定一个6
6的矩阵board,其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值,保证每个礼物价值大于100小于1000。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getMost(border):
each_path = []
col = len(border[0])
raw = len(border)
def most_momey(i=0, j=0, the_sum=0):
if j < col - 1:
most_momey(i, j + 1, border[i][j] + the_sum)
if i < raw - 1:
most_momey(i + 1, j, border[i][j] + the_sum)
if i == raw - 1 and j == col - 1:
each_path.append(the_sum + border[i][j])
else:
return
most_momey()
return max(each_path)

来自京东2016研发工程师编程题
P.s:某日坐86号公交去玩耍的时候想起之前柏雄大神说过的这道题,然后在公交上写写画画理清大概思路,然后今晚回来才把它写出来。拖延症啊。。。(逃

|