题目的主要信息：  地图上有 n 个城市，它们之间通过 n-1 条道路联通，即一棵无向树 第一天会在 s 市住宿，并游览与它距离不超过 1 的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过 1 的所有城市 不能住在一个已经浏览过的城市，最多要游览多少天  因为每个会去到与这个城市相连的所有不重复城市，因此每天住宿的城市都是不相邻的，即求树上最多的不相邻的点的问题（最大独立集） 具体做法： 可以用树型dp，对于某一个结点，是否选择这个点进入集合，我们用dp数组表示，dp[i][0]dp[i][0]dp[i][0]表示以iii结点为根的子树，不选取该结点时的最大独立集的数量，dp[...

题目的主要信息：  一个n∗mn*mn∗m的表格，从左上角走到右下角的方法种数 每次只能走下或者右 不能回头  方法一：递归 具体做法： 容易想到的是，在第一步时可以选择向右或者向下，只需要当前的路径选择上加上(n,m−1)(n,m-1)(n,m−1)和(n−1,m)(n-1,m)(n−1,m)的矩阵路径选择即可。而(n,m−1)(n,m-1)(n,m−1)与(n−1,m)(n-1,m)(n−1,m)又是(n,m)(n,m)(n,m)的子问题，可以继续递归下去。只需要用iii，jjj表示当前位置，后续限制边界的向下或者向右即可。这是容易想到的方法, 下图为从(0，0)(0，0)(0，0)开始的...

题目的主要信息：  输入xx.xx.xx.xx形式的IPv4地址，判断其是否合法  方法一：字符串流输入输出 具体做法： 可以用字符串流输入输出将字符串转换成成数字和字符点，然后判断每个数字是否在0-255之间即可。  #include<iostream> #include<string> #include<sstream> using namespace std; int main(){ string ip; while(getline(cin, ip)){ stringstream ss; ss << ip; unsigned a, b, c...

题目的主要信息：  密码按如下规则进行计分，并根据不同的得分为密码进行安全等级划分：   密码长度：   5 分: 小于等于4 个字符   10 分: 5 到7 字符   25 分: 大于等于8 个字符    字母：   0 分: 没有字母   10 分: 全都是小（大）写字母   20 分: 大小写混合字母    数字：   0 分: 没有数字   10 分: 1 个数字   20 分: 大于1 个数字    符号：   0 分: 没有符号   10 分: 1 个符号   25 分: 大于1 个符号    奖励：   2 分: 字母和数字   3 分: 字母、数字和符号   5 分: 大小写...

题目的主要信息：  求一个int类型数字对应的二进制数字中1的最大连续数 进阶要求：时间复杂度：O(log2n)O(log_2n)O(log2​n)，空间复杂度：O(1)O(1)O(1)  方法一：连除法 具体做法： 将十进制转换成二进制的方法可以用连除取余法，那我们不断连除2，每次都取余2得到最后一位的二进制数，然后检查该二进制数是否为1，如果是1则统计计数，如果不为1说明连续中断了，比较获取最大值，并更新统计计数为0. #include<iostream> using namespace std; int main(){ int n; while(cin >> n)...

题目的主要信息：  给定一个仅包含小写字母的字符串，求它的最长回文子串的长度 回文串，指左右对称的字符串 进阶：时间复杂度O(n)O(n)O(n)，空间复杂度：O(n)O(n)O(n)  方法一：暴力法 具体做法： 可以暴力遍历字符串每个字符作为起点，然后遍历每个起点所有长度的子串，检查该子串是否是回文子串。检查的时候，我们可以从子串首尾开始往中间靠，比较首尾，如果都相同就是回文，否则不是回文。我们每次检查完是回文子串，就更新维护最大长度即可。 #include<iostream> #include<string> using namespace std; bool c...

题目的主要信息：  对于最大为9∗99*99∗9的二维数组检查以下操作是否可能实现，可以实现输出0，不能实现输出-1：  建立一个mmm行nnn列的二维数组，不可以超过最大限制 输入x1x_1x1​、y1y_1y1​、x2x_2x2​、y2y_2y2​，交换坐标在(x1,y1)(x_1,y_1)(x1​,y1​)和坐标在(x2,y2)(x_2,y_2)(x2​,y2​)上的两个数 输入xxx，在第xxx行上方添加一行，下标0开始，添加后不能超过9 输入yyy，在第yyy列左边添加一列，下标0开始，添加后不能超过9 查找坐标为(x,y)(x,y)(x,y)的单元格的元素   上述操作除了建表，其...

题目的主要信息：  分子为1的分数称为埃及分数 输入一个分子比分母小的分数，请分解为分母不同的埃及分数 分子和分母有可能gcd不为1 如有多个解，输出一个即可  方法一：迭代 具体做法： 如下图公式推算，我们可以贪心地用这种除法取余地方式更新分子分母，不断获取分子为1的分数。  因为分子分母gcd可能不为1，因此，如果分母可以整除分子，可以直接输出约分后的结果，跳出循环。 #include<iostream> #include<string> using namespace std; int main(){ int a, b; //分别是分子分母 char op; //...

题目的主要信息：  找出给定字符串中大写字符(即'A'-'Z')的个数 进阶要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)  方法一：ASCⅡ码比较 具体做法： 大写字母A的ASCⅡ码为65，大写字母Z的ASCⅡ码为90，我们只要遍历字符串，比较每个字符的ASCⅡ码在这之间就可以统计大写字母的个数。  #include<iostream> #include<string> using namespace std; int main(){ string s; while(getline(cin, s)){ int count = 0; for...

题目的主要信息：  判断短字符串s1中的所有字符是否在长字符串s2中全部出现 进阶要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n) 两个字符串均由小写字母组成  方法一：暴力查找 具体做法： 可以遍历字符串s1，检查每个字符串是否在s2中出现，可以用find函数查找字符串s2中是否有这个字符，如果没有就是false，如果全部遍历完都有就是true。 #include<iostream> #include<string> using namespace std; bool check(string& s1, string& s2...

题目的主要信息：  输入两个整型数组，将两个数组按照升序合并，并且过滤掉重复数组元素 输出时相邻两数之间没有空格  方法一：合并后排序 具体做法： 直接将输入的第二个数组接到第一个数组后面，后续对合并后的数组使用sort函数排序，然后遍历输出合并后的数组，对于与后面一个元素重复的情况我们不输出即可。  #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int n, m; while(cin >> n){ vector&l...

题目的主要信息：  给定n列火车的入栈序列，0<n<100<n<100<n<10，用数列1-9表示每列火车 火车只能从一个方向进，另一个方向出，只有站内的火车出去了，另外的才能进去 要求输出所有火车出站的方案，以字典序排序输出  方法一：全排列+栈 具体做法： 我们可以使用next_permutation函数对于输入的数字序列进行全排列，记录下所有的情况，全排列之前先排序，可以使全排列的结果呈现字典序排序。 然后依次验证每个情况是否符合火车进站出现的次序。根据验证的时候，根据输入的序列依次进栈，如果栈顶元素和要验证的出站顺序刚好一样，不断弹出栈中元素即可。最...