剑指offer66题（Python）—

本文主要是介绍剑指offer66题（Python）——第十天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

55、构建乘积数组

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

【思路】如果没有不能使用除法的限制,可以用公式B[i]=A[0]*A[1]*.....*A[n-1]/A[i]表示,使用除法时要特别注意A[i]等于0的情况。

可以把B[i]=A[0]*A[1]*.....*A[i-1]*A[i+1]*.....*A[n-1].看成A[0]*A[1]*.....*A[i-1]和

A[i+1]*.....A[n-2]*A[n-1]两部分的乘积。因此，数组B可以用一个矩阵来创建。在图中，B[i]为矩阵中第i行所有元素的乘积.

转自：点击打开链接

# -*- coding:utf-8 -*-
class Solution:def multiply(self, A):# write code hereans = []_len = len(A)prod = 1for i in range(_len):ans.append(prod)prod *= A[i]prod = 1for i in range(len(A)-1, -1, -1): #range(start=None, stop=None, step=None)ans[i] *= prodprod *= A[i]return ans

56、删除链表中重复的点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def deleteDuplication(self, pHead):# write code hereif pHead is None or pHead.next is None:return pHeadhead1 = pHead.nextif head1.val != pHead.val:pHead.next = self.deleteDuplication(pHead.next)else:while pHead.val == head1.val and head1.next is not None:head1 = head1.nextif head1.val != pHead.val:pHead = self.deleteDuplication(head1)else:return Nonereturn pHead

57、判断ip是否合法

参考自：点击打开链接

IPv4的ip地址格式：（1~255）.（0~255）.（0~255）.（0~255）

方法1：正则表达式判定法

最简单的实现方法是构造一个正则表达式。判断用户的输入与正则表达式是否匹配。若匹配则是正确的IP地址，否则不是正确的IP地址。

下面给出相对应的验证ip的正则表达式：

\d表示0~9的任何一个数字

{2}表示正好出现两次

[0-4]表示0~4的任何一个数字

| 的意思是或者

1\d{2}的意思就是100~199之间的任意一个数字

2[0-4]\d的意思是200~249之间的任意一个数字

25[0-5]的意思是250~255之间的任意一个数字

[1-9]\d的意思是10~99之间的任意一个数字

[1-9])的意思是1~9之间的任意一个数字

\.的意思是.点要转义（特殊字符类似，@都要加\\转义）

import re
def check_ip(ipAddr):compile_ip=re.compile('^(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|[1-9])\.(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|\d)$')if compile_ip.match(ipAddr):return True else:  return False

方法2：字符串拆解法

把ip地址当作字符串，以.为分隔符分割，进行判断。

#!/usr/bin/python 
import os,sys 
def check_ip(ipAddr): import sys addr=ipAddr.strip().split('.') #切割IP地址为一个列表 if len(addr) != 4: #切割后列表必须有4个参数 print "check ip address failed!"sys.exit() for i in range(4): try: addr[i]=int(addr[i]) #每个参数必须为数字，否则校验失败 except: print "check ip address failed!"sys.exit() if addr[i]<=255 and addr[i]>=0:  #每个参数值必须在0-255之间 passelse: print "check ip address failed!"sys.exit() i+=1else: print "check ip address success!"
if len(sys.argv)!=2: #传参加本身长度必须为2 print "Example: %s 10.0.0.1 "%sys.argv[0] sys.exit() 
else: check_ip(sys.argv[1]) #满足条件调用校验IP函数

方法3：引入IPy类库

IPy库是一个处理IP比较强大的第三方库

import IPy 
def is_ip(address): try: IPy.IP(address) return Trueexcept Exception as e: return False

58、快速排序

# -*- coding:utf-8 -*-
def QuickSort(myList,start,end):#判断low是否小于high,如果为false,直接返回if start < end:i,j = start,end#设置基准数base = myList[i]while i < j:#如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现while (i < j) and (myList[j] >= base):j = j - 1#如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等myList[i] = myList[j]#同样的方式比较前半区while (i < j) and (myList[i] <= base):i = i + 1myList[j] = myList[i]#做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回basemyList[i] = base#递归前后半区QuickSort(myList, start, i - 1)QuickSort(myList, j + 1, end)return myList

59、二叉树遍历

代码来自：点击打开链接

# -*- coding:utf-8 -*-
class node(object):def __init__(self, data=None, left=None, right=None):self.data = dataself.left = leftself.right = right# 深度
def depth(tree):if tree == None:return 0left, right = depth(tree.left), depth(tree.right)return max(left, right) + 1# 前序遍历
def pre_order(tree):if tree == None:returnprint tree.datapre_order(tree.left)pre_order(tree.right)# 中序遍历
def mid_order(tree):if tree == None:returnmid_order(tree.left)print tree.datamid_order(tree.right)# 后序遍历
def post_order(tree):if tree == None:returnpost_order(tree.left)post_order(tree.right)print tree.data# 层次遍历
def level_order(tree):if tree == None:returnq = []q.append(tree)while q:current = q.pop(0)print current.dataif current.left != None:q.append(current.left)if current.right != None:q.append(current.right)# 按层次打印
def level2_order(tree):if tree == None:returnq = []q.append(tree)results = {}level = 0current_level_num = 1nextlevelnum = 0d = []while q:current = q.pop(0)current_level_num -= 1d.append(current.data)if current.left != None:q.append(current.left)nextlevelnum += 1if current.right != None:q.append(current.right)nextlevelnum += 1if current_level_num == 0:current_level_num = nextlevelnumnextlevelnum = 0results[level] = dd = []level += 1print resultsif __name__ == '__main__':tree = node('D', node('B', node('A'), node('C')), node('E', right=node('G', node('F'))))print'前序遍历：'pre_order(tree)print('\n')print('中序遍历：')mid_order(tree)print('\n')print '后序遍历：'post_order(tree)print('\n')print "层次遍历"level2_order(tree)

60、哈希排序

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希排序时间复杂度为O(n)，它的主体思路是：定义一个数组，每个元素表示它的下标在数列中的个数，最后用循环完成排序。

#include<cstdio>
int a[100];
int main()
{int n;scanf("%d",&n);int i,j,t;for(i=1;i<=n;i++){scanf("%d",&t);a[t]++;}for(i=0;i<100;i++) for(j=0;j<a[i];j++) printf("%d",i);
}

此文部分代码来自牛客网。

这篇关于剑指offer66题（Python）——第十天的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！