文和906

题解

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

/ 注册

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

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

对于非负数，其补码就是其源码，若其为偶数则最右边一位为0，若其为基数则最右边一位为1，每次判断其奇偶性，并更改1的个数，然后将数字右移一位，直到数字为0。对于负数，其补码为原码取反再加一，不好直接通过奇偶性统计1的个数，要先模拟该数变为补码的操作，所以先将其取绝对值，再转换为无符号类型unsigne...

C++ 数学

2021-10-20

0 309

题解 | #不用加减乘除做加法#

通过异或运算可以得到两数的无进位加法结果，通过与后左移一位可以得到进位，结合这两个运算就可以得到加法结果。 class Solution { public: int Add(int num1, int num2) { int result = num1 ^ num2; ...

C++ 数学

2021-10-20

0 314

题解 | #数据流中的中位数#

由于题目中没有对空间复杂度和时间复杂度做要求，所以上来先考虑较为直接的解法。建立一个数组用于保存数据流，每次插入数据都将数据存入数组中，在调用获取中位数的方法时，先调用sort对数组进行排序，再获得中位数。 class Solution { public: void Insert(int n...

C++ 排序

2021-10-20

0 327

题解 | #数组中的逆序对#

开始想到的是用一个二重循环来遍历数组。 class Solution { public: int InversePairs(vector<int> data) { if(!data.size()){ return 0; } ...

C++ 数组归并排序

2021-10-19

1 506

题解 | #数组中重复的数字#

题目中要求时间复杂度O(n)，可知不能使用排序来做。同时要求空间复杂度为O(n)，则可以使用经典的空间换时间方法做。创建一个与输入数组numbers相同长度的数组count，用于记录numbers中每个数出现了几次。遍历数组，每遍历一个数就将count中下标为该数的元素++，并判断++后该元素的值。...

C++ 数组

2021-10-19

7 778

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

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

C++ 回溯递归

2021-10-19

0 386

题解 | #矩阵中的路径#

经典回溯问题。选择使用循环+递归的方式进行回溯。在一个循环内遍历矩阵中的结点，以该点为起点调用寻路函数在寻路函数中，先判断当前字符串是否满足要求，若是则返回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 400

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

使用和跳台阶一样的思路。模拟跳的过程，将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 386