文和906

题解

未归档(4) 项目笔记(5)

/ 注册

全部文章 / 题解（共103篇）

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

与之前的#第一个只出现一次的字符#十分相似的题。故采用了相同的思路来做。维护一个私有的全局字符串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

题解 | #丑数#

首先给出暴力法从1开始判断是否是丑数，若是则count++。每趟遍历都n++。当count==index时，返回当前数，即为对应丑数。这种做法逻辑上是完全没问题的，就是时间复杂度过高。提交运行时会在第11个用例(共13个)处超时，其输入为1500。这种算法的核心在判断一个数是否是丑数，具体体现为ju...

C++ 数学

2021-10-25

0 354

题解 | #把数组排成最小的数#

直接解题需要将int数组中所有元素的排列都列出来，逐一比较。看到题目中给出了贪心的tag，所以一定能用更快的方法来做。选择用比较直接的类似冒泡排序的思路来做。即只两两比较int数组中元素所组成的数字，将大的往后放。先将int数组中的元素使用to_string()方法存入string数组中。使用二重循...

C++ 贪心数组

2021-10-25

0 372

题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

暴力法，遍历从1道n的数，对每个数字计算1的个数。时间复杂度O(nlogn)，空间复杂度O(1)。 class Solution { public: int NumberOf1Between1AndN_Solution(int n) { int count = 0; ...

C++ 数学

2021-10-22

1 439

题解 | #数组中出现次数超过一半的数字#

由于有一个数字在数组中出现的次数超过了一半。则我们每次都选出两个不同的数字，将其从数组中去掉，直到数组中只剩下一个数，或多个相同的数，就是要找的众数。实际操作中，使用一个变量candi保存当前准备比较的数，用一个变量count保存这个准备比较的数还剩多少个才能完全从数组中去掉。每次比较时，若coun...

C++ 数组数学

2021-10-22

4 480

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

维护一个标记firstEven指向数组当前第一个偶数的位置。遍历数组，当遇到一个奇数时，判断其下标与firstEven是否相等，若相等，说明目前数组前面都是奇数，不需要调整顺序，使firstEven++，保持与循环控制遍历i同步。若不等，说明前面已有偶数出现，将当前i指向的奇数插入firstEven...

C++ 数组

2021-10-22

1 455