剑指offer--algorithm6

接下来会在开头简单的整理下月童度河每天所读部分的读书笔记，增加仪式感和思考的精度，抛砖引玉，希望能为看到文章的朋友带来一些生活的启示，认真生活，踏踏实实写代码，复盘代码

• 相爱
  我问他为什么要睡我的房间，他说，人生可贵，我和你在一起的机会不多
  深爱的本质是悲悯
  爱一个人，先让心清爽和温厚起来是首要
  只管走着，不必逗留，去采摘临路的鲜花来保存，因为一路上，花会继续自然地开着......人们应该带着更多的了解来彼此靠近，说，当我靠近你，我心里某些东西开始舞蹈，如果你和我有同样的感觉，或许我们可以相处几天.......人生短暂
  好的关系，应该共行趋向解脱，而不是使彼此陷入更深的轮回，初级的爱是一种深深的束缚和缠绕，高级的爱是得以解脱
• 葬礼
  泰戈尔--像一群思想的鹤鸟，日夜飞向他们的山巢，在我向你合十膜拜之中，让我全部的声明，启程回到它永久的家乡

题12--调整数组顺序奇数位与偶数的前面
关于本题的解题思路书中上进行了示例演示、方法依旧是在数组的前后设立指针

image.png
image.png

在进行解题之前，需要了解位与判断奇偶的方

• 0x开头表示的是16进制，0开头是8进制，无特殊符号的为10进制，0x1表示为00000001
• k&0x1如果得到的结果为1，说明k为奇数，如果为0,说明k为偶数

下面为代码和注释部分，分为两种方法一种是简单的基本方法，另外一种是加入了扩展函数，可以通过改变扩展函数来解决类似的问题（比如：把能被3整除的数放置在不能被三整除的数前面）

方法1
利用位与运算
"""
class solution(object):
    def __init__(self,array,odd=[],even=[]):
        self.array=array#自定义数组
        self.odd=odd#存储奇数的列表
        self.even=even#存储偶数的列表
    def odd_even(self):
        if self.array==[]:
            return None
        if len(self.array)==1:
            return self.array[0]
        for i in self.array:
            if i & 0x1==0:#说明为偶数
                self.even.append(i)
            if i & 0x1==1:#s说明为偶数
                self.odd.append(i)
        return self.odd+self.even 
    
    
def main():
    s=solution([1,2,3,4,5,6,7])
    print (s.odd_even())
    

if __name__=='__main__':
    main()

"""
方法2
指针和扩展函数的使用
"""
class solution(object):
    def __init__(self,array):
        self.array=array
    def odd_even(self):#其中func为扩展的功能函数，只写进去函数名字即可
        if len(self.array)==0:#当自定义的数组为空的时候
            return None
        if len(self.array)==1:#当自定义的数组为1的时候
            return self.array[0]
        a_begin=0#第一个指针设定在头部
        a_end=len(self.array)-1#第二个指针设定在尾部
        while a_begin<a_end:#当前指针的索引值小于后指针的索引值的时候，说明换位还没有结束
            while a_begin<a_end and not self.is_even(self.array[a_begin]):#当前指针的索引值小于后指针的索引值且，对应的值不是偶数时
                a_begin+=1#前移一位
            while a_begin<a_end and self.is_even(self.array[a_end]):#当前指针的索引值小于后指针的索引值且，对应的值是偶数时
                a_end-=1
            if a_begin<a_end:#当进行了前边的指针移动后，如果前指针的索引还小于后指针的索引的时候
                self.array[a_begin],self.array[a_end]=self.array[a_end],self.array[a_begin]#互换位置
        return self.array
    def is_even(self,n):
        return not n&0x1 #n&0x1默认的输出值为1，因此该函数返回的正向结果是偶数，即偶数为True,奇数为False
def main():
    s=solution([1,2,3,4,5,6,7])
    #print (type(s.odd_even()))
    print (s.odd_even())
    
if __name__=='__main__':
    main()

在进行下一题的切换之前，进行一些概念的陈述

• 鲁棒性（Robust）
  指的是程序能够判断输入是否合乎规范要求，并对不合要求的输入予以合理的处理。容错性是鲁棒性的一个重要的特点
  本质上就是要多考虑边界性的问题

题13--链表中倒数第k个节点
输入一个链表，输出链表的第k个节点
刚开始的时候会想到先遍历到链表的最后，然后再回溯k步，但是，单向链表的只有从前往后的指针，但是没有从后往前的指针，所以此思路对于单向链表行不通

那么书中提供了两种思路第一就是需要遍历链表两次

image.png

正如上边所讲的，如果面试官需要你只遍历一次单向链表，那该是怎样的思路呢？本题的思路十分的巧妙和新奇，书中是这样描述的

image.png
image.png

有了以上的思路后，下面为代码和注释部分：

"""
遍历单线链表一次
输出倒数第k个节点
"""
class node(object):#定义一个单向链表
    def __init__(self,value=None,next=None):
        self.value=value
        self.next=None
        



       
class solution(object):
    def printk_node(self,head,k):#两个变量，一个是链表头，即是第一个指针的起始位置，k为要输出的节点的倒数第k个的位置
        if head==None or k<=0:#首先考虑到边界问题
            return None
        pointer_ahead=head#首先将前指针实例化为表头
        pointer_behind=None#初始化第二个指针，因为第一个指针还没有向前移动，所以第二个指针初始化为None
        for i in range(k-1):#第一个指针开始移动
            if pointer_ahead.next!=None:
                pointer_ahead=pointer_ahead.next
            else:
                return pointer_ahead.value
        pointer_behind=head#当第一个指针移动K-1步的时候，第二个指针从表头开始准备遍历
        while pointer_ahead.next!=None:#说明还没遍历到链表的尾部
            pointer_ahead=pointer_ahead.next#第一个指针继续后移
            pointer_behind=pointer_behind.next#第二个指针也后移
        return pointer_behind#最终返回该节点，就是我们要找的倒数第k个节点
    
        
 



       
def main():
    n1=node(1)
    n2=node(2)
    n3=node(3)
    n4=node(4)
    n5=node(5)
    n1.next=n2
    n2.next=n3
    n3.next=n4
    n4.next=n5
    s=solution()
    print (s.printk_node(n1,1).value)
    
if __name__=='__main__':
    main()

今天的结语是： persistence、 persistence、 persistence！