找到去除最少的人，也就是保留最多的人。该问题可以转化成为找某个位置的最长递增子序列和递减子序列问题。也就是之前做过的走桩子问题。可以使用动态规划来解决。找最长递增子序列长度，可以使用动态规划设置dp数组记录各位置长度，从左往右依次遍历各位置i，对于i，找位于i之前位置中个子低于i的j，如果j记录的最长子序列大于i的长度，那么更新dp[i]为dp[j]+1。同理，对于递减子序列，相当于反向递增子序列，从后往前依次遍历。使用dp2记录最后每个位置最长子序列长度相当于dp1+dp2-1,减1是因为长度多记录了一次。 #include <iostream> #include <vec...

#include <iostream> #include <utility> #include <vector> using namespace std; struct Node{ int val; Node* next; Node(int new_val, Node* ptr=nullptr){ this->val = new_val; this->next = ptr; } }; void showList(Node* head){ Node* ptr = head...

#include <cstdio> #include <iostream> using namespace std; int main() { double height; cin >> height; double bounce = 0; double count = 0; double all = 0; while(count < 5){ all += height; bounce = height/2; all += bounce; ...

使用辗转相除法，每次除2，余数为1，则记录+1；直至除为0利用while循环读入实现多组输入输出 #include <iostream> using namespace std; int main() { int a; while (cin >> a) { // cin >> a; int count = 0; while (a) { int div = a % 2; if (div == 1) count ++;...

可以使用深度搜索DFS来解决迷宫探索问题（广度搜索待研究）实现DFS可以利用stack，也可以使用递归(本身就是一种压栈方式)。这里使用递归来完成。设计递归函数时，考虑需要判断每个节点是否在通路上，故返回值定为bool。而对于每个节点bool值的确定，利用递归进行深度搜索：上、下、左、右四个邻近节点进行探索。当这四个方向节点都不是通路，则说明该节点也不通，状态记为2。同时，为了避免走重复节点，函数需要记录上一个节点坐标（bef_row, bef_col），防止下一步移动走回去。遇到的bug：条件判断时优先判断下一步是否移动回去，再递归判断下一步是否在通路上判断下一步是否移动回去，row和col...

使用while嵌套cin读取，保证后续输出成功利用set进行排序+去重 #include <algorithm> #include <functional> #include <iostream> #include <set> using namespace std; int main() { int len1, len2 = 0; set<int> new_vec; while (cin >> len1) { // cin >> len1; // ve...

首先这道题需要解决两件事情：使用map进行词频统计使用vector对map的pair进行排序排序又分为2个阶段：词频由大到小排-->直接使用sort按照自定义compare函数排序同频词按照ASCII码由小到大排-->使用双指针，对vector[start,end)段进行自定义compare函数排序 #include <algorithm> #include <iostream> #include <string> #include <unordered_map> #include <unordered_set> #inc...

本题考查递归，简化问题成子问题，要么少放一个盘子里，要么就每个盘子都放一个先。注意没有苹果也可以算一种情况， #include <iostream> using namespace std; int plans(int apples, int plates){ // 若无苹果或盘子,注意无苹果可分也算一种方案 if(apples < 0 || plates <= 0) return 0; // 若只有一个苹果或只有一个盘子 else if(apples == 1 || plates == 1) retur...

方法：递归法：超时，思路非常简单，就是对每个当前桩子now，计算所有高于它的桩子开始到之后能走的step中的最大step。然后加上当前桩子的step：1动态规划：使用一个一维dp表，表值记录每个桩子的step。然后从第二个桩子开始遍历，对遍历桩子i的所有之前的桩子j，当高度大于之前的桩子，那么step就取dp[i]和dp[j]+1中的较大值。最后取dp表中的最大值作为输出 #include <algorithm> #include <iostream> #include <map> #include <vector> using namespac...

使用二分法解决求解立方根问题，使用printf控制一位小数点数输出 #include <cmath> #include <iostream> using namespace std; int main() { double val = 0; cin >> val; double min = -20.0; double max = 20.0; double mid = 0; while( true ){ mid = (min+max)/2; if( mid*mid*mid -...

使用unordered_set来去除重复的整数 #include <iostream> #include <unordered_set> using namespace std; int main() { int input = 0; cin >> input; unordered_set<int> hash; int res = 0; while(input){ int backend = input % 10; if(hash.find(backend) == hash...

对于一个密码验证格式，有3点要求：密码长度大于8 --> 判断code的size必须有大小写，数字，其他字符4种中的3种 --> 遍历，只要多出现一种类型就记录+1判断是否有重复的长度大于2的公共子串难点在于如何判断公共子串，使用双指针来判断：主指针：遍历每个字符副指针：在主指针后3个字符开始，查找有没有相同字符 若有，则开始判断3个长度的主、副子串是否相同。相同则存在，不相同，则移动主指针 若无，接着移动副指针 #include <cstring> #include <iostream> #include <string> usin...

使用枚举法，全排列所有可能顺序，运算符只有64种可能，判断最后结果是否为24即可。注意需要保证除法时要整除得到24才行 #include <algorithm> #include <iostream> #include <vector> using namespace std; double cal(int num1, int num2, char opt) { if (opt == '+') return num1 + num2; else if (opt == '-') return num1 - num2; else if (...

方法：使用双栈（一个正向栈，一个反向栈（vector版））+next_permutation首先介绍next_permutation: 非常好用的用于输出按字典序的全排列组合。可以对vector，int[]数组等进行重排操作接下来讲述本题思路：首先使用反向栈存储车辆编号记录车辆出现顺序trains，这里使用vector将新编号车辆插入头部，每次取最后一个元素，取完pop_back，即可实现之后对order进行从小到大排序（为了按字典序输出，并输出所有可能序列）再然后，对于给定反向栈trains与可能序列order，遍历order， 对于某一元素：id：若栈station...