题意理解 对于一个二进制字符串，我们只有一次机会选择其中一段连续的区间，将其中每个字符取反（即0变为1,1变为0），当然也可以不更新字符串。我们希望最后得到的字符串表示的数字最大。 方法一 暴力枚举 使用双重循环，列举出所有取反的可能性，并从中去最大值。由于是连续反转的，反转操作和确定反转的右边界可以公用一个循环。 具体代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num string字符串 * @retu...

题意理解 一个直方图可以视为多个宽度为1的矩形的紧密相连，每个矩形的高为heights数组中对应的值。这些矩形覆盖了平面上的一个区域，我们要在其中找到一个面积最大的矩形。 方法一 暴力搜索 面积最大的矩形的高一定是heights中的某个值，否则矩形可以增高，从而面积扩大。我们遍历每一个高度，对于heights[i]，分别向左向右搜索。如果遇到了某个高度小于heights[i]，说明以heights[i]为高的矩形的宽度不能再增加了，即到达了左右边界，此时可以得到对应矩形的面积，并更新当前最大面积。 以一个heights[i]为例，其寻找左右边界（即矩形宽度）的过程如图所示： 具体代码如下： ...

题意理解 对于字符串，我们可以从其中按照从前往后的顺序随机提取若干字符，这样构成其一个子序列。现对于两个字符串，要求出他们的最长的相同子序列的长度。 方法一 动态规划 定义一个二维数组dp，用来存储s1和s2的最长公共子序列的长度。因为会涉及到i-1和j-1，所以dp[i][j]记录s1[0]~s1[i-1]和s2[0]~s2[i-1]的最长公共子序列的长度maxlen（要注意这里的索引），我们dp数组的第0行和第0列均为0。 从前往后扫描s1和s2，如果s1[i-1]和s2[j-1]的字符相同，那么到此为止的maxlen就要加1；否则就为之前的maxlen。状态转移方程如下： dp[i][j...

题意理解 在一个数组arr中，我们可以从前往后按照顺序选择一些数字，构成一个子序列a。要求子序列从前往后是严格递增的，即对于任意i<ji<ji<j，必须满足a[i]<a[j]a[i]<a[j]a[i]<a[j]。现在我们要找出所有这样的子序列中，最长长度为多少。 方法一 贪心+二分 我们注意到，当某两个严格上升子序列长度一样时，如果选择结尾数字较小的子序列，那么后面更有可能扩张子序列长度。例如[6,1,5,3,4]，当遍历到3时，长度为2的子序列有[1,5]和[1,3]。此时后者时更优的，因为可以组成[1,3,4]；当然如果最后时大于4的数则两者一样优。总的...

题意理解 在一个数组arr中，我们可以从前往后按照顺序选择一些数字，构成一个子序列a。要求子序列从前往后是严格递增的，即对于任意i<ji<ji<j，必须满足a[i]<a[j]a[i]<a[j]a[i]<a[j]。现在我们要找出所有这样的子序列中，最长长度为多少。 方法一 动态规划 用一个数组dp记录以原数组中每个数字结尾的最长严格上升子序列的长度。在初始状态下，dp的值均为1，因为每个数字本身构成严格上升子序列。 我们从前往后更新dp。对于每个数arr[i]，依次遍历它前面的数字arr[j] (i<ji<ji<j)。如果前面的数字小，说明以...

题意理解 输入分为两部分，第一部分是候选人姓名；第二部分是每张选票对应候选人姓名。如果选票中候选人姓名正确，则对应候选人加一票，否则该票是不合法选票。 方法一 搜索法。 使用name数组存储候选人姓名，vote数组存储对应编号的候选人票数。每输入一张选票，就遍历一遍name数组。如果找到对应候选人，则将其票数加1；如果遍历完了还未找到，则不合法票数加1。 查找过程示意图如下： 具体代码如下： #include<iostream> #include<vector> #include<string> #include<algorithm> usi...

题意理解 把一个数组分成两部分（part1、part2），要求两部分的数字之和相等。其中，所有5的倍数（包括3和5的公倍数）要放在同一部分，其余3的倍数要放在同一部分。 让两部分之和相等，等价于从数组中找到一些数，使其和等于总和sum的一半。 方法一 深度优先搜索。 对于每一个数，有2种情况：放入part1；或者不放入part1（即放入part2），其中3的倍数必然放入part2。这样就构成了一个递归过程。每一个递归中遍历这2种情况，递归边界为遍历完所有的数字。 示意图如下: 具体代码如下： #include<iostream> #include<vector> #i...

题意理解 在字符串中找到长度最大的数字子串，如果有多个数字子串长度相等且最大，则按其在字符串中的顺序一次输出。数字子串指由数字连续构成的子串。 方法一 模拟，双指针。从左到右扫描字符串，并重复一下操作： 1、遇到一个数字字符，位置为i，暂停； 2、从i开始往后扫描，直到遇到非数字字符，位置为j； 3、计算当前发现的数字子串长度，并更新； 4、把j的值赋给i，继续扫描。 模拟过程如下： 具体代码如下： #include<iostream> #include<string> #include<vector> using namespace std; int...

题意理解 格子是有m行n列，沿着格子的边，从左上角走到右下角，每次只能向右或者向下走。我们是从一个点到另一个点，不是从格子到格子。 方法一 使用递推的方法。我们用数对(i,j)表示点的位置。每一个点只可能从它的左边或者上面走一步过来，所以到点(i,j)的走法总数等于到达点(i-1,j)和(i,j-1)的走法总数之和。注意初始化，到第0行和第0列上每个点的走法都为1种。 示意图如下： 具体代码如下： #include<iostream> using namespace std; int main() { int n,m; while(cin>>n&g...

题意理解 IP地址作为一个字符串输入，要判断其是否合法，即判断每个数字是不是处于0/~255之间。 方法一 从左向右遍历字符串，按照字符'.'就将字符串分隔成4个子串，用stoi()函数将其转化为数字，然后再判断每个数字是否出于0/~255之间，有一个不处于，则该IP地址不合法。 同时，要判断是否分为了4个数字，数字前是否有'+'，是否两个'.'连在一起，是否有'0'开头的数字(不为0)。 示意图如下： 具体代码如下： #include<iostream> #include<string> #include<cstdlib> using namespac...

题意理解 输入十六进制的数（以字符串的形式），将其转换成十进制数并输出。 方法一 十六进制数最前面两个字符是“0x”，不需要识别。其余字母中，A~F分别代表10~15。从右往左看，最低位要乘以16016^0160，倒数第二位要乘以16116^1161，以此类推。最后将每一位转化的结果求和即可。过程如图所示： 具体代码如下： #include<iostream> #include<string> using namespace std; int main() { string s; int ten,tran; while (cin>&g...

题意理解 对于每个输入的字符串，从前往后每8个字符为一行输出，最后如果不满8个则用“0”补齐。 方法一 使用while()循环读入字符串。每次输出字符串前8个字符，再用erase()方法将对应字符删除，直到剩余的字符个数小于8。 具体代码如下： #include<iostream> #include<string> using namespace std; int main() { string s; while(cin>>s) { int len = s.size(); //先8个一组输出字符 ...

题意理解 得到一个数组，将其中重复出现过的数字只保留一个，然后将剩余的数字从小到大排序。 方法一 读入的时候会有多组数据，我们用while()循环读入n，再读入数组中的n个数。 使用一个rp数据记录一个数是否出现过。如果出现过，就不加入数组num中去。最后使用sort()函数进行排序即可。 具体代码如下： #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n,x; vector<int> n...

题目理解 求一个字符串（可能包含空格）中给定字母出现的次数，其中字母大小写视为同一个字母。 方法一 使用getline()函数进行整行的字符串读入。 从左到右遍历字符串，比较每个字符与给定字符是否相同。对于字母的大小写问题，我们取得对应的ASCII值，比较差的绝对值是否为32。 具体代码如下： #include<iostream> #include<string> using namespace std; int main() { string s; char c; int count=0; getline(cin, s); ...