题目1 二叉树的镜像 题目描述 操作给定的二叉树，将其变换为源二叉树的镜像。 题目解析 一定要考虑到两种特殊情况： 二叉树为空 二叉树的左子树为空且二叉树的右子树为空 设计代码的时候一定要考虑代码的鲁棒性。所以需要设计到两个if语句，如果不在这两种特殊情况里面，再去新建一个TreeNode，然后交换进行做镜像。 代码 void Mirror(TreeNode *pRoot) { if(pRoot == NULL)//特殊情况1 return; //特殊情况2 if((pRoot->left == NULL)&…

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性 冒泡排序 O(n2) O(n) O(n2) O(1) 稳定 选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 插入排序 O(n2) O(n) O(n2) O(1) 稳定 希尔排序 O(nlogn)~O(n2) O(n2) O(n2) O(1) 不稳定 归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定 快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定 堆排序 O(nl…

题目7 链表倒数第k个结点 题目描述 输入一个链表，输出该链表中倒数第k个结点。 题目解析 我们很容易可以想到，由于这是一个单向链表，所以我们可以第一遍先遍历这个链表，看有多少个结点（假设为n），然后计算出pos=n-k+1，然后我们只需要再遍历一遍这个链表，输出第n-k+1个结点的值即可。 但是要注意鲁棒性。我们要考虑，如果这个链表为空呢？如果这个链表的结点数不到k个呢？那就需要对代码进行补充和完善。 代码 ListNode* FindKthToTail(ListNode* pListHead, unsigned…

题目1 斐波那契数列 题目描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 代码 递归方法： int Fibonacci(int n) { if(n==0) return 0; if(n==1||n==2) return 1; return Fibonacci(n-1)+Fibonacci(n-2); } 非递归方法： int Fibonacci(int n) { int first = 0; int second = 1; int res…

题目1：机器人的运动范围 题目描述 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ 题目解析 这个题可以看做是广度搜索优先（BFS）的一个拓展或者说是改编。如果说没有“不能进入行坐标和列坐标的数位之和大于****k****…

旅行商问题 问题分析 带权邻接矩阵g[][]如下所示，空表示为无穷，即没有路径。 15 30 5 15 6 12 30 6 3 5 12 3 算法设计 可以使用优先队列分支限界法，加快搜索速度。 设置优先级：当前已走过的城市所有的路径长度cl。cl越小，优先级越高。 从根节点开始，以广度优先的方式进行搜索。根节点首先成为活结点，也是当前的扩展结点。一次性生成所有的孩子结点，判断孩子结点是否满足约束条件和限界条件，如果满足，将其加入到队列中，反之，舍弃。然后再从队列中取出一个元素，作为当前扩展结点，搜索过程队列为空时…

广度优先 广度优先搜索，其实就是层次遍历，程序采用队列来实现。 算法思想 从根开始，常以BF或以最小耗费（即最大收益）优先的方式搜索问题的解空间树。首先将根结点加入活结点表，接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还是保留，舍弃哪些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点，重复上述扩展过程，直到找到所需的解或活结点表为空时为止。每一个活结点最多只有一次机会成为扩展结点。 算法步骤 算法解题步骤为…