大家对愚公移山想必都不陌生，今天带来一道移山所需的最少秒数。 阅读完题目，大家想必对题目都有了最基本的概念，那么如何移山，首先想到的便是去模拟这个过程，用回溯的思想，从每个工人的工作时间为0开始，逐渐增加，直至达到所需高度，再去比较哪个时间最短。给出代码如下： class Solution { public: void sm(long long&a…

今天带来一道第 N 个泰波那契数，题不难，但是我们可以从中学习到一些方法。 首先是使用动态规划来解决，题目本身的描述就把状态方程告诉你了，直接如题就能得到代码： class Solution { public: int tribonacci(int n) { int dp[38]; dp[0] = 0, dp[1] = 1,…

今天带来使二进制字符串全为 1 的最少操作次数，这道题还是比较复杂的。我采用的是数学方法，但这题也可以使用BFS来做。那么先介绍一下数学方法，代码如下： class Solution { public: int minOperations(string s, int k) { int n = s.length(); int zeros = 0; f…

今天首次通过了力扣上的一道困难题——柱状图中最大的矩形，这道题主要是在运用单调栈，单调栈就是一个单调递增的栈。在这道题让我们求最大的矩形的面积，乍一看好像无从下手，但其实我们知道面积的大小和这里面最低的数有关，他决定了这个矩形的高。那么我们就可以对每一个数，求离它的第一个比他小的数，左右各求一个。那么这之间的距离就是矩形的宽。再比较每个数能构成的最…

今天带来根据数字二进制下 1 的数目排序，题目本身不难，主要分享一下如何统计二进制里1的个数。 我们有两种思路，一种是遍历每一位，把是1的记一下。一种是通过消除最后一个1，看消除多少次，第二种可能需要理解一下。 先带来一下第一种求1个数的代码： int bitCount(int n) { int count = 0; // 计数器 while (n…

今天带来一道找到数组中所有消失的数字，这道题直接的做法就是循环两次，一次统计所有出现的，一次把没出现的输出，很简单，但是空间复杂度有点高。 class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector&l…

今天带来两道题的分享，一道是P3613 【深基15.例2】寄包柜，一道是Q1. 错误的集合。这两道题都不难，先来看第一题，这道题看一眼就能知道可以用二维数组来做，但建好二维数组之后却发现，需要建一个 105∗105 的数组，如果就这么提交肯定会超出内存限制。我已经提交过一个MLE的代码了，如下： #include <bits/stdc++.h…

今天久违的带来一题，P1095 [NOIP 2007 普及组] 守望者的逃离。这道题很有意思，是一道判断如何逃离更快的问题。直接贴一下我之前的复杂代码。 #include<bits/stdc++.h> using namespace std; int main(){ long long m,s,t; cin>>m>>s>>t; vector&…

好久没有更新了，今天带来的是P1020 [NOIP 1999 提高组] 导弹拦截，一道线性动态规划题，题目读起来比较简单，如果是用肉眼去找好像不是很难，但如何让计算机实现呢。 先放一下样例，389 207 155 300 299 170 158 65。如果是要拦截这些导弹，因为以后每一发炮弹都不能高于前一发的高度，所以我们要找一个尽量最大的并且尽量…

今天带来P1387 最大正方形，一道动态规划经典题。先贴一下代码。 #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<vector<int>> vec(n,vector<int>(m)); for(int …