觅杳

分类

题解(25)

/ 注册

全部文章（共69篇）

C++题解 | #二进制中1的个数#

此题思路较为巧妙。若直接做右移位运算，则当为负数时，对其右移一位，为了保持负数，则其最左端会替换为1，而非正数的0。则继续进行右移，会导致最后负数变成0xFFFFF，故而要另寻出路。将数据按照位数由低到高与1做与运算，若该位是1，与运算结果必为1.即1需要持续左移直到判断完毕，那么3...

2021-08-20

1 447

C++题解 | #矩形覆盖#

此题显然与斐波那契数列不能说毫不相干，只能是一模一样。以的矩形为例，其可以在左端竖着填充一个的小矩形，之后便剩下的大小，也可在左上端横着填充一个小矩形，那么左下端很显然也必须横着填充一个，即只剩下的矩形待填充。故而可知,故而，等同于斐波那契数列。则 class Solution { pub...

2021-08-19

0 467

C++题解 | #旋转数组的最小数字#

题目本身暴力法遍历数组即可求解，但其时间复杂度相对而言较大，且根据旋转数组的特点，可知时间复杂度还有减小的余地，即主体采用二分法。特殊情况，则专门考虑遍历。整体程序虽增多，但其时间复杂度却降低了。 class Solution { public: int minNumberInRotateA...

2021-08-14

0 514

C++题解 | #替换空格#

本题要求替换空格为'%20'（空格可能会在格式不兼容时，成为乱码）,即将一个字符替换为一个字符串。若按正常从前按往后替换，则为避免覆盖空格其后字符，需要将其后字符后移两位，则会直接导致整个时间复杂度达到O(n^2)。况且在转移过程中，极有可能导致同一个子字符串的多次后移。故而，此处采用从后往前替换...

2021-07-27

0 587

C++二分法求解

本题目的是判断给定数据是否存在于已知二维数组中。则可直接使用暴力法，遍历二维数组求解。但由于此方法时间复杂度高达O(n^(2)),即可能会导致运行超时。故而，需另辟蹊径。显然，当target的值大于右上角元素时，其一定不会位于第一行，故可排除，行数i增加1；则再次与此时右上角数据（第二行）...

2021-07-27

0 543

C++题解 | #最长回文子串#

>首先，当子串长度超过2时，若欲使其为回文子串，其两端字母必须相等，且除去两端字母后的子串依旧为回文子串，即当s[i + 1 : j - 1]为回文子串且s[i] == s[j] 时，s[i : j]子串为回文子串。则可得其状态转换方程为：（dp[i][j]表示s[i : j]是否为回文子串。...

2021-05-29

0 429

C++题解 | #合并两个有序的数组#

数组A的空间足以放置A和B中所有的元素，所以当前A中元素之后还有空间，用于放置B中元素，故而考虑从后往前进行放置。首先A中最大和B中最大进行比较，较大的放置在数组末尾，较小的依旧进行比较。以此类推，若A中元素首先被放置完毕，则将B中剩余元素直接复制进入A中即可，反之亦然，直到所有元素都放置完毕。cl...

2021-05-22

0 471

C++题解 | #子数组的最大累加和问题#

分治法求子数组最大累加和。从第二个位置元素开始，依次求**包含该位置元素在内**的最大子数组累计和（即该位置元素与前一位置元素之和，与该位置元素相比，哪个更大。若前者大于后者，则将该位置元素替换为该位置元素与前一位置元素之和），之后遍历数组，查询最大值即可。class Solution { pub...

2021-05-13

0 493

C++题解 | #寻找第K大#

快速排序利用快速排序（即每次都确定一个数据在从大到小的排序中所处的位置（下标））。首先经过一遍排序，基本确定元素顺序，而后判断当前所指向数据的位置（假设为第M大，此时该位置的下标也为M）是否满足题意所求，及有M == K。若恰好为第K大，则直接返回该数据，否则，若M > K，则待求数据应当位于...

2021-05-06

0 557

题解 | #找到字符串的最长无重复字符子串#

相当于将所有子串都录入到unordered_map中，保存其中最大的长度这里利用双指针，i将数据录入，如果遇到重复的，则将已录入的元素，到重复的元素为止，都从unordered_map中移除，再重新开始录入（重复的元素，其value值被更新） class Solution { public: ...

2021-04-10

0 556