由于课程作业的需求,我们要抓取京东商品的信息。在抓取商品的价格、评论人数以及评分的时候遇到一些麻烦。下面提供我的解决方案。

1. 商品价格:

京东上面的商品价格都是用图片显示的,不过庆幸的时,所有数字的字体、大小、颜色都是一样的。简单起见,直接把二维图片变成灰度图,取个反,影射成一维结构后进行切割和匹配。用了一个简单的匹配评估函数,只是对于数字不变的情况总是能得到正确的结果,如果字体、颜色、大小等变了,估计就得不到正确结果了。具体代码如下

#!/usr/bin/python
# coding=utf-8
import Image, sys

class PriceReco:
    img_data = []
    size_x, size_y = 0, 0
    def __init__(self, filename): #加载变换图片
        try:
            img = Image.open(filename)
        except:
            print filename, "load error"
            return 
        self.size_x, self.size_y = img.size
        self.img_data = list(img.convert('L').getdata())
        for i in range(0, len(self.img_data)):
            self.img_data[i] = 255 - self.img_data[i]
        #print filename, "load success, image size is", self.size_x, self.size_y
        #print self.img_data
        
    def getone(self, single): #识别单个数字
        table_value = [
                [189, 378, 945, 1512, 2079, 1701, 1701, 1134, 945, 378, 189], #¥
                [567, 567], # .
                [1323, 1701, 756, 378, 378, 378, 756, 1701, 1323], # 0
                [378, 378, 2079, 2079, 189, 189], # 1
                [567, 945, 756, 756, 756, 756, 945, 945, 567], # 2
                [756, 1134, 378, 567, 567, 567, 1323, 1512, 756], # 3
                [378, 378, 378, 378, 378, 378, 2079, 2079, 189, 189], # 4
                [378, 1512, 1134, 567, 567, 567, 945, 1134, 756], # 5
                [1134, 1512, 945, 756, 567, 567, 945, 1134, 567], # 6
                [189, 189, 378, 756, 945, 945, 945, 756, 378], # 7
                [756, 1512, 1323, 567, 567, 567, 1323, 1512, 756], # 8
                [567, 1134, 945, 567, 567, 756, 945, 1512, 1134], # 9
                ]
        table_key = ['¥', '.', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
        key_id, min_value = 0, 100000
        #print single
        for k in range(0, len(table_key)):
            #print len(table_value[k]), len(single)
            value = 10 * (len(table_value[k]) - len(single)) ** 2
            #print value
            for i in range(0, min(len(table_value[k]), len(single))):
                value += (table_value[k][i] - single[i]) ** 2
            #print value
            if value < min_value:
                key_id, min_value = k, value
                #print "updata: ", key_id, min_value
        #print min_value
        if min_value > 100:
            return 'N'
        else:
            return table_key[key_id]
            
    def recognita(self): #切分和识别图片
        cnt = [0] * self.size_x
        for x in range(0, self.size_x):
            for y in range(0, self.size_y):
                index = y * self.size_x + x
                cnt[x] += self.img_data[index]
        #print cnt
        x = 0
        number = ""
        while x < self.size_x:
            if cnt[x]:
                single = []
                while x < self.size_x and cnt[x]:
                    single.append(cnt[x])
                    x += 1
                number += self.getone(single)
            x += 1
        return number
        
if __name__ == '__main__':
    if len(sys.argv) != 2:
        print "Usage: price_reco image"
    price = PriceReco(sys.argv[1])
    print price.recognita() 

2. 评论人数以及商品评分

这个问题就简单多了,虽然京东304(重定向)了n次,稍加分析就可以知道,直接访问如下url就可以得到评论人数和商品评分了

http://club.360buy.com/ProductPageService.aspx?method=GetCommentSummaryBySkuId&referenceId=$id&callback=GetCommentSummaryBySkuId

其中 $id是商品的id,这个得到很简单。

 

于是就成功攻破京东,o(∩∩)o...哈哈!

 

01图

2012年11月03日 19:12

事情很多,就是不想干。之前看到贴吧上一些帖子用字符做画,感觉挺好玩的。于是试着用python写一个用0和1以及作画的程序。先上几个作品吧!

            01                                                              
           01  1111111111111                                                
       11111   1111111    11111                                             
     0 111111 111111111   11111 1                                           
   1  1111111111111111111111111   1                                         
  0 11111111111111111111111111111110                                        
 1111  111111111 1 111111111111111111                                       
 1 1    111111    1111111111111111111                                       
011111111111111111111111111    1111111                                      
111111111111111111111111111   111111                                        
  111111111111111111111111111111111                                         
  111111111111    11111111111111   111                                      
 11111111111111  11111111111  1                                             
111      111111 1111110          111111111                                  
1111   11111 1   11  1          11111111111    11111111111       1111       
 1111111111 1      0           1111111111111               1  11111111111   
 1  1               11         1111111111                    1111111111111  
                     11         111111                         11111111111  
       0             1 1           1                            1111111111  
      01 0            0 0         1                              11111111   
     01 01             1        0 11111                           1         
      11 1             1 0     1 111111           1111111          1        
   0    1               1 1   1    1              11111111         1        
        1               11   0                       01111          1       
                        11100       111 1111                        1       
                  1 10111 111                                        1      
                    00101  1                                         1      
                          1                                          1      
                          1                                          1      
                          1                                  1 1     1      
                          1                                1  1      011    
                          1                               1110      11      
                          1                                         1       
                           1                                       1       1
                            0                                     1         
                              11                               11           
                                  011                    1111               
                                           1111111101                       

源图片:

萌1

 

                               1111             1111                            
          00000000000001 11                            11100000000000001        
       1000000000000001                                     10000000000000      
       0000000000000                                          1000000000000     
      10000000001                                                10000000001    
      100000000                                                    100000001    
       000000                                                        100000     
        001                                                            000      
         1                                                              0       
       00000000000000000000001                      0000000000000000000000      
      100000001        1000000001               0000000001        1100000001    
     0000001              100000000           100000001               0000001   
    000000        11110       0000001        0000001      011011       100000   
   100000   111     001        0000001      0000001       1001     111  100001  
   00000011                 100000000       1000000011                 1000000  
  1000000              0000000000001         10000000000001             1000000 
 100000000        1000000000001                   1000000000001        000000001
 10000000001   100000000001                            00000000001    1000000000
 000000000000000000001                                     110000000000000000000
 000000000000000001                                            10000000000000000
10000000000001                                                     1000000000000
11  100000                                                             100001  1
 1                                                                             0
 11                                                                            1
  0                                                                           1 
  11                                                                         11 
                                                                             1  
    11                                                                      1   
      0                                                                    0    
       11                                                                 1     
          1                                                            10       
           10                                                         1         
              11                                                   1            
                 111                                            11              
                      1111                                111                   
                              1000011111111111111111100000                      

源图片:

萌2

原理很简单,也没有什么技术含量,就是那个图片变换一下,定两个0和1的阀值,然后就ok了。

 

#!/usr/bin/python
# coding=utf-8
from Tkinter import *
from FileDialog import *
import Image

file_name = 'a.jpg'

def getFileName():
    file_dialog = LoadFileDialog(frame)
    global file_name
    file_name = file_dialog.go()
    try:
        img = Image.open(file_name)
    except:
        print 'openfile error'
    show_img.image = img
    show_img.pack()


def gen():
    try:
        img_o = Image.open(file_name)
    except:
        print 'openfile error'
    img_L = img_o.convert('L')
    size_x, size_y = img_o.size
    size_y = size_y * 80 / size_x / 2
    size_x = 80
#img_L.resize((size_x, size_y)).show()
    data = list(img_L.resize((size_x, size_y)).getdata())

    min_x, min_y = size_x, size_y
    max_x, max_y = 0, 0

    for i in range(0, size_y):
        for j in range(0, size_x):
            index = i * size_x + j
            if data[index] <= 170:
                min_x, min_y = min(min_x, j), min(min_y, i)
                max_x, max_y = max(max_x, j), max(max_y, i)
    genText.delete('1.0', 'end')
    for i in range(min_y, max_y + 1):
        for j in range(min_x, max_x + 1):
            index = i * size_x + j
            if data[index] > 170:
                to = ' '
            elif data[index] > 85:
                to = '1'
            else:
                to = '0'
            genText.insert('end', to)
        #print
        genText.insert('end', '\n')



if __name__ == "__main__":
     
    mainWindow = Tk()
    mainWindow.title()
    #mainWindow.geometry('640x480+0+0')
    
    frame = Frame(mainWindow)
    frame.pack()
    
    fileBotton = Button(frame, text =u"打开文件", command = getFileName)
    fileBotton.pack(side = LEFT)
    
    genBotton = Button(frame, text = u"生成", command = gen)
    genBotton.pack(side = LEFT)
    
    genText = Text(frame, height = 40)
    genText.pack(fill = BOTH, padx = 10, pady = 10)
    
    show_img = Label(frame)
    show_img.pack()
    mainWindow.mainloop()

一个弱爆的google 翻译客户端

2012年10月10日 02:06

在ubuntu下每次想翻译一个词或者一句话都要开浏览器上google翻译,感觉挺麻烦。于是自己写了一个python小脚本(googleTranslate.py),简化这个流程。

 

#!/usr/bin/python
# coding=utf-8

import urllib,urllib2
import sys
if __name__ == '__main__':
    if len(sys.argv) < 2:
        exit()
    tolanguage = 'en'
    text = ""
    if sys.argv[1] == 'en':
        tolanguage = 'en'
    elif sys.argv[1] == 'ch':
        tolanguage = 'zh-CN'
    else:
        text = sys.argv[1]
    for i in range(2, len(sys.argv)):
        text += sys.argv[i] + " "
    values = {'client':'t', 'text': text, 'hl':'en', 'sl':'auto', 'tl':tolanguage, 'ie':'UTF-8', 'oe':'UTF-8', 'multires':'1', 'otf':'2', 'ssel':'0', 'tsel':'0', 'sc':'1'}
    url = 'http://translate.google.cn/translate_a/t'
    request = urllib2.Request(url, urllib.urlencode(values))
    request.add_header('User-Agent', "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.4 (KHTML, like Gecko) Chrome/22.0.1229.79 Safari/537.4")
    response = urllib2.urlopen(request)
    data = response.read()
    #print data
    frags = data[4:data.find("]]")].split("\"],[\"")
    totext = ""
    for frag in frags:
        totext += frag.split("\",\"")[0]
    print totext

将这个脚本放在某个目录下,此处以/path/to为例子。使用以下命令添加脚本可执行属性

chmod +x googleTranslate.py

然后在.bashrc最后添加一行

alias t='/path/to/googleTranslate.py'

于是乎在任何界面下想要翻译词句子,直接ctrl+alt+t,输入

t 想要翻译的词句

即可。默认是将词句翻译成英文,如果需要将其他语言翻译成中文,执行

t ch 想要翻译的词句

即可。方便快捷,o(∩∩)o...哈哈

 

而后觉得写成一个小软件还是很靠谱的,于是又折腾了下python Tkinter,把上面的代码加了一个GUI的外壳。废话少说,上图

GUI的代码也不复杂,顺便也贴了吧,供大家交流。BUG比较多,有待后期改进,谢谢阅读!

#!/usr/bin/python
# coding=utf-8

import urllib, urllib2
from Tkinter import *
from ttk import Combobox
 
def translate():
	tolanguage = languageMap[option.get()]
	text = startText.get('1.0', 'end').encode('utf-8')
	
	values = {'client':'t', 'text': text, 'hl':'en', 'sl':'auto', 'tl':tolanguage, 'ie':'UTF-8', 'oe':'UTF-8', 'multires':'1', 'otf':'2', 'ssel':'0', 'tsel':'0', 'sc':'1'}
	url = 'http://translate.google.cn/translate_a/t'
	request = urllib2.Request(url, urllib.urlencode(values))
	request.add_header('User-Agent', "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.4 (KHTML, like Gecko) Chrome/22.0.1229.79 Safari/537.4")
	response = urllib2.urlopen(request)
	data = response.read()
	print data
	
	frags = data[4:data.find("]]")].split("\"],[\"")
	totext = ""
	for frag in frags:
		totext += frag.split("\",\"")[0]
	
	toText.delete('1.0', 'end')
	toText.insert('1.0', totext.replace("\\n", "\n"))

if __name__ == "__main__":
	
	mainWindow = Tk()
	mainWindow.title(u"Google 翻译 by hustsxh@gmail.com")
	#mainWindow.geometry('640x480+0+0')
	
	frame = Frame(mainWindow)
	frame.pack()
	
	Label(frame, text = u'翻译成:').pack(side = LEFT)
	
	languageMap = {'English': 'en', u'中文简体': 'zh-CN', u'中文繁體': 'zh-TW', u'日本語': 'ja', u'한국의': 'ko', u'Deutsch': 'de', u'русский': 'ru', u'française': 'fr'}
	defaultLanguage = StringVar(frame, 'English')
	option = Combobox(frame, text = defaultLanguage, values = languageMap.keys())
	option.pack(side = LEFT)
	
	transBotton = Button(frame, text =u"翻译", command = translate)
	transBotton.pack(side = LEFT)
	
	startText = Text(mainWindow, height = 15)
	startText.pack(fill = BOTH, padx = 10, pady = 10)
	
	toText = Text(mainWindow, height = 15)
	toText.pack(fill = BOTH, padx = 10, pady = 10)
	
	mainWindow.mainloop()

A “bug”

2012年9月24日 19:06

今天在做codeforces 223B http://codeforces.com/problemset/problem/223/B 的时候遇到一个很隐蔽的“bug”,欣喜之余,把它记录下来。

把遇到的问题提取出来,就是下面这段代码:

#include <iostream>
#include <string>

int main()
{
	std::string str("abc");
	if(-1 < str.length()) {
		std::cout << "Yes" << std::endl;
	} else {
		std::cout << "No" << std::endl;
	}
	return 0;
}

这段代码的输出是Yes还是No呢?

表面上看,str.length()应该是3;-1小于3是true,那么应该输出Yes。

然而你编译运行下这段代码就会发现,它输出的并不是Yes,而是No,为什么呢?

我们看一下str.length()返回的是什么。众所周知,str.length()返回字符串的长度 ,然而关注返回值类型的人比较少,它的类型是size_t,在cstddef中,size_t定义为unsigned int。-1的类型是int,在int和unsigned比较前需要将数据类型提升一致。于是就把-1转化成unsigned类型,而-1在内存中存储为0xffffffff(32位),于是unsigned(-1)=0xffffffff=232-1了,那么表达式232-1<3必然为false,于是输出No

hdu3475,hdoj3475解题报告

2010年10月31日 21:19

发现自己好久好久没有写点东西了。呵呵!……

今天做了下hdu3475http://acm.hdu.edu.cn/showproblem.php?pid=3475,自己用了一种比较诡异的方法,没想法跑到了第一,以62ms的速度领先于第二名(281ms)。于是再这里和大家分享一下。

题目大意:

有一个n*m(1<=n<=100, 1<=m<=10)的矩阵,每一个格子有一盏灯,对于每一盏灯,要不就是开着要不就是关着,现在要你把所有的灯都关掉,每一次操作可以改变每一盏灯的状态(关到开,开到关),问最少要操作几次。对于每一盏灯和他相邻的8盏灯都有可能存在连线。当你改变一盏灯的状态的时候,和他有直接相连的灯都会改变状态。

题目分析:

当然这个题目可以同解方程的方法去做,但是好像时间复杂度过不去,我数学是个菜鸟,不好说多少。

还是讲讲我的方法吧。从题目的数据范围上看,m最多只有10,那就是状态压缩dp了,用2^m个状态表示某一行的灯的状态。但是由于改变某一行中一个灯的状态,可能影响它上一行等的状态,也可能影响下一行的状态,这样,我们至少要记录两行的状态才能进行转移。于是,我们定义数组dp[i=100][state1=1024][state2=1024],来表示第i行以后,第i行的状态为state1,第i+1行的状态为state2,第1至i-1行的状态均为0(所有的灯都关着)的最少操作数。计算一下会发现这样的dp数组肯定是会内存的,所以是要用滚动数组的。

状态转移的时候,用2^m枚举第i+1行的那些灯是进行过操作的(很显然一个灯是不会进行一次以上的操作的),然后进行转移,转移时一定要注意,对第i+1行操作后,第i行灯的状态一定要是全部关掉的。这里完全可以先枚举第i+1行的状态,在根据第i+1行对第i行灯的影响,去确定第i行灯的状态。这样总的空间复杂度为O(2*2^20),时间复杂度为(100*2^10*2^10),可以看到,空间能过得去,但是时间复杂度貌似还是有点勉强的,已经到了10^8。

其实有很多状态都是不可能的,能不能在转移的时候不出现这些状态?于是有了诡异的想法,就是把状态数组的最后一维改成链表,这样,枚举完第i+1行的操作状态后,直接对第i行能全部变成0的状态进行转移,这些都是合法的状态。其实这样做的理论复杂度还比原先方法还高,应为在链表中插入一个元素的时候是要遍历整个链表的,但由于链表元素比较少,真实的效果还是很好的。

这种方法再用于dp数组中合法状态很稀疏的情况还是比较好的,其他情况最会更慢。

/* 
 * File:   hdu-3475.cpp
 * Author: hust_boys
 * Created on 2010年10月31日, 上午10:23
 */

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxsize (1<<10)
using namespace std;

struct Node {
	int to, step;
	Node *next;
} t[2][maxsize * maxsize], *child[2][maxsize];
//链表的元素定义,child相对于dp数组,第一维为2,用于滚动,t数组作为节点池 
 
int street, cnt, n, m, state[101], cp[101][10], cn[101][10], cs[101][10];
//street: 当前处理到的行数
//n,m:行列数
//state:每一行状态压缩后的数值
//cp:第i行,第j列(i从1开始,j从0开始)的灯,对上一层灯的影响,压缩值
//cn: 第i行,第j列的灯,对下一层灯的影响,压缩值
//cs:第i行,第j列的灯,对当前一层灯的影响(包括自己),压缩值 

//插入元素,即状态转移 
void insert(int x, int to, int step) {
	int have = 0, now = street % 2;
	for (Node *p = child[now][x]; p; p = p->next) {
		if (p->to == to) {
			p->step = min(p->step, step);
			have = 1;
			break;
		}
	}
	if (!have) {
		t[now][cnt].to = to, t[now][cnt].step = step;
		t[now][cnt].next = child[now][x];
		child[now][x] = &t[now][cnt++];
	}
}

//dfs产生当前行的状态 
void DFS(int k, int now, int pre, int next, int s) {
	if (k == m) {
		for (Node *p = child[(street - 1) % 2][pre]; p; p = p->next) {
			insert(p->to ^ now, next, p->step + s);
		}
		return;
	}
	DFS(k + 1, now, pre, next, s);
    //不改变第k个的状态 
	DFS(k + 1, now ^ cs[street][k], pre ^ cp[street][k], next ^ cn[street][k], s + 1);
	// 改变第k个的状态 
}

int solve() {
    //初始化 
	cnt = street = 0;
	memset(child[0], 0, sizeof (child[0]));
	insert(0, 0, 0);
	//dp 
	int now;
	for (street = 1; street <= n; ++street) {
		now = street % 2;
		memset(child[now], 0, sizeof (child[0]));
		cnt = 0;
		DFS(0, state[street], 0, 0, 0);
	}
	//获得结果 
	int res = -1;
	for (Node *p = child[now][0]; p; p = p->next) {
		if (p->to == 0) {
			if (res == -1) {
				res = p->step;
			} else {
				res = min(res, p->step);
			}
		}
	}
	return res;
}

void input() {
	char s[30];
	scanf("%d%d", &n, &m);
	gets(s);
	memset(state, 0, sizeof(state));
	memset(cn, 0, sizeof (cn));
	memset(cp, 0, sizeof (cp));
	memset(cs, 0, sizeof (cs));
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			cs[i][j] = 1 << j;
		}
	}
	for (int i = 1; i < n * 2; ++i) {
		gets(s);
		if (i % 2) {
			int now = i / 2 + 1;
			for (int j = 0; j < m; ++j) {
				if (s[j * 2] == 'o') {
					state[now] |= 1 << j;
				}
			}
			for (int j = 1; j < m; ++j) {
				if (s[j * 2 - 1] == '-') {
					cs[now][j - 1] |= 1 << j;
					cs[now][j] |= 1 << (j - 1);
				}
			}
		} else {
			for (int j = 0; j < m; ++j) {
				if (s[j * 2] == '|') {
					cn[i / 2][j] |= 1 << j;
					cp[i / 2 + 1][j] |= 1 << j;
				}
			}
			for (int j = 1; j < m; ++j) {
				if (s[j * 2 - 1] == '/') {
					cn[i / 2][j] |= 1 << (j - 1);
					cp[i / 2 + 1][j - 1] |= 1 << j;
				} else if (s[j * 2 - 1] == '\\') {
					cn[i / 2][j - 1] |= 1 << j;
					cp[i / 2 + 1][j] |= 1 << (j - 1);
				} else if (s[j * 2 - 1] == 'X') {
					cn[i / 2][j] |= 1 << (j - 1);
					cp[i / 2 + 1][j - 1] |= 1 << j;
					cn[i / 2][j - 1] |= 1 << j;
					cp[i / 2 + 1][j] |= 1 << (j - 1);
				}
			}
		}
	}
}

int main(int argc, char** argv) {
	int T;
	scanf("%d", &T);
	for (int test = 1; test <= T; ++test) {
		input();
		int res = solve();
		printf("Case %d: %d\n", test, res);
	}
	return 0;
}