这是算法设计与分析课程的上机实验。
-
1002
两重循环可过
-
1003
按照冒泡排序的定义，扫描第一遍即可
-
1004
使用递归进行归并排序，需要一个变量来记录递归过程中的层数，当层数为3时输出该段的数据
-
1006
按堆排序定义操作即可
-
1007
和1026类似，作业也写过， 考虑最后一个数会和哪些数组合， 写出动态规划的公式即可， 不需要使用高精度，unsigned long long可以过
-
1008
1008的第一问和1009一样，第二问需要用到Dilworth分割定理：要求出最长不上升子序列的最少划分数，只需要求出这个序列中最长上升子序列的长度，这就转化成了和1009完全类似的问题。
-
1009
本质是找出序列中的一个最长不上升子序列，动态规划的数组dp[i]记录末位为data[i]时最长不上升子序列的长度。
-
1010
二分搜索的子问题应该划分成search(left,mid-1)和search(mid+1,right)，如果频繁提示Wrong Answer，很可能是这里出现问题
-
1013
这道题使用$O(n^2)$的方法会超时，正确的做法是使用归并排序，在归并的过程中得到逆序数，见 https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/ ，LeetCode官方的题解非常详细
-
1014
动态规划即可，LeetCode上有一样的题目，见 https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
-
1016
我用哈希表过了，不知道暴力解法行不行
-
1017
看清题目的本质，就是求给定排列的逆序数，只需要把1013的代码复制过来就可以过
-
1018
如果要求背包问题恰好装满，需要把动态规划数组里面的值初始化为$-\infty$，其他都和1019一样
-
1019
动态规划，解法见教材
-
1020
动态规划，解法见教材
-
1021
动态规划，解法见教材
-
1022
动态规划，解法见教材
-
1025
动态规划，和导弹拦截一样。
-
1026
动态规划，和1007一样，只需要把计算数组中一段数的函数修改一下就可以。
-
1030
直接暴力贪心，复杂度是$O(n^2)$，会超时，需要线性复杂度的算法
-
1040
这题数据结构课上好像做过但是没讲，见 https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
-
1040
正常进行拓扑排序即可
-
1041
将两个数组归并然后输出中位数即可，不需要设置输出的小数位数，不要被样例误导