牛客313925129号

分类

题解(51)

/ 注册

全部文章（共51篇）

题解 | #长度为 K 的重复字符子串#

题意理解以长度为k的子串中如果某个字符出现多次，则判定该子串符合条件。计算一共有多少这样的子串。方法一枚举从左向右遍历字符串，取出其中所有长度为k的子串。对于每个子串也遍历一遍，使用一个map<char, bool>类型find记录某个字符是否出现过，如果遇到了某个字符对应的fi...

C++

2022-03-01

0 629

题解 | #打家劫舍(三)#

题意理解相比于前面两题，这里把房子的布局设置为二叉树的形式。现在要求选择数字的时候，父结点和孩子结点不能同时选。方法一深度优先搜索对于某个结点，可以选择或者不选，我们通过深度优先搜索遍历出每种可能的情况，并计算出对应结点数字的总和。如果选择当前结点，那么以它为根结点的数字总和为它本身加上以其...

C++

2022-02-28

0 426

题解 | #打家劫舍(二)#

题意理解同样的，也是从一个数组中不相邻地取出若干的数，使其之和最大，这里把第0个数和最后一个数视为相邻的。方法一动态规划和题目176一样，我们使用value数组表示从前往后到第i个数字，且选择第i个数字的时候，选到的数之和的最大值。因为最后的结果中肯定有某个数是最后一个被选到的数字，所以我们...

C++

2022-02-25

0 359

题解 | #打家劫舍(一)#

题意理解对于一个非负数组nums，我们从中选取若干个数，要求被选到的数不能相邻。问选到的数之和最大为多少。方法一动态规划由于相邻的数字不能同时选，那么不确定的因素太多了，我们先要确定一个下来。使用value数组表示从前往后到第i个数字，且选择第i个数字的时候，选到的数之和的最大值。因为最后的...

C++

2022-02-25

0 335

题解 | #最大值#

题意理解输入一个字符串s（由1~9组成）和一个整数k，我们从s中获取连续的长度为k的子串，求所有子串对应的数字中最大值为多少。方法一枚举因为子串长度固定，且是从s中连续的位置提取，所以遍历一遍字符串，每次取连续的k个字符即可。每次取出后直接使用字符串比较大小。最后将最大的字符串转为数字。具...

C++

2022-02-24

0 566

题解 | #填充数组#

题意理解给我们一个数组a，由自然数组成，以及一个最大值k。我们要把所有的0换成1~k中的某个值（可以重复），保持数组是递增的（这里的递增不是单调的）。问一共有多少种方法。方法一暴力枚举（会超时）最简单且容易想到的方法就是列举出数组所有可能的取值，再判断是否满足递增，如果满足，种数加1。这里使...

C++

2022-02-24

0 361

题解 | #二进制取反#

题意理解对于一个二进制字符串，我们只有一次机会选择其中一段连续的区间，将其中每个字符取反（即0变为1,1变为0），当然也可以不更新字符串。我们希望最后得到的字符串表示的数字最大。方法一暴力枚举使用双重循环，列举出所有取反的可能性，并从中去最大值。由于是连续反转的，反转操作和确定反转的右边界可...

C++

2022-02-22

0 318

题解 | #直方图内最大矩形#

题意理解一个直方图可以视为多个宽度为1的矩形的紧密相连，每个矩形的高为heights数组中对应的值。这些矩形覆盖了平面上的一个区域，我们要在其中找到一个面积最大的矩形。方法一暴力搜索面积最大的矩形的高一定是heights中的某个值，否则矩形可以增高，从而面积扩大。我们遍历每一个高度，对于he...

C++

2022-02-22

0 528

题解 | #最长公共子序列(一)#

题意理解对于字符串，我们可以从其中按照从前往后的顺序随机提取若干字符，这样构成其一个子序列。现对于两个字符串，要求出他们的最长的相同子序列的长度。方法一动态规划定义一个二维数组dp，用来存储s1和s2的最长公共子序列的长度。因为会涉及到i-1和j-1，所以dp[i][j]记录s1[0]~s1...

C++

2022-02-19

0 348

题解 | #最长上升子序列(二)#

题意理解在一个数组arr中，我们可以从前往后按照顺序选择一些数字，构成一个子序列a。要求子序列从前往后是严格递增的，即对于任意i<ji<ji<j，必须满足a[i]<a[j]a[i]<a[j]a[i]<a[j]。现在我们要找出所有这样的子序列中，最长长度为多少。 ...

2022-02-19

0 365