import time


start_time = time.time()
for a in range(1001):
   for b in range(1001):
       for c in range(1002):
           if a+b+c == 1000 and a*a+b*b == c*c:
               print('a=%d,b=%d,c=%d' % (a, b, c))

end_time = time.time()
print('共耗時(shí)：%f' % (end_time-start_time))

a=0,b=500,c=500
a=200,b=375,c=425
a=375,b=200,c=425
a=500,b=0,c=500
共耗時(shí)：123.326442

Process finished with exit code 0

import time


start_time = time.time()

for a in range(1001):
    for b in range(1001):
        c = 1000-a-b
        if a*a+b*b == c*c:
            print('a=%d,b=%d,c=%d' % (a, b, c))

end_time = time.time()
print('共耗時(shí)：%f' % (end_time - start_time))

a=0,b=500,c=500
a=200,b=375,c=425
a=375,b=200,c=425
a=500,b=0,c=500
共耗時(shí)：0.281858

Process finished with exit code 0

class Node(object):
    """節(jié)點(diǎn)"""

    def __init__(self, item):
        self.item = item
        self.next = None  # 指向下一節(jié)點(diǎn)


class SingleLinkList(object):
    """單向鏈表"""

    def __init__(self):
        self.__head = None  # 頭節(jié)點(diǎn)

    def is_empty(self):
        """鏈表是否為空"""
        return self.__head is None

    def length(self):
        """鏈表長度"""
        cur = self.__head
        count = 0
        while cur is not None:
            cur = cur.next
            count += 1
        return count

    def travel(self):
        """遍歷鏈表"""
        cur = self.__head  # 創(chuàng)建游標(biāo)指向頭節(jié)點(diǎn)
        while cur is not None:
            print(cur.item, end=' ')
            cur = cur.next
        print()  # 換行

    def add(self, item):
        """鏈表頭部添加節(jié)點(diǎn)"""
        node = Node(item)  # 創(chuàng)建節(jié)點(diǎn)
        node.next = self.__head  # 新節(jié)點(diǎn)下個(gè)元素指向頭節(jié)點(diǎn)
        self.__head = node  # 頭節(jié)點(diǎn)指向新節(jié)點(diǎn)

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self.__head
            index = 0
            while index < pos-1:  # 注意這里是pos-1
                index += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        """刪除節(jié)點(diǎn)"""
        cur = self.__head  # 頭節(jié)點(diǎn)
        pre = None  # 前一個(gè)節(jié)點(diǎn)
        while cur is not None:
            if cur.item == item:
                if pre is None:  # 首節(jié)點(diǎn)
                    self.__head = cur.next
                else:  # 中間節(jié)點(diǎn)（或尾節(jié)點(diǎn)）
                    pre.next = cur.next
                break
            # 鏈表繼續(xù)后移
            pre = cur
            cur = cur.next

    def search(self, item):
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

class Node(object):
    """單向鏈表節(jié)點(diǎn)"""

    def __init__(self, item):
        self.item = item
        self.next = None


class SinCycLinkList(object):
    """單向循環(huán)鏈表"""

    def __init__(self):
        self.__head = None

    def is_empty(self):
        return self.__head is None

    def length(self):
        if self.is_empty():
            return 0
        cur = self.__head
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        cur = self.__head
        if self.is_empty():
            return
        while cur.next != self.__head:
            print(cur.item, end=' ')
            cur = cur.next
        print(cur.item)

    def add(self, item):
        node = Node(item)
        cur = self.__head
        if self.is_empty():
            self.__head = node
            node.next = node
            return
        while cur.next != self.__head:
            cur = cur.next
        node.next = self.__head
        self.__head = node
        cur.next = node

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self.add(item)
            return
        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
        node.next = self.__head
        cur.next = node

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            node = Node(item)
            cur = self.__head
            index = 0
            while index < pos-1:
                cur = cur.next
                index += 1
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        # 要刪除的是頭節(jié)點(diǎn)的話需要知道尾節(jié)點(diǎn),，因此先判斷是頭節(jié)點(diǎn)的情況
        if cur.item == item:
            while cur.next != self.__head:
                pre = cur
                cur = cur.next
            # 循環(huán)執(zhí)行完后,，cur為尾節(jié)點(diǎn)
            if pre is None:  # 只有頭節(jié)點(diǎn)
                self.__head = None
            else:
                cur.next = self.__head.next
                self.__head = self.__head.next
        else:
            while cur.next != self.__head:
                if cur.item == item:
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            if cur.item == item:
                pre.next = self.__head

    def search(self, item):
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.item == item:
                return True
            cur = cur.next
        if cur.item == item:
            return True
        return False

class DNode(object):
    """雙向鏈表節(jié)點(diǎn)"""

    def __init__(self, item):
        self.item = item
        self.pre = None
        self.next = None


class DoubleLinkList(object):
    """雙向鏈表"""

    def __init__(self):
        self.__head = None

    def is_empty(self):
        return self.__head is None

    def length(self):
        cur = self.__head
        count = 0
        while cur is not None:
            cur = cur.next
            count += 1
        return count

    def travel(self):
        cur = self.__head
        while cur is not None:
            print(cur.item, end=' ')
            cur = cur.next
        print()

    def add(self, item):
        node = DNode(item)
        if self.is_empty():
            self.__head = node
        else:
            node.next = self.__head
            self.__head.pre = node
            self.__head = node

    def append(self, item):
        if self.is_empty():
            self.append(item)
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            node = DNode(item)
            node.pre = cur
            cur.next = node

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            cur = self.__head
            index = 0
            while index < pos-1:
                cur = cur.next
                index += 1
            node = DNode(item)
            node.next = cur.next
            node.pre = cur
            cur.next.pre = node
            cur.next = node

    def remove(self, item):
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                if cur.pre is None:  # 頭節(jié)點(diǎn)
                    self.__head = cur.next
                else:
                    cur.pre.next = cur.next
                if cur.next is not None:
                    cur.next.pre = cur.pre
                return
            cur = cur.next

    def search(self, item):
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

class Stack(object):
    """棧"""

    def __init__(self):
        """創(chuàng)建一個(gè)新的空棧"""
        self.__list = list()  # 棧底層使用list來實(shí)現(xiàn)

    def is_empty(self):
        """判空"""
        return self.__list == []

    def size(self):
        """返回棧中元素個(gè)數(shù)"""
        return len(self.__list)

    def push(self, item):
        """添加一個(gè)新的元素item到棧頂"""
        self.__list.append(item)

    def pop(self):
        """彈出棧頂元素"""
        if self.is_empty():
            return None
        return self.__list.pop()

    def peek(self):
        """返回棧頂元素"""
        if self.is_empty():
            return None
        return self.__list[self.size()-1]

class Queue(object):
    """隊(duì)列"""

    def __init__(self):
        self.__list = list()  # 使用list實(shí)現(xiàn)隊(duì)列

    def is_empty(self):
        return self.__list == []

    def size(self):
        return len(self.__list)

    def enqueue(self, item):
        """往隊(duì)列中添加一個(gè)元素"""
        self.__list.append(item)

    def dequeue(self):
        """從隊(duì)列頭中取出元素"""
        if self.is_empty():
            return None
        return self.__list.pop(0)

def bubble_sort(alist):
    # 因?yàn)槊芭菖判蛎看螌⒆畲蟮臄?shù)移動到最后,，因此需要n-1次循環(huán)即可，因?yàn)槠渌藕煤?，第一個(gè)即是最小元素
    for i in range(len(alist)-1):  # n-1次循環(huán)
        # 每次循環(huán)旨在將前n-i個(gè)元素中的最大元素放置至最后
        # 由于是兩兩相鄰比較,，即拿到一個(gè)元素與該元素后元素比較，因此循環(huán)至n-i-1即可
        for j in range(len(alist)-i-1):
            # 核心思想為：將大的數(shù)向后移動
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]

def bubble_sort(alist):
    # 因?yàn)槊芭菖判蛎看螌⒆畲蟮臄?shù)移動到最后,，因此需要n-1次循環(huán)即可,，因?yàn)槠渌藕煤螅谝粋€(gè)即是最小元素
    for i in range(len(alist) - 1):  # n-1次循環(huán)
        # 每次循環(huán)旨在將前n-i個(gè)元素中的最大元素放置至最后
        # 由于是兩兩相鄰比較,，即拿到一個(gè)元素與該元素后元素比較,，因此循環(huán)至n-i-1即可
        count = 0  # 定義一個(gè)計(jì)數(shù)器，當(dāng)前后元素發(fā)生位置變化時(shí)加1,，如果最后計(jì)數(shù)器為0,，說明本身就是正序的
        for j in range(len(alist) - i - 1):
            
            # 核心思想為：將大的數(shù)向后移動
            if alist[j] > alist[j + 1]:
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
                count += 1
        if count == 0:
            break
           

def select_sort(alist):
    # 第一次將首位置換成最小值，以此類推,，共需要n-1次
    for i in range(len(alist)-1):
        # 拿到第i個(gè)元素,，與其之后的元素挨個(gè)比較，把較小值放置i位
        for j in range(i+1, len(alist)):
            if alist[i] > alist[j]:
                alist[i], alist[j] = alist[j], alist[I]

def insert_sort(alist):
    # 首次分為第一個(gè)元素和其余元素兩部分,，從第二個(gè)元素開始,，與前面元素挨個(gè)比較，直到找到屬于自己的位置,。因此外層需要n-1次
    for i in range(len(alist)-1):
        # 將i+1位置的元素,，向前挨個(gè)比較，找到自己的位置,。即由第i個(gè)元素依次向前直至第0個(gè)元素
        for j in range(i+1, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]

"""
 快速排序和前面三種思想上有較大不同,，不再是外層循環(huán)次數(shù)下,，內(nèi)層循環(huán)實(shí)現(xiàn)將某一元素放至某位置。其核心思想是以某個(gè)值作為基準(zhǔn)值,，
 將小于該值的元素放至左側(cè)（交換位置）,，大于該值的元素放至右側(cè)（交換位置），然后分別將左右兩側(cè)列表遞歸再次排序,。
"""


# 為了實(shí)現(xiàn)遞歸而不用重新定義左右列表變量,，將左右下標(biāo)作為參數(shù)
def quick_sort(alist, left, right):
    # 1. 遞歸退出條件
    if left >= right:
        return
    # 2. 核心：
    # 以首值為基準(zhǔn)值，判斷元素大小交換位置
    mid_value = alist[0]
    while left < right:
        # 循環(huán)找出小于基準(zhǔn)值的元素放至左側(cè)
        while left < right and alist[right] >= mid_value:
            right -= 1
        alist[left] = alist[right]
        # 循環(huán)找出大于基準(zhǔn)值的元素放至右側(cè)
        while left < right and alist[left] < mid_value:
            left += 1
        alist[right] = alist[left]
    # 循環(huán)結(jié)束后,，left=right,，該位置放基準(zhǔn)值
    alist[left] = mid_value
    # 對基準(zhǔn)值左右兩側(cè)元素遞歸快排
    quick_sort(alist, 0, left-1)
    quick_sort(alist, left+1, right)

"""
希爾排序是插入排序的改進(jìn)版，先以一定步長將列表分為多個(gè)子列表,，然后對每個(gè)子列表插入排序,。執(zhí)行完成后，縮小步長繼續(xù),，直至步長為0,。
這里可能會有疑惑,，最終步長為1時(shí)就是插入排序，為什么還要多幾次步長不為1的循環(huán),？
實(shí)際上,，前面知道插入排序后面每個(gè)元素向前插入時(shí)，需要從前往后遍歷比較,，但如果比首個(gè)元素都小則可直接插入,。我們可以理解為，對大部分
無序隨機(jī)數(shù)列,，步長取合適時(shí),，時(shí)間復(fù)雜度會有很大改善。
"""


def shell_sort(alist):
    # 取首次步長為列表長度一半
    gap = len(alist) // 2
    while gap > 0:
        # 內(nèi)層類似插入排序,，只不過步長為gap
        # 循環(huán)次數(shù)：gap->len
        for i in range(gap, len(alist)):
            # 內(nèi)層：將第i個(gè)元素依次與前面元素比較調(diào)整位置,，不過步長為gap
            for j in range(i, 0, -gap):
                if alist[j] < alist[j-gap]:
                    alist[j], alist[j-gap] = alist[j-gap], alist[j]
        # 排序后gap減小
        gap = gap // 2

"""
歸并排序,，如名字一樣，是將序列一邊合并一邊排序,。其核心思想為：
先將序列遞歸的折半拆分,，直到長度為1，然后執(zhí)行排序后作為本層遞歸的返回,。
需注意歸并排序每層遞歸都有返回值,，因此比前面幾個(gè)排序耗費(fèi)空間。
"""


def merge_sort(alist):
    # 1. 遞歸退出條件
    if len(alist) <= 1:
        return alist  # 注意有返回值
    # 2.核心思想
    # 二分分解
    num = len(alist) // 2
    # 取左右兩截（內(nèi)部遞歸）
    left_list = merge_sort(alist[0:num])
    right_list = merge_sort(alist[num:])
    # 返回根據(jù)左右兩截實(shí)現(xiàn)的排序序列
    return merge(left_list, right_list)


def merge(left_list, right_list):
    # 排序核心：將左右兩個(gè)有序數(shù)列內(nèi)依次取滿足大小比較的元素,，放置新序列
    # 定義左右兩序列的其實(shí)元素位置
    left, right = 0, 0
    # 定義一個(gè)新序列接收排序后序列
    result = list()
    # 循環(huán)退出條件：一側(cè)遍歷完,，將另一側(cè)剩余元素直接添加至后面
    while left < len(left_list) and right < len(right_list):
        if left_list[left] < right_list[right]:
            result.append(left_list[left])
            left += 1
        else:
            result.append(right_list[right])
            right += 1
    result += left_list[left:]
    result += right_list[right:]
    return result

"""
二分查找法核心思想為：
找中間值將序列（等分地）分成兩段,，判斷要找的元素比中間值大還是小，小的話在左側(cè)段繼續(xù)二分查找,，大的在右側(cè),。
python實(shí)現(xiàn)二分查找可以通過遞歸和非遞歸兩種方式實(shí)現(xiàn)
"""


def binary_search(alist, item):
    """非遞歸實(shí)現(xiàn)二分查找"""
    # 定義出始末下標(biāo)
    start = 0
    end = len(alist)-1
    # 循環(huán)結(jié)束條件：二分查找的序列長度為大于0
    while start <= end:
        # 找到中間值下標(biāo)
        mid_point = (start+end) // 2
        if item == alist[mid_point]:
            return True
        elif item > alist[mid_point]:
            start = mid_point+1
        else:
            end = mid_point-1
    return False

def binary_search(alist, item):
    """遞歸實(shí)現(xiàn)二分查找"""
    # 遞歸結(jié)束條件：二分到長度為0時(shí)說明未找到
    if len(alist) == 0:
        return False
    mid_point = len(alist) // 2
    if alist[mid_point] == item:
        return True
    if alist[mid_point] > item:
        return binary_search(alist[:mid_point], item)
    else:
        return binary_search(alist[mid_point+1:], item)

class Node(object):
    """二叉樹節(jié)點(diǎn)"""
    # 二叉樹節(jié)點(diǎn)三個(gè)屬性：值,，左子節(jié)點(diǎn)，右子節(jié)點(diǎn)
    def __init__(self, item):
        self.item = item
        self.lchild = None
        self.rchild = None


class Tree(object):
    """(滿)二叉樹"""
    # 二叉樹初始化時(shí)需要根節(jié)點(diǎn)
    def __init__(self):
        self.__root = None

    def add(self, item):
        """添加元素"""
        node = Node(item)
        if self.__root is None:
            self.__root = node
        else:
            # 核心思想：將頭節(jié)點(diǎn)加入至隊(duì)列,，先判斷左節(jié)點(diǎn),，為空則將節(jié)點(diǎn)放置左側(cè)；若不為空,，判斷右節(jié)點(diǎn),，為空則放置右節(jié)點(diǎn)。若左右都不為空,，分別將左右
            # 節(jié)點(diǎn)加入至隊(duì)列尾,，再取隊(duì)列首節(jié)點(diǎn)繼續(xù)上面邏輯
            queue = list()
            queue.append(self.__root)
            while queue:
                cur = queue.pop()
                if cur.lchild is None:
                    cur.lchild = node
                    return
                if cur.rchild is None:
                    cur.rchild = node
                    return
                # 左右都不為空，將左右節(jié)點(diǎn)放置隊(duì)列尾
                queue.append(cur.rchild)
                queue.append(cur.rchild)

"""
二叉樹深度優(yōu)先遍歷根據(jù)遍歷順序不同可分為三類：
先序遍歷：先訪問根節(jié)點(diǎn),，再訪問左節(jié)點(diǎn),，最后右節(jié)點(diǎn)；
中序遍歷：先訪問左節(jié)點(diǎn),，再訪問根節(jié)點(diǎn),，最優(yōu)右節(jié)點(diǎn)；
后續(xù)遍歷：先訪問左節(jié)點(diǎn),，再當(dāng)問右節(jié)點(diǎn),，最后根節(jié)點(diǎn)，注意左節(jié)點(diǎn)永遠(yuǎn)在右節(jié)點(diǎn)前,，后續(xù)指根節(jié)點(diǎn)和右節(jié)點(diǎn)的順序,。
"""


def preorder(root):
    """遞歸實(shí)現(xiàn)先序遍歷"""
    if root is None:
        return
    print(root.item)
    preorder(root.lchild)
    preorder(root.rchild)

def inorder(root):
    """遞歸實(shí)現(xiàn)中序遍歷"""
    if root is None:
        return
    inorder(root.lchild)
    print(root.item)
    inorder(root.rchild)

def postorder(root):
    """遞歸實(shí)現(xiàn)后續(xù)遍歷"""
    if root is None:
        return
    postorder(root.lchild)
    postorder(root.rchild)
    print(root.item)

"""
廣度優(yōu)先遍歷的核心：從根節(jié)點(diǎn)開始，從上到下,，從左到右遍歷整個(gè)樹的節(jié)點(diǎn)
"""


def breadth_travel(root):
    if root is None:
        return
    queue = list()
    queue.append(root)
    while queue:
        node = queue.pop(0)
        print(node.item)
        if node.lchild is not None:
            queue.append(node.lchild)
        if node.rchild is not None:
            queue.append(node.rchild)

class Node(object):
    """二叉樹節(jié)點(diǎn)"""
    # 二叉樹節(jié)點(diǎn)三個(gè)屬性：值,，左子節(jié)點(diǎn)，右子節(jié)點(diǎn)
    def __init__(self, item):
        self.item = item
        self.lchild = None
        self.rchild = None


class Tree(object):
    """(滿)二叉樹"""
    # 二叉樹初始化時(shí)需要根節(jié)點(diǎn)
    def __init__(self):
        self.root = None

    def add(self, item):
        """添加元素"""
        node = Node(item)
        if self.root is None:
            self.root = node
        else:
            # 核心思想：將頭節(jié)點(diǎn)加入至隊(duì)列,，先判斷左節(jié)點(diǎn),，為空則將節(jié)點(diǎn)放置左側(cè)；若不為空,，判斷右節(jié)點(diǎn),，為空則放置右節(jié)點(diǎn),。若左右都不為空，分別將左右
            # 節(jié)點(diǎn)加入至隊(duì)列尾,，再取隊(duì)列首節(jié)點(diǎn)繼續(xù)上面邏輯
            queue = list()
            queue.append(self.root)
            while queue:
                cur = queue.pop(0)  # 注意是取第0個(gè)元素,，與下面的append相斥
                if cur.lchild is None:
                    cur.lchild = node
                    return
                if cur.rchild is None:
                    cur.rchild = node
                    return
                # 左右都不為空，將左右節(jié)點(diǎn)放置隊(duì)列尾
                queue.append(cur.lchild)
                queue.append(cur.rchild)

    def preorder(self, root):
        """遞歸實(shí)現(xiàn)先序遍歷"""
        if root is None:
            return
        print(root.item)
        self.preorder(root.lchild)
        self.preorder(root.rchild)

    def inorder(self, root):
        """遞歸實(shí)現(xiàn)中序遍歷"""
        if root is None:
            return
        self.inorder(root.lchild)
        print(root.item)
        self.inorder(root.rchild)

    def postorder(self, root):
        """遞歸實(shí)現(xiàn)后續(xù)遍歷"""
        if root is None:
            return
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print(root.item)

    def breadth_travel(self, root):
        """廣度優(yōu)先遍歷"""
        if root is None:
            return
        queue = list()
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print(node.item)
            if node.lchild is not None:
                queue.append(node.lchild)
            if node.rchild is not None:
                queue.append(node.rchild)