文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共113篇）

题解 | #nico和niconiconi#

典型的线性动态规划。使用前缀和的思路，建立一个数组用于存储字符串str前i个字符中最大的值，然后寻找其递推关系。显然，每遍历一个字符，都要判断其前i个字符中最大的前缀和的a, b, c的状态，有可能仅是增加1个a, b, c，亦有可能增加3个a，减少一个c。最后，前缀和数组中的末项即为整个字符串最大...

C++ 线性动态规划

2021-10-27

0 470

题解 | #不相邻取数#

开始时使用暴力法，用一个三重循环枚举出所有可能的不相邻数的和，并选出其中最大的和作为输出其核心思想是对每一种可能的间隔，每一种可能的起点，计算出其最大的和。由于数组元素非负，所以在起点与间隔固定的情况下，数字当然越多越好。具体做法为，最外层循环控制间隔，间隔是从1~size()-2的。中间层循环控制...

C++ 线性动态规划

2021-10-27

0 669

题解 | #子数组最大连续和#

从头遍历输入数组，先假设数组中元素不全为负。每次都将当前元素加到sum中，然后判断，sum，若sum<0，则令sum=0。因为之后sum必定已经加到或将会加到一个不为负的数。若sum>max，则令max=sum。然后对数组全为负的情况添加一些判断。此时max必定为负，则当sum<0...

C++ 线性动态规划

2021-10-27

0 455

题解 | #调整数组顺序使奇数位于偶数前面(二)#

思路与调整数组顺序使奇数位于偶数前面(一)完全相同。这里就不赘述。具体讲一下有差异的地方。在(一)中要求奇数之间及偶数之间的相对位置不变，那么在交换奇数偶数时就涉及到稳定性的问题，在(一)中选择使用类似插入排序的操作来保证稳定性。而在(二)中，对稳定性不做要求，这无疑降低了难度，直接交换第一个偶数及...

C++ 数组

2021-10-26

0 399

题解 | #剪绳子#

这题比较偏数学思维了。观察几个数手动切割的结果可以发现，它们最大的乘积都是拆分成若干个2和3相乘得到的，不存在1，5，7。根据这一结论可以将长度为n的数分为两部分，一部分由若干个3相乘得到，另一部分由若干个2相乘得到，且3必定多于2。所以实际操作时，可以先找出3部分的乘积，在得出2部分的乘积。最后将...

C++ 数学

2021-10-26

0 445

题解 | #字符流中第一个不重复的字符#

与之前的#第一个只出现一次的字符#十分相似的题。故采用了相同的思路来做。维护一个私有的全局字符串str，每次Insert()都将输入的字符串添加到该str之后。调用FirstAppearingOnce()时，遍历str，找到其中第一个只出现一次的字符。其中找第一个只出现一次的字符的方法则使用了与上面...

C++ 字符串

2021-10-26

0 364

题解 | #孩子们的游戏(圆圈中最后剩下的数)#

经典约瑟夫环问题。这里需要掌握一个约瑟夫环的递推公式，f(n)=(f(n-1)+m)mod(n)。其中f(n)为在n个人中最后剩下的人，m为每次选出的人与第一个人的间隔。即若第一个人为0号，报到m-1的人出局。该公式也比较容易理解，每次n个人中的第m个人出局，剩下的n-1个人组成新的约瑟夫环。这个...

C++ 约瑟夫环

2021-10-26

0 479

题解 | #左旋转字符串#

直接法，模拟字符串左旋转的过程。先判断n与字符串长度的关系。当n等于字符串长度时，不用处理，直接返回原字符串。当n大于字符串长度时，另n等于n与字符串相减之差。当n小于字符串长度时，不做处理。新建一个数组，用于保存字符串前n个字符，这些字符会因左旋而插入字符串尾部。将str从第0位开始，使str[i...

C++ 字符串

2021-10-26

0 365

题解 | #和为S的两个数字#

模仿#和为S的连续数列#中双指针的思路。使用左右两个指针，左指针left从数组最左侧开始，右指针right从数组最右侧开始。计算左右两个指针所指向的值的和，若该和大于sum，则left++，若该和小于sum，则right--。直到左右指针之和等于sum，此时找到结果；或左右指针指向同一位置，此时无结...

C++ 双指针

2021-10-26

0 401

题解 | #和为S的连续正数序列#

先用暴力法解。用一个二重循环遍历1～sum/2+1中的数。外层循环控制该连续序列的起点，内层循环用于记录该序列以及该序列的和。当序列和等于sum时，将当前序列加入结果集，退出内层循环。当序列和大于sum时，直接退出内层循环。这样做时间复杂度在O(n^2)，空间复杂度为O(n)。 class Solu...

C++ 穷举

2021-10-25

0 374