1.解题思路 窗口滑动前，已经找到其中最大值，那么滑动以后新增的一个元素只需和之前找到的最大值比较，但是有一个问题，如果之前的最大值正好离开了窗口就会出现错误，因此需要一个可以各时刻最大值的数据结构。该数据结构要满足以下功能： 1）随窗口向后移动，会有一个元素离开窗口，如果离开的元素是之前的最大值，那么该数据结构要及时移除那个值； 2）随窗口向后移动，会有一个元素进入窗口，如果进入的元素比之前的元素小，但是前面的元素离开窗口时，该元素可能成为最大值，因此需要保留；如果进入元素比之前的元素大，那么之前较小的元素绝不可能成为之后任意时刻的最大值了，无需保留，因此该数据结构里的...

1 解题思路 本题判断是否是完全二叉树，根据完全二叉树的性质，考虑使用按层次遍历检查。可以先枚举所有不是完全二叉树的形态，当程序检查到该形态后可以直接返回false，全部遍历完成后证明所有结点符合要求，返回true。 所有不是完全二叉树的形态： （1）某一个结点有右孩子，没有左孩子； （2）某一个结点只有左结点，右侧的兄弟结点或堂兄弟结点不存在； （3）某一个结点只有左结点或一个结点都没有，右侧兄弟结点或堂兄弟结点有孩子结点。 /** * struct TreeNode { * int val; * struct TreeNode *left; *...

1 解题思路 二叉树的链式存储结构很容易想到递归法： 首先确定递归结束条件：已到达叶子结点，判断当前分支数值和是否与给定sum相等。相同返回true，不同返回false。 再确定递归子问题：若当前结点有左孩子，则将当前结点值累加到 部分和(part_sum) 作为子问题的参数；有右孩子同理。 假设在左子树已经找到一个分支与给定sum相同，引入剪枝的思想，如果左子树返回结果为true，无需再进入右子树寻找。2 代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struc...

1. 解题思路 一维数组查找使用二分法的思路是是中间元素 mid 先和 target 比较，相等直接返回 true，否则： 若mid < target, 在右半区间继续查找； 若 mid > target, 在左半区间继续查找。 同理，二维数组可以将左下角元素或右上角元素作为中间元素，以右上角元素作为 mid 举例。mid先和target比较： 相等直接返回 true； 若mid < target, 因为同一行左侧元素都比mid小，所以将同列下一行元素作为新的mid； 若mid > targ...

1. 解题思路时间复杂度要求O(nlogn)，冒泡排序时间为O(n^2)大概率会超时，所以想到快排。因为链表结构不能随机访问，所以建立vector先将链表数据保存到vector中，将对链表排序转换为对数组排序。有两种方案： 1.vector保存每个结点的值对值排序后将结果按顺序为链表每个结点赋值。这时问题变成了简单的对数组元素排序。 2.vector保存每个结点的指针以上方案对结点的值进行了修改，如果不想修改结点值，就要比较结点值为结点指针排序。以下代码为该方案的实现。本来自己写了快排函数quick_sort，但是会超时。最终使用了模板库提供的sort函数。 /** ...

解题思路 分别遍历两个链表，分别求出结点个数： 若长度不等，求二者差值diff，长链表 的循环指针从头开始 先向后移动 diff 次，短链表 循环指针指向首结点，使两指针所在位置到链表尾部距离相同。 若长度相同，不做操作。两循环指针同时向后移动，如果指向了相同结点，返回该结点元素；否则当到达尾部NULL时，表明两链表无公共部分。代码实现 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class S...

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: //返回两个有序链表合成的有序列表 ListNode *sort(ListNode* list1,ListNode* list2){ if(!list1) return list...

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, int n) { // writ...