剑指offer--algorithm5

最近开始尝试告别手机，缩短与手机接触的时间，买了一个随身包，用来装书，在地铁里把这些散碎的时间利用起来。

题9--数值的整数次方

本题的关键有三点

• 考虑到指数运算的边界问题
• 如何减少循环的次数，从而提高指数运算的效率
• 利用右移和位与运算方法，来代替除以2和求余的运算，将代码进行优化

image.png
image.png
image.png
image.png
image.png

下面为代码：

class Solution:
    def power(self, base, exponent):
        if exponent == 0:
            return 1
        if exponent == 1:
            return base
        if exponent == -1:
            return 1/base
        result = self.power(base, exponent >> 1)
        result *= result
        if (exponent & 0x1) == 1:#奇数次幂
            result *= base
        return result



def main():
     s=Solution()
     print (s.power(2,3))
     
if __name__=='__main__':
    main()

题10--从1打印到最大数
题目：输入一个数，即从1打印到以该数为最大位数的值，比如3，则从1打印到999

书中对于本题给出了两种解题的思路，最为简单的思路即是我们在数字前面补0，发现n位十进制的数实际上就是n个从1到9的数的全排列 ------**巧妙利用递归不仅可以使得代码简洁，而且也更加的有效

下面为代码：

"""
本题的思路非常有趣，注意掌握
递归的使用
"""

class solution(object):
    def __init__(self,n):
        self.n=n 
    def print_number(self,number):
        isbeginning0=True#flag的设立，用于判断最前边的数字是否为0
        len_number=len(number)
        for i in range(len_number):
            if isbeginning0 and number[i]!=0:#当遍历后发现有不为0的数存在
                isbeginning0=False
            if not isbeginning0:
                print ('%s'%number[i],end='')#python3中end的用法是结尾不加换行符，这样做可以将不为0的数字全部串联起来
        print ('')
    def number_recursion(self):#开始构造，思路是将数字问题转化为字符串
        if self.n<0:
            return None 
        number=['0']*self.n#构造一个n位的字符串
        for i in range(10):
            number[0]=str(i)#先确定数字最高位的值，且转化为字符串
            self.print1tomax(number,0)#第一次递归
    def  print1tomax(self,number,index):
        if index==(self.n-1):#当索引到达最低位的时候
            self.print_number(number)#打印该数字
        else:
            for i in range(10):
                number[index+1]=str(i)
                self.print1tomax(number,index+1)#第二次递归
                


        
def main():
    test=solution(3)
    test.number_recursion()
    
    
    
if __name__=='__main__':
    main()

题11--在O(1)时间内删除链表的节点
删除链表的节点，首先想到的思路就是顺序检索，然后找到要删除的节点，随之删除。但是这样的时间 复杂度为O(n),书中对于此也有所解释

image.png
那为什么我们一般只会想到这个思路呢？
image.png
那是否一定要得到我们所要删除的节点的前一个节点才能进行删除工作呢？答案也是否定的，这就是O(1)思路的由来
image.png
当然，除了这些之外，还要考虑到边缘问题 image.png

下面为代码注释部分：

class node(object):
    def __init__(self,x=None):
        self.value=x#节点的值
        self.next=None#节点的指向   
    def logg(self):#用于看清链表的结构
        while self is not None:
            print ('value',self.value)
            self=self.next
    
class solution(object):
    def __del__(self):#用于删除节点的函数
        self.value=None
        self.next=None
    def delatenode(self,nodehead,node_delete):#两个参数，一个是头结点，一个是要删除的节点
        if not nodehead or not node_delete:#当没有检测到这样的头结点或者要删除的节点的时候
            return None
        if node_delete.next!=None:#当要删除的节点有后续节点时
            n_next=node_delete.next#实例化要删除节点的后续节点
            node_delete.next=n_next.next#将要删除节点的指针指向原先它的下一个节点的指针指向
            node_delete.value=n_next.value#将要删除的后续节点的值赋值给要删除的节点本身，形成覆盖
            n_next.__del__()#删除原本要删除的节点的后一个节点
        elif nodehead==node_delete:#当要删除的节点就是头节点的时候
            nodehead.__del__()
            nodehead.__del__()
        else:#表明要删除的节点为尾部节点，只能遍历
            phead=nodehead#进行一次实例性的赋值
            while phead.next!=node_delete:#当遍历的下一个节点不是尾部节点的时候
                phead=phead.next#向前遍历
            phead.next=None#一直遍历到倒数第二个节点的时候，将其后续的节点转化为None
            node_delete.__del__()#最后切掉原本要删除的节点，即是原来的尾节2点
            
            
            
        

            
    




def main():          
    n1=node(1)
    n2=node(2)
    n3=node(3)
    n4=node(4)
    n1.next=n2
    n2.next=n3
    n3.next=n4  
    n1.logg()#这个实例调用很重要
    #s=solution()
    #s.delatenode(n1,n2)
    
        
                
if __name__=='__main__':
    main()

雷布斯的故事告诉我们--1.之前他说 只有愚笨的人才没日没夜的工作，当上市后，福布斯排第5的时候，我知道又一次被骗了， 不要肆意玩耍却活在别人大智若愚的谎言里。