Java开发笔记

变治法

算法设计与分析方法之中的一种特殊的变换思想，严格意义上说，他并不想分治法、动态规划那样标准，它只是一种变换问题的思想。

变：将问题变得更加容易

治：求解容易的问题

实例化简（预排序、高斯消元）

预排序，一种简单的预处理技术（主要是意识）。

检验数组元素唯一性

词频统计

元素查找

以上三种模式，都可以使用蛮力来做，但是明显的性能太差了。

将数组排序是一个解决方案，无论是唯一性还是词频都可以很好的得到答案，代价仅仅是遍历一次数组，而元素查找在适合的数组之中，也可以使用诸如二分的方式很快的得到结果。但是对于查找来说，遍历随便比较差，但是对于多次查找来说，这是值得的。

高斯消元法

求解线性方程组的方式，将系数矩阵化为上三角矩阵。（就是一种变治和化简的思想）

改变问题（AVL、多路查找树）

AVL，为了改善二叉排序树的查找性能

问题化简（堆排序）

堆排序

def heapsort2(arr):
    # 建立堆
    def heapify(arr, low, high):
        # 开始指向堆顶元素
        i = low
        # 开始指向左节点
        j = 2 * i + 1
        # 储存堆顶元素
        temp = arr[low]
        # j位置有效
        while j <= high:
            # 右结点大于左结点
            if j + 1 <= high and arr[j + 1] >= arr[j]:
                # 指向右结点
                j = j + 1
            # 子结点大于父节点
            if arr[j] > temp:
                # 交换
                arr[i] = arr[j]
                i = j
                j = 2 * i + 1
            else:
                # temp放入某一节父节点
                arr[i] = temp
                break
        else:
            # temp放到叶子结点
            arr[i] = temp

    # 排序
    def sort(nums):
        n = len(nums)

        for i in range((n - 2) // 2, -1, -1):
            heapify(nums, i, n - 1)

        for i in range(n - 1, -1, -1):
            nums[0], nums[i] = nums[i], nums[0]
            heapify(nums, 0, i - 1)

    sort(arr)
    # print("结果数组：", arr)

霍纳法则

P（x） = an * x^n + ……a1* x + a0

一项一项的计算很慢，如果改变表现形式，这样就只要进行迭代。

# 霍纳法则
# arr（多项式，a1-an的数组）
# n（项数）
# x（x的值）
def Horner_rule(arr, n, x):
    i = 0
    ans = 0
    while i < n:
        ans = arr[i] + x * ans
        i+=1
    print(ans)
    return ans

if __name__ == '__main__':
    arr = [1 for i in range(0,10)]
    print(arr)
    x = 4
    n = 4
    Horner_rule(arr,4,4)