写在前面

国科大算法复习的时候，想着复习一下平常的作业题，也正好记录一下。作业题总共分为四个部分，分治算法，动态规划，贪心算法，线性规划。可以说是算法学习中比较基础，经典的几个方面。

作业1：寻找两个有序数组的中位数

**问题描述：**对于两个数集A,B;已知|A| = |B| = n，且A,B集里无重复相同的数，每一次可以向A、B中任意一个提问，得到其第K小的数，其中K由提问者决定;那么试在O(logn)中求得A、 B中所有数的中位数。
**分析：**这个问题最关键的点是在O(logn)时间内求得A、 B中所有数的中位数，而对于O(logn)这种算法复杂度常见的就是二分，每次的问题规模需要减半。

**解法：**每次找两个数组的中位数，比较两个中位数，假设是amida_{mid}amid​和bmidb_{mid}bmid​，如果amid

另外也可以每次只去掉较小的那一部分，直到只剩n个数，那么只需要比较两个数组中最小的两个数，最小的就是要找的中位数target。

result = (findKth(nums1, 0, nums2, 0, n) + findKth(nums1, 0, nums2, 0, n)) / 2;
int findKth(int nums1[], int i, int nums2[], int j, int k)
{if (nums1.length() == 0 || nums2.length() == 0){return -1;}if (k == 1){return min(nums1[i], nums2[j]);}int midk1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;int midk2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;if (midk1 < midk2){return findKth(nums1, i + k / 2, nums2, j, k - k / 2);}else{return findKth(nums1, i, nums2, j + k / 2, k - k / 2);}
}

作业2：翻转二叉树

给定一棵二叉树，在时间复杂度O(n)对二叉树的所有左右孩子进行翻转。

解法：只需要递归的把左右子树进行翻转，然后交换左右孩子的指针，这样就实现了二叉树翻转。每个节点操作一次，算法复杂度是O(n)。

Inverse_Tree(Root)
{if Root != NULL:inverse_left_child = Inverse_Tree(Root->leftchild)inverse_right_child = Inverse_Tree(Root-> rightchild)Root->leftchild = inverse_right_child Root->rightchild = inverse_left_child return Rootelsereturn
}

作业3：越狱

监狱有连续编号为 1…N 的 N个房间，每个房间关押一个犯人，有 M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

解法：从问题事件的对立问题入手。考虑每个相邻房间都不存在相同宗教这一事件出现的可能数目。
取最左边的犯人,得该犯人可能信仰的宗教数量是m；设该犯人选了宗教j, 那么在他右边的犯人的可供选择就只剩下m−1种了。 那么再以这个选m−1种宗教的犯人为标准,设他随便选了宗教k (k!=j) ， 他的左边肯定跟他不一样,所以只要他右边也跟他不一样即可；
那么右边剩下选择依然为m−1种；
对于任意一名犯人,他需要与他左边相邻的犯人不同； 递推过去,他的右边相邻犯人会避免选择他选择的宗教，因而我们不用把相邻右边的犯人考虑进去。 所以情况数就为m×(m−1)n−1m\times\left(m-1\right)^{n-1}m×(m−1)n−1。
那么相邻房间的犯人的宗教相同（越狱）的情况数mn−m×(m−1)n−1m^n-{m\times\left(m-1\right)}^{n-1}mn−m×(m−1)n−1，通过快速幂可以实现O(log n).

//递归快速幂
int qpow(int a, int n)
{if (n == 0)return 1;else if (n % 2 == 1)return qpow(a, n - 1) * a;else{int temp = qpow(a, n / 2);return temp * temp;}
}

在递归快速幂中，每次只需要递归计算an2a^{\frac{n}{2}}a2n​，每次把结果存在temp里，不需要重复计算，进而算法复杂度是O(log n)，这是递归写法，空间开销比较大，快速幂算法也能改写成非递归写法。比如我们要计算7107^{10}710，可以把指数10拆成2和8，那么就可以写成72×787^2 \times 7^872×78，是不是任意大于0的指数都能这样拆，是的，因为这就是二进制，任何指数都可以拆分1，2，4，8，16…这些组合，这其实就是二进制的每一位，当这一位是1的时候，就把结果ans乘以当前的值a，这个a值每次都会自乘，由此计算了2，4，8这种次方。

//非递归快速幂
int qpow(int a, int n){int ans = 1;while(n){if(n&1)        //如果n的当前末位为1ans *= a;  //ans乘上当前的aa *= a;        //a自乘n >>= 1;       //n往右移一位}return ans;
}

作业4：二叉树中的最大距离

给一个二叉树，假设相邻节点的距离为1，求二叉树中任意两个节点的最大距离。

解法：这个最大距离可能过根节点，也可能不过根节点，如果过了根节点，那这个最大距离就是左右子树高度之和，如果不过根节点，那这个最大距离会在左子树或者右子树里产生，同样会产生过不过左右子树根节点的问题。也就是需要维护一个全局变量，对二叉树中每个节点进行递归查询，把该节点当作根节点，看能够产生的最大距离是多少。

class Solution {int ans;int depth(TreeNode* root){if (root == NULL) return 0;int L = depth(root->left);int R = depth(root->right);ans = max(ans, L + R + 1);return max(L, R) + 1;}
public:int diameterOfBinaryTree(TreeNode* root) {ans = 1;depth(root);return ans - 1;}
};

作业5：实现三路快速排序

选择一个pivot，将数组划分为小于，大于，等于pivot三部分，对于等于pivot的部分没有必要再进行排序，剩下两部分等同于快速排序。

void triSort(int *a, int low, int high){if(low >= high)return;int key = a[low];int i = low, j = low;int k = high;while( i <= k){if(a[i] < key)swap(a[i++], a[j++]);else if(a[i] > key)swap(a[i], a[k--]);else i++;}triSort(a, low, j);triSort(a, k + 1, high);
}

作业6：切绳子

有n条不同长度绳子，从中选择m条绳子切割，使得m条绳子长度一致，求m条绳子的长度的最大值。

解法：绳子长度从0到最长的长度lmaxl_{max}lmax​，二分查找长度，每次判断在这个长度下，有没有m条绳子满足条件，也即是大于这个长度，如果有m条绳子，就在右区间找，没有m条绳子满足，就在左区间找。