给个offer行不行x

算法题

sql(46) 题解(2)

/ 注册

全部文章 / 算法题（共26篇）

题解 | JZ12 矩阵中的路径

经典的搜索路径算法。 maze数组的作用是记录走过的路径避免重复走。搜到ans为true之后就直接返回函数，不再继续往下搜素。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * ...

C++

2022-01-04

0 420

题解 | JZ46 把数字翻译成字符串

这个题可以看作是带约束的走台阶一共有多少种走法。转移方程为： f[i] = f[i-1](nums[i]!='0') + f[i-2](nums[i-1] == '1' or (nums[i-1] == '2' and nums[i] <= '6')) c++ python ...

Python3 C++

2022-01-03

0 402

题解 | JZ48 最长不含重复字符的子字符串

这道题虽然放在动态规划里，但是其实是一道经典的尺取法（双指针）的题目。我们把两个指针都放在最左端，让R指针先移动。当R指针发现，移动到这个元素发现有重复元素了，那么我们需要移动L指针。为什么？因为我们始终维护的是这一段区间，也就是说当发现有重复值了，这一段区间是没法使用的，那么只要包括了这段...

Python3 C++

2022-01-02

0 424

题解 | JZ47 礼物的最大价值

这道题是二维动态规划的经典题，我们把0行和0列的值更新好了，就可以用下面的动态规划的方程来求解了。 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]; c++ python class Solution { public: ...

Python3 C++

2022-01-01

0 407

题解 | JZ63 买卖股票的最好时机(一)

这个题看一眼就会想到是动态规划的解法，但是我们发现它只能买卖一次股票，这个限制条件很强。而且下面也给出了空间复杂度为O(1),也就意味着DP的解法并不是最优的。所以我们想到一个方法，就是拿后面的最大值，来减去前面的最小值，就可以知道了。这里面需要注意有一个次序在里面，不是随便找一个最大值和最小值...

Python3 C++

2022-01-01

0 385

题解 | JZ85 连续子数组的最大和(二)

这题比上一题，增加了条件，需要我们把答案相同，最长的序列返回回来。所以，我们不能直接两行完事了，需要在比较的时候做一下判断。还是分为两个部分，第一部分更新dp[i]，第二部分更新ans。在第一部分中， sum+a[i] >= a[i] 这里特别要注意，要≥就可以更新，因为我们需要找到...

C++ Python3

2021-12-29

0 371

题解 | JZ42 连续子数组的最大和

这道题可以从标准的动态规划(DP)推过来。我们可以假设dp[i]表示以位置i为结尾的子数组的最大和是多少？所以对于我们要求的答案就是max(dp[0], dp[1], ..., dp[n]) 在这n个数中找到一个最大值就是我们最后的答案。而对于单独的dp[i]，我们可以递推得到： dp[i]...

Python3 C++

2021-12-28

0 358

题解 | JZ44 数字序列中某一位的数字

提示：力扣的数据更强，试试提交到力扣里。这个题意思挺清晰的，但是边界条件处理有点麻烦。可以通过找规律发现： 0 ... 9 每个数字都是一个字符共(101−100)×1(10^1-10^0) \times 1(101−100)×1个字符 10 ... 99 每个数字都是两个字符 (102−1...

C++ Python3

2021-12-27

0 315

题解 | JZ38 字符串的排列

因为本题的答案不看顺序，所以，也不用对初始数据进行预处理。本题最核心的函数就是dfs，关键看里面是怎么操作的。因为要N!把所有情况都遍历一遍，所以我们想到要配合一个done[]数组，来记录我们当前已经把哪些字符算进去了，这样好做到不重复。同时，我们还需要一个num变量记录一下当前已经加入了多少个...

C++ Python3

2021-12-26

0 495

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

这题对于C++来说是很好写的,因为C++已经帮我们实现好了在一个排好序中的数组中二分查找某个数。 lower_bound()函数对应着查找给数第一次出现的位置，upper_bound()函数对应着查找大于给定数出现第一次出现的位置。因此，upper_bound()-lower_bound()的值，...

Python3 C++

2021-12-25

0 414