知识点 动态规划 思路 设river数组的长度为n 考虑每一个点都可以转移到后续的点，所以我们假设dp[i]代表从下标0走到i所需的最小步数。对于每一个点i，都一步可达[i+1~i+river[i]]的所有点。 所以步数转移方程为min（dp[i+j],dp[i]+1） 遍历每一个点，维护dp数组即可，答案ans=dp[n-1] 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param rivers int整型vector ...

知识点 哈希，贪心 思路 使用map建立奶牛指数到出现次数的映射，对于milk[i]，从1milk[i]指数它都涵盖出现了一次，mp[1milk[i]]的值都++。 遍历一次milk数组，预处理所有的指数以及出现的次数。 初始化ans为-1（小值） 然后再遍历map，若map.second>=map.first（即出现次数n不小于n公斤），且map.first>ans（多个牛奶指数取n大的），则更新答案。ans即为所求。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即...

知识点 模拟，贪心 思路 假设grass和cost的长度为n 首先，我们预处理出grass和cost的差s，若s[0~n-1]<0,那必然无解，否则必然有解。 设sum为区间[ans~~n-1]的和 判断完有解后，我们只需要找到一个下标最小的点，使其一直向右遍历，维护sum=sum+s[i]，若sum<0，则需要更新起点下标了。否则，若存在一个点i,使sum[i~n-1]都大于0，那ans即为i+1(下标为0的地方是第一个) 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的...

知识点 模拟，贪心 思路 我们可以观察到，对于rating[i]处的数，它的个数只取决于相邻左右两个数中最大的那一个。 为了维护左右的最大值，我们可以使用两个数组l和r分别维护位置i左侧的值和右侧的值。 l[i],r[i]分别代表rating[i]位置为了左边/右边应该取到的次数 l和r与rating等长，都初始化为1（题意的最少喂一次） 首先从左往右遍历rating数组，若rating[i]>rating[i-1]，则l[i]=l[i-1]+1;（至少，多一次即可）。 同理，从右往左遍历rating数组，若rating[i]>rating[i+1]，则r[i]=r[i+1]+1;...

知识点 模拟 思路 设nums.size()=n; 首先用一个长度为n的bool数组a维护每个障碍的可达状态，true表示可达，false表示不可达。初始化只有a[0]为true，其他全为false 开始遍历Nums[]数组： 对于a[i]==true的位置，a[i~i+nums[i]]都是可达的，都可以赋值为true。 对于a[i]==false的位置，不可达，无意义。 最后判断a[n-1]是否为true即可，这就是最后一个障碍的可达状态。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法...

思路 模拟，高精度加法 知识点 使用类似高精度加法的逐位增加，维护进位即可。 代码c++ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param milk int整型vector * @return int整型vector */ vector<int> tomorrowMilk(vector<int>& milk) { ...

知识点 哈希 思路 使用map维护每个数到出现次数的映射，遍历nums获取每个数的出现个数。再遍历一遍map，若当前数的出现次数即为2，返回此数即可。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int singleNumberII(vector<int>& nums) { // ...

知识点 哈希 思路 使用map维护每个数到出现次数的映射，遍历nums获取每个数的出现个数。再遍历一遍map，若当前数的出现次数即为1，返回此数即可。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int singleNumberII(vector<int>& nums) { // ...

知识点 思维 思路 对于出现两次的数，由异或的性质可以直接知道：a^a=0，b^a^a=b. 所以我们初始化ans为0，将其与nums的每一位都作异或运算，最后的ans即为只出现一次的数 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int singleNumber(vector<int>& nums) ...

知识点 数论 思路 讨论一个数翻倍多次以后最终的后导0的个数，只需要考虑这个数的因子中5的个数以及2的个数，二者中最小的那个数即为答案。 对于n，很容易统计出因子2和因子5的个数。此外，由于n还翻倍了m次，所以最终的数的因子2的个数还要加m。 min(count2+m,count5)即为答案。 代码c++ #include <algorithm> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 ...

知识点 位运算 思路 我们可以使用异或运算^以及进位来计算加法，乘法的本质就是多次加法，利用循环进行多次相加即可。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param a int整型 * @return int整型 */ int add(int a, int b) { while (b) { int temp =...

知识点 位运算 思路 由翻转，我们可以反向，从右往左遍历，赋值到res中的时候从左往右赋值即可（使用左移运算） 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int reverseBits(int n) { // write code here int res=0; for(int i=0...

知识点 位运算 思路 利用数字的位运算，不断将n右移，根据最后一位&1后的结果，统计32位中0的个数count。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int countZeros(int n) { // write code here int count=0; f...

知识点 递归 思路 求官方出一个标准答案，我看看怎么不用循环和条件判断写阶乘。对于此题，不用循环可以用递归方式写，不过注意判断递归的终止条件以及数据范围即可 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ long long int ans=1; void dfs(int n) { if(n==1)return; ...