题目难度：二星考察点：贪心 分析：对于这道题来说，如果在第i个位置上安装路灯，那么它能够照亮的地方就是i-1, i和i+1,那么安装路灯最少的方法就是在三个位置的中间设置路灯，即如果第i个位置为'.'， 那么显然在 i+1 处安装路灯是最好的，它可以照到位置i, i+1和i+2，这样能够最大程度的减少路灯的数目。例如下图：算法实现：(1) 设置遍历指针i=0;(2) 如果第i个位置为'.'，ans++（在i+1处放置路灯，可以照亮i, i+1, i+2），然后从第i+3位置处继续遍历，即i=i+3；(3) 如果第i个位置为'x'，那么指针i++。(4) 一直遍历字符串末尾结束，最后输出ans...

题目难度：二星考察点：找规律简要说明：这是一道找规律的题目，只要我们发现其中的规律，题目也就迎刃而解。 分析： 对于这道题来说，我们肯定不能直接从l到r遍历一遍，然后对于每个数判断是否能够被3整除，这样的复杂度太高，因为数据范围是10^9，所以我们考虑找规律，打表如下：1%3 =====> 112%3 =====> 0123%3 =====> 01234%3 =====> 112345%3 =====> 0123456%3 =====> 0那么我们发现从1开始，每隔3个数就有两个数%3=0，...

题目难度：三星考察点：贪心、排序 方法1：暴力算法 分析：对于每个小伙伴，从1-n遍历一遍找到超过自身能力值的情况下报酬最高的那个人，输出即可。 复杂度分析：时间复杂度：O(m*n)空间复杂度：O(n) 代码：#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5+5; struct Node { int x, y; }a[MAXN]; int main() { int n, m; cin>>n>>m; for(int i=0; i<n; i++) cin>&g...

题目的主要信息： 题目给出我们一棵树的其中的某一个结点指针 我们需要返回这棵树按照中序遍历的该节点的下一个顺序结点指针 树的每个节点都有三个指针，指向左子节点、右子节点、父节点 举一反三： 学习完本题的思路你可以解决如下题目： JZ54. 二叉搜索树的第k个节点 JZ68. 二叉搜索树的最近公共祖先 方法一：中序遍历递归（推荐使用） 知识点：二叉树递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。 而二叉...

题目的主要信息： 实现一个函数用来找出字符流中第一个只出现一次的字符 Insert函数插入字符流的下一个字符， FirstAppearingOnce找到第一个不重复出现的字符 如果找不到返回# 字符串中出现的字符一定在 ASCII 码内 举一反三： 学习完本题的思路你可以解决如下题目： JZ50. 第一个只出现一次的字符 JZ39. 数组中出现次数超过一半的数字 JZ56. 数组中只出现一次的两个数字 方法一：哈希表+字符串（推荐使用） 知识点：哈希表 哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在O(1)O(1)O(1)时...

描述 这是一篇针对初学者的题解。讲述了如何从归并排序的思想到解决本题。知识点：递归难度：二星 题解 题目描述：给定一个数组arr， 数组元素各不相同，求arr[i] > arr[j] 且 i < j的个数。 首先还是提出两个问题，带着问题来看题解，我觉得效率更好。Q1：为什么归并排序需要额外的空间？Q2：为什么此题的最优解法可以借助归并排序的思想？ 方法一：暴力方法 对于此题，按住一个arr[i], 依次判断{i+1 ... n-1]是否满足条件。n为数组的大小。代码如下： class Solution { private: const int kmod = 100000...

题目的主要信息： 把一根长度为nnn的绳子分成mmm段，每段长度都是整数 求每段长度乘积的最大值 举一反三： 学习完本题的思路你可以解决如下题目： JZ83. 剪绳子（进阶版） JZ71. 跳台阶扩展问题 JZ42. 连续子数组的最大和 方法一：动态规划（推荐使用） 知识点：动态规划 动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。 思路： 一旦分出一段...

题目的主要信息： 有一个坐标从 [0,0] 到 [rows-1,cols-1] 的方格 机器人每次只能走上下左右四个方向，但是行坐标和列坐标的数位之和大于 threshold 的格子不能进入 求从起点[0, 0]开始最多经过可以多少个格子 举一反三： 学习完本题的思路你可以解决如下题目： JZ12. 矩阵中的路径 方法一：深度优先搜索（推荐使用） 知识点：深度优先搜索（dfs） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。 ...

描述 这是一篇针对初学者的题解，给出一个比较好的DFS模板。知识点:DFS难度：二星 题解 题目描述：给定一个二维字符串矩阵mat,和一个字符串str,判断str是否可以在mat中匹配。可以选择的方向是上下左右。 方法：DFS 这道题大家都知道是DFS的题，关键是怎么可以快速并且正确的写出，是本题解讨论的重点。首先解释一下递归函数。递归函数：就是当前处理的问题是什么，并且下一次在规模减小的情况下处理相同的问题。比如此题：当前处理的问题是：判断字符串str[0 ... len]是否在mat中匹配，显然下一次递归处理的问题是:如果str[0]已经匹配，则判断字符串str[1 ... len]是否...

描述 这是一篇针对初学者的题解。共用两种方法解决。从暴力算法一步步到最优算法。知识点：数组，队列难度：二星 题解 题目描述：给定一个数组num和一个窗口大小size，求每个窗口的最大值。 方法一：暴力方法 根据题目描述，我们很容易想到暴力方法。并且也很轻松的就可以写出来。如果数组的大小是n，窗口的大小是size，那么窗口的数量就是 n - size + 1.算法步骤如下： 枚举每个窗口的左边界 i 根据窗口的左边界i可以对应计算出右边界j 遍历窗口，计算出最大值 代码如下： class Solution { public: vector<int> maxInWindo...

描述 这是一篇针对初学者的题解，共用三种方法解决，从暴力算法到最优算法。知识点：排序，堆难度：二星 题解 题目描述：对动态数据流求中位数。 方法一：暴力方法 对于一组数据，我们可以用vector<int> arr来存取。如果对vector排好序，则很容易求出中位数。如果vector的大小为sz。 如果sz为奇数，假如为3，即[0 1 2]，则中位数就是中间的那个数arr[1]。 如果sz为偶数，假如为4，即[0 1 2 3], 则中位数就是中间两个数的加权平均数。即 (arr[1] + arr[2]) / 2 代码如下： class Solution { public: ...

#描述 这是一篇针对初学者的题解，共用两种方法解决。 知识点：二叉树，先序遍历，层次遍历 难度：二星 #题解 题目描述：给定一颗二叉树，将其序列化和反序列化。 ##方法一：先序遍历实现 预备知识：先序遍历的递归实现： void pre_order(TreeNode *root) { if (!root) { return; } // process root // ... pre_order(root->left); pre_order(root->right); } 对于本题来说，可以套用上述模板。 假设序列化的结果为字符串 str, 初始s...

题目的主要信息： 给定一个数组A，要求返回数组B，数组B每个元素等于数组A所有元素除了对应下标以外的全部元素的乘积 即B[i]=A[0]∗A[1]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1]B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]B[i]=A[0]∗A[1]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1] 程序不能使用除法 举一反三： 学习完本题的思路你可以解决如下题目： JZ17. 打印从1到最大的n位数 JZ64. 求1+2+3+...+n 方法：双向遍历（推荐使用） 思路： 如上图所示，矩阵中由对角线1将其分成了...

题目的主要信息： 给定一个二叉树，返回该二叉树的之字形层序遍 第一层从左向右，下一层从右向左，一直这样交替 举一反三： 学习完本题的思路你可以解决如下题目： JZ32. 从上往下打印二叉树 JZ78. 把二叉树打印成多行 方法一：非递归层次遍历（推荐使用） 知识点：队列 队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。 思路： 按照层次遍历按层打印二叉树的方式，每层分开打印，然后对于每一层利用flag标记，第一层为...