文和906

分类

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

/ 注册

全部文章（共113篇）

题解 | #机器人的运动范围#

开始时比较简单的想法就是直接将每个点的位相加，若小于等于阈值，则累计数++。这种做法在方格的长宽小于10时是生效的，而当方格的长宽之一大于等于10后就会出问题。简答举个例子，(0,10)位数和为1，假设阈值为1，机器人显然不能到达该点，但通过上面的逻辑判断则会将累计数++。所以解决办法应该是模拟...

C++ 回溯递归

2021-10-19

0 392

题解 | #矩阵中的路径#

经典回溯问题。选择使用循环+递归的方式进行回溯。在一个循环内遍历矩阵中的结点，以该点为起点调用寻路函数在寻路函数中，先判断当前字符串是否满足要求，若是则返回true，否则将其周围四个点拼接至当前字符串尾部，递归调用寻路函数。为了避免一个字符被多次使用，引入一个visited数组，用于记录被访问过的点...

C++ 回溯递归

2021-10-19

0 350

题解 | #正则表达式匹配#

看到题目第一时间没有想用递归，想直接用两个指针遍历两个字符串来解。但是写到后面发现判断结构太过复杂，太过冗余，故回到递归的方法来。字符串处理的题目，细节必定特别多。要把每一步想的特别透彻才能做对。本题主要的难点就是'*'的处理，遇到这个符号，可以不匹配，也可以匹配多个，处理这一问题的判断就是下面这个...

C++

2021-10-15

1 386

题解 | #矩形覆盖#

解决这题的突破口是找到递推规律。根据题目给出的条件，从水平方向看，可以知道，我们竖着摆放21矩形时，必须一次至少摆两个，而横着摆放时，则可以一次摆一个。所以我们对2n的大矩形，在第一次摆放时，有两种选择，要么摆放一个横着的小矩形，要么一次摆放两个竖着的小矩形。这样就可以得到递推式f(n)=f(n-1...

C++ 递归完美覆盖

2021-10-14

0 399

题解 | #跳台阶扩展问题#

使用和跳台阶一样的思路。模拟跳的过程，将n阶台阶分为第一次跳1阶，第一次跳2阶，...，第一次跳n阶。这样就得到了一个类似于原始跳台阶的公式，f(n)=f(1)+f(2)+...+f(n-1)+1，f(n)表示n阶台阶的跳法数。最后不是加f(n)而是加1，是因为一次跳n个台阶就直接跳完了，只有一种跳...

C++ 递归

2021-10-14

0 391

题解 | #斐波那契数列#

基础斐波那契数列，基础递归方法。 class Solution { public: int Fibonacci(int n) { if(n == 1 || n == 2){ return 1; } else{ ...

C++ 递归

2021-10-14

0 276

题解 | #数字在升序数组中出现的次数#

题目中要求时间复杂度O(logn)，所以直接用二分查找。总体思路是通过二分查找找到要找的数，然后在查找该数周围相同的数，最后返回累计计数。复杂度满足题目要求。因为写完一次过了，所以代码结构还有较大调整空间。 class Solution { public: int GetNumberOfK...

C++ 二分查找

2021-10-13

0 343

题解 | #字符串的排列#

刚看到题其实稍微有点蒙，不过看了题目配的图就很简单了。图里已经给出了一种解题思路。按顺序遍历遍历字符串，对每一个字符都调换它以及大于等于它的下标的字符，将新得到的字符串压栈，并对新字符串也执行该操作，直到遍历完整个字符串。由于调用的层数比较深，这里选择递归的方法来实现。传入参数中的index为开始交...

C++ 字符串递归排列组合

2021-10-13

0 392

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

这题常规使用二分查找来解，这里先皮一下，直接用set初始化函数排序，两行代码秒解。同理也可以直接用sort函数排序，也是两行解。ps: 使用set函数初始化的运行速度和使用sort排序的时间基本一致，都是超过95%www。空间复杂度上当然sort更优。 class Solution { public...

C++ 二分查找

2021-10-13

0 340

题解 | #滑动窗口的最大值#

模拟窗口滑动的过程，用一个数组来记录滑动窗口内的值，一个数组来记录最大值。每次窗口滑动都将最大值数组的队尾压入结果栈，最后返回结果栈。这题要做出来并不难，难在追求优秀的时间复杂度和空间复杂度。感觉这个代码还有较大改进空间。欢迎讨论。 class Solution { public: vec...

C++ 队列

2021-10-12

0 383