元素交换

¶数组

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
并保证奇数和奇数，偶数和偶数之间的相对位置不变。

表面上这是一个很简单的任务,实际上应该夜不难…

但是有意义的事,如何仅在原有的数组之上来进行操作,而不是另外再开放一个空间.

举一个例子.

假设该数组为1,4,5,2,4,5,2

该如何进行操作呢?

我们概念中的交换数组元素的过程应该是这样的.

从第二个元素开始直到最后一个元素为止,如果这个元素为奇数,而前面的数为偶数,那么将这个数和前面的数交换.

这样的过程会将原来的那个数组依次变为

1,5,4,2,4,5,2
1,5,4,2,5,4,2

目前为止,显然没有完全完成任务.

但如果不断这样做,显然是可以成功的,但时间复杂度未免有点高了.

实际上,不难想到,如果放开相邻元素之间的交换,而改为直接插入会更好…

但是这样做又相当于改变了数组的数据结构.

暂时不大理解…

¶链表元素交换

举个例子说,我要反转一个链表,并且返回反转后的链表的头结点.

a->b->c->d->e

如何反转呢.

首先我们要明白一个事实,就是子节点不知道父节点是谁,所以一定有个变量保存着父节点的引用.

比如要将d->e反转为d<-e,只需让e指向d即可.

然而关键是d又怎么指向c呢?

看起来是个很难理解的问题…那就抽象吧…

我们假设上面的链表为L,有个过程X可以将L反转并且得到其头结点.

接下来就是如何拆解X的过程.

我们尝试这样做,将X分为:

X1: 用X将L的子节点所连接的链表反转,并且得到其头结点.
X2: 尾节点指向L的头结点.

看起来这是可行的,再自己看看对于基本情况,也就是输入L为0,1个节点的情况.

0的话返回空,1的话返回该节点

上面的想法是错误的,不应该从后往前推,而应该从前往后推

直接参照别人的代码吧.

 class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        
        last = None
        while pHead:
            tmp = pHead.next
            pHead = last
            last = pHead
            pHead = tmp
 
        return last

¶指针

上面两个例子,跟指针都有关…

你对指针的了解很浅显…

现在仔细梳理一下.

先以链表为例,代码如下

 #!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2018-06-12 11:23:21
# @Author  : yudanqu (943775910@qq.com)
# @Link    : https://www.cnblogs.com/yudanqu/
# @Version : $Id$
 
 
class Node(object):
    """节点"""
 
    def __init__(self, elem):
        self.elem = elem
        self.next = None  # 初始设置下一节点为空
 
'''
上面定义了一个节点的类，当然也可以直接使用python的一些结构。比如通过元组（elem, None）
'''
 
 
# 下面创建单链表，并实现其应有的功能
 
 
class SingleLinkList(object):
    """单链表"""
 
    def __init__(self, node=None):  # 使用一个默认参数，在传入头结点时则接收，在没有传入时，就默认头结点为空
        self.__head = node
 
    def is_empty(self):
        '''链表是否为空'''
        return self.__head == None
 
    def length(self):
        '''链表长度'''
        # cur游标，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count
 
    def travel(self):
        '''遍历整个列表'''
        cur = self.__head
        while cur != None:
            print(cur.elem, end=' ')
            cur = cur.next
        print("\n")
 
    def add(self, item):
        '''链表头部添加元素'''
        node = Node(item)
        node.next = self.__head
        self.__head = node
 
    def append(self, item):
        '''链表尾部添加元素'''
        node = Node(item)
        # 由于特殊情况当链表为空时没有next，所以在前面要做个判断
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
 
    def insert(self, pos, item):
        '''指定位置添加元素'''
        if pos <= 0:
                # 如果pos位置在0或者以前，那么都当做头插法来做
            self.add(item)
        elif pos > self.length() - 1:
            # 如果pos位置比原链表长，那么都当做尾插法来做
            self.append(item)
        else:
            per = self.__head
            count = 0
            while count < pos - 1:
                count += 1
                per = per.next
            # 当循环退出后，pre指向pos-1位置
            node = Node(item)
            node.next = per.next
            per.next = node
 
    def remove(self, item):
        '''删除节点'''
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判断该节点是否是头结点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
 
    def search(self, item):
        '''查找节点是否存在'''
        cur = self.__head
        while not cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

¶数组

¶链表元素交换

¶指针

如何去思考

tips-change-git-log

misaka7690

	class Solution:
	# 返回ListNode
	def ReverseList(self, pHead):
	if not pHead or not pHead.next:
	return pHead

	last = None
	while pHead:
	tmp = pHead.next
	pHead = last
	last = pHead
	pHead = tmp

	return last

	#!/usr/bin/env python
	# -- coding: utf-8 --
	# @Date : 2018-06-12 11:23:21
	# @Author : yudanqu (943775910@qq.com)
	# @Link : https://www.cnblogs.com/yudanqu/
	# @Version : $Id$


	class Node(object):
	"""节点"""

	def __init__(self, elem):
	self.elem = elem
	self.next = None # 初始设置下一节点为空

	'''
	上面定义了一个节点的类，当然也可以直接使用python的一些结构。比如通过元组（elem, None）
	'''


	# 下面创建单链表，并实现其应有的功能


	class SingleLinkList(object):
	"""单链表"""

	def __init__(self, node=None): # 使用一个默认参数，在传入头结点时则接收，在没有传入时，就默认头结点为空
	self.__head = node

	def is_empty(self):
	'''链表是否为空'''
	return self.__head == None

	def length(self):
	'''链表长度'''
	# cur游标，用来移动遍历节点
	cur = self.__head
	# count记录数量
	count = 0
	while cur != None:
	count += 1
	cur = cur.next
	return count

	def travel(self):
	'''遍历整个列表'''
	cur = self.__head
	while cur != None:
	print(cur.elem, end=' ')
	cur = cur.next
	print("\n")

	def add(self, item):
	'''链表头部添加元素'''
	node = Node(item)
	node.next = self.__head
	self.__head = node

	def append(self, item):
	'''链表尾部添加元素'''
	node = Node(item)
	# 由于特殊情况当链表为空时没有next，所以在前面要做个判断
	if self.is_empty():
	self.__head = node
	else:
	cur = self.__head
	while cur.next != None:
	cur = cur.next
	cur.next = node

	def insert(self, pos, item):
	'''指定位置添加元素'''
	if pos <= 0:
	# 如果pos位置在0或者以前，那么都当做头插法来做
	self.add(item)
	elif pos > self.length() - 1:
	# 如果pos位置比原链表长，那么都当做尾插法来做
	self.append(item)
	else:
	per = self.__head
	count = 0
	while count < pos - 1:
	count += 1
	per = per.next
	# 当循环退出后，pre指向pos-1位置
	node = Node(item)
	node.next = per.next
	per.next = node

	def remove(self, item):
	'''删除节点'''
	cur = self.__head
	pre = None
	while cur != None:
	if cur.elem == item:
	# 先判断该节点是否是头结点
	if cur == self.__head:
	self.__head = cur.next
	else:
	pre.next = cur.next
	break
	else:
	pre = cur
	cur = cur.next

	def search(self, item):
	'''查找节点是否存在'''
	cur = self.__head
	while not cur:
	if cur.elem == item:
	return True
	else:
	cur = cur.next
	return False

¶数组

¶链表元素交换

¶指针

微信扫一扫：分享

如何去思考

tips-change-git-log

misaka7690