剑指offer66题(Python)——第十天

2024-06-23 23:08
文章标签 python 第十天 offer66

本文主要是介绍剑指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)——第十天的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1088538

相关文章

Python脚本实现自动删除C盘临时文件夹

《Python脚本实现自动删除C盘临时文件夹》在日常使用电脑的过程中,临时文件夹往往会积累大量的无用数据,占用宝贵的磁盘空间,下面我们就来看看Python如何通过脚本实现自动删除C盘临时文件夹吧... 目录一、准备工作二、python脚本编写三、脚本解析四、运行脚本五、案例演示六、注意事项七、总结在日常使用

Python将大量遥感数据的值缩放指定倍数的方法(推荐)

《Python将大量遥感数据的值缩放指定倍数的方法(推荐)》本文介绍基于Python中的gdal模块,批量读取大量多波段遥感影像文件,分别对各波段数据加以数值处理,并将所得处理后数据保存为新的遥感影像... 本文介绍基于python中的gdal模块,批量读取大量多波段遥感影像文件,分别对各波段数据加以数值处

python管理工具之conda安装部署及使用详解

《python管理工具之conda安装部署及使用详解》这篇文章详细介绍了如何安装和使用conda来管理Python环境,它涵盖了从安装部署、镜像源配置到具体的conda使用方法,包括创建、激活、安装包... 目录pytpshheraerUhon管理工具:conda部署+使用一、安装部署1、 下载2、 安装3

Python进阶之Excel基本操作介绍

《Python进阶之Excel基本操作介绍》在现实中,很多工作都需要与数据打交道,Excel作为常用的数据处理工具,一直备受人们的青睐,本文主要为大家介绍了一些Python中Excel的基本操作,希望... 目录概述写入使用 xlwt使用 XlsxWriter读取修改概述在现实中,很多工作都需要与数据打交

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志(Binlog)获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat

利用Python编写一个简单的聊天机器人

《利用Python编写一个简单的聊天机器人》这篇文章主要为大家详细介绍了如何利用Python编写一个简单的聊天机器人,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 使用 python 编写一个简单的聊天机器人可以从最基础的逻辑开始,然后逐步加入更复杂的功能。这里我们将先实现一个简单的

基于Python开发电脑定时关机工具

《基于Python开发电脑定时关机工具》这篇文章主要为大家详细介绍了如何基于Python开发一个电脑定时关机工具,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 简介2. 运行效果3. 相关源码1. 简介这个程序就像一个“忠实的管家”,帮你按时关掉电脑,而且全程不需要你多做

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作(适用于大文件)四、使用 pand

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1,PDF转Word2,PDF转Excel三、前端页面效果展示总结一