编程内功修炼-算法

发表于 | 更新于 | 分类于
本文字数： 3.5k | 阅读时长 ≈ 3 分钟

思考并回答以下问题：

本章涵盖：

  • 分治算法的介绍
  • 最大子数组问题的介绍
  • 使用暴力求解法解决最大子数组问题
  • 使用分治法分析最大子数组问题
  • 代码实现分治法
  • 树的介绍
  • 树的存储结构
  • 二叉树、满二叉树和完全二叉树的定义
  • 二叉树性质
  • 二叉树的存储结构
  • 二叉树的四种遍历方法
  • 使用代码实现二叉树的顺序存储
  • 二叉树的遍历（代码实现）
  • 二叉树的遍历-中序、后序、层序（代码实现）
  • 二叉排序树的介绍
  • 二叉排序树的代码实现 - 添加操作
  • 二叉排序树的代码实现 - 排序和查找
  • 二叉排序树的代码实现 - 查找方法的优化
  • 二叉排序树的代码实现 - 删除操作
  • 什么是堆，什么是堆排序
  • 堆排序-使用代码把二叉树构造成大顶堆
  • 堆排序-首尾交换和大顶堆的重新构造
  • 动态规划算法的介绍
  • 钢条切割问题-最优解方案分析
  • 钢条切割问题-第二种最优解方案分析
  • 钢条切割文题-自顶向下递归方法的代码实现
  • 钢条切割问题-带备忘的自顶向下递归方法代码实现
  • 钢条切割问题-自底向上法（动态规划算法）
  • 背包问题的问题描述
  • 使用穷举法实现背包问题
  • 背包问题-递归方式解决分析
  • 背包问题-递归代码实现（不带备忘的自顶向下法）
  • 背包问题-递归实现（带备忘的自顶向下法）
  • 背包问题-动态规划（自底向上法）
  • 贪心算法的介绍
  • 贪心算法-活动选择问题的介绍
  • 动态规划思路解决活动选择问题
  • 动态规划代码实现解决活动选择问题
  • fixbug问题修复
  • 贪心算法分析活动选择问题
  • 贪心算法-递归代码实现活动选择问题
  • 贪心算法-迭代代码实现活动选择问题
  • 贪心算法-钱币找零问题
  • 图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Program
{
    //最大子数组的结构体
    struct SubArray
    {
        public int startIndex;
        public int endIndex;
        public int total;
    }
    
    static void Main(string[] args)
    {
        int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97 };
        int[] pf = new int[priceArray.Length - 1];//价格波动的数组
        for (int i = 1; i < priceArray.Length; i++)
        {
            pf[i - 1] = priceArray[i] - priceArray[i - 1];
        }

        SubArray subArray = GetMaxSubArray(0, pf.Length - 1, pf);
        Console.WriteLine(subArray.startIndex);
        Console.WriteLine(subArray.endIndex);
        Console.WriteLine("我们在第" + subArray.startIndex + "天买入， 在第" + (subArray.endIndex + 1) + "天卖出");
        Console.ReadKey();
    }

    static SubArray GetMaxSubArray(int low, int high, int[] array)//这个方法是用来取得array 这个数组 从low到high之间的最大子数组
    {
        if (low == high)
        {
            SubArray subarray;
            subarray.startIndex = low;
            subarray.endIndex = high;
            subarray.total = array[low];
            return subarray;
        }

        int mid = (low + high) / 2; // 低区间 [low,mid]  高区间[mid=1,high]

        SubArray subArray1 = GetMaxSubArray(low, mid, array);

        SubArray subArray2 = GetMaxSubArray(mid + 1, high, array);

        //从【low,mid】找到最大子数组[i,mid]
        int total1 = array[mid] ;
        int startIndex = mid;
        int totalTemp = 0;
        for (int i = mid; i >= low; i--)
        {
            totalTemp += array[i];
            if (totalTemp > total1)
            {
                total1 = totalTemp;
                startIndex = i;
            }
        }
        //从【mid+1,high】找到最大子数组[mid+1,j]
        int total2 = array[mid + 1];
        int endIndex = mid + 1;
        totalTemp = 0;
        for (int j = mid + 1; j <= high; j++)
        {
            totalTemp += array[j];
            if (totalTemp > total2)
            {
                total2 = totalTemp;
                endIndex = j;
            }
        }
        SubArray subArray3;
        subArray3.startIndex = startIndex;
        subArray3.endIndex = endIndex;
        subArray3.total = total1 + total2;
        if (subArray1.total >= subArray2.total && subArray1.total >= subArray3.total)
        {
            return subArray1;
        }
        else if (subArray2.total >= subArray1.total && subArray2.total >= subArray3.total)
        {
            return subArray2;
        }
        else
        {
            return subArray3;
        }
    }
}
0%