发表于 | 分类于 |
最长无重复子字符串练习题

任务描述：对于一个字符串，设计一个算法，找到字符串的最长无重复子串长度

输入：”aabcb”, 5
返回：3

思路：先从第一个字符开始往后遍历，当遇到第一个重复字符时停止遍历，记录此时字符串长度。然后从第二个字符开始往后遍历，遇到重复字符时停止遍历，记录此时字符串长度，一直到最后从最后一个字符遍历。返回所有记录长度中最大的一个值。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class DistinctSubstring:
    def longestSubstring(self, A, n):
        # write code here
        max_len = 0
        for i in range(n):
            tem_str = ""
            tem_len = 0
            for j in range(i, n):
                if A[j] not in tem_str:
                    tem_str += A[j]
                    tem_len += 1
                    max_len = max(max_len, tem_len)
                else:
                    max_len = max(max_len, tem_len)
                    break
        return max_len

发表于 | 分类于 |
判断二叉树B是否为二叉树A的子树

任务描述：对于两棵彼此独立的二叉树A和B，请编写算法，检查A中是否存在一颗子树与B树的拓扑结构完全相同。给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。

思路：可以先将二叉树A与二叉树B序列化，转化为字符串，若树B是树A的子树的话B序列化后的字符串则是A字符串的子字符串。python中的in语法可以方便做到这一点。

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class IdenticalTree:
    def chkIdentical(self, A, B):
        # write code here
        StringA = self.serialize(A)
        StringB = self.serialize(B)
        if StringB in StringA:
            return True
        else:
            return False

    def serialize(self, tree):
        if tree is None:
            return "#"
        serial = str(tree.val)
        serial += self.serialize(tree.left)
        serial += self.serialize(tree.right)
        return serial

发表于 | 分类于 |
按层打印二叉树

任务描述：有一课二叉树，设计一个算法，按照层次打印这棵二叉树。给定二叉树的根节点root，返回打印结果数组，结果按照每一层一个数组进行储存，数组排列顺序按照从上到下，数组内元素顺序按从左往右。

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class TreePrinter:
    def printTree(self, root):
        # write code here
        if root is None:
            return []
        else:
            queue = [root, "#"]
            res = []
            temp = []
            while queue:
                cur = queue.pop(0)
                if cur == "#":
                    res.append(temp)
                    temp = []
                else:
                    temp.append(cur.val)
                    if cur.left:
                        queue.append(cur.left)
                    if cur.right:
                        queue.append(cur.right)
                    if queue[0] == "#":
                        queue.append("#")
            return res[:-1]

发表于 | 分类于 |
任务：判断两个字符串是否互为变形词

任务描述：对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词。设计一个算法，检查两个给定字符串是否互为变形词。

输入：”abc”, 3, “bca”, 3
返回： true

思路：利用python内建字典数据结构给字符串A和B分别建立自己的空字典，分别遍历他们的字符，用字典的key保存出现过的字符，用字典对应的value保存该字符出现的次数。若A，B分别遍历完后得到的字典相同，则A和B互为变形词。

python实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Transform:
    def chkTransform(self, A, lena, B, lenb):
        # write code here
        if lena != lenb:
            return False
        dicA = self.counter(A, lena)
        dicB = self.counter(B, lenb)
        if dicA != dicB:
            return False
        else:
            return True

    def counter(self, A, lena):
        dic = {}
        for i in A:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        return dic
Python内置计数器

查询资料后发现Python内建模块中有相关计数器的实现

1
2
3
4
5
6
7
>>> from collections import Counter
>>> c = Counter()
>>> for i in "sdfsdfawerxcvwdf":
...     c[i] += 1
...
>>> c
Counter({'d': 3, 'f': 3, 's': 2, 'w': 2, 'a': 1, 'c': 1, 'e': 1, 'r': 1, 'v': 1, 'x': 1})

发表于 | 分类于 |

最近希望能够弥补一下数据结构与算法相关基础知识，便先尝试用python去实现常见的几种基础排序算法,实现代码归纳如下。

冒泡排序
1
2
3
4
5
6
7
8
def bubbleSort(nums):
    count = len(nums) - 2
    while count > 0:
        for i in range(count + 1):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
        count -= 1
    return nums
选择排序
1
2
3
4
5
6
def insert_sorted(a_list):
    for i in range(len(a_list) - 1):
        for j in range((i + 1), len(a_list)):
            if a_list[i] > a_list[j]:
                a_list[i], a_list[j] = a_list[j], a_list[i]
    return a_list
归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def mergeSort(A, n):
    # write code here
    if n <= 1:
        return A
    num = int(n / 2)
    left = mergeSort(A[:num], len(A[:num]))
    right = mergeSort(A[num:], len(A[num:]))
    return merge(left, right)


def merge(list1, list2):
    result = []
    i, j = 0, 0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
    result += list1[i:]
    result += list2[j:]
    return result
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
def quickSort(aList):
    if len(aList) <= 1:
        return aList
    else:
        smaller = []        
        bigger = []
        piv = aList.pop(0)
        for i in aList:
            if i <= piv:
                smaller.append(i)
            else:
                bigger.append(i)
        return quickSort(smaller) + [piv] + quickSort(bigger)

发表于 | 分类于 |
遍历字典
1
2
3
d = {"x":1, "y":2, "z":3}
for key, value in d.items():
	print key, "corresponds to ", value
并行迭代
1
2
3
4
5
6
7
8
names = ["ych", "cpp", "ws"]
ages = [12, 14, 54]

>>> zip(name, ages)
[("ych", 12	), ("cpp", 14), ("ws", 54)]

for name, age in zip(names, ages):
    print name, "is", age, "years old"
使用for循环同时迭代索引
1
2
for index, item in enumerate(some_list):
    print "index: ", index, "item: ", item

发表于 | 分类于 |

最近在写一个拉钩网招聘信息的简单爬虫。爬取到了信息之后希望能够储存在excel文件当中方便查看。谷歌了一会后找到了一个相关模块xlwt，用来将python数据写入外部excel文件，记录下用到的基础功能。

导入模块
import xlwt
新建一个excel文件
myfile = xlwt.Workbook()
新建一个sheet
sheet = myfile.add_sheet("sheet1", cell_overwrite_ok=True)

在myfile文件中新建一个叫”sheet1”的新sheet，后面的cell_overwrite_ok
参数表示允许覆盖写入。即sheet1当中加入已经存在内容，会覆盖原来的内容写入。

往sheet中写入内容
sheet.write(0, 0, "test")

表示往第0行第0列写入“test”字符串

关闭文件
myfile.save("filename.xls")

最后一定记得关闭文件完成写入过程

发表于 | 分类于 |

最近几天在学习爬虫，想把拉钩网上面关于python的招聘信息全部爬下来方便查看。先去github上面搜索了下其他人的代码，很多代码都用到了多线程模块，目前知识储备还不够，看的有些吃力。于是便准备自己写一个简单的爬虫当作练手。在写的过程中，学习了requests模块，重温了beautifulsoup模块的知识。

Requests模块的基本用法

发送请求

get请求

>>> r = requests.get(url)

Post请求

>>> r = requests.post(url)
为url传递参数
>>> payload = {"key1": "value1", "key2": "value2"}
>>> r = request.get(url, params = payload)
读取相应内容
>>> r = requests.get(url)
>>> r.text

Requests会自动解码来自服务器的内容。大多数unicode字符集都能被无缝地解码。

定制请求头部
>>> payload = {'key1': 'value1', 'key2': 'value2'}
>>> r = requests.post("http://httpbin.org/post", data=payload)
>>> print r.text

发表于 | 分类于 |
接受用户输入
1
2
3
4
5
6
7
8
9
import java.uti.Scanner;

public class Demo {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in); //创建Scanner对象
		System.out.println("请输入：");
		int num = input.nextInt(); //获取用户输入的整数，并保存在num变量
	}
}
数组

Java 中数组操作需要四个步骤：

1.声明数组

1
2
3
int[] scores;  //声明一个类型为整型的数组
double height[]; //声明一个类型为浮点型的数组
String[] name; //声明一个类型为字符串的数组

2.分配空间

1
scores = new int[5]; //长度为5的整数型数组

或者将两个步骤合并，在声明数组的同时为他们分配空间

1
int[] scores = new int[5];

3.赋值

1
2
scores[0] = 89;
scores[1] = 79;

通过下标直接访问

直接将三步合并操作

1
int [] scores = {78, 91, 84, 68};

发表于 | 分类于 |

以下笔记部分参考廖雪峰的博客

Python的内置装饰器@property负责把一个方法变成属性调用的

1
2
3
4
5
6
7
8
9
10
11
12
13
class Student(object):

    @property
    def score(self):
        return self._score

    @score.setter
    def score(self, value):
        if not isinstance(value, int):
            raise ValueError('score must be an integer!')
        if value < 0 or value > 100:
            raise ValueError('score must between 0 ~ 100!')
        self._score = value
1
2
3
4
5
6
7
8
>>> s = Student()
>>> s.score = 60 # OK，实际转化为s.set_score(60)
>>> s.score # OK，实际转化为s.get_score()
60
>>> s.score = 9999
Traceback (most recent call last):
  ...
ValueError: score must between 0 ~ 100!