python装饰器完整写法

在24中设计模式中有装饰模式,该模式的思想很简单,装饰物和被装饰物继承共同的类,然后装饰物中包含被装饰物的引用,这样就可以一层层进行装饰——可以有很多层装饰。 python中的装饰器跟这一模式类似,可以对方法进行装饰。比如对已有的函数要在其前后加上相应的预处理和后处理功能,可以使用装饰器方便的完成这一过程。 下面首先通过一个例子说明python中装饰器的用法。 假设有一个发送消息的方法sendMs …

Continue reading

[leetcode题解]215.Kth Largest Element in an Array(数组中找第k大数)

leetcode,215,Kth Largest Element in an Array,给定一个包括若干元素的数组以及一个k,要求在数组中找出第k大的数。 通常的思路是排序,然后可以快速找到第k大的数,时间复杂度o(nlogn)。比较好的方法是借助快排的思想,一次轴分,可以以o(n)的时间复杂度找到第k大数。 c++代码: class Solution { public: //author:凌风 …

Continue reading

[pat题解]1074.Reversing Linked List(25)

本题要求对一个链表进行分组逆置,给定K,每K个元素为一组,将组中元素逆置,如果最后一组元素不足K个,则不做处理。 本题个人做法为使用map来组织链表结构,可以方便的进行查询和处理。 c++代码如下:  #include <algorithm> #include <cstdio> #include <iostream> #include <vect …

Continue reading

[leetcode题解]143. Reorder List(链表重排序)

leetcode第143题,recorder list,属于linked-list相关的题目。 题目给定一个单链表,然后要求按给定的顺序重新排列所有元素,要求在原地做,而且不能修改节点中的值,只能修改节点的插入顺序。重排序的规则如下示例: L:a0->a1->a2->a3…..->an 将其修改为L:a0->an->a1->an-1->& …

Continue reading

[leetcode题解]2.Add Two Numbers

leetcode,2,Add Two Numbers,给定两个单链表,将两个单链表从左到右进行相加,题目中已知不会出现前导0。本题可以直接对两单链表同时进行遍历相加即可,保留一个进位,检测最后是否要进行正确进位,python和c++两种语言写,代码如下: python代码 class Solution(object): def addTwoNumbers(self, l1, l2): “”” :t …

Continue reading

[leetcode题解]19.Remove Nth Node From End of List(删除倒数N个元素)

leetcode,19,Remove Nth Node From End of List,给定一个单链表,删除倒数第N个元素,要求进行一遍遍历即可。思路是利用两个指针,一个提前走N步,然后另一个指针指向开头,两个指针同时走,当前面的指针到尾部时,后面的指针正好位于要删除的元素位置。为了得到要删除位置的前一个位置,可以加入一个预头,然后,前面的指针从头开始,后面的指针从预头开始。 c++代码: cl …

Continue reading

[leetcode题解]21.Merge two Sorted Lists(两排序链表合并)

leetcode,21,Merge Two Sorted Lists,单链表合并问题,合并两个已排序链表为一个完整的已排序链表。 直接使用两个指针依次比较其中值大小即可,小的插入,并且指针后移,最后不要忘记把剩下的非空链表加入链尾。 此题的升级版本为leetcode,23,Merge K Sorted Lists.  c++代码: class Solution { public: Lis …

Continue reading

[leetcode题解]23.Merge K Sorted Lists(多链表合并)

leetcode,23题,Merge K Sorted Lists,多排序链表合并为一个有序链表问题。可以直接使用priority_queue或者heap。 多个链表以vector形式组织,vector中可能含有空链表,所以建堆或者初始化优先队列之前先对vector进行过滤,将空链表过滤掉。 注意优先队列的写法,类型,底层容器,以及要用到的比较器,比较器是一个重载了括号操作符的普通类。 c++题解 …

Continue reading

[leetcode题解]24.Swap Nodes in Pairs(节点交换)

leetcode 第24题,将链表中相邻元素位置颠倒,题目要求不能改变元素节点中元素的值,只能改动节点位置。也就是要求在链表中删除插入。 python代码如下: # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = No …

Continue reading

[随手写]统计英文文本中每个单词出现的频率

给定一个文本文件,内部为纯英文文本即不会包含中文以及中文符号,要求统计出其中各不同单词的频率。 主要是过滤掉数字,英文标点符号,但是一个特例是类似can’t这类的上引号不能过滤掉,另外要注意单词间的分隔符可以为一个或者多个空白字符(空格、制表符、回车符),也可以为换行符或者标点符号。 主要步骤,第一步为从文件读取文本,然后全部转换为小写字母,然后将其中的所有数字和非单词的字符替换成空格 …

Continue reading

[leetcode题解]25.Reverse Nodes in k-Group(链表每k个元素逆置)

这个题很有意思,虽然标的难度为hard,但是其实就是链表相关知识点的一个小综合,比如尾插法,段遍历,双指针操作等。题目给定一个单链表和一个k值,要求将链表中的元素从表头开始每k个元素组成一个组,然后组内的元素进行逆置操作,如果最后一组不满k个元素,则该组中的元素顺序保持不变。特别的,题目中说操作过程中不能改变元素节点的值,只能对整个节点进行操作,这就要求我们要通过链表指针的操作来完成上述过程。 总 …

Continue reading

[leetcode题解]82.Remove Duplicates from Sorted List-II(排序链表保留唯一)

上一篇论文中写了一个排序链表去重的题目解法,那个题目要求对于重复的元素只保留一个,而本题给定一个排序链表,要求把重复的元素全部删除,所以与上个题目有点差异,但是解法可以基本一致,这里对每个元素,判断其是否唯一,如果不唯一就直接删除,如果唯一,那么就将这个唯一的元素拿出来插入新的链表中,最后将新的链表返回去即可。 题意演示 Given 1->2->3->3->4->4- …

Continue reading

[leetcode题解]61. Rotate List(链表旋转)

题目中给定一个单链表和一个数字k,要求将链表循环右移k次,每次将最右边的元素移动到最左边。最简单的思路先找到最后的k个元素的起始位置,然后把这k个元素直接搬到链表最前面并插入即可(可以使用尾插法,当然也可以把最后一个元素记录下来,然后直接将整段插入)。但是这里k的值可能非常大,是链表长度的好几倍,我们要先处理下k值,我们需要的k值是对链表长度取余得到的值,所以这里先写一个方法求得链表的长度,然后k …

Continue reading

[leetcode题解]83.Remove Duplicates from Sorted List(排序链表去重)

题目给定一个单链表,该单链表已排序,要求删除所有重复值的节点。因为链表已排序,所以相同的值的节点都相邻,所以本题是相邻节点去重问题,可以直接两个指针操作即可。比较简单的排序链表去重问题。一种逐个去重,一种把所有重复的找出来,直接去除所有重复元素,两种方法分别是python实现和c++实现。 python代码: class Solution(object): def deleteDuplicates …

Continue reading

wordpress最合适代码高亮编辑器及其配置

比如我写博客的时候通常会在博客中加入很多代码,所以就对代码高亮有很大的需求,以前用过各种插件实现代码高亮,也使用sublime中的highlight非插件的形式实现过代码高亮,比如本篇文章之前的代码高亮都是这个方法实现的,这需要粘贴到sublime,生成html代码,然后再复制回来,非常不方便,后来使用百度的UEditor富文本编辑器,但是它的代码高亮会转义空格,浏览没问题,但是查看页面源码的时候 …

Continue reading

[leetcode题解]86.Partition List(链表分割)

leetcode第86题,partition-list,是一个关于链表分割的题目。题目给定一个单链表和一个数x,要求链表中节点val小于x的节点全部在左边,而大于等于x的节点全部在右边,而且左右两边中的元素分别保持在原链表中的相对位置。总体来说就类似于快排中的partition部分。所以这个的实现可以直接使用快排的中partition方法直接在单链表上更换节点的值就好。 这里使用最原始的思路,就是 …

Continue reading

[leetcode题解]92.Reverse Linked List II(链表部分逆置)

leetcode第92题,reverse-linked-list-ii,题目是一个单链表的题目,给定一个单链表,然后告诉一个区间[n,m],然后要求将链表中第n到m个节点逆序,这里保证n和m是合法的,即1 <= n <= m <= 链表长度,链表的节点id从1开始计数。 思路比较简单,设定两个指针,以前以后,首先数n个节点,然后将后面的m – n个节点进行头插(逆序插 …

Continue reading

[leetcode题解]109.Convert sorted list to binary search tree

leetcode 109,convert sorted list to binary search tree,给定一个已排好序的单链表,将其转换为一棵平衡二叉查找树,平衡二叉查找树要求左右子树的高度差小于等于1,而且左子树上的节点都小于等于当前根节点,有子树上的节点都大于当前根节点。 由于单链表本身就已经排好序了,所以,只要保证左右子树高度满足即可,可以以链表的中心节点为界,将链表一分为二,这样左 …

Continue reading

[转]非CS水硕的2016研发岗位校招总结 = = 互联网求职失败的经验教训

有些事不好好给它画上句号,很容易在脑子里转来转去,几个月的校招经历了大大小小几十家公司的信息量,互联网、银行、金融、IC行业、游戏行业都有尝试,当然岗位都是技术方面的,想着稍微记录下来该清空的就可以清空了,后面可以安心写论文啊学车了。加上今年版上的经验分享帖实在是少,所以想了一会还是总结一下自己的非科班互联网求职之路吧,随便看看好了。 首先反思一下,Lz电气小硕,虽然自认为基础还可以,但是并没有知 …

Continue reading

[leetcode题解]138.Copy List with Random Pointer(linked-list)

leetcode,138.copy list with random pointer. 正常的单链表中只有一个next的指针指向下一个元素的地址,本题给定一个链表,这个链表比较特殊,不仅有指向下一个元素的next指针,还有一个指向链表中随机元素的一个random指针(random pointer)。 题目要求对该链表进行拷贝,在新的拷贝中,元素的链接关系不变,注意这里的拷贝要求的是深拷贝。 由于r …

Continue reading

[leetcode题解]142.Linked List Cycle II(python + c++)

leetcode第142题,linked list cycle ii,前面有道题目是判断单链表是否有环。 本题就是将上个题目进行改进,首先判断是否有环,如果有环则返回环的入口节点,如果没有环的话返回NULL。 本题的解法首先按照上篇文章中提到的快慢指针法来判断环,并返回快慢指针相遇的节点。 然后,将一个指针从头开始,另一个指针从相遇节点开始,一步一步走下去,直到两者相遇的点就是环的入口节点。 直接 …

Continue reading

[leetcode题解]141.Linked List Cycle(链表环问题)

leetcode题解141.Linked list cycle,给定一个单链表,判断该单链表是否有环问题,这个问题蛮简单的,但是在面试中也是经常被问到的,所以要注意一下。解决这道题的思路就是使用两个指针,一个一次走两步,一个一次走一步,如果有环两者必定在某个位置处相遇,只要快的走到了NULL节点,则说明此链表无环。这就是快慢指针找环法,是比较经典的问题。 c++代码如下: class Soluti …

Continue reading

[leetcode题解]147.Insertion Sort List

对单链表的排序,前几天写过一篇文章使用o(nlog(n))的时间复杂度进行排序,当时说可选的方法是利用归并或者快排对单链表进行排序,这个题目同样给定一个单链表,只不过这里要求用插入排序对其进行排序。在数组中我们使用插入排序的时候通常在寻找插入位置的时候是从后向前,这样可以同时查找并把较大的元素后移一位,然后腾出要插入的位置,但是在单链表中就不行了,首先,单链表不能逆向遍历,第二,单链表无需移动,可 …

Continue reading

[pat题解]1005.Spell It Right(map+reduce)

pat 1005.spell it right. 题目给定一个非负的整数,要求把每一位上的数字相加,得到一个和,然后把这个和从高位到低位翻译成英文单词,1对应one,2对应two,3对three,0对应zero,这样依次将每一位表示成一个单词,输出。 给定的这个整数小于等于10^100次方,所以超出了数据类型int的表示范围,所以注意处理,另外题目中说明是非负整数,所以这就要考虑到临界条件0的处理 …

Continue reading

[leetcode题解]148.sort list

leetcode第148题,sort list,题目给定一个单链表,要求用o(nlogn)的时间复杂度对链表进行排序,其实对于单链表的排序可以使用快排,也可以使用归并排序,对于已排序链表的合并由于比较简单,所以这里就使用归并排序实现一下。 设计了一个找链表中间节点的方法halfList,找到中间节点后将链表一分为二,左右各进行归并排序就好了,最后一个合并两个已排序链表的操作就可以了。 下面使用c+ …

Continue reading

[pat题解]1004.Counting Leaves

pat 1004题。 每个家族结构通常表示为一棵家谱树,家谱树种每一带偶尔会有一些人没有后代。也就是树种每一层偶尔会有无子节点的情况。 题目给定一个家谱树,要求统计每一代,也就是树中每一层有多少个节点没有子节点。 家谱树的输入为按标号输入,输入某个节点,然后后面跟着其所有子节点,一次类推。 做法是逐层遍历,累死与层序遍历,统计每一层中的无子节点的节点个数即可,即每层的叶子节点个数,记录层的方法很多 …

Continue reading

[pat题解]1002.A+B for Polynomials

pat第二题,给定两个多项式,计算两个多项式相加后的多项式,多项式的给出示例,指数+对应的系数,计算规则是相同指数的系数相加作为新的系数,例如2x^2 + 3x和-x^2 + 3则得到x^2 + 3x + 3。这里需要注意的点有三个,第一要求按指数降序排列,第二精确到小数点后一位,如果计算中出现系数为0,则该项不应该出现在结果中。尤其是第三点如果忘记过滤掉的话,最后一个case会过不去,所以要记得 …

Continue reading

[pat题解]1003.Emergency

PAT的1003题,题目告诉了一张图,图中有很多城市,给出不同城市之间的通路情况,以及路的距离,每个城市中有一定数量的救援队,现在给定一个源城市和一个目的城市,找一条最短路,是的两城市之间的距离最短,同时保证经过的城市中的救援队总和最大。 所以题目就是个双重条件的最短路问题,第一重条件是距离,第二重条件是救援队的数量,首先保证距离最短,在距离相同的情况下选择救援队数量多的路径。所以可以直接使用df …

Continue reading

[pat题解]1001.A + B

重新开始刷PAT,第一题,最简单的A + B,要求输入两个数A和B,求A+B的值,并对该值做千位分割,即从个位开始,每三位加一个逗号进行隔开,比如10000->10,000,这种格式,因为python中有直接的千位分割的format可用,所以直接用python做了。 python代码: import re if __name__ == '__main__': str = input …

Continue reading

python中正则表达式的使用

程序中经常要对字符串进行处理,处理用户的输入,对文本的编辑等等,都是对字符串的操作,对字符串的操作可以使用正则表达式来进行,正则表达式的使用会使得字符串的处理很方便。 这里就总结下python中的正则表达式,以及主要的用法。 首先\d,\s,\w,. 这四个表达式可以匹配单个字符,其中\d可以匹配任意一个数字0-9,\s可以匹配任意的空白字符,比如空格,tab键等等,\w可以匹配一个数字或者字母, …

Continue reading

[leetcode题解]160.Intersection of Two Linked Lists

leetcode第160题,给定两个链表的头节点,求两个链表是否相交,如果相交则返回相交的首节点,否则返回NULL。 思路是两个指针分别从头开始走,直到一个指针为NULL,这说明另一个链表比较长,而且长的这个链表剩下的节点个数正好是长度超出的节点数。这个时候把长的从头开始走,走的步数为整下的节点个数,这样短的节点从头开始,就能保证两者要走的节点数相同,也就是如果相交,那么两者分别走下去一定会在交点 …

Continue reading

[leetcode题解]203.Remove Linked List Elements

leetcode第203题,remove linked list elements,题目给定一个单链表和一个值,要求将该单链表中所有val与该给定值相等的节点删除,结果返回删除后的链表,原链表中的元素相对位置不变。 例如: Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5 …

Continue reading

[leetcode题解]206-Reverse-Linked-List

简单链表逆置,这个在面试中多次要求被写,是在搞不懂这么简单的问题为什么要放在面试中,直接用头插法就可以了,下面是c++和python代码 c++代码: class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *pre = new ListNode(-1); ListNode *p = head; while …

Continue reading

[leetcode题解]234.Palindrome-Linked-list

leetcode第234题,简单链表操作的题目,题目要求判断给定的单链表是否是回文的,是返回true,否则返回false。 题目比较简单,直接暴力解,通过快慢指针找到中点,然后把前半部分逆置一下,最后把前后向部分判断元素是否依次相等即可,全相等则回文,否则就不是回文。下面用了c++和python同时实现,两者的思路是完全一样的。 c++代码: class Solution { public: bo …

Continue reading

python中多线程及锁的应用

python中的多线程执行可以使用threading模块,导入该模块然后可以利用模块中的多线程类来编写多线程程序,一般涉及到多线程程序的话就避不开锁,因为线程一般是共享进程的资源,所以当多线程要访问进程的资源时,为了保证一致性就要加锁。 在python中多线程实现主要是两种方式:1.直接生成threading.Thread的实例;2.以对象的方式(OOP)实现 1.直接生成threading.Th …

Continue reading

[leetcode题解]237.Delete a node in a linked list-python+c++

leetcode第237题,题目要求写一个函数实现删除链表中的一个节点,该节点以指针给出。一般链表中删除某个节点的时候我们通常是找到要删除节点的前一个节点,然后把当前节点删除掉,但是这里直接给了要删除节点的指针,题目中也说了,该节点不会是尾节点,这样我们就可以把当前节点的内容与当前节点的下一个节点的内容交换,然后删掉下一个节点就可以了。 所以代码比较简单,可以用不同的方法,以下是python和c+ …

Continue reading

逆波兰表达式求解四则运算式

python的内建函数eval能对四则运算的表达式进行求解,这里简单实现下模拟eval,当然没有实现的向eval那么复杂,现在只能处理所有数字均为个位数的四则运算表达式,表达式包括+,-,*,/,(,)和数字(0-9)。实现的过程很简单,就是借助了逆波兰表达式,先把四则运算表达式转换成逆波兰表达式,然后根据逆波兰表达式求解结果。 程序代码如下,代码中已经实现写了文档测试,可以多测几个: #!/us …

Continue reading

python之异常和单元测试及文档测试

python中类似java和c++中一样,建立了一套异常体系,这样允许程序员能够捕获程序中出现的异常,然后简单处理或者继续抛出异常,从而保证程序的健壮性。 异常的语法比较简单,大体框架如下: try: express except oneException: solve exception except twoException solve exception finally: some post …

Continue reading